Clases de funciones booleanas cerradas

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. $PAGS$ $[P]=P$ $PAGS$

En 1941, Emil Post presentó una descripción completa del sistema de clases cerradas, también llamado entramado de Post .

Propiedades de cierre de función con variables

Cualquier conjunto es un subconjunto de su cierre: . $A\subconjunto [A]$
Un cierre de subconjunto es un subconjunto de un cierre: . Cabe señalar que la incrustación estricta de conjuntos implica solo una incrustación no estricta de sus cierres: . $A\subconjunto B\Rightarrow [A]\subconjunto [B]$
$A\subconjunto B\Rightarrow [A]\subconjuntoq [B]$
La aplicación múltiple de la operación de cierre equivale a una sola aplicación: . $[[A]]=[A]$

Ejemplos de clases cerradas

El conjunto de todas las funciones booleanas posibles es cerrado. $P_2$

De particular importancia para la teoría de las funciones booleanas son las siguientes clases cerradas, llamadas clases precompletas :

La clase de funciones que conservan la constante 0: . $T_{0}$
$T_{0}=\izquierda\{f(x_{1},\puntos,x_{n})|f(0,\puntos,0)=0\derecha\}$
La clase de funciones que conservan la constante 1: . $T_{1}$
$T_{1}=\izquierda\{f(x_{1},\puntos,x_{n})|f(1,\puntos,1)=1\derecha\}$
La clase de funciones auto-dual : . $S$
$S=\left\{f(x_{1},\dots,x_{n})|f(\overline {x_{1}},\dots,\overline {x_{n}})=\overline {f (x_{1},\puntos,x_{n})}\derecha\}$
Clase de funciones booleanas monótonas : . $METRO$
$M=\left\{f(x_{1},\dots ,x_{n})|\forall i(a_{i}\leq b_{i})\Rightarrow f(a_{1},\dots ,a_ {n})\leq f(b_{1},\dots,b_{n})\right\}$
Clase de función booleana lineal : . $L$
$L=\left\{f(x_{1},\dots,x_{n})|f(x_{1},\dots,x_{n})=a_{0}\oplus a_{1}x_{ 1}\oplus \dots \oplus a_{n}x_{n},a_{i}\in \{0,1\}\right\}$

Cualquier clase cerrada de funciones booleanas que no sea , está completamente contenida en al menos una de las cinco clases precompletas . $P_2$

Otras clases cerradas importantes son:

La clase de conjunciones K, que es el cierre del conjunto . Es un conjunto de funciones de la forma . $\{\ cuña, 0,1\}$ $c_{0}\cuña (c_{1}\vee x_{1})\cuña \ldots \cuña (c_{n}\vee x_{n})$
Disyunción clase D, que es la clausura del conjunto . Es un conjunto de funciones de la forma . $\{\vee,0,1\}$ $c_{0}\vee (c_{1}\cuña x_{1})\vee \ldots \vee (c_{n}\cuña x_{n})$
Clase de funciones de una variable U, que contiene solo constantes, negación y un selector (una función igual a uno de sus argumentos en todos los conjuntos de sus valores).
Una clase de funciones (m es cualquier número natural mayor que uno) que satisface la siguiente condición: para cualquier m conjuntos en los que la función toma un valor cero, hay una variable que también toma un valor cero en todos estos conjuntos. $O^{m}$
La clase de funciones para las que se cumple la condición , donde es una de las variables de función. $O^{\infty}$ $f(x_{1},\ldots,x_{n})\geq x_{i}$ $x_{yo}$
La clase de funciones (m es cualquier número natural mayor que uno) que satisface la siguiente condición: para cualesquiera m conjuntos en los que la función toma el valor unitario, existe una variable que también toma el valor unitario en todos estos conjuntos. $yo^{m}$
La clase de funciones para las que se cumple la condición , donde es una de las variables de función. $yo^{\infty}$ $f(x_{1},\ldots,x_{n})\leq x_{i}$ $x_{yo}$

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.

Algunas propiedades de las clases cerradas

Una intersección no vacía de clases cerradas es nuevamente una clase cerrada.
La unión de clases cerradas no puede ser una clase cerrada.
Una clase cerrada de funciones booleanas que contienen no solo constantes necesariamente contiene una función idéntica.
El complemento de una clase cerrada de funciones booleanas al conjunto de todas las funciones booleanas no es una clase cerrada. $P_2$

Sistemas completos de funciones

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 . $A$ $[A]=P_{2}$ $A$

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 , , , , . $T_{0}$ $T_{1}$ $S$ $METRO$ $L$
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:

$\left\{\land ,\lor ,\neg \right\}$ ( conjunción , disyunción , negación );
$\left\{\land ,\oplus ,1\right\}$ (conjunción, suma módulo 2 , constante 1);
$\left\{\land ,\neg \right\}$ ( conjunción , negación );
$\left\{\lor ,\neg \right\}$ ( disyunción , negación );
$\izquierda\{\flecha abajo \derecha\}$ ( Flecha perforante );
$\izquierda\{|\derecha\}$ ( golpe de Scheffer ).

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:

$\left\{\rightarrow ,\neg \right\}$ ( implicación , negación );
$\izquierda\{\flecha derecha,\oplus \derecha\}$ ( implicación , suma módulo 2 );
$\izquierda\{\flecha derecha,0\derecha\}$ ( implicación , constante 0);

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. $\izquierda\{\oplus,1\derecha\}$

Notas

Literatura

Yablonsky SV Introducción a las matemáticas discretas. — M .: Nauka, 1986.
Marchenkov S. S. Clases cerradas de funciones booleanas. — M .: Fizmatlit, 2000.
Gavrilov G. P., Sapozhenko A. A. Colección de problemas en matemáticas discretas. — M.: Nauka. — 1969
Alekseev V. B. Matemáticas discretas (curso de conferencias, II semestre). compensación AD Pospelov
Akhmetova N.A., Usmanova Z.M. Matemáticas discretas, funciones del álgebra de la lógica.