celosía de correos

Diagrama de Hasse de la red de Post.

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 . Lleva el nombre de 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 más grande), que tiene la cardinalidad del continuo y una estructura interna complicada. Se puede encontrar una exposición moderna del resultado de Post en Lau (2006). ^[2]

Conceptos básicos

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}. 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 n funciones 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})),}$

llamó su composición . Un conjunto de funciones cerradas bajo composición y que contiene todas las proyecciones se llama clon .

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

Usamos 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 suma de anillo booleano ), ↛, L pq , ^[3] ( no implicación ), ?: (el operador condicional ternario ) y las funciones unarias constantes 0 y 1. Además, necesitamos el funciones de umbral

${\displaystyle \mathrm {th} _{k}^{n}(x_{1},\dots ,x_{n})={\begin{cases}1&{\text{if }}{\bigl |}\{i\mid x_{i}=1\}{\bigr |}\geq k,\\0&{\text{otherwise.}}\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 mayoritaria.

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

Denotamos elementos de 2 ⁿ (es decir, asignaciones de verdad) como vectores: a = ( a ₁ , ..., a _n ) . El conjunto 2 ⁿ tiene una estructura de álgebra booleana de producto natural . Es decir, ordenar, reunir, unir y otras operaciones en asignaciones de verdad n -arias se definen puntualmente:

${\displaystyle (a_{1},\dots ,a_{n})\leq (b_{1},\dots ,b_{n})\iff a_{i}\leq b_{i}{\text{ for }}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}).}$

Denominación de clones

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

• M es el conjunto de funciones monótonas : f ( a ) ≤ f ( b ) para cada a ≤ b .
• D es el conjunto de funciones autoduales : ¬ f ( a ) = f (¬ a ) .
• A 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 . De manera equivalente, las funciones expresables como f ( x ₁ , ..., x _n ) = a ₀ + a ₁ x ₁ + ... + a _n x _n para algunos a ₀ , a .

• U es el conjunto de funciones esencialmente unarias , es decir, funciones que dependen como máximo de una variable de entrada: existe an i = 1, ..., n tal que f ( a ) = f ( b ) siempre que a _i = b _i .
• Λ es el conjunto de funciones conjuntivas : f ( a ∧ b ) = f ( a ) ∧ f ( b ) . El clon Λ consta de las conjunciones para todos los subconjuntos I de {1,..., n } (incluida la conjunción vacía, es decir, la constante 1) y la constante 0. ${\displaystyle f(x_{1},\dots ,x_{n})=\bigwedge _{i\in I}x_{i}}$
• V es el conjunto de funciones disyuntivas : f ( a ∨ b ) = f ( a ) ∨ f ( b ) . De manera equivalente, V consta de 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},\dots ,x_{n})=\bigvee _{i\in I}x_{i}}$
• Para cualquier k ≥ 1, T ₀ ^k 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.}$

Además, el conjunto de funciones está acotado anteriormente por una variable: existe i = 1, ..., n tal 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 conservan 0 : f ( 0 ) = 0 . Además, ⊤ puede considerarse T ₀ ⁰ cuando se tiene en cuenta el encuentro vacío.

• Para cualquier k ≥ 1, T ₁ ^k 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 a continuación por una variable: existe i = 1, ..., n tal 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 conservan 1 : f ( 1 ) = 1 . Además, ⊤ puede considerarse T ₁ ⁰ cuando se tiene 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 ₁ es el clon de funciones que conservan constantes .

Descripción de la celosía

El conjunto de todos los clones es un sistema de cierre , por lo que forma una red completa . La red es numerablemente infinita y todos sus miembros están generados de forma finita. Todos los clones se enumeran en la siguiente tabla.

Diagrama de Hasse de la red de Post.

Parte central de la celosía

Las ocho familias infinitas en realidad también tienen miembros con k = 1, pero 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 Morgan de una función booleana f . Por ejemplo, Λ ^d = V , (T ₀ ^k ) ^d = T ₁ ^k y M ^d = M .

Aplicaciones

La clasificación completa de clones booleanos proporcionada por Post ayuda a resolver varias preguntas sobre 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 subclon adecuado de ⊤ está contenido en uno de ellos. Como un conjunto B de conectivos es funcionalmente completo si y sólo si genera ⊤, obtenemos la siguiente caracterización: B es funcionalmente completo si no está incluido en una de las cinco clases de Post.
• El problema de satisfacibilidad de las fórmulas booleanas es NP-completo según el teorema de Cook . Considere 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 determinada fórmula B es satisfactoria. Lewis ^[4] usó 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 .

Variantes

Subconjunto de la red de Post que muestra solo los 7 clones que contienen todas las funciones constantes

Clones que requieren funciones constantes

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

Clones que permiten funciones nulas

La composición por sí sola no permite generar una función nula a partir de la función constante unaria correspondiente; esta es la razón técnica por la que las funciones nulas están excluidas de los clones en la clasificación de Post. Si levantamos la restricción, obtendremos 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 según la definición menos restrictiva: C y C junto con todas las funciones nulas cuyas versiones unarias están en C.

Sistemas iterativos

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

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

así como permutación e identificación de variables. La principal diferencia es que los sistemas iterativos no necesariamente contienen 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 que su diagrama no tiene el menor elemento y no es un entramado). Como otra alternativa, algunos autores trabajan con la noción de clase cerrada , que es un sistema iterativo cerrado bajo 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.

Referencias

1. EL Post, Los sistemas iterativos de lógica matemática de dos valores , Annals of Mathematics Studies, no. 5, Princeton University Press, Princeton 1941, 122 págs.
2. D. Lau, Álgebras de funciones en conjuntos finitos: curso básico sobre lógica multivaluada y teoría de clones , Springer, Nueva York, 2006, 668 págs. ISBN  978-3-540-36022-3
3. Jozef Maria Bochenski (1959), rev., Albert Menne, ed. y trans., Otto Bird, Precis of Mathematical Logic , Nueva York: Gordon and Breach, Part II, "Logic of Sentences", Sec. 3.23, "'N p '", Sec. 3.32, "16 functores de verdad diádicos", págs. 10-11.
4. HR Lewis , Problemas de satisfacción para cálculos proposicionales , Teoría de sistemas matemáticos 13 (1979), págs.
5. Apéndice 12 de Aaronson, Scott; Grier, Daniel; Schaeffer, Lucas (2015). "La clasificación de operaciones de bits reversibles". arXiv : 1504.05155 [cuántico-ph].