La celosía de Post

En lógica y álgebra universal , el retículo de Post denota el retículo de todos los clones en un conjunto de dos elementos {0, 1}, ordenados por inclusión . Recibe su nombre de Emil Post , quien publicó una descripción completa del retículo en 1941. ^{[ 1 ]}

La red se muestra en la imagen de la derecha. La relativa simplicidad de la red de Post contrasta marcadamente con la red de clones en un conjunto de tres elementos (o más), que tiene la cardinalidad del continuo y una estructura interna compleja.

Como caso especial, el retículo implica el teorema de completitud funcional de Post : cualquier conjunto de operaciones booleanas es funcionalmente completo si y solo si no es un subconjunto de las funciones monótonas, afines, autoduales, que preservan la verdad o que preservan la falsedad.

La red de Post consta de 9 clones con nombre, dos familias de clones infinitamente numerables indexadas por los enteros positivos y todas las intersecciones finitas de estos.

Una función booleana , o conectiva lógica , es una operación n - aria f : 2 ⁿ → 2 para algún n ≥ 1 , donde 2 denota el conjunto de dos elementos {0, 1}. Las funciones booleanas particulares son las proyecciones

${\displaystyle \pi _{k}^{n}(x_{1},\dots ,x_{n})=x_{k},}$

y dada una función m -aria f y funciones n -arias g ₁ , ..., g _m , podemos construir otra función n -aria

${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{m}(x_{1},\dots ,x_{n})),}$

llamada su composición . Un conjunto de funciones cerrado bajo composición, y que contiene todas las proyecciones, se llama clon .

Sea B un conjunto de conectivos. Las funciones que se pueden definir mediante una fórmula que utiliza variables proposicionales y conectivos de B forman un clon [ B ], que es el clon más pequeño que incluye a B. Llamamos [ B ] al clon generado por B , y decimos que B es la base de [ B ]. Por ejemplo, [¬, ∧] son ​​todas funciones booleanas, y [0, 1, ∧, ∨] son ​​las funciones monótonas.

Utilizamos las operaciones ¬, N p , ( negación ), ∧, K pq , ( conjunción o encuentro ), ∨, A pq , ( disyunción o unión ), →, C pq , ( implicación ), ↔, E pq , ( bicondicional ), +, J pq ( disyunción exclusiva o adición de anillo booleano ), ↛, L pq , ^{[ 2 ]} ( no implicación ), ?: (el operador condicional ternario ) y las funciones unarias constantes 0 y 1. Además, necesitamos las funciones umbral. 

${\displaystyle \mathrm {th} _{k}^{n}(x_{1},\dots ,x_{n})={\begin{cases}1&{\text{si }}{\bigl |}\{i\mid x_{i}=1\}{\bigr |}\geq k,\\0&{\text{en otro caso.}}\end{cases}}}$

Por ejemplo, th ⁿ ₁ es la disyunción grande de todas las variables x _i , y th ⁿ _n es la conjunción grande. De particular importancia es la función de mayoría.

${\displaystyle \mathrm {maj} =\mathrm {th} _{2}^{3}=(x\land y)\lor (x\land z)\lor (y\land z).}$

Denotamos los elementos de 2 ⁿ (es decir, las asignaciones de verdad) como vectores: a = ( a ₁ , ..., a _n ) . El conjunto 2 ⁿ posee una estructura de álgebra booleana de producto natural . Es decir, el ordenamiento, las intersecciones, las uniones y otras operaciones sobre asignaciones de verdad n -arias se definen punto por punto:

${\displaystyle (a_{1},\dots ,a_{n})\leq (b_{1},\dots ,b_{n})\iff a_{i}\leq b_{i}{\text{ para }}i=1,\dots ,n,}$

${\displaystyle (a_{1},\dots ,a_{n})\land (b_{1},\dots ,b_{n})=(a_{1}\land b_{1},\dots ,a_{n}\land b_{n}).}$

La intersección de un número arbitrario de clones es, de nuevo, un clon. Es conveniente denotar la intersección de clones mediante una simple yuxtaposición , es decir, el clon C ₁ ∩ C ₂ ∩ ... ∩ C _k se denota por C ₁ C ₂ ... C _k . A continuación se presentan algunos clones especiales:

• M = [∧, ∨, 0, 1] es el conjunto de funciones monótonas : f ( a ) ≤ f ( b ) para todo a ≤ b .
• D = [maj, ¬] es el conjunto de funciones autoduales : ¬ f ( a ) = f (¬ a ) .
• A = [↔, 0] es el conjunto de funciones afines : las funciones que satisfacen

${\displaystyle {\begin{aligned}&f(a_{1},\dots ,a_{i-1},c,a_{i+1},\dots ,a_{n})=f(a_{1},\dots ,d,a_{i+1},\dots )\\\Rightarrow &f(b_{1},\dots ,c,b_{i+1},\dots )=f(b_{1},\dots ,d,b_{i+1},\dots )\end{aligned}}}$

para cada i ≤ n , a , b ∈ 2 ⁿ , y c , d ∈ 2 . Equivalentemente, las funciones expresables como f ( x ₁ , ..., x _n ) = a ₀ + a ₁ x ₁ + ... + a _n x _n para algún a ₀ , a .

