cálculo proposicional implicacional

En lógica matemática , el cálculo proposicional implicacional es una versión del cálculo proposicional clásico que utiliza solo un conector , llamado implicación o condicional . En fórmulas , esta operación binaria se indica mediante "implica", "si ..., entonces ...", "→", " $\rightarrow$ ", etc..

Incompletitud (funcional)

La implicación por sí sola no es funcionalmente completa como operador lógico porque no se pueden formar a partir de ella todas las demás funciones de verdad de dos valores .

Por ejemplo, la función de verdad binaria que siempre devuelve falso no se puede definir a partir de → y variables proposicionales arbitrarias: cualquier fórmula construida a partir de → y variables proposicionales debe recibir el valor verdadero cuando todas sus variables se evalúan como verdaderas. De ello se deduce que {→} no es funcionalmente completa.

Sin embargo, si se añade un conector nulo ⊥ para la falsedad, entonces se pueden definir todas las demás funciones de verdad. Las fórmulas sobre el conjunto resultante de conectores {→, ⊥} se denominan f-implicacionales . ^{[ 1 ]} Si P y Q son proposiciones, entonces:

¬ P es equivalente a P → ⊥
P ∧ Q es equivalente a ( P → ( Q → ⊥)) → ⊥
P ∨ Q es equivalente a ( P → Q ) → Q
P ↔ Q es equivalente a (( P → Q ) → (( Q → P ) → ⊥)) → ⊥

Dado que se sabe que los operadores anteriores son funcionalmente completos, se deduce que cualquier función de verdad puede expresarse en términos de → y ⊥.

Sistema axiomático

Las siguientes afirmaciones se consideran tautologías (irreductibles e intuitivamente verdaderas, por definición).

El esquema de axioma 1 es P → ( Q → P ).
El esquema del axioma 2 es ( P → ( Q → R )) → (( P → Q ) → ( P → R )).
El esquema axiomático 3 ( ley de Peirce ) es (( P → Q ) → P ) → P .
La única regla de inferencia no nula ( modus ponens ) es: de P y P → Q inferir Q.

En cada caso, P , Q y R pueden ser reemplazados por cualquier fórmula que contenga solo "→" como conector. $\Gamma$ es un conjunto de fórmulas y A una fórmula, entonces $\Gamma \vdash A$ significa que A se puede derivar utilizando los axiomas y reglas anteriores y las fórmulas de $\Gamma$ como hipótesis adicionales.

Łukasiewicz (1948) encontró un sistema axiomático para el cálculo implicacional que reemplaza los esquemas 1-3 anteriores con un único esquema.

(( P → Q ) → R ) → (( R → P ) → ( S → P )).

También argumentó que no existe un sistema axiomático más corto. ^{[ 2 ]}

Propiedades básicas de la derivación

Dado que todos los axiomas y reglas del cálculo son esquemas, la derivación es cerrada bajo sustitución :

Si

\Gamma \vdash A,

entonces

\sigma (\Gamma )\vdash \sigma (A),

donde σ es cualquier sustitución (de fórmulas que utilizan únicamente la implicación).

El cálculo proposicional implicacional también satisface el teorema de deducción :

Si

\Gamma ,A\vdash B

, entonces

\Gamma \vdash A\to B.

Como se explica en el artículo sobre el teorema de deducción , esto se cumple para cualquier extensión axiomática del sistema que contenga los esquemas axiomáticos 1 y 2 anteriores y el modus ponens.

Lo completo

El cálculo proposicional implicacional es semánticamente completo con respecto a la semántica bivaluada usual de la lógica proposicional clásica. Es decir, si Γ es un conjunto de fórmulas implicacionales, y A es una fórmula implicacional derivada de Γ, entonces $\Gamma \vdash A$ .

Prueba

A continuación se describe una demostración del teorema de completitud. En primer lugar, utilizando el teorema de compacidad y el teorema de deducción, podemos reducir el teorema de completitud a su caso particular con Γ vacío; es decir, solo necesitamos demostrar que toda tautología es derivable en el sistema.

La demostración es similar a la completitud de la lógica proposicional completa, pero también utiliza la siguiente idea para superar la incompletitud funcional de la implicación. Si A y F son fórmulas, entonces $A \to F$ es equivalente a $(\neg A*) \lor F,$ donde A* es el resultado de reemplazar en A todas, algunas o ninguna de las ocurrencias de F por falsedad. De manera similar, $(A \to F) \to F$ es equivalente a $A* \lor F .$ Por lo tanto, bajo ciertas condiciones, se pueden usar como sustitutos para decir que A* es falso o A* es verdadero, respectivamente.

