Expresiones
booleanas minimales
Considérese una expresión E en un álgebra de Boole B.
Como E puede representar un circuito lógico, es posible que pretendamos obtener
una expresión F que, siendo equivalente a la expresión original, sea en algún sentido
mínima; de esta forma, lograríamos minimizar la cantidad de compuertas lógicas
utilizadas para implementar la operación buscada, con la consiguiente economía
de recursos. Aquí nos concentraremos en la forma minimal de las expresiones
booleanas que están en forma de suma de productos.
Si E es una expresión booleana en forma de suma de productos,
EL denota el número de literales en E (contados con sus repeticiones) y ES
denota el número de sumandos en E.
Por ejemplo, si E es la siguiente expresión:
Entonces EL=14 y ES=4.
Sea ahora F una expresión booleana de suma de productos
equivalente a E. Decimos que E es más simple que F si se cumple que:
EL ≤ FL y ES ≤ FS
Y por lo menos una de las relaciones es una desigualdad
estricta.
Definición: Una expresión booleana E está en forma minimal
de suma de productos si está en forma de suma de productos y no hay ninguna
otra expresión equivalente en forma de suma de productos que sea más simple que
E.
No hay comentarios.:
Publicar un comentario