Funciones

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 e es una expresión booleana, (e) es una expresiónbooleana
Si 1 e y 2 e son expresiones booleanas, 1 2 e e y 1 2 e e 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 expresionesbooleanas 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ón
booleana está definiendo una función de (por lo menos) las variables que incluye.
La expresiónanterior 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 uncircuito asociados.
x y z f (x, y, z)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Podemos preguntarnos si no habrá una expresión que represente la misma función y sea más sencilla, o permita
construir un circuito más rápido (de menos niveles) o más barato (con menos compuertas).
Matemática Discreta y Lógica 1 Material teórico
Página 2 de 3
Suma de productoscanó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 producto canó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ónformada sumando productos canónicos. Se puede demostrar que
toda función de n variables puede expresarse como:
... (0,0,...,0)
...
... (1,0,...,1)
... (0,1,...,1)
( , ,..., ) ... (1,1,...,1)
1 2
1 2
1 2
1 2 1 2
x x x f
x x x f
x x x f
f x x x x x x f
n
n
n
n n




Es decir que toda función se puede representar como una suma de productoscanó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 1 (lo que significaría que
este producto canónico sí estará en la representación).
Si un producto canónico está en la representació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 lasvariables que aparecen de forma simple en 1 y con las
variables que aparecen complementadas en 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 que corresponde a las combinaciones que dan 1.
Por ejemplo, para el caso de la función f (x, y, z) (x y) z x ( y z) , que se puede evaluar de lasiguiente forma:
x y z f (x, y, z)
0 0 0 0
0 0 1 1 x y z
0 1 0 1 x y z
0 1 1 1 x y z
1 0 0 0
1 0 1 1 x y z
1 1 0 0
1 1 1 1 x y z
Los productos canónicos que hemos puesto al lado de cada combinación de variables que produce un 1 en la función,
corresponden al producto canónico que produce un 1 sólo para esa combinación. Si sumamos los productos canónicos...