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 mediante “implica”, “si..., entonces...”, “→”, “ ”, etc. ${\displaystyle \rightarrow }$

Incompletitud 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 es funcionalmente completa.

Sin embargo, si se añade un conectivo nulario ⊥ para falsedad, entonces se pueden definir todas las demás funciones de verdad. Las fórmulas sobre el conjunto resultante de conectivos {→, ⊥} 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 ) → ⊥)) → ⊥

Como 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 de axiomas

Las siguientes afirmaciones se consideran tautologías (irreducibles 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 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.

Donde en cada caso, P , Q y R pueden ser reemplazadas 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 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 solo esquema

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

También argumentó que no existe un sistema de axiomas 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 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 utilizan sólo 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 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 bivalente 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 presenta 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 especial con Γ vacío, es decir, sólo necesitamos demostrar que toda 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 ciertas condiciones, uno puede usarlos como sustitutos para decir que A* es falso o A* es verdadero respectivamente.

Primero observemos 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) a partir del Axioma 2.

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

Si además suponemos que 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 ). 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 → 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 por la hipótesis de inducción, podemos inferir (( B → C ) → F ) → F .

2. e ( B ) = 0. Entonces 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 por 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 por 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}$

Sea ahora F una tautología en las 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 deduce 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 ) se cumple para k + 1, lo demostraremos 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 estableciendo 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 se quería demostrar.

Esta prueba es constructiva, es decir, dada una tautología, se podrían seguir las instrucciones y crear una prueba de ella 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, excepto para las más cortas.

El sistema de axiomas de Bernays-Tarski

El sistema de axiomas de Bernays-Tarski se utiliza a menudo. En particular, el artículo de Łukasiewicz deriva los axiomas de Bernays-Tarski a partir del único axioma de Łukasiewicz como un medio para mostrar su completitud.
Se diferencia de los esquemas axiomáticos anteriores al reemplazar el esquema axiomático 2, ( P →( Q → R ))→(( P → Q )→( P → R )), por

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

Lo que se denomina 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 axiomático 2 para obtener el metateorema.

1. P →( Q → R ) dado
2. P → Q dado
3. ( P → Q )→(( Q → R )→( P → R )) ax2'
4. ( Q → R ) → ( P → R ) pf 2,3
5. ( P →( Q → R ))→((( Q → R )→( P → R ))→( P →( P → R ))) ax 2'
6. (( Q → R )→( P → R ))→( P →( P → R )) pf 1,5
7. P →( P → R ) punto de fusión 4,6
8. ( P →( P → R ))→((( P → R )→ R )→( P → R )) ax 2'
9. (( P → R )→ R )→( P → R ) pf 7,8
10. ((( P → R )→ R )→( P → R ))→( P → R ) ax 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 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 tiene éxito, entonces no se trata de una tautología. Si se fracasa, 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.

Como 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.

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

C → A es falso, luego C es verdadero.

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

Resumiendo, la valoración que establece que B , C y D sean verdaderos y que A , E y F sean falsos hará que [( A → B )→(( C → A )→ E )]→([ F →(( C → D )→ E )]→[( A → F )→( D → E )]) sea falso. 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.

Como A es falso, A → B es verdadero. Por lo tanto, C es verdadero. Por lo tanto, A debe ser verdadero, lo que contradice el hecho de que es falso.

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

Añadiendo un esquema de axioma

¿Qué ocurriría si se añadiera otro esquema axiomático a los que se han enumerado 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 puede ser posible encontrar demostraciones de teoremas 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 seguirá habiendo teoremas que no se puedan demostrar en n o menos pasos.

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 un límite superior en la longitud mínima de una prueba de cada fórmula, porque hay un método común para probar 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 una tautología. Pero [(( A →( A → A ))→( A → A ))→ A ]→ A es una tautología y, por lo tanto, un teorema debido a los viejos axiomas (usando el resultado de completitud anterior). Aplicando modus ponens, obtenemos que A es un teorema del sistema extendido. Entonces, todo lo que hay que hacer para demostrar cualquier fórmula es reemplazar A por la fórmula deseada a lo largo de 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 completitud. Aquí hay otro sistema de axiomas que apunta directamente a la completitud sin pasar por el metateorema de deducción.

Primero tenemos esquemas axiomáticos que están diseñados para probar eficientemente 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 se insertarían hipótesis adicionales entre ellas. Luego se insertarían hipótesis tautológicas adicionales (que son verdaderas incluso cuando la única variable es falsa) en la hipótesis original. Luego se agregarían más hipótesis en el exterior (a la izquierda). Este procedimiento dará rápidamente todas las tautologías que contienen solo una variable. (El símbolo "ꞈ" en cada esquema axiomático indica dónde comienza la conclusión utilizada en la prueba de completitud. Es simplemente un comentario, no una parte de la fórmula).

Consideremos cualquier fórmula Φ que pueda contener A , B , C ₁ , ..., C _n y que termine con A como su conclusión final. Luego 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 A y 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 considerando el caso cuando B es falso Φ ₋ y el caso cuando 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. Por lo tanto, sin pérdida de generalidad, podemos suponer que A es falsa. 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. Observe también que Φ ₋ →(Φ ₊ →Φ) es una tautología independientemente de si Φ lo es, 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

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 )) mp 21,16 qed

El uso de una tabla de verdad para verificar el único axioma de Łukasiewicz requeriría la consideración de 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, como estamos trabajando dentro del sistema formal de lógica (en lugar de fuera de él, informalmente), cada caso requirió mucho más esfuerzo.

Véase 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)
• Tabla de verdad
• Valoración (lógica)

Referencias

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, págs. 25–33.
3. Heusch, Peter (1999). "La complejidad del problema de falsabilidad para fórmulas implicacionales puras". Matemáticas Aplicadas Discretas . 96–97: 127–138. doi : 10.1016/S0166-218X(99)00036-0 .

Lectura adicional

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