¿Existe algún sistema deductivo finito para la lógica proposicional que sólo utilice reglas unarias?

Question

No estoy seguro de si esto se ha demostrado/desmentido alguna vez, pero, asumiendo la gramática habitual de la lógica proposicional, ¿existe algún sistema deductivo que derive exactamente las tautologías de la lógica clásica utilizando sólo un número finito de reglas unarias y esquemas axiomáticos? Esto equivaldría, por supuesto, a demostrar una afirmación similar para los tipos habituales de lógica intuicionista, mínima o incluso subminimal.

Por regla unaria entiendo dos fórmulas proposicionales (premisa y conclusión) construidas a partir de variables y las conectivas habituales.

Es necesario asumir implícitamente un concepto de sustitución así como las reglas sintácticas. La restricción a las reglas unarias prohíbe explícitamente el uso de reglas binarias como el modus ponens o la introducción de la conjunción habitual, ya que sus premisas consisten tanto en una implicación como en su antecedente.

No creo que exista tal sistema, simplemente porque no se me ocurre ningún "patrón" real en las implicaciones verdaderas que se aplique en tal caso. ¿Se ha demostrado alguna afirmación similar o existe alguna aproximación razonablemente difícil a tales cuestiones?

Answer 1

Existe un sistema deductivo que deriva exactamente las tautologías de la lógica proposicional clásica utilizando un número finito de reglas y esquemas axiomáticos at-most-unary.

Limitaremos nuestra atención a la lógica proposicional clásica dada por las dos conectivas $\neg, \rightarrow$ donde las otras conectivas se definen como abreviaturas, como es habitual en los cálculos de estilo Hilbert (además, una estrategia casi idéntica funcionaría incluso si diéramos las otras conectivas explícitamente). Abreviamos $\neg (A \rightarrow \neg B)$ como $A \wedge B$ . Para la gestión de paréntesis escribimos $\wedge$ y $\rightarrow$ como derecho-asociativo, de modo que $A \wedge B \wedge C$ denota $A \wedge (B \wedge C)$ , mientras que $A \rightarrow B \rightarrow C$ denota $A \rightarrow (B \rightarrow C)$ .

---

Consideremos el sistema deductivo (llamado "nuestro sistema" de aquí en adelante) que tiene las siguientes reglas de inferencia (nulas y unarias).

Reglas del axioma

Llamamos axioma lógico a una fórmula que aparece como instancia de sustitución de una de las siguientes: $P \rightarrow (Q \rightarrow P), (P \rightarrow Q \rightarrow R) \rightarrow (P \rightarrow Q) \rightarrow P \rightarrow R, (\neg Q \rightarrow \neg P) \rightarrow P \rightarrow Q$ . Sea $\varphi$ denotan un axioma lógico. Admitimos las siguientes reglas de inferencia:

1. Inferir $\varphi$ .
2. Desde $C$ infiere $\varphi \wedge C$ .
3. Desde $C$ infiere $C \wedge \varphi \wedge \varphi$ .

Reglas del modus ponens

1. Desde $C \wedge D \wedge (A \wedge (A \rightarrow B) \wedge E)$ infiere $C \wedge D \wedge (A \wedge (A \rightarrow B) \wedge B \wedge E)$ .
2. Desde $C \wedge D \wedge ((A \rightarrow B) \wedge A \wedge E)$ infiere $C \wedge D \wedge ((A \rightarrow B) \wedge A \wedge B \wedge E)$ .

Normas de maniobra

1. Desde $(A \wedge C) \wedge D \wedge E$ infiere $C \wedge (A \wedge D) \wedge E$ .
2. Desde $(A \wedge C) \wedge D \wedge E$ infiere $C \wedge D \wedge (A \wedge E)$ .
3. Desde $C \wedge (A \wedge D) \wedge E$ infiere $(A \wedge C) \wedge D \wedge E$ .
4. Desde $C \wedge D \wedge (A \wedge E)$ infiere $(A \wedge C) \wedge D \wedge E$ .

Eliminación de la conjunción

1. Desde $A \wedge B$ infiere $A$ .

---

Nuestro sistema satisface claramente la solidez de la lógica clásica proposicional. También satisface la completitud: lo demostramos reduciendo la completitud de nuestro sistema a la del cálculo de pruebas de Hilbert.

Lema. Dada una derivación de longitud $n$ ,

• {1) $Q_1$
• (2) $Q_2$
• (3) $\dots$
• (n) $Q_n$

en el cálculo de Hilbert, podemos encontrar una derivación de $Q_n \wedge \dots \wedge Q_2 \wedge Q_1$ en nuestro sistema.

Prueba. Por inducción en la longitud de la derivación del cálculo de Hilbert $\delta$ . Si la derivación tiene longitud 1, entonces $Q_1$ es una instancia de sustitución de un axioma $\varphi$ por lo que podemos utilizar la primera regla axiomática de nuestro sistema para demostrar $Q_1$ . A partir de aquí supongamos que la derivación tiene una longitud $n+1$ . Por hipótesis de inducción, nuestro sistema tiene una derivación de $Q_n \wedge \dots \wedge Q_1$ . Tenemos que considerar dos casos.

