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