• U = [¬, 0] es el conjunto de funciones esencialmente unarias , es decir, funciones que dependen como máximo de una variable de entrada: existe un i = 1, ..., n tal que f ( a ) = f ( b ) siempre que a _i = b _i .
• Λ = [∧, 0, 1] es el conjunto de funciones conjuntivas : f ( a ∧ b ) = f ( a ) ∧ f ( b ) . El clon Λ consta de las conjunciones${\displaystyle f(x_{1},\dots ,x_{n})=\bigwedge _{i\in I}x_{i}}$para todos los subconjuntos I de {1, ..., n } (incluida la conjunción vacía, es decir, la constante 1) y la constante 0.
• V = [∨, 0, 1] es el conjunto de funciones disyuntivas : f ( a ∨ b ) = f ( a ) ∨ f ( b ) . Equivalentemente, V consta de las disyunciones${\displaystyle f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}}$para todos los subconjuntos I de {1, ..., n } (incluida la disyunción vacía 0) y la constante 1.
• Para cualquier k ≥ 1, T ^k ₀ = [th ^k+2 _k+1 , ↛] es el conjunto de funciones f tales que

${\displaystyle \mathbf {a} ^{1}\land \cdots \land \mathbf {a} ^{k}=\mathbf {0} \ \Rightarrow \ f(\mathbf {a} ^{1})\land \cdots \land f(\mathbf {a} ^{k})=0.}$

Como caso especial, P ₀ = T ¹ ₀ = [∨, +] es el conjunto de funciones que preservan el 0 : f ( 0 ) = 0 . Además, ⊤ puede considerarse T ⁰ ₀ cuando se tiene en cuenta el encuentro vacío.

• Además,${\displaystyle \mathrm {T} _{0}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{0}^{k}}$= [↛] es el conjunto de funciones acotadas superiormente por una variable: existe i = 1, ..., n tal que f ( a ) ≤ a _i para todo a .
• Para cualquier k ≥ 1, T ^k ₁ = [th ^k+2 _k+1 , →] es el conjunto de funciones f tales que

${\displaystyle \mathbf {a} ^{1}\lor \cdots \lor \mathbf {a} ^{k}=\mathbf {1} \ \Rightarrow \ f(\mathbf {a} ^{1})\lor \cdots \lor f(\mathbf {a} ^{k})=1,}$

El caso especial P ₁ = T ¹ ₁ = [∧, →] consiste en las funciones que preservan 1 : f ( 1 ) = 1 . Además, ⊤ puede considerarse T ⁰ ₁ cuando se tiene en cuenta la unión vacía.

• Además,${\displaystyle \mathrm {T} _{1}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{1}^{k}}$= [→] es el conjunto de funciones acotadas inferiormente por una variable: existe i = 1, ..., n tal que f ( a ) ≥ a _i para todo a .
• El clon más grande de todas las funciones se denota ⊤ = [∨, ¬].

Además, el clon más pequeño (que contiene solo proyecciones) se denota ⊥ = [], y P = P ₀ P ₁ = [ x  ? y  : z ] es el clon de funciones que preservan la constante .

El conjunto de todos los clones constituye un sistema de cierre , por lo que forma un retículo completo . El retículo es numerablemente infinito y todos sus elementos son finitamente generados. Todos los clones se enumeran en la tabla siguiente.

Las ocho familias infinitas en realidad también tienen miembros con k = 1, pero estos aparecen por separado en la tabla: T ₀ ¹ = P ₀ , T ₁ ¹ = P ₁ , PT ₀ ¹ = PT ₁ ¹ = P , MT ₀ ¹ = MP ₀ , MT ₁ ¹ = MP ₁ , MPT ₀ ¹ = MPT ₁ ¹ = MP .

La red tiene una simetría natural que mapea cada clon C a su clon dual C ^d = { f ^d | f ∈ C }, donde f ^d ( x ₁ , ..., x _n ) = ¬ f (¬ x ₁ , ..., ¬ x _n ) es el dual de de Morgan de una función booleana f . Por ejemplo, Λ ^d = V , (T ₀ ^k ) ^d = T ₁ ^k , y M ^d = M .

La clasificación completa de clones booleanos proporcionada por Post ayuda a resolver varias cuestiones sobre las clases de funciones booleanas. Por ejemplo:

• Una inspección del retículo muestra que los clones máximos distintos de ⊤ (a menudo llamados clases de Post ) son M, D, A, P ₀ , P ₁ , y cada subclon propio de ⊤ está contenido en uno de ellos. Como un conjunto B de conectivos es funcionalmente completo si y solo si genera ⊤, obtenemos la siguiente caracterización: B es funcionalmente completo si y solo si no está incluido en ninguna de las cinco clases de Post.
• El problema de satisfacibilidad para fórmulas booleanas es NP-completo según el teorema de Cook . Consideremos una versión restringida del problema: para un conjunto finito fijo B de conectivos, sea B -SAT el problema algorítmico de comprobar si una fórmula B dada es satisfacible. Lewis ^{[ 3 ]} utilizó la descripción del retículo de Post para demostrar que B -SAT es NP-completo si la función ↛ puede generarse a partir de B (es decir, [ B ] ⊇ T ₀ ^∞ ), y en todos los demás casos B -SAT es decidible en tiempo polinomial .

Una exposición moderna del retículo de Post se puede encontrar en David Lau (2006): Function algebras on finite sets: Basic course on many-valued logic and clone theory. ^{[ 5 ]}