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 sólo un conectivo , llamado implicación o condicional . En las fórmulas , esta operación binaria se indica con "implica", "si..., entonces...", "→", " ", etc. ${\displaystyle \rightarrow }$

(in)completitud funcional

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

Por ejemplo, la función de verdad de dos lugares 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 está funcionalmente completo.

Sin embargo, si se agrega un conectivo nular ⊥ para la falsedad, entonces se pueden definir todas las demás funciones de verdad. Las fórmulas sobre el conjunto resultante de conectivos {→, ⊥} se denominan f-implicativas . ^[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 se puede expresar en términos de → y ⊥.

sistema de axiomas

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 de axioma 2 es ( P → ( Q → R )) → (( P → Q ) → ( P → R )).
• El esquema de axioma 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 .

Donde en cada caso, P , Q y R pueden reemplazarse por cualquier fórmula que contenga solo "→" como conectivo. Si Γ es un conjunto de fórmulas y A una fórmula, entonces significa que A es derivable usando los axiomas y reglas anteriores y las fórmulas de Γ como hipótesis adicionales. ${\displaystyle \Gamma \vdash A}$

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

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

También argumentó que no existe un sistema de axiomas más corto.

Propiedades básicas de la derivación.

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

si entonces ${\displaystyle \Gamma \vdash A,}$ ${\displaystyle \sigma (\Gamma )\vdash \sigma (A),}$

donde σ es cualquier sustitución (de fórmulas que usan solo implicación).

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

Si entonces ${\displaystyle \Gamma ,A\vdash B}$ ${\displaystyle \Gamma \vdash A\to B.}$

Como se explica en el artículo sobre el teorema de deducción , esto es válido para cualquier extensión axiomática del sistema que contenga los esquemas de axiomas 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 habitual de la lógica proposicional clásica. Es decir, si Γ es un conjunto de fórmulas implicacionales y A es una fórmula implicacional implicada por Γ, entonces . ${\displaystyle \Gamma \vdash A}$

Prueba

A continuación se describe una prueba del teorema de completitud. Primero, usando el teorema de compacidad y el teorema de deducción, podemos reducir el teorema de completitud a su caso especial con Γ vacío, es decir, sólo necesitamos demostrar que cada tautología es derivable en el sistema.

La prueba 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 → F es equivalente a (¬ A* ) ∨ 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 → F ) → F es equivalente a A* ∨ F . Entonces, bajo algunas condiciones, uno puede usarlos como sustitutos de decir que A* es falso o A* es verdadero, respectivamente.

Primero observamos algunos hechos básicos sobre la derivabilidad:

De hecho, podemos derivar A → ( B → C ) usando el axioma 1, y luego derivar A → C mediante modus ponens (dos veces) de Ax. 2.

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

Si asumimos además C → B , podemos derivar A → B usando ( 1 ), luego derivamos C por modus ponens. Esto muestra y el teorema de deducción da . Aplicamos Ax. 3 para obtener ( 3 ). ${\displaystyle A\to C,(A\to B)\to C,C\to B\vdash C}$ ${\displaystyle A\to C,(A\to B)\to C\vdash (C\to B)\to C}$

Sea F una fórmula fija arbitraria. Para cualquier fórmula A , definimos A ⁰ = ( A → F ) y A ¹ = (( A → F ) → F ). Considere sólo 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 ,

Probamos ( 4 ) por inducción en A. El caso base A = p _i es trivial. Sea A = ( B → C ). Distinguimos tres casos:

1. e ( C ) = 1. Entonces también e ( A ) = 1. Tenemos

   ${\displaystyle (C\to F)\to F\vdash ((B\to C)\to F)\to F}$

   aplicando ( 2 ) dos veces al axioma C → ( B → C ). Como hemos derivado ( C → F ) → F mediante la hipótesis de inducción, podemos inferir (( B → C ) → F ) → F .

2. e ( B ) = 0. Luego nuevamente e ( A ) = 1. El teorema de deducción aplicado a ( 3 ) da

   ${\displaystyle B\to F\vdash ((B\to C)\to F)\to F.}$

   Como hemos derivado B → F mediante la hipótesis de inducción, podemos inferir (( B → C ) → F ) → F .

3. e ( B ) = 1 y e ( C ) = 0. Entonces e ( A ) = 0. Tenemos

   ${\displaystyle {\begin{aligned}(B\to F)\to F,C\to F,B\to C&\vdash B\to F&&{\text{by (1)}}\\&\vdash F&&{\text{by modus ponens,}}\end{aligned}}}$

   así por el teorema de deducción. Hemos derivado ( B → F ) → F y C → F mediante la hipótesis de inducción, por lo que podemos inferir ( B → C ) → F . Esto completa la prueba de ( 4 ). ${\displaystyle (B\to F)\to F,C\to F\vdash (B\to C)\to F}$

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

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

