Enrejado de postes

En lógica y álgebra universal , la red de Post denota la red de todos los clones en un conjunto de dos elementos {0, 1}, ordenados por inclusión . Recibe su nombre por Emil Post , quien publicó una descripción completa de la red en 1941. ^[1] La relativa simplicidad de la red de Post contrasta marcadamente con la red de clones en un conjunto de tres elementos (o mayor), que tiene la cardinalidad del continuo y una estructura interna complicada. Una exposición moderna del resultado de Post se puede encontrar en Lau (2006). ^[2]

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},\puntos ,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},\puntos ,x_{n})=f(g_{1}(x_{1},\puntos ,x_{n}),\puntos ,g_{m}(x_{1},\puntos ,x_{n})),}$

Se denomina su composición . Un conjunto de funciones cerradas bajo composición, y que contienen todas las proyecciones, se denomina clon .

Sea B un conjunto de conectivos. Las funciones que se pueden definir mediante una fórmula que utilice variables proposicionales y conectivos de B forman un clon [ B ], de hecho 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 , ^[3] ( 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 caso contrario.}}\end{cases}}}$

Por ejemplo, el^número
₁es la gran disyunción de todas las variables x _i , y la^y
_yes la gran conjunción. De particular importancia es la función mayoritaria

${\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, asignaciones de verdad) como vectores: a = ( a ₁ , ..., a _n ) . El conjunto 2 ⁿ tiene una estructura de álgebra de Boole de producto natural . Es decir, las operaciones de ordenación, encuentros, uniones y otras operaciones sobre asignaciones de verdad n -arias se definen puntualmente:

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

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

La intersección de un número arbitrario de clones es nuevamente un clon. Es conveniente denotar la intersección de clones por 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},\puntos ,a_{i-1},c,a_{i+1},\puntos ,a_{n})=f(a_{1},\puntos ,d,a_{i+1},\puntos )\\\Rightarrow &f(b_{1},\puntos ,c,b_{i+1},\puntos )=f(b_{1},\puntos ,d,b_{i+1},\puntos )\end{aligned}}}$

para cada i ≤ n , a , b ∈ 2 ⁿ , y c , d ∈ 2 . De manera equivalente, 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 una 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 Λ consiste en las conjunciones para todos los subconjuntos I de {1, ..., n } (incluyendo la conjunción vacía, es decir, la constante 1), y la constante 0.${\displaystyle f(x_{1},\puntos ,x_{n})=\bigwedge _{i\in I}x_{i}}$
• V = [∨, 0, 1] es el conjunto de funciones disyuntivas : f ( a ∨ b ) = f ( a ) ∨ f ( b ) . De manera equivalente, V consiste en las disyunciones para todos los subconjuntos I de {1, ..., n } (incluida la disyunción vacía 0), y la constante 1.${\displaystyle f(x_{1},\puntos ,x_{n})=\bigvee _{i\in I}x_{i}}$
• Para cualquier k ≥ 1, T^el
  ₀= [el^k+2k
  ₊₁, ↛] 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})\ tierra \cdots \land f(\mathbf {a} ^{k})=0.}$

Además, = [↛] es el conjunto de funciones acotadas anteriormente por una variable: existe i = 1, ..., n tales que f ( a ) ≤ a _i para todo a .${\displaystyle \mathrm {T} _{0}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{0}^{k}}$

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

• Para cualquier k ≥ 1, T^el
  ₁= [el^k+2k
  ₊₁, →] 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,}$

y = [→] es el conjunto de funciones acotadas inferiormente por una variable: existe i = 1, ..., n tales que f ( a ) ≥ a _i para todo a .${\displaystyle \mathrm {T} _{1}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{1}^{k}}$

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

• El clon más grande de todas las funciones se denota ⊤ = [∨, ¬], el clon más pequeño (que contiene solo proyecciones) se denota ⊥ = [], y P = P ₀ P ₁ = [ x  ? y  : z ] es el clon de las funciones que preservan constantes .

El conjunto de todos los clones es un sistema de cierre , por lo tanto forma una red completa . La red es infinitamente numerable y todos sus miembros se generan de forma finita. 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 asigna 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 los clones booleanos que ofrece Post ayuda a resolver diversas cuestiones sobre las clases de funciones booleanas. Por ejemplo:

• Una inspección de la red muestra que los clones máximos diferentes de ⊤ (a menudo llamados clases de Post ) son M, D, A, P ₀ , P ₁ , y cada subclón 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 una de las cinco clases de Post.
• El problema de satisfacibilidad para fórmulas booleanas es NP-completo por el teorema de Cook . Considérese una versión restringida del problema: para un conjunto finito fijo B de conectivos, sea B -SAT el problema algorítmico de verificar si una B -fórmula dada es satisfacible. Lewis ^[4] utilizó la descripción de la red de Post para mostrar 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 .

Si sólo se consideran los clones que deben contener las funciones constantes, la clasificación es mucho más sencilla: sólo hay siete clones de este tipo: UM, Λ, V, U, A, M y ⊤. Si bien esto se puede deducir de la clasificación completa, existe una prueba más sencilla que ocupa menos de una página. ^[5]

La composición por sí sola no permite generar una función nularia a partir de la función constante unaria correspondiente, esta es la razón técnica por la que las funciones nularias están excluidas de los clones en la clasificación de Post. Si eliminamos la restricción, obtenemos más clones. Es decir, cada clon C en la red de Post que contiene al menos una función constante corresponde a dos clones bajo la definición menos restrictiva: C y C junto con todas las funciones nularias cuyas versiones unarias están en C.

Post originalmente no trabajaba con la definición moderna de clones, sino con los llamados sistemas iterativos , que son conjuntos de operaciones cerrados bajo sustitución.

${\displaystyle h(x_{1},\puntos ,x_{n+m-1})=f(x_{1},\puntos ,x_{n-1},g(x_{n},\puntos ,x_{n+m-1})),}$

así como la permutación e identificación de variables. La principal diferencia es que los sistemas iterativos no contienen necesariamente todas las proyecciones. Cada clon es un sistema iterativo, y hay 20 sistemas iterativos no vacíos que no son clones. (Post también excluyó el sistema iterativo vacío de la clasificación, por lo tanto su diagrama no tiene elemento mínimo y no es una red). Como otra alternativa, algunos autores trabajan con la noción de una clase cerrada , que es un sistema iterativo cerrado bajo la introducción de variables ficticias. Hay cuatro clases cerradas que no son clones: el conjunto vacío, el conjunto de funciones constantes 0, el conjunto de funciones constantes 1 y el conjunto de todas las funciones constantes.