Cálculo de Proposiciones Clásico de Gentzen • Conectivos primitivos: , , , ,

• Reglas de Deducción:

– Modus Ponens

– Sustitución

• Axiomas

G1:

G2:

G3:

G4:

G5:

G6:

G7

G8:

G9:

G10: x

G11:

G12:

G13:

CPC de Hilbert-Ackermann Lista de Conectivos

El sistema completo de conectivos es { , }. Los conectivos , y son abreviaturas.

Axiomas

(HA)1: ⊢

(HA)2: ⊢

(HA)3: ⊢

(HA)4: ⊢

Reglas de Deducción

i) Modus Ponens: Si A es un teorema y A B es teorema, entonces B es teorema.

ii) Regla de Sustitución: Si A es un teorema en el que aparece la letra x, entonces al sustituir dicha x

(en cada ocurrencia) por una fórmula B (no necesariamente teorema), se obtiene una fórmula A’

que es teorema.

Notación:

Teorema 1: ⊢

Teorema 2 (Silogismo hipotético) ⊢

Teorema 3 (Principio del tercio excluido) ⊢

Teorema 4: ⊢

Reglas Derivadas

Regla S: Sean A,B,C fórmulas. De ⊢ y ⊢ , se deduce que ⊢ .

Regla I:

De ⊢ (A A), se deduce ⊢ A.

Regla II:

De ⊢ A, se deduce ⊢ A B, para cualquier fórmula

B.

Regla III:

De ⊢ (A B), se deduce ⊢ (B A).

Regla IV:

De ⊢ (A B), se deduce ⊢ C A C B.

Regla V:

De ⊢ (A B), se deduce ⊢ ( A B).

De ⊢ ( A B), se deduce ⊢ (A B).

Regla VI:

De ⊢ A y ⊢ B, se deduce ⊢ A B.

Regla VII

De ⊢ (A C) y ⊢ (B C), se deduce ⊢ (A B) C

TAREA

Ejercicio ):

Previo al inicio del ejercicio, debe investigarse el procedimiento para comprobar la independencia de un

conjunto de axiomas.

1. Demostrar la teoría de -Ackermann es equivalente a la teoría de Gentzen (i.e. HA G)

Considere el CP de Gentzen y sustituya el axioma G10 por el axioma G10*: ( x) (x y). El sistema formal

que se obtiene se conoce como el Cálculo de Proposiciones Intuicionista (CPI) de Gentzen.

2. Demostrar el CPC de Hilbert-Ackermann y el CPI de Gentzen no son equivalentes.

3. La no equivalencia entre CPC y CPI significa que existen tautologías que no son teoremas intuicionistas.

Por ejemplo, estudie la situación de .

4. Demuestre qué sucede si se incorpora al conjunto de conectivos primitivos de HA a . Es este nuevo

sistema (denotémoslo HA ), demuestre si es equivalente a CPI.

5. Reemplazar G10* por G10**: y demostrar si este nuevo sistema es equivalente a CPC.