MA265 Espacio vectorial -Comb lineal- LI- LD[Diapo]

Matemática Discreta Funciones booleanas • Definición y propiedades. • Representación. • Simplificación. Logro de la sesión Al finalizar la sesión, estarás preparado para : Simplificar expresiones booleanas mediante el uso de Mapas de Karnaugh . Bibliografía • Profesores UPC – Libro digital – Funciones booleanas. • Forero A. (2009). Matemática Estructural . Departamento de Matemáticas Universidad de los Andes Bogotá, D.C - Colombia. Revisar páginas desde 1 hasta 35. • Epp S. (2012). Matemáticas discretas con aplicaciones . México, D.F. Cengage Learning . Revisar páginas desde 336 hasta 382. Bibliografía textos de consulta. Funciones Booleanas Sea el álgebra booleana 𝐵 = {0, 1} , sean 𝑥, 𝑦 dos variables booleanas que pueden tomar el valor 0 o 1 y las operaciones booleanas : • Unión : 𝑥 ∨ 𝑦 • Conjunción : 𝑥 ∧ 𝑦 • Complemento : 𝑥′ Una función 𝑓: 𝐵 𝑛 → 𝐵 se denomina una función booleana de grado 𝑛 i . e . 𝑓 𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ∈ 𝐵 con 𝑥 𝑖 ∈ 𝐵, 1 ≤ 𝑖 ≤ 𝑛 Ejemplos : ‒ 𝑓 𝑥, 𝑦 = (𝑥 ′ ∧ 𝑦 ) ∨ 𝑥 ∧ 𝑦 ′ ‒ 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ∧ 𝑦) ∨ (𝑦 ∧ 𝑧 ′ ) ‒ 𝑓 𝑤, 𝑥, 𝑦, 𝑧 = (𝑤 ∧ 𝑥 ′ ∧ 𝑦) ∨ (𝑥 ∧ 𝑦 ∧ 𝑧 ′ ) ∨ (𝑤 ′ ∧ 𝑦 ∧ 𝑧) ∨ (𝑥′ ∧ 𝑦 ∧ 𝑧) Propiedades Conmutativa 𝑥 ∨ 𝑦 = 𝑦 ∨ 𝑥 𝑥 ∧ 𝑦 = 𝑦 ∧ 𝑥 Asociativa 𝑥 ∨ 𝑦 ∨ 𝑧 = 𝑥 ∨ 𝑦 ∨ 𝑧 𝑥 ∧ 𝑦 ∧ 𝑧 = (𝑥 ∧ 𝑦) ∧ 𝑧 Distributiva 𝑥 ∧ 𝑦 ∨ 𝑧 = (𝑥 ∧ 𝑦) ∨ (𝑥 ∧ 𝑧) 𝑥 ∨ 𝑦 ∧ 𝑧 = (𝑥 ∨ 𝑦) ∧ (𝑥 ∨ 𝑧) P1: Identidad (Elemento neutro) 𝑥 ∨ 0 = 𝑥 𝑥 ∧ 1 = 𝑥 P2: Del complemento 𝑥 ∨ 𝑥′ = 1 𝑥 ∧ 𝑥′ = 0 (𝑥 ′ )′ = 𝑥 P3: Dominancia 𝑥 ∨ 1 = 1 𝑥 ∧ 0 = 0 P4: Idempotencia 𝑥 ∨ 𝑥 = 𝑥 𝑥 ∧ 𝑥 = 𝑥 P5: Absorción 𝑥 ∨ (𝑥 ∧ 𝑦) = 𝑥 𝑥 ∧ (𝑥 ∨ 𝑦) = 𝑥 Leyes de DeMorgan 𝑥 ∨ 𝑦 ′ = 𝑥 ′ ∧ 𝑦 ′ 𝑥 ∧ 𝑦 ′ = 𝑥′ ∨ 𝑦′ Representación de funciones booleanas Una función booleana puede ser representada mediante una tabla de verdad o mediante un circuito lógico . Tabla de verdad Una tabla de verdad contiene todos los posibles valores de la función booleana . El número total de combinaciones para una función de 𝑛 variables está dado por 2 𝑛 . 𝑥 𝑦 𝑓 0 0 1 0 1 1 1 0 0 1 1 1 Ejemplo: Construir la tabla de verdad de la función booleana: 𝑓 𝑥, 𝑦 = 𝑥 ′ ∨ 𝑦 Solución: La función tiene 2 variables, entonces hay 2 2 = 4 posibles combinaciones. Se halla los valores de la función para cada combinación de valores de las variables 𝑥, 𝑦 . Ejemplo : Construir la tabla de verdad de la función booleana : 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦) ∨ (𝑦′ ∧ 𝑧) Solución : La función tiene 3 variables, entonces hay 2 3 = 8 posibles combinaciones . Se halla los valores de la función para cada combinación de valores de las variables 𝑥, 𝑦, 𝑧 . 𝑥 𝑦 𝑧 𝑓 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 Representación de funciones booleanas Circuitos lógicos Las operaciones booleanas (∨ , ∧ , ′ ) se pueden representar mediante las compuertas lógicas básicas : OR, AND y NOT respectivamente . 𝑦 𝑥 𝑥 ∨ 𝑦 Compuerta OR 𝑦 𝑥 𝑥 ∧ 𝑦 Compuerta AND 𝑥 𝑥′ Compuerta NOT Ejemplo : Implemente el circuito lógico que representa a la función : 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦) ∨ (𝑦 ′ ∧ 𝑧) Solución : Simplificación de funciones booleanas Las funciones booleanas se pueden simplificar usando las propiedades del álgebra de Boole o mediante los mapas de Karnaugh . Ejemplo : Usando las propiedades del álgebra Boole, simplificar la siguiente función : 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦 ∧ 𝑧 ′ ) ∨ (𝑥′ ∧ 𝑦 ∧ 𝑧) ∨ (𝑥 ∧ 𝑦 ′ ∧ 𝑧) ∨ (𝑥 ∧ 𝑦 ∧ 𝑧) Solución : 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦 ∧ 𝑧 ′ ) ∨ (𝑥′ ∧ 𝑦 ∧ 𝑧) ∨ (𝑥 ∧ 𝑦 ′ ∧ 𝑧) ∨ (𝑥 ∧ 𝑦 ∧ 𝑧) 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦 ∧ 𝑧 ′ ) ∨ (𝑥′ ∧ 𝑦 ∧ 𝑧) ∨ (𝑥 ∧ 𝑧 ∧ 𝑦′) ∨ (𝑥 ∧ z ∧ y) 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦) ∧ (𝑧′ ∨ 𝑧) ∨ (𝑥 ∧ 𝑧) ∧ (𝑦 ′ ∨ 𝑦) 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦) ∧ 1 ∨ (𝑥 ∧ 𝑧) ∧ 1 𝑓 𝑥, 𝑦, 𝑧 = (𝑥 ′ ∧ 𝑦) ∨ (𝑥 ∧ 𝑧) Asociativa Conmutativa Distributiva Complemento Elemento neutro Simplificación de funciones booleanas Mapas de Karnaugh Es una herramienta gráfica que se utiliza para simplificar una función booleana a partir de la tabla de verdad…