En primer lugar, observamos algunos hechos básicos sobre la derivabilidad:

De hecho, podemos derivar A → ( B → C ) usando el Axioma 1, y luego derivar A → C por modus ponens (dos veces) del Ax. 2.

Esto se deduce de ( 1 ) por el teorema de deducción.

Si además asumimos C → B , podemos derivar

A \to B

usando ( 1 ), luego derivamos C por modus ponens. Esto muestra

A\to C,(A\to B)\to C,C\to B\vdash C

y el teorema de deducción da

A\to C,(A\to B)\to C\vdash (C\to B)\to C

. Aplicamos el eje 3 para obtener ( 3 ).

Sea F una fórmula fija arbitraria. Para cualquier fórmula A , definimos $A 0 = (A \to F)$ y $A 1 = ((A \to F) \to F).$ Consideremos solo fórmulas en variables proposicionales p ₁ , ..., p _n . Afirmamos que para cada fórmula A en estas variables y cada asignación de verdad e ,

Demostramos ( 4 ) por inducción sobre A. El caso base A = p _i es trivial. Sea $A = (B \to C).$ Distinguimos tres casos:

e ( C ) = 1. Entonces también e ( A ) = 1. Tenemos
$(C\to F)\to F\vdash ((B\to C)\to F)\to F$
aplicando ( 2 ) dos veces al axioma $C \to (B \to C).$ Dado que hemos derivado $(C \to F) \to F$ por la hipótesis de inducción, podemos inferir $((B \to C) \to F) \to F .$
e ( B ) = 0. Entonces, nuevamente e ( A ) = 1. El teorema de deducción aplicado a ( 3 ) da
$B\to F\vdash ((B\to C)\to F)\to F.$
Dado que hemos derivado $B \to F$ por la hipótesis de inducción, podemos inferir $((B \to C) \to F) \to F .$
e ( B ) = 1 y e ( C ) = 0. Entonces e ( A ) = 0. Tenemos
${\begin{aligned}(B\to F)\to F,C\to F,B\to C&\vdash B\to F&&{\text{por (1)}}\\&\vdash F&&{\text{por modus ponens,}}\end{aligned}}$
de este modo $(B\to F)\to F,C\to F\vdash (B\to C)\to F$ por el teorema de deducción. Hemos derivado $(B \to F) \to F$ y $C \to F$ por la hipótesis de inducción, por lo tanto podemos inferir $(B \to C) \to F .$ Esto completa la demostración de ( 4 ).

Ahora sea F una tautología en variables p ₁ , ..., p _n . Demostraremos por inducción inversa sobre k = n ,...,0 que para cada asignación e ,

El caso base k = n se deduce de un caso especial de ( 4 ) usando

F^{e(F)}=F^{1}=((F\to F)\to F)

y el hecho de que F → F es un teorema por el teorema de deducción.

Supongamos que ( 5 ) se cumple para k + 1, lo demostraremos para k . Aplicando el teorema de deducción a la hipótesis de inducción, obtenemos

{\begin{aligned}p_{1}^{e(p_{1})},\dots ,p_{k}^{e(p_{k})}&\vdash (p_{k+1}\to F)\to F,\\p_{1}^{e(p_{1})},\dots ,p_{k}^{e(p_{k})}&\vdash ((p_{k+1}\to F)\to F)\to F,\end{aligned}}

primero estableciendo e ( p _{k +1} ) = 0 y segundo estableciendo e ( p _{k +1} ) = 1. A partir de esto derivamos ( 5 ) usando modus ponens.

Para k = 0 obtenemos que la tautología F es demostrable sin suposiciones. Esto era lo que se debía demostrar.

Esta demostración es constructiva. Es decir, dada una tautología, se podrían seguir las instrucciones y construir una demostración a partir de sus axiomas. Sin embargo, la longitud de dicha demostración aumenta exponencialmente con el número de variables proposicionales de la tautología, por lo que no resulta un método práctico salvo para las tautologías más cortas.

El sistema de axiomas de Bernays-Tarski

El sistema de axiomas de Bernays-Tarski se usa con frecuencia. En particular, el artículo de Łukasiewicz deriva los axiomas de Bernays-Tarski a partir del único axioma de Łukasiewicz como un medio para demostrar su completitud. Se diferencia de los esquemas de axiomas anteriores al reemplazar el esquema de axioma 2, ( P →( Q → R ))→(( P → Q )→( P → R )), con

Esquema de axioma 2': ( P → Q )→(( Q → R )→( P → R )),

