Electrónica Y Sistemas Digitales

Matemática Discreta y Lógica 1

Material teórico

Expresiones y funciones booleanas
Expresiones y funciones booleanas
Podemos definir las expresiones booleanas por medio de una definición recursiva de la siguiente forma:
•
•
•

0 es una expresión booleana y 1 es una expresión booleana
Las variables son expresiones booleanas
Si e es una expresión booleana, e es una expresión booleana•

Si

•

Si

e es una expresión booleana, (e) es una expresión booleana
e1 y e2 son expresiones booleanas, e1 + e2 y e1 ⋅ e2 son expresiones booleanas

El primer caso base que define los elementos del conjunto

G = {0,1}

como expresiones booleanas, se podría

simplificar cambiándolo por “Las constantes son expresiones booleanas”. Los elementos del álgebra son constantes,tienen un valor y éste no cambia.
Si no incluímos las variables, las expresiones booleanas siempre se podrían evaluar, y podrían por lo tanto siempre
escribirse como

0

o como

1.

Un ejemplo de expresión booleana es la siguiente:

( x + y) ⋅ z + x ⋅ ( y + z )
El valor de la evaluación de esta expresión estará en función de los valores de

x, y, z . De otra forma, la expresiónbooleana está definiendo una función de (por lo menos) las variables que incluye.
La expresión anterior podría ser la definición de la función:

f ( x, y, z , w) = ( x + y ) ⋅ z + x ⋅ ( y + z )
Para determinar los valores de una función se puede organizar una tabla que contemple todas las posibles
combinaciones de las variables de la función.
Consideremos por ejemplo la función booleana

f (x, y, z ) = ( x + y ) ⋅ z + x ⋅ ( y + z )

Para cada expresión dada, es posible hallar una tabla de evaluación y un circuito asociados.

x
0
0
0
0
1
1
1
1

y
0
0
1
1
0
0
1
1

z
0
1
0
1
0
1
0
1

f ( x, y , z )
0
1
1
1
0
1
0
1

Podemos preguntarnos si no habrá una expresión que represente la misma función y sea más sencilla, o permita
construir un circuitomás rápido (de menos niveles) o más barato (con menos compuertas).

Página 1 de 3

Matemática Discreta y Lógica 1

Material teórico

Suma de productos canónicos
Llamaremos producto canónico de n variables al producto de todas ellas en el cual cada variable aparece de forma
simple o complementada. Por ejemplo, un producto canónico de tres variables x, y , z es:

x⋅ y⋅z
Cada productocanónico da 1 sólo para una determinada combinación de las variables, y 0 para todas las otras
combinaciones.
Una suma de productos canónicos es una expresión formada sumando productos canónicos. Se puede demostrar que
toda función de n variables puede expresarse como:

f ( x1 , x2 ,..., xn ) = x1 ⋅ x2 ⋅ ... ⋅ xn ⋅ f (1,1,...,1)
+ x1 ⋅ x2 ⋅ ... ⋅ xn ⋅ f (0,1,...,1)
+ x1 ⋅ x2 ⋅ ... ⋅ xn ⋅ f(1,0,...,1)
...
+ x1 ⋅ x2 ⋅ ... ⋅ xn ⋅ f (0,0,...,0)
Es decir que toda función se puede representar como una suma de productos canónicos, ya que los coeficientes sólo
pueden ser 0 (lo que significaría que ese producto canónico no estará en la representación) o
este producto canónico sí estará en la representación).

1 (lo que significaría que

Si un producto canónico está en larepresentación de suma de productos canónicos de una función, significa que para
esa función, la combinación de variables que se obtiene con las variables que aparecen de forma simple en
variables que aparecen complementadas en

1 y con las

0 , se corresponde con un 1 .

Es fácil entonces buscar la representación de una función como suma de productos canónicos, buscando el producto
canónico quecorresponde a las combinaciones que dan
Por ejemplo, para el caso de la función

1.

f ( x, y, z ) = ( x + y ) ⋅ z + x ⋅ ( y + z ) ,

que se puede evaluar de la

siguiente forma:

x
0
0
0
0
1
1
1
1

y
0
0
1
1
0
0
1
1

z
0
1
0
1
0
1
0
1

f ( x, y , z )
0
1
1
1
0
1
0
1

→ x⋅ y⋅z
→ x⋅ y⋅z
→ x⋅ y⋅z
→ x⋅ y⋅z

→ x⋅ y⋅z

1 en la función,
1 sólo...