${\displaystyle 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 ) es válido para k + 1, lo mostraremos para k . Aplicando el teorema de deducción a la hipótesis de inducción, obtenemos

${\displaystyle {\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}}}$

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

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

Esta prueba es constructiva. Es decir, dada una tautología, uno podría seguir las instrucciones y crear una prueba a partir de los axiomas. Sin embargo, la longitud de dicha prueba aumenta exponencialmente con el número de variables proposicionales en la tautología, por lo que no es un método práctico para ninguna tautología que no sea la más corta.

El sistema de axiomas de Bernays-Tarski

A menudo se utiliza el sistema del axioma de Bernays-Tarski. En particular, el artículo de Łukasiewicz deriva los axiomas de Bernays-Tarski del único axioma de Łukasiewicz como medio para mostrar su integridad.
Se diferencia de los esquemas de axioma 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 llama silogismo hipotético . Esto hace que la derivación del metateorema de deducción sea un poco más difícil, pero aún se puede hacer.

Demostramos que de P →( Q → R ) y P → Q se puede derivar P → R . Este hecho se puede utilizar en lugar del esquema de axioma 2 para obtener el metateorema.

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

Satisfacción y validez

La satisfacibilidad en el cálculo proposicional implicacional es trivial, porque cada fórmula es satisfacible: simplemente establezca todas las variables en verdaderas.

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

En este caso, una técnica útil es suponer que la fórmula no es una tautología e intentar encontrar una valoración que la haga falsa. Si uno tiene éxito, entonces no se trata de una tautología. Si uno falla, entonces es una tautología.

Ejemplo de 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 cierto; F →(( C → D )→ E ) es verdadero; A → F es verdadero; D es verdadero; y E es falso.

Como D es verdadero, C → D es verdadero. Entonces 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.

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

C → A es falso, entonces C es verdadero.

El valor de B no importa, por lo que podemos elegir arbitrariamente que sea verdadero.

En resumen, la valoración que establece que B , C y D son verdaderas y A , E y F falsas hará que [( A → B )→(( C → A )→ E )]→([ F →(( C → D )→ E )]→[( A → F )→( D → E )]) falso. Entonces 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 falsa.

Como A es falso, A → B es verdadero. Entonces C es verdadera. Por tanto, A debe ser verdadera, contradiciendo el hecho de que es falsa.

Por lo tanto, no existe ninguna valoración que haga que (( A → B )→ C )→(( C → A )→( D → A )) sea falso. En consecuencia, es una tautología.

Agregar un esquema de axioma

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

Si es una tautología, entonces el conjunto de teoremas sigue siendo el conjunto de tautologías como antes. Sin embargo, en algunos casos es posible encontrar demostraciones de teoremas significativamente más breves. Sin embargo, la duración mínima de las demostraciones de teoremas seguirá siendo ilimitada, es decir, para cualquier número natural n todavía habrá teoremas que no se pueden demostrar en n o menos pasos.

Si el nuevo esquema de axioma 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, existe un límite superior en la longitud mínima de una demostración de cada fórmula, porque existe un método común para demostrar cada fórmula. Por ejemplo, supongamos que el nuevo esquema de axioma fuera (( B → C )→ C )→ B . Entonces (( A →( A → A ))→( A → A ))→ A es una instancia (uno de los nuevos axiomas) y tampoco una tautología. Pero [(( A →( A → A ))→( A → A ))→ A ]→ A es una tautología y, por tanto, un teorema debido a los antiguos axiomas (utilizando el resultado de completitud anterior). Aplicando modus ponens, obtenemos que A es un teorema del sistema extendido. Entonces todo lo que uno tiene que hacer para probar cualquier fórmula es reemplazar A por la fórmula deseada durante toda la prueba de A. Esta prueba tendrá el mismo número de pasos que la prueba de A.

Una axiomatización alternativa

Los axiomas enumerados anteriormente funcionan principalmente a través del metateorema de deducción para llegar a la integridad. Aquí hay otro sistema de axiomas que apunta directamente a la completitud sin pasar por el metateorema de deducción.

Primero, tenemos esquemas de axiomas que están diseñados para probar 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 prueba de cada una de estas tautologías comenzaría con dos partes (hipótesis y conclusión) que son iguales. Luego inserte hipótesis adicionales entre ellas. Luego inserte hipótesis tautológicas adicionales (que son verdaderas incluso cuando la única variable es falsa) en la hipótesis original. Luego agregue más hipótesis afuera (a la izquierda). Este procedimiento dará rápidamente todas las tautologías que contengan una sola variable. (El símbolo "ꞈ" en cada esquema de axioma indica dónde comienza la conclusión utilizada en la prueba de completitud. Es simplemente un comentario, no una parte de la fórmula).

Considere cualquier fórmula Φ que pueda contener A , B , C ₁ , ..., C _n y termine con A como conclusión final. entonces tomamos

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

