Expresiones y funciones booleanas
El álgebra de Boole es el álgebra de la lógica. Se trata de variables que pueden tener dos valores discretos, 0 (falso) y 1 (verdadero); y operaciones que tienen un significado lógico. El primer método de manipulación de la lógica simbólica fue inventado por George Boole y, posteriormente, se conoció como álgebra booleana.
El álgebra de Boole se ha convertido ahora en una herramienta indispensable en la informática por su amplia aplicabilidad en la teoría de la conmutación, la construcción de circuitos electrónicos básicos y el diseño de computadoras digitales.
Funciones booleanas
A Boolean functiones un tipo especial de función matemática $ f: X ^ n \ rightarrow X $ de grado n, donde $ X = \ lbrace {0, 1} \ rbrace $ es un dominio booleano yn es un número entero no negativo. Describe la forma de derivar la salida booleana de las entradas booleanas.
Example- Sea, $ F (A, B) = A'B '$. Esta es una función de grado 2 del conjunto de pares ordenados de variables booleanas al conjunto $ \ lbrace {0, 1} \ rbrace $ donde $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ y $ F (1, 1) = 0 $
Expresiones booleanas
A Boolean expressionsiempre produce un valor booleano. Una expresión booleana se compone de una combinación de constantes booleanas (verdadero o falso), variables booleanas y conectivas lógicas. Cada expresión booleana representa una función booleana.
Example - $ AB'C $ es una expresión booleana.
Identidades booleanas
Ley de doble complemento
$ \ sim (\ sim A) = A $
Ley de complemento
$ A + \ sim A = 1 $ (forma OR)
$ A. \ sim A = 0 $ (forma Y)
Ley idempotente
$ A + A = A $ (formulario OR)
$ A. A = A $ (forma Y)
Ley de identidad
$ A + 0 = A $ (formulario OR)
$ A. 1 = A $ (formulario Y)
Ley de dominancia
$ A + 1 = 1 $ (formulario OR)
$ A. 0 = 0 $ (formulario Y)
Ley conmutativa
$ A + B = B + A $ (Forma OR)
$ A. B = B. A $ (formulario AND)
Ley asociativa
$ A + (B + C) = (A + B) + C $ (Forma OR)
$ A. (B. C) = (A. B). C $ (formulario Y)
Ley de absorción
$ A. (A + B) = A $
$ A + (A. B) = A $
Ley de simplificación
$ A. (\ sim A + B) = A. B $
$ A + (\ sim A. B) = A + B $
Ley distributiva
$ A + (B. C) = (A + B). (A + C) $
$ A. (B + C) = (A. B) + (A. C) $
Ley de De-Morgan
$ \ sim (A. B) = \ sim A + \ sim B $
$ \ sim (A + B) = \ sim A. \ sim B $
Formas canónicas
Para una expresión booleana, hay dos tipos de formas canónicas:
- La forma de suma de minitérminos (SOM)
- El producto de la forma maxterms (POM)
El formulario de suma de términos mínimos (SOM) o suma de productos (SOP)
Un minitérmino es un producto de todas las variables tomadas en su forma directa o complementada. Cualquier función booleana se puede expresar como una suma de sus 1 minitérminos y la inversa de la función se puede expresar como una suma de sus 0 minitérminos. Por lo tanto,
F (lista de variables) = ∑ (lista de índices de 1 minitérmino)
y
F '(lista de variables) = ∑ (lista de índices de término mínimo 0)
UNA | segundo | C | Término | Minterm |
---|---|---|---|---|
0 | 0 | 0 | x'y'z ' | m 0 |
0 | 0 | 1 | x'y'z | m 1 |
0 | 1 | 0 | x'yz ' | m 2 |
0 | 1 | 1 | x'yz | m 3 |
1 | 0 | 0 | xy'z ' | m 4 |
1 | 0 | 1 | xy'z | m 5 |
1 | 1 | 0 | xyz ' | m 6 |
1 | 1 | 1 | xyz | m 7 |
Example
Sea, $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $
O $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $
Por lo tanto,
$ F (x, y, z) = \ sum (0, 5, 6, 7) $
Ahora encontraremos el complemento de $ F (x, y, z) $
$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $
O $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $
Por lo tanto,
$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $
El formulario Producto de Maxterms (POM) o Producto de Sumas (POS)
Un maxterm es la suma de todas las variables tomadas en su forma directa o complementada. Cualquier función booleana se puede expresar como un producto de sus 0-maxterms y la inversa de la función se puede expresar como un producto de sus 1-maxterms. Por lo tanto,
F (lista de variables) = $ \ pi $ (lista de índices 0-maxterm).
y
F '(lista de variables) = $ \ pi $ (lista de índices 1-maxterm).
UNA | segundo | C | Término | Maxterm |
---|---|---|---|---|
0 | 0 | 0 | x + y + z | M 0 |
0 | 0 | 1 | x + y + z ' | M 1 |
0 | 1 | 0 | x + y '+ z | M 2 |
0 | 1 | 1 | x + y '+ z' | M 3 |
1 | 0 | 0 | x '+ y + z | M 4 |
1 | 0 | 1 | x '+ y + z' | M 5 |
1 | 1 | 0 | x '+ y' + z | M 6 |
1 | 1 | 1 | x '+ y' + z ' | M 7 |
Ejemplo
Sea $ F (x, y, z) = (x + y + z). (x + y + z '). (x + y '+ z). (x '+ y + z) $
O $ F (x, y, z) = M_0. M_1. M_2. M_4 $
Por lo tanto,
$ F (x, y, z) = \ pi (0, 1, 2, 4) $
$ F '' (x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y' + z). (x '+ y' + z ') $
O $ F (x, y, z) = M_3. M_5. M_6. M_7 $
Por lo tanto,
$ F '(x, y, z) = \ pi (3, 5, 6, 7) $
Puertas lógicas
Las funciones booleanas se implementan mediante puertas lógicas. Las siguientes son las puertas lógicas:
NO puerta
Una puerta NOT invierte una entrada de un solo bit en un solo bit de salida.
UNA | ~ A |
---|---|
0 | 1 |
1 | 0 |
Y puerta
Una puerta AND es una puerta lógica que da una salida alta solo si todas sus entradas son altas; de lo contrario, da una salida baja. Se utiliza un punto (.) Para mostrar la operación AND.
UNA | segundo | AB |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Puerta OR
Una puerta OR es una puerta lógica que da una salida alta si al menos una de las entradas es alta. Se utiliza un signo más (+) para mostrar la operación OR.
UNA | segundo | A + B |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Puerta NAND
Una puerta NAND es una puerta lógica que da una salida baja solo si todas sus entradas son altas; de lo contrario, da una salida alta.
UNA | segundo | ~ (AB) |
---|---|---|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Puerta NOR
Una puerta NOR es una puerta lógica que da salida alta si ambas entradas son bajas; de lo contrario, da salida baja.
UNA | segundo | ~ (A + B) |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Puerta XOR (OR exclusivo)
Una puerta XOR es una puerta lógica que da salida alta si las entradas son diferentes; de lo contrario, da salida baja.
UNA | segundo | A⊕B |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Puerta X-NOR (NOR exclusiva)
Una puerta EX-NOR es una puerta lógica que da una salida alta si las entradas son las mismas, de lo contrario, da una salida baja.
UNA | segundo | A X-NOR B |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |