Representar la función booleana a partir de una tabla de verdad y/o circuito lógico

 

Un

en donde

un minitérmino es un producto de n literales con un literal para cada variable.

Un minitérmino tiene un valor de

Tomando sumas booleanas de distintos minitérminos se puede construir una expresión

booleana con un conjunto específico de valores. En particular una suma booleana de minitérminos

tiene un valor de 1 cuando exactamente uno de los minitérminos en la suma tiene valor

el valor 0 para cualquier otra combinación de valores de las variables.

Una expansión de suma-producto es una suma de minitérminos. Los minitérminos en la

suma booleana corresponden a aquellas combinaciones de valores en los cuales la función adquiere

el valor

A modo de ejemplo se puede encontrar la función booleana correspondiente a la tabla B.2

minitérmino de las variables booleanas x1, x2, ... , xn es un producto booleano y1 . y2 ... yni i y = x o bien i i y = x . Un literal es una variable booleana o su complemento. Por lo tanto1 si y solo si cada variable y i tiene un valor de 1.1 y adquiere1.

x y z F(x,y,z)

0 0 0 0

1 0 0 0

0 1 0 0

1 1 0 0

0 0 1 0

1 0 1 0

0 1 1 1

1 1 1 1

Tabla B.2

Para representar

bien

productos diferentes. Por lo tanto la función

F, se necesita una expresión que valga 1 en caso de que x = 0 e y = z = 1 ox = y = z = 1. Dicha expresión se puede construir por medio de una suma booleana de dosF quedaría

F

 

Toda función booleana puede representarse por una suma de minitérminos. Cada

minitérmino es el producto booleano de variables booleanas o sus complementos. Esto demuestra

que cada función booleana puede expresarse con los operadores

booleana se puede representar, se dice que el conjunto {+, . , } es

conjunto menor funcionalmente completo puede construirse si se consigue expresar alguno de los

operadores en términos de los otros dos. Por lo tanto si se utilizan las leyes de DeMorgan, se pueden

eliminar las sumas booleanas utilizando la identidad

+, . y [23]. Como cada funciónfuncionalmente completo. Un

x

+ y = x.y

Esto significa que el conjunto { , .} es funcionalmente completo. De manera similar se

puede deducir que el conjunto { , +} también es funcionalmente completo aplicando la segunda

ley de DeMorgan

x

.y = x + y

Sin embargo se pueden obtener conjuntos funcionalmente completos, aún mas pequeños. Se

define la operación | o (NAND), que dados dos variables booleanas retorna el complemento del

producto booleano y \ (NOR) que dadas dos variables booleanas retorna el complemento de la suma

booleana. Si se construye un conjunto con cada uno de los operadores, { | } y { \ }, se puede

demostrar que ambos conjuntos son funcionalmente completos.

. ( | ) | ( | )

|

x y x y x y

x x x

=

=

. ( \ 0) \ ( \ 0)

\ 0

x y x y

x x

=

=

En virtud de la completitud funcional de { . , }, queda demostrada la completitud de { | }

y { \ }

 Completitud funcional

(x, y, z) = x.y.z + x.y.z

Representación de funciones booleanas

Expansiones de suma-producto