como un esquema de axioma donde Φ ₋ es el resultado de reemplazar B por A en Φ y Φ ₊ es el resultado de reemplazar B por ( A → A ) en Φ. 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 (incluidas A y B ) puede sustituirse por fórmulas arbitrarias del cálculo proposicional implicacional. Este esquema permite probar tautologías con más de una variable considerando el caso en que B es falso Φ ₋ y el caso en que B es verdadero Φ ₊ .

Si la variable que es 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 otras variables. En consecuencia, si A es verdadera, entonces Φ, Φ ₋ , Φ ₊ y Φ ₋ →(Φ ₊ →Φ) son todas verdaderas. Entonces, sin pérdida de generalidad, podemos suponer que A es falso. Observe que Φ es una tautología si y sólo si tanto Φ ₋ como Φ ₊ son tautologías. Pero mientras Φ tiene n +2 variables distintas, Φ ₋ y Φ ₊ tienen n +1. Así pues, 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. Observe también que Φ ₋ →(Φ ₊ →Φ) es una tautología independientemente de si Φ lo es, porque si Φ es falso entonces Φ ₋ o Φ ₊ será falso dependiendo de si B es falso o verdadero.

Ejemplos:

Derivando la ley de Peirce

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

Derivando el único axioma de Łukasiewicz

1. [(( 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
2. [(( P → P )→ P )→(( P → P )→( S → P ))]→([(( P →( P → P ))→ P )→(( P → P )→( S → P ))]→[(( P → Q )→ P )→(( P → P )→( S → P ))]) aa 5
3. P →( S → P ) aa 4
4. ( P →( S → P ))→( P →(( P → P )→( S → P ))) aa 2
5. P →(( P → P )→( S → P )) pf 3,4
6. P → P aa 1
7. ( P → P )→(( P →(( P → P )→( S → P )))→[(( P → P )→ P )→(( P → P )→( S → P ))] ) aa 3
8. ( P →(( P → P )→( S → P )))→[(( P → P )→ P )→(( P → P )→( S → P ))] pf 6,7
9. (( P → P )→ P )→(( P → P )→( S → P )) pf 5,8
10. [(( P →( P → P ))→ P )→(( P → P )→( S → P ))]→[(( P → Q )→ P )→(( P → P )→( S → P ))] pf 9,2
11. P →( P → P ) aa 4
12. ( P →( P → P ))→(( P →(( P → P )→( S → P )))→[(( P →( P → P ))→ P )→(( P → P ) →( S → P ))]) aa 3
13. ( P →(( P → P )→( S → P )))→[(( P →( P → P ))→ P )→(( P → P )→( S → P ))] pf 11, 12
14. (( P →( P → P ))→ P )→(( P → P )→( S → P )) pf 5,13
15. (( P → Q )→ P )→(( P → P )→( S → P )) pf 14,10
16. [(( P → Q )→( P → P ))→((( P → P )→ P )→( S → P ))]→[(( P → Q )→ R )→(( R → P )→( S → P ))] pf 15,1
17. ( P → P )→(( P →( S → P ))→[(( P → P )→ P )→( S → P )]) aa 3
18. ( P →( S → P ))→[(( P → P )→ P )→( S → P )] pf 6,17
19. (( P → P ) → P ) → ( S → P ) pf 3,18
20. ((( P → P )→ P )→( S → P ))→[(( P → Q )→( P → P ))→((( P → P )→ P )→( S → P )) ] aa 4
21. (( P → Q ) → ( P → P )) → ((( P → P ) → P ) → ( S → P )) pf 19,20
22. (( P → Q )→ R )→(( R → P )→( S → P )) pf 21,16 qed

Usar 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 trabajamos dentro del sistema formal de lógica (en lugar de fuera de él, de manera informal), cada caso requirió mucho más esfuerzo.

Ver también

• Teorema de deducción
• Lista de sistemas lógicos § Cálculo proposicional implicacional
• ley de peirce
• Cálculo proposicional
• Tautología (lógica)
• Mesa de la verdad
• Valoración (lógica)

Referencias

• Mendelson, Elliot (1997) Introducción a la lógica matemática, 4ª ed. Londres: Chapman & Hall.
• Łukasiewicz, Jan (1948) El axioma más corto del cálculo implicacional de proposiciones, Proc. Real Academia Irlandesa, vol. 52, sec. R, no. 3, págs. 25–33.

1. Francola, Juan; Orfebre, Judy; Schlipf, Juan; Speckenmeyer, Ewald; Swaminathan, RP (1999). "Un algoritmo para la clase de fórmulas implicacionales puras". Matemática Aplicada Discreta . 96–97: 89–106. doi : 10.1016/S0166-218X(99)00038-4 .
2. Heusch, Peter (1999). "La complejidad del problema de falsabilidad de fórmulas implicacionales puras". Matemática Aplicada Discreta . 96–97: 127–138. doi : 10.1016/S0166-218X(99)00036-0 .