Celosía del poste - Post's lattice

Diagrama de Hasse de la celosía 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 celosía en 1941. La relativa simplicidad de la celosía de Post está en marcado contraste con la celosía de los 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).

Conceptos básicos

Una función booleana , o conectiva lógica , es una operación n -aria f : 2 ⁿ → 2 para algunos 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 -ary f , yn funciones -ary g ₁ , ..., g _m , podemos construir otra función n -ary

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

llamado su composición . Un conjunto de funciones cerradas por composición y que contienen todas las proyecciones se denomina clon .

Sea B un conjunto de conectivos. Las funciones que pueden ser definidos por una fórmula usando variables proposicionales y conectivos de B forman un clon [ B ], de hecho es el clon más pequeño que incluye 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 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 adición de anillo booleano ), ↛, L pq , (no implicación ),?: (el operador condicional ternario ) y las funciones unarias constantes 0 y 1. Además, necesitamos las 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 {de lo contrario.}} \ 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 ⁿ lleva una estructura de álgebra de Boole de producto natural . Es decir, ordenar, encontrar, unir y otras operaciones en asignaciones de verdad n -ary se definen puntualmente:

{\ Displaystyle (a_ {1}, \ dots, a_ {n}) \ leq (b_ {1}, \ dots, b_ {n}) \ iff a_ {i} \ leq b_ {i} {\ text {para }} i = 1, \ puntos, 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 por yuxtaposición simple , es decir, el clon C ₁ ∩ C ₂ ∩ ... ∩ C _k se denota por C ₁C ₂ ... C _k . A continuación se presentan algunos clones especiales:

M es el conjunto de funciones monótonas : f ( a ) ≤ f ( b ) para todo a ≤ b .
D es el conjunto de funciones auto-duales : ¬ f ( a ) = f (¬ a ) .
A es el conjunto de funciones afines : las funciones que satisfacen

{\ Displaystyle {\ begin {alineado} & f (a_ {1}, \ dots, a_ {i-1}, c, a_ {i + 1}, \ dots, a_ {n}) = f (a_ {1}) , \ dots, d, a_ {i + 1}, \ dots) \\\ Flecha derecha & f (b_ {1}, \ dots, c, b_ {i + 1}, \ dots) = f (b_ {1}, \ puntos, d, b_ {i + 1}, \ puntos) \ end {alineado}}}

para todo 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 un 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}) = \ bigve _ {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}) \ tierra \ cdots \ tierra f (\ mathbf {a} ^ {k}) = 0.}

Además, el conjunto de funciones está acotado arriba 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 preservadoras de 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 limitadas 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 conservadoras de 1 : f ( 1 ) = 1 . Además, ⊤ puede considerarse T ₁⁰ cuando se tiene en cuenta la combinació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 preservan 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 celosía es infinitamente numerable y todos sus miembros se generan de forma finita. Todos los clones se enumeran en la tabla siguiente.

Diagrama de Hasse de la celosía de Post

Parte central de la celosía

clon	una de sus bases
⊤	∨, ¬
P ₀	∨, +
P ₁	∧, →
PAGS	x ? y : z
T ₀^k , k ≥ 2	th _k^{k +1} , ↛
T ₀^∞	↛
PT ₀^k , k ≥ 2	th _k^{k +1} , x ∧ ( y → z )
PT ₀^∞	x ∧ ( y → z )
T ₁^k , k ≥ 2	th ₂^{k +1} , →
T ₁^∞	→
PT ₁^k , k ≥ 2	th ₂^{k +1} , x ∨ ( y + z )
PT ₁^∞	x ∨ ( y + z )
METRO	∧, ∨, 0, 1
MP ₀	∧, ∨, 0
MP ₁	∧, ∨, 1
MP	∧, ∨
MT ₀^k , k ≥ 2	th _k^{k +1} , 0
MT ₀^∞	x ∧ ( y ∨ z ), 0
MPT ₀^k , k ≥ 2	th _k^{k +1} para k ≥ 3, maj, x ∧ ( y ∨ z ) para k = 2
MPT ₀^∞	x ∧ ( y ∨ z )
MT ₁^k , k ≥ 2	th ₂^{k +1} , 1
MT ₁^∞	x ∨ ( y ∧ z ), 1
MPT ₁^k , k ≥ 2	th ₂^{k +1} para k ≥ 3, maj, x ∨ ( y ∧ z ) para k = 2
MPT ₁^∞	x ∨ ( y ∧ z )
Λ	∧, 0, 1
ΛP ₀	∧, 0
ΛP ₁	∧, 1
ΛP	∧
V	∨, 0, 1
VP ₀	∨, 0
VP ₁	∨, 1
Vicepresidente	∨
re	maj, ¬
DP	maj, x + y + z
DM	comandante
UN	↔, 0
ANUNCIO	¬, x + y + z
AP ₀	+
AP ₁	↔
AP	x + y + z
U	¬, 0
UD	¬
UM	0, 1
ARRIBA ₀	0
ARRIBA ₁	1
⊥

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 con 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 solo 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 verificar si una fórmula B dada es satisfactoria. Lewis usó la descripción de la celosía de Post para mostrar que B -SAT es NP-completo si la función ↛ se puede generar a partir de B (es decir, [ B ] ⊇ T ₀^∞ ), y en todos los demás casos B -SAT es polinomio- tiempo decidible.

Variantes

Post originalmente no funcionaba 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 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 que su diagrama no tiene el menor elemento y no puede ser una celosía). Como otra alternativa, algunos autores trabajan con la noción de una 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.

La composición por sí sola no permite generar una función nular a partir de la función constante unaria correspondiente, esta es la razón técnica por la que las funciones nulares se excluyen de los clones en la clasificación de Post. Si levantamos la restricción, obtenemos más clones. A saber, cada clon C en celosía de Post, que contiene al menos un constantes corresponde de función a dos clones bajo la definición menos restrictiva: C , y C , junto con todas las funciones nularia cuyas versiones unario están en C .

Referencias

^ EL Post, Los sistemas iterativos de dos valores de la lógica matemática , Annals of Mathematics Studies, no. 5, Princeton University Press, Princeton 1941, 122 págs.
^ 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
^ Jozef Maria Bochenski (1959), rev., Albert Menne, ed. y trad., Otto Bird, Precis of Mathematical Logic , Nueva York: Gordon y Breach, Parte II, "Lógica de sentencias", Sec. 3.23, "'N p '" Sec. 3.32, "16 functores de verdad diádicos", págs. 10-11.
^ HR Lewis , Problemas de satisfacción para cálculos proposicionales , Teoría de sistemas matemáticos 13 (1979), págs. 45-53.

[1] EL Post, Los sistemas iterativos de dos valores de la lógica matemática , 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 trad., Otto Bird, Precis of Mathematical Logic , Nueva York: Gordon y Breach, Parte II, "Lógica de sentencias", 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. 45-53.

Languages

In other projects