lo que se denomina silogismo hipotético . Esto dificulta un poco la derivación del metateorema de deducción, pero aún así es posible.

Demostramos que a partir de P →( Q → R ) y P → Q se puede derivar P → R . Este hecho puede utilizarse en lugar del esquema axiomático 2 para obtener el metateorema.

P → ( Q → R ) dado
P → Q dado
( P → Q )→(( Q → R )→( P → R )) ax 2'
( Q → R ) → ( P → R ) pf 2,3
( P →( Q → R ))→((( Q → R )→( P → R ))→( P →( P → R ))) ax 2'
(( Q → R )→( P → R ))→( P →( P → R )) pf 1,5
P →( P → R ) mp 4,6
( P →( P → R ))→((( P → R )→ R )→( P → R )) ax 2'
(( P → R )→ R )→( P → R ) pf 7,8
((( P → R )→ R )→( P → R ))→( P → R ) ax 3
P → R mp 9,10 qed

Satisfacibilidad y validez

La satisfacibilidad en el cálculo proposicional implicacional es trivial, porque toda fórmula es satisfacible: basta con establecer todas las variables como verdaderas.

La falsabilidad en el cálculo proposicional implicacional es NP-completa , ^{[ 3 ]} lo que significa que la validez (tautología) es co-NP-completa .

En este caso, una técnica útil consiste en suponer que la fórmula no es una tautología e intentar encontrar una valoración que la haga falsa. Si se logra, entonces efectivamente no es una tautología. Si no se logra, entonces sí lo es.

Ejemplo de una no tautología :

Supongamos que [( A → B )→(( C → A )→ E )]→([ F →(( C → D )→ E )]→[( A → F )→( D → E )]) es falso.

Entonces ( A → B )→(( C → A )→ E ) es verdadero; F →(( C → D )→ E ) es verdadero; A → F es verdadero; D es verdadero; y E es falso.

Dado que D es verdadero, C → D es verdadero. Por lo tanto, la verdad de F →(( C → D )→ E ) es equivalente a la verdad de F → E .

Entonces, como E es falso y F → E es verdadero, obtenemos que F es falso.

Dado que A → F es verdadero, A es falso. Por lo tanto, A → B es verdadero y ( C → A )→ E es verdadero.

C → A es falso, por lo tanto C es verdadero.

El valor de B no importa, por lo que podemos elegirlo arbitrariamente como verdadero.

En resumen, la valoración que establece B , C y D como verdaderas y A , E y F como falsas hará que [( A → B )→(( C → A )→ E )]→([ F →(( C → D )→ E )]→[( A → F )→( D → E )]) sea falsa. Por lo tanto, no es una tautología.

Ejemplo de tautología :

Supongamos que (( A → B )→ C )→(( C → A )→( D → A )) es falso.

Entonces ( A → B )→ C es verdadero; C → A es verdadero; D es verdadero; y A es falso.

Dado que A es falso, A → B es verdadero. Por lo tanto, C es verdadero. Así pues, A debe ser verdadero, lo que contradice el hecho de que sea falso.

Por lo tanto, no existe ninguna valoración que haga falsa la proposición (( A → B )→ C )→(( C → A )→( D → A )). En consecuencia, se trata de una tautología.

Agregar un esquema axioma

¿Qué pasaría si se añadiera otro esquema axiomático a los enumerados anteriormente? Hay dos casos: (1) es una tautología; o (2) no es una tautología.

Si se trata de una tautología, el conjunto de teoremas sigue siendo el mismo que antes. Sin embargo, en algunos casos es posible encontrar demostraciones significativamente más cortas. No obstante, la longitud mínima de las demostraciones de teoremas seguirá siendo ilimitada; es decir, para cualquier número natural n, siempre habrá teoremas que no se puedan demostrar en n pasos o menos.

Si el nuevo esquema axiomático no es una tautología, entonces cada fórmula se convierte en un teorema (lo que hace que el concepto de teorema sea inútil en este caso). Es más, entonces hay una cota superior para la longitud mínima de una demostración de cada fórmula, porque hay un método común para demostrar cada fórmula. Por ejemplo, supongamos que el nuevo esquema axiomático fuera (( B → C )→ C )→ B . Entonces (( A →( A → A ))→( A → A ))→ A es una instancia (uno de los nuevos axiomas) y tampoco es una tautología. Pero [(( A → ( A → A ))→( A → A ))→ A ]→ A es una tautología y por lo tanto un teorema debido a los axiomas antiguos (usando el resultado de completitud anterior). Aplicando el modus ponens, obtenemos que A es un teorema del sistema extendido. Entonces, para demostrar cualquier fórmula, basta con sustituir A por la fórmula deseada en toda la demostración de A. Esta demostración tendrá el mismo número de pasos que la demostración de A.