Caso 1: La última regla de la derivación $\delta$ es una regla axiomática del sistema de Hilbert. En este caso $Q_{n+1}$ es una instancia de sustitución de un axioma, y de $Q_n \wedge \dots \wedge Q_1$ podemos deducir $Q_{n+1} \wedge Q_n \wedge \dots \wedge Q_1$ utilizando la segunda regla del axioma de nuestro sistema.

Caso 2: La última regla de la derivación $\delta$ es una regla de modus ponens del sistema de Hilbert, que infiere $Q_{n+1}$ de $Q_k$ y $Q_\ell$ (por ejemplo, asumir $k > \ell > 1$ ). Tome su axioma favorito $\varphi$ , entonces argumenta en nuestro sistema lo siguiente:

1. Tenga $Q_n \wedge \dots \wedge Q_1$ por hipótesis de inducción.
2. Inferir $(Q_n \wedge \dots \wedge Q_1) \wedge \varphi \wedge \varphi$ utilizando la regla del tercer axioma.
3. Inferir $(Q_k \wedge \dots \wedge Q_1) \wedge (Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge \varphi$ utilizando repetidamente la primera regla de derivación.
4. Inferir $(Q_{k-1} \wedge \dots \wedge Q_1) \wedge (Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge (Q_k \wedge \varphi)$ utilizando la segunda regla de derivación.
5. Inferir $(Q_\ell \wedge \dots \wedge Q_1) \wedge (Q_{\ell + 1} \wedge \dots \wedge Q_{k-1} \wedge Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge (Q_k \wedge \varphi)$ utilizando repetidamente la primera regla de derivación.
6. Inferir $(Q_{\ell-1} \wedge \dots \wedge Q_1) \wedge (Q_{\ell + 1} \wedge \dots \wedge Q_{k-1} \wedge Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge (Q_\ell \wedge Q_k \wedge \varphi)$ utilizando la segunda regla de derivación.
7. Inferir $(Q_{\ell-1} \wedge \dots \wedge Q_1) \wedge (Q_{\ell + 1} \wedge \dots \wedge Q_{k-1} \wedge Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge (Q_\ell \wedge Q_k \wedge Q_{n+1} \wedge \varphi)$ utilizando la regla de modus ponens correspondiente.
8. Inferir $(Q_{\ell} \wedge \dots \wedge Q_1) \wedge (Q_{\ell + 1} \wedge \dots \wedge Q_{k-1} \wedge Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge (Q_k \wedge Q_{n+1} \wedge \varphi)$ utilizando la cuarta regla de derivación.
9. Inferir $(Q_{k-1} \wedge \dots \wedge Q_1) \wedge (Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge (Q_k \wedge Q_{n+1} \wedge \varphi)$ utilizando repetidamente la tercera regla de derivación.
10. Inferir $(Q_{k} \wedge \dots \wedge Q_1) \wedge (Q_{k+1} \wedge \dots \wedge Q_n \wedge \varphi) \wedge (Q_{n+1} \wedge \varphi)$ utilizando la cuarta regla de derivación.
11. Inferir $(Q_{n} \wedge \dots \wedge Q_1) \wedge \varphi \wedge (Q_{n+1} \wedge \varphi)$ utilizando repetidamente la tercera regla de derivación.
12. Inferir $(Q_{n+1} \wedge \dots \wedge Q_1) \wedge \varphi \wedge \varphi$ utilizando la cuarta regla de derivación.
13. Inferir $Q_{n+1} \wedge \dots \wedge Q_1$ utilizando la eliminación de la conjunción.

Qed.

Como corolario, obtenemos la completitud para nuestro sistema.

Prueba. Tomemos una tautología clásica $P$ . Por completitud para el cálculo de Hilbert, podemos encontrar una derivación $\delta$ de $P$ en el cálculo de Hilbert. Por nuestro lema anterior, podemos encontrar una derivación de $P \wedge Q_n \wedge \dots \wedge Q_1$ para algunos $n \in \mathbb{N}$ en nuestro sistema. Usando la eliminación de la conjunción, podemos inferir $P$ en nuestro sistema. Qed.

Answer 2

Si se permiten reglas de equivalencia, entonces sí.

Podrías tener una regla de inferencia que infiera una tautología de la nada (por ejemplo, la Ley del Medio Excluyente): $\vdash \phi \lor \neg \phi$ ), y aparte de eso utilizar las reglas de equivalencia como reglas de inferencia. Como sabemos que un conjunto relativamente pequeño de reglas de equivalencia puede transformar cualquier enunciado en cualquier enunciado equivalente, esa tautología de partida puede transformarse en cualquier otra tautología.