MA265 Sesión 11.2 Bas-gen-ind[Libro]

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Funciones booleanas y Mapas de Karnaugh CONTENIDO Unidad 4: Estructuras de Orden y Álgebra de Boole 4.3 Funciones booleanas y Mapas de Karnaugh ▪ Funciones booleanas ▪ Circuitos lógicos ▪ Mapas de Karnaugh UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Funciones booleanas y Mapas de Karnaugh 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: 𝑥′ Nota: Otra forma de notación es: 𝒙 + 𝒚 (para la unión) y 𝒙 ⋅ 𝒚 (para la conjunción). Una función 𝑓: 𝐵 𝑛 → 𝐵 se denomina una función booleana de grado 𝑛 i.e. 𝑓(𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ) ∈ 𝐵 con 𝑥 𝑖 ∈ 𝐵, 1 ≤ 𝑖 ≤ 𝑛 Ejemplos: ‒ 𝑓(𝑥, 𝑦) = (𝑥′ ∧ 𝑦 ∨ (𝑥 ∧ 𝑦 ′ ) ‒ 𝑓(𝑥, 𝑦, 𝑧) = (𝑥 ∧ 𝑦) ∨ (𝑦 ∧ 𝑧 ′ ) ‒ 𝑓(𝑤, 𝑥, 𝑦, 𝑧) = (𝑤 ∧ 𝑥 ′ ∧ 𝑦) ∨ (𝑥 ∧ 𝑦 ∧ 𝑧 ′ ) ∨ (𝑤 ′ ∧ 𝑦 ∧ 𝑧) ∨ (𝑥′ ∧ 𝑦 ∧ 𝑧) Propiedades Conmutativa 𝑥 ∨ 𝑦 = 𝑦 ∨ 𝑥 𝑥 ∧ 𝑦 = 𝑦 ∧ 𝑥 Distributiva 𝑥 ∧ (𝑦 ∨ 𝑧) = (𝑥 ∧ 𝑦) ∨ (𝑥 ∧ 𝑧) 𝑥 ∨ (𝑦 ∧ 𝑧) = (𝑥 ∨ 𝑦) ∧ (𝑥 ∨ 𝑧) Asociativa 𝑥 ∨ (𝑦 ∨ 𝑧) = (𝑥 ∨ 𝑦) ∨ 𝑧 𝑥 ∧ (𝑦 ∧ 𝑧) = (𝑥 ∧ 𝑦) ∧ 𝑧 P1: Identidad (Elemento neutro) 𝑥 ∨ 0 = 𝑥 𝑥 ∧ 1 = 𝑥 P3: Dominancia 𝑥 ∨ 1 = 1 𝑥 ∧ 0 = 0 P2: Del complemento 𝑥 ∨ 𝑥′ = 1 𝑥 ∧ 𝑥′ = 0 (𝑥 ′ )′ = 𝑥 P4: Idempotencia 𝑥 ∨ 𝑥 = 𝑥 𝑥 ∧ 𝑥 = 𝑥 P5: Absorción 𝑥 ∨ (𝑥 ∧ 𝑦) = 𝑥 𝑥 ∧ (𝑥 ∨ 𝑦) = 𝑥 Leyes de DeMorgan (𝑥 ∨ 𝑦) ′ = 𝑥 ′ ∧ 𝑦 ′ (𝑥 ∧ 𝑦) ′ = 𝑥′ ∨ 𝑦′ UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 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 𝑛 . 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 𝑥, 𝑦 . 𝑥 𝑦 𝑓 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 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 UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 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: 𝑓(𝑥, 𝑦, 𝑧) = [(𝑥 ′ ∧ 𝑦 ∧ 𝑧 ′ ) ∨ (𝑥′ ∧ 𝑦 ∧ 𝑧)] ∨ [(𝑥 ∧ 𝑦 ′ ∧ 𝑧) ∨ (𝑥 ∧ 𝑦 ∧ 𝑧)] 𝑓(𝑥, 𝑦, 𝑧) = [(𝑥 ′ ∧ 𝑦 ∧ 𝑧 ′ ) ∨ (𝑥′ ∧ 𝑦 ∧ 𝑧)] ∨ [(𝑥 ∧ 𝑧 ∧ 𝑦′) ∨ (𝑥 ∧ 𝑧 ∧ 𝑦)] 𝑓(𝑥, 𝑦, 𝑧) = [(𝑥 ′ ∧ 𝑦) ∧ (𝑧′ ∨ 𝑧)] ∨ [(𝑥 ∧ 𝑧) ∧ (𝑦 ′ ∨ 𝑦)] 𝑓(𝑥, 𝑦, 𝑧) = [(𝑥 ′ ∧ 𝑦) ∧ 1] ∨ [(𝑥 ∧ 𝑧) ∧ 1] 𝑓(𝑥, 𝑦, 𝑧) = (𝑥 ′ ∧ 𝑦) ∨ (𝑥 ∧ 𝑧) Asociativa Conmutativa Distributiva Complemento Elemento neutro 𝑦 𝑥 𝑥 ∧ 𝑦 𝑦 𝑥 𝑥 ∨ 𝑦 𝑥 𝑥′ 𝑥 𝑦 𝑧 𝑓 UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 5 Mapas de Karnaugh Es una herramienta gráfica que se utiliza para simplificar una…