Una axiomatización alternativa

Los axiomas mencionados anteriormente se basan principalmente en el metateorema de la deducción para alcanzar la completitud. A continuación, se presenta otro sistema axiomático que busca directamente la completitud sin recurrir al metateorema de la deducción.

En primer lugar, tenemos esquemas axiomáticos diseñados para demostrar de manera eficiente el subconjunto de tautologías que contienen solo una variable proposicional .

aa 1: ꞈ A → A
aa 2: ( A → B )→ꞈ( A →( C → B ))
aa 3: A →(( B → C )→ꞈ(( A → B )→ C ))
aa 4: A →ꞈ( B → A )

La demostración de cada tautología comenzaría con dos partes idénticas (hipótesis y conclusión). Luego, se insertarían hipótesis adicionales entre ellas. Posteriormente, se insertarían hipótesis tautológicas adicionales (que son verdaderas incluso cuando la única variable es falsa) en la hipótesis original. Finalmente, se añadirían más hipótesis fuera (a la izquierda). Este procedimiento permitirá obtener rápidamente cualquier tautología que contenga una sola variable. (El símbolo "ꞈ" en cada esquema axiomático indica dónde comienza la conclusión utilizada en la demostración de completitud. Es simplemente un comentario, no forma parte de la fórmula).

Consideremos cualquier fórmula Φ que pueda contener A , B , C1 , ..., _Cn y que termine con _Acomo su conclusión final. Entonces tomamos

aa 5: Φ ₋ →( Φ ₊ →ꞈ Φ )

como un esquema axiomático donde Φ ₋ es el resultado de reemplazar B por A en todo Φ y Φ ₊ es el resultado de reemplazar B por ( A → A ) en todo Φ . Este es un esquema para esquemas axiomáticos ya que hay dos niveles de sustitución: en el primero Φ se sustituye (con variaciones); en el segundo, cualquiera de las variables (incluyendo tanto A como B ) puede ser reemplazada por fórmulas arbitrarias del cálculo proposicional implicacional. Este esquema permite probar tautologías con más de una variable al considerar el caso cuando B es falso Φ ₋ y el caso cuando B es verdadero Φ ₊ .

Si la variable que constituye la conclusión final de una fórmula toma el valor verdadero, entonces toda la fórmula toma el valor verdadero independientemente de los valores de las demás variables. Por consiguiente, si A es verdadero, entonces Φ, Φ⁻, Φ⁺ y Φ⁻ → ( _Φ⁺ → Φ ) _son todos verdaderos _.Así pues, _sinpérdida de generalidad , podemos suponer que A es falso. Nótese que Φ es una tautología si y solo si tanto Φ⁻ como Φ⁺ son tautologías. Pero mientras que Φ tiene n + 2 variables distintas, Φ⁻ y Φ⁺ tienen _ambas n + 1. Por lo _tanto , la _cuestión de _si una fórmula es una tautología se ha reducido a la cuestión de si ciertas fórmulas con una variable cada una son todas tautologías. También observe que Φ ₋ →( Φ ₊ → Φ ) es una tautología independientemente de si Φ es falso, porque si Φ es falso, entonces Φ ₋ o Φ ₊ serán falsos dependiendo de si B es falso o verdadero.

Ejemplos:

Derivación de la ley de Peirce

[(( P → P )→ P )→ P ]→([(( P →( P → P ))→ P )→ P ]→[(( P → Q )→ P )→ P ]) aa 5
P → P aa 1
( P → P )→(( P → P )→((( P → P )→ P )→ P )) aa 3
( P → P ) → ((( P → P ) → P ) → P ) pf 2,3
(( P → P )→ P )→ P pf 2,4
[(( P →( P → P ))→ P )→ P ]→[(( P → Q )→ P )→ P ] pf 5,1
P →( P → P ) aa 4
( P →( P → P ))→(( P → P )→((( P →( P → P ))→ P )→ P )) aa 3
( P → P ) → ((( P → ( P → P )) → P ) → P ) pf 7,8
(( P →( P → P ))→ P )→ P pf 2,9
(( P → Q )→ P )→ P mp 10,6 qed

Derivando el único axioma de Łukasiewicz

