FUNCIONES BOOLEANAS 11

Vista previa del material en texto

TEMA : FUNCIONES BOOLEANAS
Universidad Nacional de Ingeniería
Facultad de Ingeniería Industrial y de Sistemas
DEFINICIONES
Variable booleana.-Una variable lógica o booleana es un elemento del conjunto booleano B, es decir
𝑎 ∈ 𝐵 que puede tomar 0 o 1.
Función booleana
La función booleana de se define por:
𝑓: 𝐵𝑛 → 𝐵
Donde 𝑓 𝑎1, 𝑎2…… . . 𝑎𝑛 = 𝑏, 𝑐𝑜𝑛 𝑎1, 𝑎2…… . . 𝑎𝑛 ∈ 𝐵
𝑛, 𝑏 ∈ 𝐵
La función puede definirse de manera que dando los valores de verdad toma cada
posible combinación de entradas. Esta representación se llama tabla de verdad.
Ejemplo
Sea la función 𝑓: 𝐵3 → 𝐵
Definida por 𝑓 𝑎, 𝑏, 𝑐 = 𝑐(𝑎 + 𝑏)
a b b 𝒇 𝒂, 𝒃, 𝒄 = 𝒄(𝒂 + 𝒃)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
OPERACIONES LÓGICAS 
Suma lógica: (OR)≡ 𝑂 ≡ ∨
Sea la función 𝑓: 𝐵2 → 𝐵
𝑓 𝑎, 𝑏 = 𝑎 + 𝑏 = ቊ
0 , 𝑠𝑖 𝑎 = 0 , 𝑏 = 0
1 , 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Producto lógico: (AND)≡ 𝑌 ≡ ∧
Sea la función 𝑓: 𝐵2 → 𝐵
𝑓 𝑎, 𝑏 = 𝑎𝑏 = ቊ
1 , 𝑠𝑖 𝑎 = 1 , 𝑏 = 1
0 , 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Negación: (NOT)≡ ∼
Sea la función 𝑓: 𝐵 → 𝐵
𝑓 𝑎 = ത𝑎 = ቊ
1 , 𝑠𝑖 𝑎 = 1
0 , 𝑠𝑖 𝑎 = 0
Suma Producto
a b 𝐟 𝐚, 𝐛 = 𝐚 + 𝐛 a b 𝐟 𝐚, 𝐛 = 𝐚𝐛
0 0 0 0 0 0
0 1 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1
Ilustración de las operaciones lógicas suma y producto en una tabla de verdad
Funciones booleanas a partir de tablas de verdad
Para describir una función booleana donde nos proporcionan los valores de salida parta todas las 
combinaciones de las entradas es necesario los postulados y teoremas del algebra de Boole
Ejemplo
Determinar la función booleana a partir de siguiente tabla de
verdad
a b 𝑓(𝑎, 𝑏)
0 0 0
0 1 1
1 0 1
1 1 0
La función booleana estará dado por la siguiente regla de correspondencia
𝑓 𝑎, 𝑏 = ത𝑎. 𝑏 + 𝑎. ത𝑏
Principio de dualidad
Si analizamos los postulados veremos que los mismos se presentan de pares y en tal 
forma que uno de la pareja se obtiene de otro cambiando "0" por "1" junto con las operaciones "+" por 
"." ( y viceversa). Esto asegura que cada propiedad que se 
demuestre en esta Álgebra tiene una "dualidad" que también es cierta (para demostrar 
la dualidad bastaría con repetir la demostración realizada sustituyendo cada postulado 
o propiedad utilizada por su dual
Postulado Dualidad
𝒂 + ഥ𝒂=1 𝐚. ത𝐚 = 𝟎
a.0=0 𝐚 + 𝟏 = 𝟏
0+0=0 1.1=1
Ejemplos
Termino producto
Es un grupo de expresiones que se encuentran relacionadas
entre sí, por el termino AND que indica producto (.).
Ejemplo
𝐴. 𝐵, 𝐶. 𝐴, ҧ𝑥. 𝑦. 𝑧
Termino suma
Es un grupo de expresiones que se encuentran relacionadas
entre sí, por el termino OR que indica suma (+).
Ejemplo
𝐴 + 𝐵, 𝐶 + 𝐴, ҧ𝑥. 𝑦 + 𝑦𝑧
Termino canónico
Es aquel término que es exactamente uno de cada uno de los literales o 
expresiones de las funciones booleanas
Termino normal
Termino normal es aquel termino producto o termino suma en el que un literal no
aparece más de una vez.
Mintérmino
Es un producto booleano en la que cada variable aparece sólo una vez; es decir, es una
expresión lógica que se compone de variables y los operadores lógicos AND y NOT.
Ejemplo
X.Y.Z y 𝑋. ത𝑌. 𝑍
Maxtérmino
Es una expresión lógica que se compone de variables y los operadores lógicos OR y NOT.
Ejemplo
X+Y+Z y 𝑋 + ത𝑌 + 𝑍
Forma canónica de una función booleana
Es aquella forma constituida exclusivamente por términos canónicos que aparecen una sola
vez.
Ejemplo
𝑓 𝑥, 𝑦, 𝑧 = ҧ𝑥. 𝑦. ҧ𝑧 + ( ҧ𝑥 + 𝑦 + 𝑧) + ( ҧ𝑥 + ത𝑦 + ҧ𝑧)
Formas canónicas de funciones booleanas
a) Forma canónica suma de productos: (forma suma de minterminos)
Es aquella constituida exclusivamente por términos canónicos producto (mintermino)
sumandos que aparecen una sola vez.
Ejemplo
𝑓 𝑥, 𝑦, 𝑧 = ( ҧ𝑥. ത𝑦. 𝑧) + 𝑥. ത𝑦. ҧ𝑧 + 𝑥. ത𝑦. 𝑧 + 𝑥. 𝑦. ҧ𝑧 + (𝑥. 𝑦. 𝑧)
Simplificaron de la escritura forma canónica suma de productos
Para simplificar la escritura en forma de suma canónica de productos, se utiliza la notación
binaria, es decir que a cada termino (mintermino) se le asocia un numero binario de “n” bits,
considerando como 0 las variables complementarias y 1 a las variables no complementarias.
Consideremos el ejemplo anterior
Mintermino Binario Decimal
( ҧ𝑥. ത𝑦. 𝑧) 001 1
𝑥. ത𝑦. ҧ𝑧 100 4
𝑥. ത𝑦. 𝑧 101 5
𝑥. 𝑦. ҧ𝑧 110 6
(𝑥. 𝑦. 𝑧) 111 7
Donde se puede expresar de la siguiente forma
𝑓 𝑥, 𝑦, 𝑧 =෍
𝑚
(1,4,5,6,7)
Quiere decir la suma de los minterminos 1,4,5,6,7.
b) Forma canónica de producto de sumas: (forma de productos maxterminos)
Es aquella constituida exclusivamente por términos canónicos sumas (maxtermino)
multiplicadas que aparecen una sola vez.
Ejemplo
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + 𝑦 + 𝑧 . 𝑥 + ത𝑦 + 𝑧 𝑥 + ത𝑦 + ҧ𝑧
Simplificaron de la escritura forma canónica suma de productos
Para simplificar la escritura en forma de suma canónica de productos, se utiliza la
notación binaria, es decir que a cada termino (maxtermino) se le asocia un numero
binario de “n” bits, considerando como 1 las variables complementarias y 0 a las
variables no complementarias
Consideremos el ejemplo anterior
Maxtermino Binario Decimal
(𝐱 + 𝐲 + 𝐳) 000 0
𝐱 + ത𝐲 + 𝐳 010 2
𝐱 + ത𝐲 + ത𝐳 011 3
Donde se puede expresar de la siguiente forma
𝑓 𝑥, 𝑦, 𝑧 =ෑ
𝑀
(0,2,3)
Quiere decir el producto de los maxterminos 0,2,3.
Resumen para cada mintermino que se asocia con la combinación de entradas de la tabla de
verdad, la función producirá una salida de 1, y para maxtermino que se asocia con la
combinación de entradas de la tabla de verdad, la función producirá una salida de 0, a
continuación se ilustrara en la siguiente tabla.
Tabla de maxterminos y minterminos asociados con cada combinación en 
una tabla de verdad de tres variables
Decimal x y z Mintermino 𝑚𝑖 Maxtermino 𝑀𝑖
0 0 0 0 ഥ𝑥. ഥ𝑦. ҧ𝑧 = 𝑚0 1 𝑥 + 𝑦 + 𝑧 = 𝑀0 0
1 0 0 1 ഥ𝑥. ഥ𝑦. 𝑧 = 𝑚1 1 𝑥 + 𝑦 + ҧ𝑧 = 𝑀1 0
2 0 1 0 ഥ𝑥. 𝑦. ҧ𝑧 = 𝑚2 1 𝑥 + ത𝑦 + 𝑧 = 𝑀2 0
3 0 1 1 ഥ𝑥. 𝑦. 𝑧 = 𝑚3 1 𝑥 + ത𝑦 + ҧ𝑧 = 𝑀3 0
4 1 0 0 𝑥. ഥ𝑦. ҧ𝑧 = 𝑚4 1 ҧ𝑥 + 𝑦 + 𝑧 = 𝑀4 0
5 1 0 1 𝑥. ഥ𝑦. 𝑧 = 𝑚5 1 ҧ𝑥 + 𝑦 + ҧ𝑧 = 𝑀5 0
6 1 1 0 𝑥. 𝑦. ҧ𝑧 = 𝑚6 1 ҧ𝑥 + ത𝑦 + 𝑧 = 𝑀6 0
7 1 1 1 𝑥. 𝑦. 𝑧 = 𝑚7 1 ҧ𝑥 + ത𝑦 + ҧ𝑧 = 𝑀7 0
Ejemplo .-
Expresar la siguiente función como una suma de minterminos
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦. 𝑧
Solución
Hay dos formas de resolver el problema
i) Establecer la tabla de verdad de la expresión, luego tomar los minterminos, es decir
se evalúa la función para todas las combinaciones de entrada, luego se toma los
minterminos, para la cual la función tiene como salida 1
Luego la función expresada en suma de minterminos estará dada por
𝑓 𝑥, 𝑦, 𝑧 = ഥ𝑥. ഥ𝑦. 𝑧 + 𝑥. ഥ𝑦. ҧ𝑧 + 𝑥. ഥ𝑦. 𝑧 + 𝑥. 𝑦. ҧ𝑧 + 𝑥. 𝑦. 𝑧
En forma literal simplificada estará por
𝑓 𝑥, 𝑦, 𝑧 = σ𝑚(1,4,5,6,7), que quiere decir la suma de los minterminos 1,4,5,6,7.
ii) Aplicando los teoremas de expansión canónica para las variables faltantes
Teorema
Para obtener la forma canónica de una función suma de productos (minterminos), se multiplica
por un término de la forma (𝑎 + ത𝑎), donde falta un literal para que el término sea canónico.
En efecto
Si 𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦. 𝑧 entonces
𝑓 𝑥, 𝑦, 𝑧 = 𝑥. 𝑦 + ത𝑦 . (𝑧 + ഥ𝑧) + ത𝑦. 𝑧. (𝑥 + ҧ𝑥)
𝑓 𝑥, 𝑦, 𝑧 = 𝑥. 𝑦 + 𝑥. ത𝑦 . (𝑧 + ഥ𝑧) + ത𝑦. 𝑧. 𝑥 + ത𝑦. 𝑧. ҧ𝑥
𝑓 𝑥, 𝑦, 𝑧 = 𝑥. 𝑦. 𝑧 + 𝑥. 𝑦. ҧ𝑧 + 𝑥. ത𝑦. 𝑧 + 𝑥. ത𝑦. ҧ𝑧 + ത𝑦. 𝑧. 𝑥 + ത𝑦. 𝑧. ҧ𝑥
Por tanto el resultado.
Ejemplo
Expresar la siguiente función como una suma de maxterminos
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦. 𝑧
Solución
De igual manera que el caso anterior hay dos formas de resolver el problema
i) Establecer la tabla de verdad de la expresión, luego tomar los maxterminos, es decir se
evalúa la función para todas las combinaciones de entrada, luego se toma los
maxterminos, para la cual la función tiene como salida 0
Luego la función expresada como productode maxterminos estará dada por
𝑓 𝑥, 𝑦, 𝑧 = (𝑥 + 𝑦 + 𝑧)( 𝑥 + ത𝑦 + 𝑧)(𝑥 + ത𝑦 + ҧ𝑧)
En forma literal simplificada estará por
𝑓 𝑥, 𝑦, 𝑧 = ς𝑀(0,2,3), que quiere decir el producto de los maxterminos, 0,2,3.
ii) Aplicando los teoremas de expansión canónica para las variables faltantes
Teorema
Para obtener la forma canónica de una función productos sumas (maxterminos),
se suma un término de la forma (𝑎. ത𝑎), donde falta un literal para que el
término sea canónico.
En efecto
Si 𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦. 𝑧 entonces
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦 . (𝑥 + 𝑧)
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦 + 𝑧. ҧ𝑧 . (𝑥 + 𝑧 + 𝑦. ത𝑦)
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦 + 𝑧 𝑥 + ത𝑦 + ҧ𝑧 . (𝑥 + 𝑧 + 𝑦)(𝑥 + 𝑧 + ത𝑦)
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 + ത𝑦 + 𝑧 𝑥 + ത𝑦 + ҧ𝑧 . (𝑥 + 𝑧 + 𝑦)
Por tanto el resultado.