Una clase cerrada en la teoría de funciones booleanas es un conjunto de funciones del álgebra lógica , cuya clausura respecto a la operación de superposición coincide consigo misma: . En otras palabras, cualquier función que pueda expresarse mediante una fórmula utilizando funciones de conjunto se incluye nuevamente en el mismo conjunto.
En 1941, Emil Post presentó una descripción completa del sistema de clases cerradas, también llamado entramado de Post .
El conjunto de todas las funciones booleanas posibles es cerrado.
De particular importancia para la teoría de las funciones booleanas son las siguientes clases cerradas, llamadas clases precompletas :
Cualquier clase cerrada de funciones booleanas que no sea , está completamente contenida en al menos una de las cinco clases precompletas .
Otras clases cerradas importantes son:
En 1941, Emil Post demostró que cualquier clase cerrada de funciones booleanas es la intersección de un número finito de las clases descritas anteriormente, dando una descripción completa de la estructura de las clases cerradas de la lógica de dos valores. Post también estableció que cualquier clase cerrada puede ser generada por una base finita.
Un conjunto de funciones del álgebra lógica se llama sistema completo si la clausura de este conjunto coincide con el conjunto de todas las funciones. (En particular, para la lógica de dos valores ). En otras palabras, debería ser posible expresar cualquier función del álgebra de la lógica mediante una fórmula usando funciones de conjuntos .
El criterio de Post formula una condición necesaria y suficiente para la completitud de un sistema de funciones booleanas:
El sistema de funciones booleanas es completo si y sólo si no está enteramente contenido en ninguna de las clases , , , , .
En particular, si una función no está incluida en ninguna de las clases de Post, forma un sistema completo por sí misma. Un ejemplo es la función de Schaeffer (negación de conjunción ).
Los siguientes sistemas completos de funciones booleanas son ampliamente conocidos:
El primer sistema se usa, por ejemplo, para representar funciones en forma de formas normales disyuntivas y conjuntivas , el segundo se usa para representarlas en forma de polinomios de Zhegalkin .
Otros sistemas completos de funciones booleanas menos conocidos:
Un sistema completo de funciones se llama base si deja de ser completo cuando se excluye de él algún elemento. El primero de los sistemas completos mencionados anteriormente no es una base, ya que, según las leyes de Morgan, tanto la disyunción como la conjunción pueden excluirse del sistema y restaurarse utilizando las dos funciones restantes. El segundo sistema es la base: sus tres elementos son necesarios para la integridad. El número máximo posible de funciones booleanas en la base es 4.
A veces se habla de un sistema de funciones que está completo en alguna clase cerrada y, en consecuencia, de la base de esta clase. Por ejemplo, el sistema puede llamarse la base de una clase de funciones lineales.