[(( P → Q )→ P )→(( P → P )→( S → P ))]→([(( P → Q )→( P → P ))→((( P → P )→ P )→( S → P ))]→[(( P → Q )→ R )→(( R → P )→( S → P ))]) aa 5
[(( P → P )→ P )→(( P → P )→( S → P ))]→([(( P →( P → P ))→ P )→(( P → P )→( S → P ))]→[(( P → Q )→ P )→(( P → P )→( S → P ))]) aa 5
P →( S → P ) aa 4
( P →( S → P ))→( P →(( P → P )→( S → P ))) aa 2
P →(( P → P )→( S → P )) pf 3,4
P → P aa 1
( P → P )→(( P →(( P → P )→( S → P )))→[(( P → P )→ P )→(( P → P )→( S → P ))]) aa 3
( P →(( P → P )→( S → P )))→[(( P → P )→ P )→(( P → P )→( S → P ))] pf 6,7
(( P → P )→ P )→(( P → P )→( S → P )) pf 5,8
[(( P →( P → P ))→ P )→(( P → P )→( S → P ))]→[(( P → Q )→ P )→(( P → P )→( S → P ))] mp 9,2
P →( P → P ) aa 4
( P →( P → P ))→(( P →(( P → P )→( S → P )))→[(( P →( P → P ))→ P )→(( P → P )→( S → P ))]) aa 3
( P →(( P → P )→( S → P )))→[( P →( P → P ))→ P )→(( P → P )→( S → P ))] mp 11,12
(( P →( P → P ))→ P )→(( P → P )→( S → P )) pf 5,13
(( P → Q )→ P )→(( P → P )→( S → P )) pf 14,10
[(( P → Q )→( P → P ))→((( P → P )→ P )→( S → P ))]→[(( P → Q )→ R )→(( R → P )→( S → P ))] pf 15,1
( P → P )→(( P →( S → P ))→[(( P → P )→ P )→( S → P )]) aa 3
( P →( S → P ))→[(( P → P )→ P )→( S → P )] pf 6,17
(( P → P ) → P ) → ( S → P ) pf 3,18
((( P → P )→ P )→( S → P ))→[(( P → Q )→( P → P ))→((( P → P )→ P )→( S → P ))] aa 4
(( P → Q ) → ( P → P )) → ((( P → P ) → P ) → ( S → P )) pf 19,20
(( P → Q )→ R )→(( R → P )→( S → P )) mp 21,16 qed

Utilizar una tabla de verdad para verificar el único axioma de Łukasiewicz requeriría considerar 16 = 2⁴ ^casos , ya que contiene 4 variables distintas. En esta derivación, pudimos restringir la consideración a solo 3 casos: R es falso y Q es falso, R es falso y Q es verdadero, y R es verdadero. Sin embargo, debido a que estamos trabajando dentro del sistema formal de la lógica (en lugar de fuera de él, de manera informal), cada caso requirió mucho más esfuerzo.

Véase también

Referencias

↑ Francola, John; Goldsmith, Judy; Schlipf, John; Speckenmeyer, Ewald; Swaminathan, RP (1999). "Un algoritmo para la clase de fórmulas implicacionales puras" . Matemáticas Aplicadas Discretas . 96–97 : 89–106 . doi : 10.1016/S0166-218X(99)00038-4 .
↑ Łukasiewicz, Jan (1948) El axioma más corto del cálculo implicacional de proposiciones , Proc. Royal Irish Academy, vol. 52, sec. A, no. 3, pp. 25–33.
↑ Heusch, Peter (1999). "La complejidad del problema de la falsabilidad para fórmulas puramente implicacionales" . Matemáticas Aplicadas Discretas . 96–97 : 127–138 . doi : 10.1016/S0166-218X(99)00036-0 .

Lecturas adicionales

Mendelson, Elliot (1997) Introducción a la lógica matemática , 4.ª ed. Londres: Chapman & Hall.

[1] Francola, John; Goldsmith, Judy; Schlipf, John; Speckenmeyer, Ewald; Swaminathan, RP (1999). "Un algoritmo para la clase de fórmulas implicacionales puras" . Matemáticas Aplicadas Discretas . 96–97 : 89–106 . doi : 10.1016/S0166-218X(99)00038-4 .

[2] Łukasiewicz, Jan (1948) El axioma más corto del cálculo implicacional de proposiciones , Proc. Royal Irish Academy, vol. 52, sec. A, no. 3, pp. 25–33.

[3] Heusch, Peter (1999). "La complejidad del problema de la falsabilidad para fórmulas puramente implicacionales" . Matemáticas Aplicadas Discretas . 96–97 : 127–138 . doi : 10.1016/S0166-218X(99)00036-0 .

[ 1 ]

[ 2 ]

[ 3 ]