SOLUCIONARIO

INTRODUCCIÓN A LA LÓGICA&

TEORÍA DE CONJUNTOS

CON NOTAS DE CLASE

PorD. OSPINA M

Estudiante de Matemáticas

UNIVERSIDAD DE ANTIOQUÍA

FACULTAD DE CIENCIAS EXACTAS Y NATURALES

INSTITUTO DE MATEMÁTICAS

2013

ÍNDICE GENERAL

1.1 Ejercicio.Cuando A⇔B es falsa, ¿Que se puede decir sobre el valor de verdad de lassiguientes F.S.?

(a) A∧B (b) A∨B (c) A⇒B (d) (A∧C)⇔ (B ∧C)↓ ↓ ↓ ↓F V F no es V ni F

1.2 Ejercicio.Determine si las siguientes formas sentenciales son tautologias por el metodo delejemplo 1.7 o por tablas de verdad.

(a) ((A⇒B)⇒B)⇒B

A B A⇒B (A⇒B)⇒B ((A⇒B)⇒B)⇒B

vvff

vfvf

vfvv

vvvf

vfvv

⇒no es contradicciónni tautología

(b) A⇒ (B⇒ (B⇒A)) (c) ((A⇒B)⇒A)⇒A

↓ l ↓ l ↓ l ↓v f v f v f f

↓ l ↓ l ↓ l ↓v f f v f f f

tautología tautología

(d) ((B⇒C)⇒ (A⇒B))⇒ (A⇒B) (e) (A∨¬(B ∧C))⇒ ((A⇔B)∨B)

↓ l ↓ l ↓ l ↓ l ↓ l ↓v f f v v f f f v f f

↓ l ↓ l ↓ l ↓ l ↓ l ↓v v v f v f v f f f f

tautología tautologia

(f) (A⇔B)⇔ (A⇔ (B⇔A)) (g) (A⇒B)∨ (B⇒A)

↓ l ↓ l ↓ l ↓ l ↓v f f f v v v v v

↓ l ↓ l ↓ l ↓v f f f v f f

tautología tautología

(h) (¬(A⇒B))⇒A

↓ l ↓ l ↓v f f f f

tautología

4

1.3 Ejercicio.

(a) ⊢L ¬B ⇒ (B ⇒ C)

1. ¬B⇒ (¬B ∨C) (A.2)2. ¬B⇒ (¬B⇒C) def⇒

(b) ⊢L C ⇒ (B ⇒ C)

1. C⇒ (¬B ∨C) (L.2)2. C⇒ (B⇒C) def⇒

(c) B ⇒ C ⊢L(B ∨ D) ⇒ (C ∨ D)

1. B⇒C (hip)2. (B⇒C)⇒ (D ∨B)⇒ (D∨C) (A.4)3. (D ∨B)⇒ (D ∨C) (MP)4. (B ∨D)⇒ (D ∨B) (A.3)5. (B ∨D)⇒ (D ∨C) 3,4(L.1)6. (D ∨C)⇒ (C ∨D) (A.3)7. (B ∨D)⇒ (C ∨D) 5,6(L.1)

(d) ⊢L(C ⇒ D) ⇒ [(B ⇒ C) ⇒ (B ⇒ D)]

1. (B⇒C)⇒ [(¬B ∨C)⇒ (¬B ∨D)] (A.4)2. (B⇒C)⇒ [(B⇒C)⇒ (B⇒D)] def⇒

(e) B ⇒ C ⊢L (C ⇒ D) ⇒ (B ⇒ D) « LEMA 8 »

1. B⇒C (hip)2. ¬C⇒¬B (L.7)3. (¬C⇒¬B)⇒ [(D ∨¬C)⇒ (D ∨¬B)] (A.4)4. [(D∨¬C)⇒ (D∨¬B)] (M.P)5. (¬C ∨D)⇒ (D ∨¬C) (A.3)6. (¬C ∨D)⇒ (D ∨¬B) 4,5(L.1)7. (D ∨¬B)⇒ (¬B ∨D) (A.3)8. (¬C ∨D)⇒ (¬B ∨D) 6,7(L.1)8. (C⇒D)⇒ (B⇒D) def⇒

(f) B ⇒ D, ¬B ⇒ D⊢L D

1. B⇒D (hip)2. ¬B⇒D (hip)3. B ∨¬B (L.5)4. D 1,2,3(L.9)

5

1.4 Ejercicio.

(a) ⊢L [B ∨ (C ∨ D)] ⇒ [(C ∨ (B ∨ D)) ∨ B]

1. D⇒ (B ∨D) (L.2)2. [D⇒ (B ∨D)]⇒ (C ∨D)⇒ [C ∨ (B ∨D)] (A.4)3. [(C ∨D)⇒ (C ∨ (B ∨D))] 1,2(M.P)4. [(C ∨D)⇒ (C ∨ (B ∨D))]⇒ [(B ∨ (C ∨D))⇒ (B ∨ (C ∨ (B ∨D)))] 3(A.4)5. [(B ∨ (C ∨D))⇒ (B ∨ (C ∨ (B ∨D)))] 3,4(M.P)6. [B ∨ (C ∨ (B ∨D))]⇒ [(C ∨ (B ∨D))∨B] 5(A.3)7. [B ∨ (C ∨D)]⇒ [(C ∨ (B ∨D))∨B] 5,6(L.1)

(b) ⊢L[(C ∨ (B ∨ D)) ∨ B] ⇒ [C ∨ (B ∨ D)]

1. B⇒ (B ∨D) (A.1)2. [B⇒ (B ∨D)]⇒ [(C ∨B)⇒ (C ∨ (B ∨D))] 1(A.4)3. (C ∨B)⇒ (C ∨ (B ∨D)) 1,2(M.P)4. B⇒ (C ∨ (B ∨D)) 1,3(L.1)5. [B⇒ (C ∨ (B∨D))]⇒ [(C ∨ (B∨D)∨B)⇒ [((C ∨ (B∨D)))∨ (C ∨ (B∨D))]] (A.4)6. [(C ∨ (B ∨D)∨B)⇒ [((C ∨ (B ∨D)))∨ (C ∨ (B ∨D))]] 4.5(M.P)7. [((C ∨ (B ∨D)))∨ (C ∨ (B ∨D))]⇒ (C ∨ (B ∨D)) (A.1)8. (C ∨ (B ∨D)∨B)⇒ (C ∨ (B ∨D)) 6,7(L.1)

(c) ⊢L(B ∨ (C ∨ D)) ⇒ (C ∨ (B ∨ D))

1. B⇒ (B ∨D) (A.1)2. (B⇒ (B ∨D))⇒ [(C ∨B)⇒ (C ∨ (B ∨D)] (A.4)3. (C ∨B)⇒ (C ∨ (B ∨D)) 1,2(M.P)4. B⇒ (C ∨B) (L.2)5. B⇒ (C ∨ (B ∨D)) 4.3(L.1)6. D⇒ (B ∨D) (L.2)7. [D⇒ (B ∨D)]⇒ [(C ∨D)⇒ (C ∨ (B ∧D))] 6(A.4)8. [(C ∨D)⇒ (C ∨ (B ∧D))] 6,7(M.P)9. [B ∨ (C ∨D)]⇒ (C ∨ (B ∨D)) 5,8(L.9)

(d) ⊢L(B ⇒ (C ⇒ D)) ⇒ (C ⇒ (B ⇒ D))

1. D⇒ (¬B ∨D) (L.2)2. [D⇒ (¬B ∨D)]⇒ [(¬C ∨D)⇒ (¬C ∨ (¬B ∨D))] 1(A.4)3. [(¬C ∨D)⇒ (¬C ∨ (¬B ∨D))] 1,2(M.P)4. ¬B⇒ (¬B ∨D) (A.2)5. [¬B⇒ (¬B ∨D)]⇒ [(¬C ∨¬B)⇒ (¬C ∨ (¬B ∨D))] 4(A.4)6. [(¬C ∨¬B)⇒ (¬C ∨ (¬B ∨D))] 4,5(M.P)7. ¬B⇒ (¬C ∨¬B) (L.2)8. ¬B⇒ [¬C ∨ (¬B ∨D)] 6,7(L.1)9. [¬C ∨ (¬B ∨D)]⇒ [¬C ∨ (¬B ∨D)] 3.8(L.9)10. [C ⇒ (B⇒D)]⇒ [C⇒ (B⇒D)] def⇒

6

(e) ⊢L(B ⇒ C) ⇒ [(C ⇒ D) ⇒ (B ⇒ D)]

1. (C⇒D)⇒ [(B⇒C)⇒ (B⇒D)] ejercicio 1.3(d)2. (B⇒C)⇒ [(C⇒D)⇒ (B⇒D)] 1, ejercicio 1.4(d)

1.5 Ejercicio.

(a) ⊢L¬¬B ⇒ B

este se demuestra en el Lema 11, por el momento lo tomamos por verdadero

(b) ⊢L(¬C ⇒ ¬B) ⇒ (B ⇒ C) (c) ⊢L(¬B ⇒ B) ⇒ B

1. ¬¬C⇒C ejer 1.5 a 1. B⇒B (L.3)2. (¬¬C⇒C)⇒ [(¬B ∨¬¬C)⇒ (¬B ∨C)] (A.4) 2. ¬¬B⇒B ejer 1.5 a3. [(¬B ∨¬¬C)⇒ (¬B ∨C)] 1,2(M.P) 3. (¬¬B ∨B)⇒B (L.9)4. (¬¬C ∨¬B)⇒ (¬B ∨¬¬C) 3(A.3) 3. (¬B⇒B)⇒B def⇒5. (¬¬C ∨¬B)⇒ (¬B ∨C) 4,3(L.1)5. (¬C⇒¬B)⇒ (B⇒C) def⇒

(d) ⊢L(B ⇒ ¬B) ⇒ ¬B (e) ⊢L(B ∨ C) ⇒ (¬B ⇒ C)

1. (¬B ∨¬B)⇒¬B (A.1) 1. B⇒¬¬B (L.5)1. (B⇒¬B)⇒¬B 1 def⇒ 2. (B⇒¬¬B)⇒ [(C ∨B)⇒ (C ∨¬¬B)] (A.4)

3. [(C ∨B)⇒ (C ∨¬¬B)] 2(M.P)4. (B ∨C)⇒ (C ∨B) (A.3)5. (B ∨C)⇒ (C ∨¬¬B) 4,3(L.1)6. (C ∨¬¬B)⇒ (¬¬B ∨C) (A.3)7. (B ∨C)⇒ (¬¬B ∨C) 5,6(L.1)7. (B ∨C)⇒ (¬B⇒C) def⇒

(f) ⊢L(¬B ⇒ C) ⇒ (B ∨ C)

1. ¬¬B⇒B ejer 1.5 a2. (¬¬B⇒B)⇒[(C ∨¬¬B)⇒ (C ∨B)] (A.4)3. [(C ∨¬¬B)⇒ (C ∨B)] (M.P)4. (¬¬B ∨C)⇒ (C ∨¬¬B) (A.3)5. (¬¬B ∨C)⇒ (C ∨B) 4,3(L.1)6. (C ∨B)⇒ (B ∨C) (A.3)7. (¬¬B ∨C)⇒ (B ∨C) 5,6(L.1)7. (¬B⇒C)⇒ (B ∨C) def⇒

7

1.6 Ejercicio.

« Generalizacíon de la diyuncion de casos ».B1 ⇒ D, , Bn⇒ D ⊢L (B1 ∨ ∨ Bn) ⇒ D

Por inducción sobre n:n=1: B1⇒D ⊢L B1⇒D

Por Hipotesis Inductiva tenemos B1⇒D, , Bn⇒D,⊢L(B1∨ ∨Bn)⇒D.Paso inductivo:1. B1⇒D (hip) n +1. Bn+1⇒D (hip)n +2. (B1∨ ∨Bn)⇒D Hipotesis Inductivan +3. ((B1∨ ∨Bn)∨Bn+1)⇒D (disyunción de casos n+ 1, n+ 2)luego B1⇒D, , Bn⇒D, Bn+1⇒D,⊢L((B1∨Bn)∨Bn+1)⇒D.

Disyunción de casos “caso general”

Si B⇒D, C⇒D ⊢L (B ∨C)⇒D entonces B ∨C,B⇒D, C⇒D ⊢L D.

Justificación.supongamos B⇒D,C⇒D ⊢L (B ∨C)⇒D existe una deducción de (B ∨C)⇒D

a partir de B⇒D y C ⇒D, es decir existe una secuencia de formulas α1,αn, «quesatisfacen la definicion de ser una deducción, con hipotesis B⇒D, C⇒D enformula final (B ∨C)⇒D»α1,αn, es tambien una deducción de (B∨C)⇒D a partir de {B∨C,B⇒D,C⇒D}

Esquema→

α18 B⇒D (hip)α28 C⇒D (hip) αn8 (B ∨C)⇒D

αn+18 (B ∨C) (hip)αn+28 D (M.P,αn,αn+1)

Meta-Teorema de Deducción

Si Γ, α⊢L β entonces Γ,⊢L α⇒ β conΓ⊆ formuas, α, β ∈ formulas.

Demostración:Sea Γ,α⊢Lβ, es decir, existe una secuencia α1, ,αn que es una deducción de β a partirde Γ∪ {α}, por inducción sobre n, vamos a mostrar que Γ,⊢L α⇒ β;Si n=1 entonces α1 = β; Por definición de deducción β ∈Γ∪ {α} o β es instancia deun axioma si β ∈Γ∪{α} si β ∈Γ, entonces Γ,⊢L β, por (Lema.4)“absorción” se tieneΓ⊢L α⇒ β.

Si β =α: Por (Lema.3)“identidad” se tiene Γ,⊢L β⇒ β y sustituyendo por igualesΓ,⊢L α⇒ β.Si β es instancia de un axioma Γ⊢Lβ y por (Lema.4)“absorción” se tiene Γ,⊢L α⇒ β.

8

Paso inductivo:Supongamos que el Meta-Teorema de Deducción vale para todas las deducciones detamaño menor a n y veamos que vale para las deducciones de tamaño n siαn∈Γ∪{α} o αn es instancia de un axioma (αn = β); La demostracion es igual a ladel paso base (n=1).Si αn es obtenido por M.P. existen αi yαj tales que i, j<n y αj 8 αi⇒αn, luegoα1, , αi es una deducción de αi a partir de Γ∪ {α}, (Γ, α⊢L αi) o analogamenteα8 αj⇒αn y α1, , αj es una dedeucción de α; a partir de Γ∪ {α}, (Γ, α⊢L αj)

por Hipotesis Inductiva se tiene Γ⊢L α⇒αj y Γ⊢L α⇒αj , Γ⊢L α⇒ (αj⇒αn) porLema.10 se tiene Γ⊢L α⇒αn “ es decir Γ⊢L α⇒ β ”

1.7 Ejercicio.

(a)(L.16b) B ⇔ C ⊢L C ⇔ B. (L.16d) B ⇔ C ⊢L ¬B ⇔ ¬C

1. B⇔C (hip) 1. B⇔C (hip)2. B⇒C 1,L.15c,M.P 2. B⇒C 1,L.15c,M.P3. C⇒B 1,L.15d,M.P 3. ¬C⇒¬B 2,L.7,M.P4. C⇔B 3,2(L.14b) 4. C⇒B 1,L.15d,M.P

5. ¬B⇒¬C 4,L.7,M.P6. ¬B⇔¬C 5,3(l.14b)

(L.16f) B ⇔ C ⊢L (B ∨ D) ⇔ (C ∨ D)

1. B⇔C (hip) (L.16h) B ⇔ C ⊢L (D ⇒ B) ⇔ (D ⇒ C)2. B⇒C 1,L.15c,M.P3. C = B 1,L.15d,M.P 1. B⇔C (hip)4. (D ∨B)⇒ (D ∨C) 2,A.4,M.P 2. B⇒C 1,L.15c,M.P5. (B ∨D)⇒ (D ∨B) (A.3) 3. (¬D∨B)⇒ (¬D∨C) 2,A4,M.P6. (B ∨D)⇒ (D ∨C) 5,4(L.1) 4. C⇒D 1,L.15d,M.P7. (D ∨C)⇒ (C ∨D) (A.3) 5. (¬D∨C)⇒ (¬D∨B) 4,A4,M.P8. (B ∨D)⇒ (C ∨D) 6,7(L.1) 6. (¬D∨B)⇔ (¬D∨C) 3,5(L.14b)9. (D ∨C)⇒ (D ∨B) 3,A.4,M.P 6. (D⇒B)⇔ (D⇒C) def⇒10. (C ∨D)⇒ (D ∨C) (A.3)11. (C ∨D)⇒ (D ∨B) 10,9(L.1)12. (D ∨B)⇒ (B ∨D) (A.3)13. (C ∨D)⇒ (B ∨D) 11,12(L.1)14. (B ∨D)⇔ (C ∨D) 8,13(L.14b)

(b)(L.17a) ⊢LB ⇔ ¬¬B (l.17b) ⊢L(B ∨ B) ⇔ B

1. B⇒¬¬B (L.6) 1. (B ∨B)⇒B (A.1)2. ¬¬B⇒B (L.11) 2. B⇒ (B ∨B) (A.2)3. B⇔¬¬B 1,2(L.14b) 3. (B ∨B)⇔B 1,2(L.14b)

9

(L.17c) ⊢L(B ∧ B) ⇔ B (L.17d) ⊢L(B ∨ C) ⇔ (C ∨ B)

1. (¬B ∨¬B)⇔¬B (L.17b) 1. (B ∨C)⇒ (C ∨B) (A.3)2. ¬(¬B ∨¬B)⇔¬¬B (L.16d) 2. (C ∨B)⇒ (B ∨C) (A.3)2. (B ∧B)⇔¬¬B def ∧ 3. (B ∨C)⇔ (C ∨B) 1,2(L.14b)3. (B ∧B)⇔B (L.17a)T.S.E

(L.17f) ⊢L(B ⇒ C) ⇔ (¬C ⇒ ¬B)(L.17e) ⊢L(B ∧ C) ⇔ (C ∧ B)

1. (B⇒C)⇒ (¬C⇒¬B) (L.7)1. (¬C ∨¬B)⇔ (¬B ∨¬C) (L.17d) 2. (¬C⇒¬B)⇒ (B⇒C) (L.13)2. ¬(¬B ∨¬C)⇔¬(¬C ∨¬B) (L.16d) 3. (B⇒C)⇔ (¬C⇒¬B) 1,2(L.14b)2. (B ∧C)⇔ (C ∧B) def ∧

(c)(L.19a) ⊢L(B ∧ (C ∧ D)) ⇔ ((B ∧ C) ∧ D)

1. B ∧ (C ∧D) (hip)2. B 1,(L.15a)M.P3. C ∧D 1,(L.15b)M.P4. C 3,(L.15a)M.P5. D 3,(L.15b)M.P6. B ∧C 2,4(L.14a)7. (B ∧C)∧D 6,5(L.14a)8. (B ∧ (C ∧D))⇒ ((B ∧C)∧D) 1,7(T. Deducción)9. (B ∧C)∧D (hip)10. B ∧C 9,(L.15a)M.P11. D 9,(L.15b)M.P12. B 10,(L.15a)M.P13. C 10,(L.15b)M.P14. C ∧D 13,11(L.14a)15. B ∧ (C ∧D) 12,14(L.14a)16. ((B ∧C)∧D)⇒ (B ∧ (C ∧D)) 9,15(T. Deducción)17. (B ∧ (C ∧D))⇔ ((B ∧C)∧D) 8,16(L.14b)

(L.19d) ⊢L(B ∨ (C ∧ D)) ⇔ [(B ∨ C) ∧ (B ∨ D)]

1. (¬B ∧ (¬C ∨¬D))⇔ [(¬B ∧¬C)∨ (¬B ∧¬D)] (L.19c)2. (¬B ∧¬(C ∧D))⇔ [¬(B ∨C)∨¬(B ∨D)] D’ Morgan3. ¬(B ∨ (C ∧D))⇔¬[(B ∨C)∧ (B ∨D)] D’ Morgan4. ¬¬(B ∨ (C ∧D))⇔¬¬[(B ∨C)∧ (B ∨D)] 3(L.16d)5. (B ∨ (C ∧D))⇔ [(B ∨C)∧ (B ∨D)] (L.17a)T.S.E

10

(d) B ⇒ C ⊢L (B ∨ C) ⇔ C

1. B⇒C (hip)2. (B⇒C)⇒ (C ∨B)⇒ (C ∨C) 1(A.4)3. (C ∨B)⇒ (C ∨C) 1,2(M.P)4. (C ∨B)⇒C 3(L.17b)T.S.E5. (B ∨C)⇒C 4(L.17d)T.S.E6. C⇒ (B ∨C) (L.2)7. (B ∨C)⇔C 5,6(L.14b)

(e) B ⇒ C ⊢L (B ∧ C) ⇔ B

1. B⇒C (hip)2. ¬C⇒¬B 1(L.7)M.P3. [(¬B ∨¬C)⇒ (¬B ∨¬B)] 2(A.4)M.P4. (¬B ∨¬C)⇒¬B 3(L.17b)T.S.E5. ¬(B ∧C)⇒¬B 4,D’ Morgan7. ¬¬B⇒¬¬(B ∧C) 5(L.7)MP8. B⇒ (B ∧C) 7(L.17a)T.S.E9. (B ∧C)⇒B (L.15a)10. (B ∧C)⇔B 9,8(l.14b)

1.8 Ejercicio.

(a) ⊢L(¬B ⇒ C) ⇔ (B ∨ C) (b) ⊢L(B ∨ C) ⇔ ¬(¬B ∧ ¬C)

1. (¬B⇒C)⇔ (¬B⇒C) (L.16a) 1. (B ∨C)⇔ (B ∨C) (L.16a)1. (¬B⇒C)⇔ (¬¬B ∨C) def⇒ 2. ¬(B ∨C)⇔¬(B ∨C) (L.16d)2. (¬B⇒C)⇔ (B ∨C) 1(L.17a)T.S.E 3. ¬(B ∨C)⇔ (¬B ∧¬C) 2 D’ Morgan

4. ¬¬(B ∨C)⇔¬(¬B ∧¬C) 3(L.16d)5. (B ∨C)⇔¬(¬B ∧¬C) 4(L.17a)T.S.E

(c)(L.19f) ⊢L[B ⇒ (C ⇒ D)] ⇔ [C ⇒ (B ⇒ D)]

1. (¬B ∨ (¬C ∨D))⇔ ((¬B ∨¬C)∨D) (L.19b)2. (¬B ∨ (¬C ∨D))⇔ ((¬C ∨¬B)∨D) 1(L.17b)T.S.E3. (¬B ∨ (¬C ∨D))⇔ (¬C ∨ (¬B ∨D)) 2(L.19b)T.S.E4. (B⇒ (C⇒D))⇔ (C⇒ (B⇒D)) defi⇒

(L.19h) ⊢L(B ⇔ C) ⇔ (C ⇔ B)

1. B⇔C hip2. C⇔B 1(L.16b)3. (B⇔C)⇒ (C ⇔B) 1,2(T. Deducción)4. C⇔B hip5. B⇔C 4(L.16b)6. (C⇔B)⇒ (B⇔C) 4,5(T. Deducción)

11

(d)

(L.20a) B ⊢L (B ∧ C) ⇔ C (L.20b) ¬B ⊢L (B ∨ C) ⇔ C

1. B (hip) 1. ¬B (hip)2. B⇒ (¬C ∨B) (L.2) 2. ¬B⇒ (¬B ∨C) (A.2)3. ¬C ∨B 2(M.P) 3. ¬B ∨C 1,2(M.P)3. C⇒B def⇒ 3. B⇒C def⇒4. ¬B⇒¬C 3(L.7)M.P 4. (C ∨B)⇒ (C ∨C) 3(A.4)M.P5. (¬C ∨¬B)⇒ (¬C ∨¬C) 4(A.4)M.P 5. (C ∨B)⇒C 4(L.17b)T.S.E6. (¬C ∨¬B)⇒¬C 5(L.17b)T.S.E 6. (B ∨C)⇒C 5(L.17d)T.S.E7. ¬¬C⇒¬(¬C ∨¬B) 6(L.7)M.P 7. C⇒ (B ∨C) (L.2)8. C⇒¬(¬C ∨¬B) 7(L.17a)T.S.E 8. (B ∨C)⇔C 6,7(L.14b)M.P8. C⇒ (C ∧B) def⇒9. C⇒ (B ∧C) 8(L.17e)T.S.E10. (B ∧C)⇒C (L.15 b)11. (B ∧C)⇔C 10,9(L.14b)

(e) B, C ⊢L B ⇔ C (f) B ⇔ ¬B es una hipótesisinconsistente de L

1. B (hip) 1. B⇔¬B (hip)2. C (hip) 2. B⇒¬B 1(L.15c)M.P3. C⇒B 1(L.4) 2. ¬B ∨¬B def⇒4. B⇒C 2(L.4) 3. ¬B 2(A.1)M.P5. B⇔C 3,4(L.14b) 4. ¬B⇒B 1(L.15d)M.P

4. B ∨B def⇒5. B 4(A.1)M.PDe 3 y 5 se concluye que B⇔¬B, esun conjunto de hipótesis inconsistentes de L

(g)(L.19i) ⊢L [¬(B ⇔ C)] ⇔ [(¬B) ⇔ C]

1. ¬(B⇔C)⇔¬[(B⇒C)∧ (C⇒B)] def⇒2. ⇔[¬(B⇒C)∨¬(C⇒B)] 1,D’ Morgan2. ⇔[¬(¬B ∨C)∨¬(¬C ∨B)] def⇒3. ⇔[(¬¬B ∧¬C)∨ (¬¬C ∧¬B)] 2,D’ Morgan4. ⇔[(B ∧¬C)∨ (C ∧¬B)] 3,(L.17a)T.S.E5. ⇔[((B ∧¬C)∨C)∧ ((B ∧¬C)∨¬B)] 4(L.19d)T.S.E6. ⇔[((B ∨C)∧ (¬C ∨C))∧ ((B ∨¬B)∧ (¬C ∨¬B))] 5(L.19d)T.S.E

7. ⇔[(B ∨C)∧ (¬C ∨¬B)] 6

(

tercer excluido, eliminaciónde la verdad en la conjuncion

)

T.S.E

8. ⇔[(¬¬B ∨C)∧ (¬C ∨¬B)] 7(L.17a)T.S.E8. ⇔[(¬B⇒C)∧ (C ⇒¬B)] def⇒8. ¬(B⇔C)⇔ [(¬B)⇔C] def⇔

12

(h) ⊢L (C ⇔ (C ⇔ D)) ⇒ D

1. C⇔ (C⇔D) (hip)2. C⇒ (C⇔D) 1(L.15c)M.P3. (C⇔D)⇒ (C⇒D) (L.15c)4. C⇒ (C⇒D) 2,3(L.195. (C ∧C)⇒D 4(L.19g)T.S.E6. C⇒D 5(L.17c)T.S.E7. ¬C⇔¬(C⇔D) 1(L.16d)T.S.E8. ¬C⇒¬(C⇔D) 7(L.15c)M.P9. ¬C⇒ (¬C⇔D) 8(L.19i)T.S.E10. (¬C⇔D)⇒ (¬C⇒D) 9(L.15c)11. ¬C⇒ (¬C⇒D) 9,10 (L.1)12. (¬C ∧¬C)⇒D 11(L.19g)T.S.E13. ¬C⇒D 12(L.17c)T.S.E14. C ∨¬C (L.5)15. D 6,13,14(L.9)16. (C⇔ (C⇔D))⇒D 1, 15(T. Deducción)

Prueba (1)⊢L(B ⇔ C) ⇔ [(B ∧ C) ∨ (¬B ∧ ¬C)]

1. ¬(B⇔C)⇔¬(B⇔C) (L.16a,d)2. ¬(B⇔C)⇔ (¬B⇔C) 1(L.19i)2. ¬(B⇔C)⇔ [(¬B⇒C)∧ (C⇒¬B)] def⇔2. ¬(B⇔C)⇔ [(¬¬B ∨C)∧ (¬C ∨¬B)] def⇒3. ¬¬(B⇔C)⇔¬[(¬¬B ∨C)∧ (¬C ∨¬B)] 2(l.16d)4. (B⇔C)⇔¬[(B ∨C)∧ (¬C ∨¬B)] 3(L.17a)T.S.E5. (B⇔C)⇔ [¬(B ∨C)∨¬(¬C ∨¬B)] D’ Morgan6. (B⇔C)⇔ [(¬B ∧¬C)∨ (C ∧B)] D’ Morgan7. (B⇔C)⇔ [(C ∧B)∨ (¬B ∧¬C)] 6(L.17d)

(i)(L.19j) ⊢L(B ⇔ (C ⇔ D)) ⇔ ((B ⇔ C) ⇔ D)

1. B⇒ (C⇒D) (hip)2. (B ∧ (C⇔D))∨ (¬B ∧¬(C⇔D)) 1(Prueba.1)T.S.E

3. B ∧ (C⇔D) 2(hip)3.1.1. B 3(L.15a)M.P3.1.2. C⇔D 3(L.15b)M.P3.1.3. B⇔C (hip)3.1.4. B⇔D 3.1.3, 3.1.2, (L.16c)3.1.5. D 3.1.4, 3.1.1, T.S.E3.1.6. (B⇔C)⇒D 3.1.3, 3.1.5, T.Deducción

13

3.2. D (hip)3.2.1. C 3.2, 3.1.2, T.S.E.3.2.2. B ∧C 3.1.1, 3.2.1, (L.14a)3.2.3. (B ∧C)∨ (¬B ∧¬C) 3.2.2,(A.2)M.P3.2.4. (B⇔C) 3.2.3, (Prueba.1)M.P3.2.5. D⇒ (B⇔C) 3.2, 3.2.4, T. Deducción4. (B⇔C)⇔D 3.1.6, 3.2.5, (L.14b)5. (B ∧ (C⇔D))⇒ ((B⇔C)⇔D) 3,4 T.Deducción

6. ¬B ∧¬(C⇔D) 2(hip)6.1. B⇔C (hip)6.2. ¬(C⇔D) 6(L.15c)M.P6.3. ¬(B⇔D) 6.1, 6.2, T.S.E.6.4. ¬B⇔D (L.19i)6.5. ¬B 6(L.15a)M.P6.6. D 6.4, 6.5, T.S.E.7. (B⇔C)⇒D 6.1, 6.6 T.Deducción8. D (hip)8.1. ¬B 6(L.16a)M.P8.2. ¬(C⇔D) 6(L.16b)M.P8.3. ¬C⇔D 8.2(L.19i)8.4. ¬C 8, 8.3, T.S.E8.5. ¬B ∧¬C 8.1, 8.4,(L.14a)8.6. (B ∧C)∨ (¬B ∧¬C) 8.5, (L.2)M.P8.7. B⇔C 8.6(Prueba.1)9. D⇒ (B⇔C) 8, 8.7, T.Deducción10. (B⇔C)⇔D 7,9(L.14b)11. (¬B ∧¬(C⇔D))⇒ ((B⇔C)⇔D) 6,10 T.Deducción12. (B⇔C)⇔D 2,5,11, (L.9)13. (B⇔ (C⇔D))⇒ ((B⇔C)⇔D) 1,12, T.Deducción

14. ((B⇔C)⇔D) (hip)15. ((B⇔C)∧D)∨ (¬(B⇔C)∧¬D) 14(Prueba.1)T.S.E16. (B⇔C)∧D 15(hip)16.1.1. D 16(L.15b)M.P16.1.2. B⇔C 16(L.15a)M.P16.1.3. C⇔D (hip)16.1.4. B⇔D 16.1.2, 16.1.3, (L.16c)16.1.5. B 16.1.4, 16.1.1 T.S.E16.1.6. (C⇔D)⇒B 16.1.3, 16.1.5 T.Deducción16.2. B (hip)16.2.1. C 16.1.2, 16.2 T.S.E16.2.2. C ∧D 16.2.1, 16.1.1(L.14a)16.2.3. (C ∧D)∨ (¬C ∧¬D) 16.2.2(A.2)M.P16.2.4. C⇔D 16.2.3 (Prueba.1)T.S.E16.2.5. B⇒ (C⇔D) 16.2, 16.2.4 T.Deducción17. B⇔ (C⇔D) 16.1.6, 16.2.5 (L.14b)18. ((B⇔C)∧D)⇒ (B⇔ (C⇔D)) 16, 17 T.Deducción

14

19. (¬(B⇔C)∧¬D) 15 (hip)19.1. C ⇔D (hip)19.2. ¬(B⇔C) 19(L.15a)M.P19.3. ¬D 19(L.15b)M.P19.4. ¬(D⇔B) 19.1, 19.2 T.S.E19.5. ¬D⇔B 19.4 (L.19i)19.6. B 19.3, 19.5 T.S.E19.7. (C⇔D)⇒B 19.1, 19.6 T.Deducción20. B (hip)20.1. ¬D 19(l.15b)M.P20.2. ¬(B⇔C) 19(l.15a)M.P20.3. ¬(C⇔B) 20.2(L.16b)20.4. ¬C⇔B 20.3(L.19i)20.5. ¬C 20, 20.4 T.S.E20.6. ¬C ∧¬D 20.1, 20.5(L.14a)20.7. (C ∧D)∨ (¬C ∧¬D) 20.6(L.2)M.P20.8. C ⇔D 20.7(Prueba.1)T.S.E20.9. B⇒ (C⇔D) 20, 20.8 T.Deducción21. B⇔ (C⇔D) 19.7, 20.9 (L.14b)22. (¬(B⇔C)∧¬D)⇒ (B⇔ (C⇔D)) 19,21 T.Deducción

23. B⇔ (C⇔D) 15, 18, 22(L.9)24. ((B⇔C)⇔D)⇒ (B⇔ (C⇔D)) 14, 23 T.Deducción25. (B⇔ (C⇔D))⇔ ((B⇔C)⇔D) 13,24(L.14b)

Definición (complejidad de la formula)

comp: For⇒N tal quecomp(Pi)=0 Csi Pi es una variable proposicionalcomp(¬α)=comp(α)+1comp(α∨ β)=max{comp(α), comp(β)}+1

EjemploA8 ¬(B ∨¬C)compA8 3comp(B)=comp(C)=0comp(¬C)=1comp(B ∨¬C)=2comp¬(B ∨¬C)=3

Inducción Estructural

sea P una propiedad sobre formulas si:

i. P(pi) =para todo pi

ii. si P(α), entonces P(¬α)

iii. si P(α) y P(β), entonces P(α∨ β).entonces P vale para toda formula α

15

Meta-Teorema “ Sustitución por equivalencias ” (T.S.E).

Sean A,B , C∈ Formulas y sea A′ el resultado de sustituir una ocurrencia de B enApor C, entonces B⇔C⊢LA=A′

Demostración:Por inducción estructural sobre A1. si A=Pi: la única subfómulas de A es el propio A, entonces B=Pi,si se supone B⇔C entonces A′= C y por supuesto B⇔C⊢LB⇔C,B⇔C⊢LA⇔A′.

2. Supongamos que A=¬D vale sustituir por equivalencias para D(es decir, B⇔C⊢LD⇔D ′), si D ′ es el resultado de sustituir una ocurrencia deB en D por C , por (L.16d) se tiene B⇔C⊢LD⇔D ′, es decir, B⇔C⊢LA⇔A′

(si A’ es el resultado de sustituir una ocurrencia de B por C enA, entonces esasustitución tiene que ser hecha en D).

3. Si A8 D∨F : si A’ es el resultado de sustituir una ocurrencia de B porC en A,esa sustitución pudo haber sido hecha en DoF . Si la sustitución fue hecha en D:por Hipótesis Inductiva vale sustituir por equivalencias para D,es decir, B⇔C⊢LD⇔D ′, por lema 16f se tiene B⇔C ⊢L (D∨F)⇔(D ′∨F),es decir, B⇔C⊢LA⇔A′, si la sustitución es hecha en F se prueba de manerasimilar (lema 16).

1.9 Ejercicio.

(a) ⊢L(B ⇔ C) ⇔ [(B ∧ C) ∨ (¬B ∧ ¬C)]Este se demuestra en la prueba(1)

(b) (L.19i) ⊢L ¬(B ⇔ C) ⇔ (¬B ⇔ C)

1. (B⇔C)⇔ [(C ∧B)∨ (¬B ∧¬C)] Ejercicio 1.9a2. ¬(B⇔C)⇔¬[(C ∧B)∨ (¬B ∧¬C)] 1(L.16)T.S.E3. ¬(B⇔C)⇔ [¬(C ∧B)∧¬(¬B ∧¬C)] 2,D’MorganT.S.E4. ¬(B⇔C)⇔ [(¬C ∨¬B)∧ (B ∨C)] 3,D’MorganT.S.E4. ¬(B⇔C)⇔ [(C⇒¬B)∧ (¬B⇒C)] def⇒4. ¬(B⇔C)⇔ (¬B⇔C) def⇔

1.10 Ejercicio.Sea Γ un conjunto de fórmulas

(a) Si Γ, B, forman un conjunto inconsistente de hipótesis,entonces Γ ⊢L ¬B

• Por teorema de reducción al absurdo donde B es la hipótesis de R.A.

(b) Si Γ, B, ¬C , forman un conjunto inconsistente de hipótesis,entonces Γ ⊢L B ⇒ C .• Por teorema de ruduccion al absurdo se tiene Γ,B ⊢L C , luego por teoremade deducción Γ⊢LB⇒C

16

(c) Si existe una fórmula D tal que Γ ⊢L D ⇔ ¬D, entonces Γesun conjunto inconsistente.• Por definición 3.2 Γ es un conjunto inconsistente

LEMASea B ∈ formula y sea P1, ,Pn las variables proposicionales de B“considere una asignación de valores de verdad a Pi, ,Pn y definamos las siguientesformulas: Pi

′=Pi (si toma valor V en la asignación considerada)Pi

′=¬Pi (si toma valor F en la asignación considerada)B ′=B (si B toma valor V en la asignación considerada)B ′=¬B (si B toma valor F en la asignación considerada)

entonces P1′, ,Pn

′ ⊢LB ′

Demostración:Por inducción estructural sobre B (o inducción sobre la complejidad de B );Caso base (B=P para alguna variable proposicional P),se tiene los siguientes casos:1. Si se asigna V a P : En este caso P ′=P y B ′=P y P ⊢LP luego P ′⊢LB ′

2. Si se asigna F a P: En este caso P ′=¬P y B ′=¬P y ¬P ⊢L¬P luego P ′⊢LB ′

Paso inductivo:

Si B=¬C sean P1,Pn las variables proposicionales en B, por Hipótsis InductivaP1

′,Pn′ ⊢L C ′ , se tienen los siguientes casos:

(1). Si C toma valor V (bajo la asignación considerada); En este caso C ′= C y ¬Ctoma valor F entonces B ′=¬B, es decir B ′=¬¬C , es decir P1

′, ,Pn′ ⊢LB ′.

(2). Si C toma valor F : En este caso C ′=¬C luego P1′, ,Pn

′ ⊢L¬C, Ademas, B va atomar valor V entonces B ′=B=¬C, por tanto P1

′, ,Pn′ ⊢LB ′.

Si B= C ∨D :Se tiene entonces los siguientes casos(i). B toma valor V : Setiene entonces que C toma valor V o D toma valor V, y B ′=B

(i.1). Si C toma valor V : El conjunto de variables proposicionales de C ,

{Pi1, ,Pim}⊆ {P1, ,Pn}, y C ′= C por Hipóteis InductivaPi1

′ , ,Pim′ ⊢L C ′

Pi1′ , ,Pim

′ ⊢L Cpor adjunción Pi1

′ , ,Pim′ ⊢L (C ∨D) luego P1

′, ,Pn′ ⊢LB ′,

(i.2). Si B toma valor V : Es similar a (i.1)

(ii). Si B toma valor F : Entonces CyD, toman valor F luego B ′=¬B , C ′=¬C yD ′=¬D; Sea {Pi1, ,Pim}⊆ {P1, ,Pm}, las variables proposicionales de C y{Pj1, ,Pjl

}⊆ {P1, ,Pn} las variables proposicionales de D.

Por Hipótesis Inductiva,Pi1

′ , ,Pim′ ⊢L C ′

⊢LC

}

P1′, ,Pn

′ ⊢L¬C

yPj1

′ , ,Pjn

′ ⊢L D ′

⊢L¬D

}

P1′, ,Pn

′ ⊢L¬D

Por conjunción y D’MorganP1

′, ,Pn′ ⊢L¬(C ∨D)⊢LB ′

17

Teorema de validez y completitud

Teorema (Validez)Todo teorema de L es una tautología.

“Como no es tautología, no es demostrable”

Demostración:Sea α un teorema de L (es decir ⊢Lα) Por definición de teoremas existe unasecuencia finita de fórmulas L, α1, , αn, tales que para todo 1 6 i 6n,

(1). αi es instantanea de un axioma.(2). αi es obtenido de formulas anteriores por M.P. y αn =α.

Basta entonces con probar todos los axiomas (instancias), son tautologías y queM.P. preserva la propiedad de ser tautología (es decir si A⇒B, A son tautologías,entonces B es tautologia.

Veamos la segunda parte (M.P. preserva tautologías )Supongamos que A⇒B, A son tautologías;Supongamos que B no es tautología, es decir existe una asignación de valores deverdad a las variables proposicionales que hacen que B sea falso, como A estautología la implicación A⇒B toma valor falso para dicha asignación de valoresde verdad, lo que es una contradicción, pues se esta suponiendo que A⇒B estautología.

Teorema (Completitud “Debil”)Toda tautología es teorema de L (Si α es tautología entonces ⊢Lα)

“Como es tautología es demostrable”

Demostración “A la KALMAR”:Sea α una tautología y P1, ,Pn las variables proposicionales de α, considere unaasignación donde P1, ,Pn toman valor V entonces P1

′ =P1, ,Pn′ =Pn y como α

es tautología αtoma valor V, en esta asignación en particular, luego α′= α

por Lema anterior.Tomando otra asignación, donde por Lema anterior P1, ,Pn−1 toma valor V, yPn toma valor F, se tiene por Lema anterior P1, ,Pn−1,¬Pn⊢L α por Teorema deDeducción P1, ,Pn−1⊢LPn⇒α y P1, ,Pn−2⊢L¬Pn⇒α, por tercer excluido ydiyunción de casos , se tiene P1, ,Pn−1⊢L α;Aplicando el mismo procedimiento n veces, se tiene finalmente que ⊢L α.

1.11 Ejercicio.Sea B una fórmula. Prueba que las siguientes afirmaciones son equivalentes:(i) B es una contradicción.(ii) ¬B es una tautología.(iii) ⊢L¬B.(iv) B es una hipótesis inconsistente de L.

18

Probemos que (i)⇒(ii), como B es una contradicción entonces B toma el valor Fluego la negación de B tomara un valor V, por tanto ¬B es una tautología;Probemos (ii)⇒(i), como la negación de B es tautología y por tanto verdadero,necesariamente B es falsa, luego entonces B es una contradicción; Como probamos(i)⇒(ii) y (ii)⇒(i) tenemos (i)⇔(ii).

Ahora probemos (ii)⇒(iii), como la negación de B es tautología, por teorema decompletitud es demostrable o lo mismo que ⊢L¬B; Miremos (iii)⇒(ii) como ¬B esdemostrable, por teorema de Validez afirmamos ¬B es una tautología, hemosprobado (ii)⇒(iii) y (iii)⇒(ii) tenemos (ii)⇔(iii).

Probemos (iii)⇒(iv), supongamos ⊢L¬B, luego B ⊢L¬B “ Si se logra demostrar sinhipótesis ¬B, entonces tambien se puede demostrar con hipótesis ”, ademas B ⊢LBluego existe una formula “ que en este caso es precisamente B ” tal que {B} deduceB y ¬B luego {B} es un conjunto inconsistente de hipótesis.Ahora probemos (iv)⇒(iii); Sea B un conjunto inconsistente de hipótesis, porteorema {B} demuestra cualquier fórmula, en particular {B}⊢L¬B , por teoremade deducción ⊢LB⇒¬B,

1. B⇒¬B2. ¬B⇒¬B identidad3. B∨¬B tercer excluido4. ¬B diyunción de casos

Hemos probado (iii)⇒(iv) y (iv)⇒(iii), entonces (iii)⇔(iv).

2.1 Ejercicio.En las siguientes fórmulas de LS indique el alcance de cada cuantificador,las variables libres y las variables ligadas.

(a) D1(w): ∃z(0+ z = w). (b) D2: w = 0∨∃z(w = s(z)).

El alcance de ∃z es (0 + z = w) El alcance de ∃z es (w = s(z))Variables libres w Variables libres w

Variables ligadas z Variables ligadas z

(c) D3(w): ∀w∃z(z = s(w)). (d) D4(w, z): w =3 ∨ ∃w(w · z =3).

El alcance de ∀w es∃z(z = s(w)) El alcance de ∃w es (w · z =3)El alcance de ∃z es (z = s(w)) Variables libres: la primera w y z

No tiene variables libres Variables ligadas: la segunda w

Variables ligadas son z, w

2.2 Ejercicio.Justificar

(i) x + 3 es libre para w enD1(w).Verdad porque x+3 no genera una nueva variable ligada.

19

(ii) z · z es libre para w enD1(w).Falso porque generaría una nueva variable ligada.

(iii) 5+ x es libre para w enD2(w).Verdad porque no generaría una nueva variable ligada.

(iv) z es libre para w enD2(w).Falso porque seria libre en la primera w y para la segunda no lo sería debido a quegeneraría nuvas variables ligadas.

(v) Cualquier término es libre para z enD2(w).Verdad por que cualquier término que se sustituya no generaría variables ligadas, ysi se sustituyen la misma z no la alteraría, esto es por la proposición 1.17(d).

(vi) z + z es libre para w enD3(w).Falso, generaría una nueva variable ligada.

(vii) Cualquier término es libre para z enD4(w, z).Falso porque existiría algun término que estaría ligado.

(viii) D3(w) es una sentencia.Verdad porque no tiene variables libres.

(ix) D1(w) es una sentencia.Falso porque w es una variable libre.

2.3 Ejercicio.1.17 Proposición.(b) Sea B una fórmula y t un término de L. Si las variables de t noaprarecen ligadas en B entoncs t es libre para cualquier variable en B.

Sean B(t, x, , y, z) una fórmula donde t, x, , y, z son términos y como t noesta ligado entonces B(t, t, , y, z) sera t libre en la fórmula y B(t, x, , t, t)tambien sera libre, por lo tanto t es libre para cualquier variable en B.

(d) Sea B una fórmula de L. Si x no aparece libre en B entonces cualquiertérmino es libre para x en B.Sea t cualquier término tal que t� x, entonces t no aparece ligado, si t=x entoncespor Proposición 1.17(c) t es libre para x enB, entonces cualquier término es librepara x enB.

2.4 Ejercicio.Sea L un lenguaje de primer orden. Indique si las siguientes afirmaciones sonciertas o no. En cada caso, dé una justificación.

(i) Si B es una fórmula de L entoces x no es libre en ∀xB.

Verdad porque x esta ligado de ∀x .

20

(ii) Considerando la fórmula ∀xB, se puede concluir que x no es libre en B.

Verdad porque x estaría ligada en B.

(iii) Si z no figura libre en la fórmula B, entonces en ∃zB no aparecen nuevasvariables ligadas.Verdad porque ∃z solo afectaría a z pero z ya estaba ligada a B.

2.5 Ejercicio.

(a) ⊢K(∀xB) ⇒ ∃xB

1. ∀xB⇒B (K.1a)2. B⇒∃x (K.1c)3. ∀xB⇒∃xB 1,2(L.1)

(b) Si x no es libre en C, entonces ⊢K(∀x(B ⇒ C)) ⇒ ((∃x) ⇒ C)

1. (∀x(¬C⇒¬B))⇒ (¬C⇒∀x¬B) (A.6) x no es libre en ¬C

2. (∀x(¬¬B⇒¬¬C))⇒ (¬∀x¬B⇒¬¬C) 1(L.17f)3. (∀x(B⇒C))⇒ (¬∀x¬B⇒C) Doble neg.3. (∀x(B⇒C))⇒ ((∃x)⇒C) def ∃

(c) ⊢K(∀xB) ⇔ ¬(∃x(¬B))

1. ¬(∃x(¬B))⇔¬(∃x(¬B)) (L.16a)2. ∀x¬¬B⇔¬(∃x(¬B)) (K.3c)3. (∀xB)⇔¬(∃x(¬B)) Doble neg.

2.6 Ejercicio.

(a) ⊢K (∀xB) ⇒ ∀x(B ∨ C) (b) ⊢K(∃xC)⇒∃x(B ⇒ C)

1. B⇒ (B ∨C) (A.2) 1. C⇒ (¬B ∨C) (L.2)2. ∀xB⇒∀x(B ∨C) 1(K.2a) 1. C⇒ (B⇒C) def⇒

2. (∃xC)⇒∃x(B⇒C) (K.2b)

(c) ⊢K ∃x(B ⇒ ¬(C ∨ D)) ⇔ ∃x(B ⇒ (¬C ∧ ¬D))

1. (B⇒¬(C ∨D))⇔ (B⇒¬(C ∨D)) (L.16a)2. (B⇒¬(C ∨D))⇔ (B⇒ (¬C ∧¬D)) 1 D’Morgan3. ∃x(B⇒¬(C ∨D))⇔∃x(B⇒¬(C ∨D)) (K.2d)

21

(d) ⊢K(∀x(B ⇒ ¬C)) ⇔ ¬∃x(B ∧ C)

1. (B⇒¬C)⇔ (B⇒¬C) (L.16a)1. (B⇒¬C)⇔ (¬B ∨¬C) def⇒2. (B⇒¬C)⇔¬(B ∧C) 1D’Morgan3. ∀x(B⇒¬C)⇔∀x¬(B ∧C) 2 (K.2c)4. ∀x(B⇒¬C)⇔¬∃x(B ∧C) 3 (K.3)

(e) ⊢K[∀y1∀yn

B] ⇒ B

Por inducción sobre n

n =1 “vale para una variable” ⊢K(∀y1B)⇒B

por Hipótesis Inductiva tenemos que “vale para n variables ⇒vale para n+1”H.I = [∀yn

∀yn−1∀y1

B]⇒BPaso inductivo[∀yn+1

∀yn∀yn−1

∀y1B]⇒∀yn+1

B (K.2a)[∀yn+1

B]⇒B (K.1a)[∀yn+1

∀yn∀yn−1

∀y1B]⇒B “Transitividad” (L.1)

deducimos ⊢K[∀y1∀yn

B]⇒B

2.7 Ejercicio.Sea B una fórmula donde x no es libre.

(a) ⊢K(∀xB) ⇔ B (b) ⊢K(∃xB) ⇔ B

1. B⇒B (L.3) 1. ¬B⇒¬B (L.3)2. ∀x(B⇒B) 1(GEN) 2. ∀x(¬B⇒¬B) 1(GEN)3. ∀x(B⇒B)⇒ (B⇒∀xB) (A.6)xnoes libreenB 3.∀x(¬B⇒¬B)⇒ (¬B⇒∀x¬B) (A.6)4. B⇒∀xB 2,3(M.P.) 4. ¬B⇒∀x¬B 2,3(M.P.)5. ∀xB⇒B (K.1) 5. ¬∀x¬B⇒¬¬B 4(L.7)M.P.6. ∀xB⇔B 4,5 (L.14b) 6. ¬∀x¬B⇒B Doble neg.

6. (∃xB)⇒B def ∃7. B⇒∃xB (K.1c)8. (∃xB)⇔B 6,7(L.14b)

2.8 Ejercicio.Decimos que las fórmulas B(x) yB(y) son similares si ambas tienen la mismaestructura y se diferencian solo que en donde aparece x libre en B(x), aparecey libre en B(y), y viceversa. Si B(x),B(y) son similares, entonces

(a) ⊢K(∀xB(x)) ⇔ (∀yB(y))

1. ∀xB(x) (hip)2. (∀xB(x))⇒B(y) (A.5) y es libreparax enB(x)porser similares

3. B(y) 1,2(M.P)4. ∀yB(y) 3(GEN)hemos probado (∀xB(x))⊢K (∀yB(y))5. (∀xB(x))⇒ (∀yB(y)) T.Deducción porser similares y noes libreenB(x)ni tampoco∀xB(x) .

22

6. ∀yB(y) (hip)7. (∀yB(y))⇒B(x) (A.5) x es librepara y enB(y)porser similares

8. B(x) 1,2(M.P)9. ∀xB(x) 3(GEN)hemos probado (∀yB(y))⊢K (∀xB(x))10. (∀yB(y))⇒ (∀xB(x)) T.Deducción por ser similaresxnoes libreenB(y)ni tampoco∀yB(y) .

11. (∀xB(x))⇔ (∀yB(y)) 5,10(L.14b)

(b) ⊢K(∃xB(x)) ⇔ (∃yB(y))

1. ∃xB(x)⇔¬(∀x(¬B(x))) def ∃2. ∃xB(x)⇔¬(∀y(¬B(y))) ejerc 2.8 (a) B(x) yB(y) sonsimilares

2. ∃xB(x)⇔∃yB(y) def ∃

2.9 Ejercicio.(a) Si x no es libre en B , entonces

(i) ⊢K(∀x(B ⇒ C)) ⇔ (B ⇒ ∀xC) (ii) ⊢K(∃x(B ⇒ C)) ⇔ (B ⇒ ∃xC)

1. ∀x(¬B ∨C)⇔ (¬B ∨∀xC) (K.7a) 1. ∃x(¬B ∨C)⇔ (¬B ∨∃xC) (K.7d)1. ∀x(B⇒C)⇔ (B⇒∀xC) def ⇒ 1. ∃x(B⇒C)⇔ (B⇒∃xC) def ⇒

2.10 Ejercicio.RST:• No es valido porque en el paso 4 se viola la definicion 3 al aplicar la escogencia “d”cuando ya se tomo en ∃x(B(x)⇒C(x)).Un ejemplo para verificar que (∃x(B⇒C))⇒ ((∃xB)⇒∃xC) no es lógicamente validaseria B8 (x =1) y C: =(x� x)(∃x((x =1)⇒ (x� x)))⇒ ((∃x(x =1))⇒∃x(x� x))

↓ l ↓ l ↓ l ↓f v v f v f f

2.11 Ejercicio.

(a) (K.6a) ⊢K(∃x(B ∧ C)) ⇒ ((∃xB) ∧ (∃xC))

1. ∃x(B ∧C) (hip)2. B(c)∧C(c) Regla C3. B(c) 2(L.15a)M.P.4. B(c)⇒∃xB(x) (K.1b)5. ∃xB(x) 3,4(M.P)6. C(c) 2(L.15b)M.P.7. C(c)⇒∃xC(x) (K.1b)8. ∃xC(x) 6,7(M.P)9. (∃xB(x))∧ (∃xC(x)) 5,8(L.14a)10. (∃xB)∧ (∃xC) Notación11. (∃x(B ∧C))⇒ ((∃xB)∧ (∃xC)) T.Deducción (no se iutilizo GEN en la prueba)

23

(K.6b) ⊢K((∀xB) ∨ (∀xC)) ⇒ (∀x(B ∨ C))

1. (∃x(¬B ∧¬C))⇒ ((∃x¬B)∧ (∃x¬C)) (K.6a)2. ¬((∃x¬B)∧ (∃x¬C))⇒¬∃x(¬B ∧¬C) (L.7)M.P3. (¬(∃x¬B)∨¬(∃x¬C))⇒∀x¬(¬B ∧¬C) D’Morgan (K.3)4. ((∀x¬¬B)∨ (∀x¬¬C))⇒∀x(¬¬B ∨¬¬C) (K.3)D’Morgan5. ((∀xB)∨ (∀xC))⇒ (∀x(B ∨C)) Doble neg.

(b) Si x no es libre en B

(K.7b) (K.7c)⊢K (∀x(B ∧ C)) ⇔ (B ∧ ∀xC) ⊢K (∃x(B ∧ C)) ⇔ (B ∧ ∃xC)

1. ∀x(B ∧C)⇔ ((∀xB)∧ (∀xC)) (K.5a) 1. ∀x(¬B ∨¬C)⇔ (¬B ∨ (∀x¬C)) (K.7a)2. ∀x(B ∧C)⇔ (B ∧ (∀xC)) (K.4a(i)) 2. ∀x¬(B ∧C)⇔ (¬B ∨ (¬∃xC)) D’Morgan(K.3)

3. ¬∃x(B ∧C)⇔¬(B ∧ (∃xC)) (K.3)D’Morgan4. ¬¬∃x(B ∧C)⇔¬¬(B ∧ (∃xC)) (K.16d)5. ∃x(B ∧C)⇔ (B ∧ (∃xC)) Doble neg.

2.12 Ejercicio.Sea E(x, y) una fórmula cuyas variables libres son las señaladas y tal quesustituciones de x ó y por x, y ó z son permitidas. Demotrar que

(a) ⊢K(∀x∀yE(x, y)) ⇒ ∀xE(x, x)

1. (∀x∀yE(x, y)) (hip)2. (∀x∀yE(x, y))⇒ (∀yE(x, y)) (K.1a)3. (∀yE(x, y)) (M.P)4. (∀yE(x, y))⇒E(x, x) (A.5)5. E(x, x) (M.P)6. ∀xE(x, x) (GEN)7. (∀x∀yE(x, y))⇒∀xE(x,x)1,6(T.Deducción)x y y son variables ligadas en ∀x∀yE(x, y)

(b) ⊢K [∀x∀y(E(x, y) ⇒ ¬E(y, x))] ⇒ ¬∀xE(x, x)

1. ∀x∀y(E(x, y)⇒¬E(y, x)) (hip)1. ∀x∀y(¬E(x, y)∨¬E(y, x)) def⇒2. ∀y(¬E(x, y)∨¬E(y, x)) 1(K.1a)M.P3. ¬E(x, y)∨¬E(y, x) 2(K.1a)M.P4.1. ¬E(x, y) (hip)4.2. ¬E(x, y)⇒∃x¬E(x, x) 4.1 (K.1b)4.3. ∃x¬E(x, x) 4.1, 4.2 (M.P)4. ¬E(x, y)⇒∃x¬E(x, x) 4.1, 4.3 T.Deducción. noseutilizoGENenlaprueba

5.1. ¬E(y, x) (hip)5.2. ¬E(y, x)⇒∃x¬E(x, x) (K.1b)

24

5.3. ∃x¬E(x, x) 5.1, 5.2 (M.P)5. ¬E(y, x)⇒∃x¬E(x, x) 5.1, 5.3 T.Deducción. noseutilizoGENenlaprueba

6. ∃x¬E(x, x) 3, 4, 5 (L.9)7. ¬∀xE(x, x) 6 (K.3)hemos probado sin aplicar GEN en la prueba[∀x∀y(E(x, y)⇒¬E(y, x))]⊢K ¬∀xE(x, x)

8. [∀x∀y(E(x, y)⇒¬E(y, x))]⇒¬∀xE(x, x) T.Deducción.

(c) ⊢K ∀x(E(x, x) ⇒ ∃yE(x, y))

1. ∀y¬E(x, y)⇒¬E(x, x) (A.5)2. ¬¬E(x, x)⇒¬∀y¬E(x, y) 1(L.7)M.P3. E(x, x)⇒∃yE(x, y) Doble neg. (K.3)4. ∀x(E(x, x)⇒∃yE(x, y)) 3(GEN)

(d) ⊢K [(∀x∀y(E(x, y) ⇒ E(y, x))) ∧ (∀x∀y∀z((E(x, y) ∧ E(y, z)) ⇒ E(x, z)))]

⇒∀x∀y(E(x, y) ⇒ E(x, x))

1. (E(x, y)⇒E(y, x))∧∀z((E(x, y)∧E(y, z))⇒E(x, z)) (hip)2. E(x, y) (hip)3. E(x, y)⇒E(y, x) 1 (L.15a)M.P.4. E(y, x) 2,3 (M.P)5. ∀z((E(x, y)∧E(y, z))⇒E(x, z)) 1.(L,15b)M.P.6. (E(x, y)∧E(y, x))⇒E(x, x) 5,(A.5)M.P.x libre

7. (E(y, x)∧E(x, y))⇒E(x, x) 6(L.17e)8. E(y, x)⇒ [E(x, y)⇒E(x, x)] 7(L.19g)9. E(x, y)⇒E(x, x) 4,8(M.P)10. E(x, x) 2,9(M.P)hemos probado(E(x, y)⇒E(y, x))∧∀z((E(x, y)∧E(y, z))⇒E(x, z)), E(x, y) ⊢K E(x, x)como no utilizamos GEN en la prueba por T.Deducción tenemos(E(x, y)⇒E(y, x))∧∀z((E(x, y)∧E(y, z))⇒E(x, z))⊢K E(x, y)⇒E(x, x)utilizando T.Deducción por segunda vez, se sigue11. ⊢K[(E(x, y)⇒E(y, x))∧∀z((E(x, y)∧E(y, z))⇒E(x, z))]⇒ (E(x, y)⇒E(x, x))12. ∀x∀y[(E(x, y)⇒E(y, x))∧∀z((E(x, y)∧E(y, z))⇒E(x, z))]

⇒∀x∀y(E(x, y)⇒E(x, x)) 11(K.2a)13. [(∀x∀y(E(x, y)⇒E(y, x)))∧ (∀x∀y∀z((E(x, y)∧E(y, z))⇒E(x, z)))]

⇒∀x∀y(E(x, y)⇒E(x, x)) 12(K.5a)

(e) ⊢K ¬∃y∀x(E(x, y) ⇔ ¬E(x, x))

1. ¬¬∀x(E(x, y)⇔¬E(x, x)) HIP de R.A2. ∀x(E(x, y)⇔¬E(x, x)) 1 D. Neg.3. ∀x(E(x, y)⇔¬E(x, x))⇒ (E(y, y)⇔¬E(y, y)) (A.5)

25

4. (E(y, y)⇔¬E(y, y)) 2, 3(M.P)5. E(y, y)∧¬E(y, y) tautología (B⇔¬B)⇔ (B∧¬B)Hemos probado ¬¬∀x(E(x, y)⇔¬E(x, x))⊢K E(y, y)∧¬E(y, y) sin utilizar (GEN).luego, por Reducción al Absurdo, se sigue6. ⊢K ¬∀x(E(x, y)⇔¬E(x, x))7. ∀y¬∀x(E(x, y)⇔¬E(x, x)) 5(GEN)8. ¬∃y∀x(E(x, y)⇔¬E(x, x)) 6(K.3)

(f) Relacionar el inciso anterior con la paradoja del barbero y la paradoja de Russel.

• Sea E(x, y)8 “y afeita a x”, donde y es el barbero;No existe un barbero que afeite a las personas que no se afeitan a si mismas.

• Sea E(x, y)8 (x∈ y)No existe un x, que cumpla que si x∈ y equivale x � x

2.13 Ejercicio.

(a) ⊢K[(∃xB) ⇒ ∀xC] ⇒ ∀x(B ⇒ C) (b) ⊢K (∃x(B ⇒ C)) ⇔ ((∀xB) ⇒ ∀xC)

1. (∃xB)⇒∀xC (hip) 1. ∃x(¬B ∨C)⇔ ((∃x¬B)∨ (∃xC)) (K.5b)1. ¬(∃xB)∨∀xC def⇒ 2. ∃x(¬B ∨C)⇔ ((¬∀xB)∨ (∃xC)) 1(K.3)2. (∀x¬B)∨∀xC 1(K.3) 2. ∃x(B⇒C)⇔ ((∀xB)⇒ (∃xC)) def⇒3. ∀x(¬B ∨C) 2(K.6)M.P.3. ∀x(B⇒C) def⇒4. [(∃xB)⇒∀xC]⇒∀x(B⇒C) 1,3 T.D

(c)⊢K(∀x(B ⇒ C)) ⇒ (∀xB ⇒ ∀xC) (d)⊢K(∀x(B ⇒ C)) ⇒ ((∀x¬C) ⇒ ∀x¬B)

1. ∀x(B⇒C) (hip) 1. ∀x(B⇒C) (hip)2. ∀xB (hip) 2. ∀x(¬C ⇒¬B) 1(L.17f)3. (B⇒C) 1(K.1a)M.P 3. (∀x¬C)⇒ (∀x¬B) 2, (Ejer.2.13c)M.P4. B 2(K.1a)M.P 4. (∀x(B⇒C))⇒ ((∀x¬C)⇒∀x¬B) 1,3 T.D5. C 4,3(M.P)6. ∀xC 5(GEN) (f) ⊢K((∃xB) ⇒ C) ⇒ ((∀xB) ⇒ ∃xC)7. (∀x(B⇒C))⊢K ∀xB⇒ (∀xC) T.D 1. (∃xB)⇒C (hip)8. ⊢K(∀x(B⇒C))⇒ (∀xB⇒∀xC) T.D 2. ∀xB (hip)todas las variables estaban ligadas 3. B 2(K.1a)M.P

4. B⇒∃xB (K.1c)

(e) ⊢K ∃y(B ⇒ ∀yB) 5. ∃xB 3,4(M.P)6. C 5,1(M.P)

1. (∀yB)⇒∃y(∀yB) (K.1c) 7. C⇒∃xC (K.1c)1. ¬(∀yB)∨∃y(∀yB) def⇒ 8. ∃xC 6,7(M.P)2. (∃y¬B)∨∃y(∀yB) 1(K.3) ((∃xB)⇒C), ((∀xB)⊢K ∃xC)3. ∃y(¬B ∨ (∀yB)) 2 (K.5b) 9. ((∃xB)⇒C)⊢K ((∀xB)⇒∃xC) T.D3. ∃y(B⇒ (∀yB)) def⇒ 10. ((∃xB)⇒C)⇒ ((∀xB)⇒∃xC) T.D

26

(g)⊢K[(∀x(B ⇒ (C ∨ D))) ∧ ¬∀x(B ⇒ C)] ⇒ ∃x(B ∧ D) (h)⊢K(∀x∃xB ⇔ ∃xB)

1. (∀x(B⇒ (C ∨D)))∧¬∀x(B⇒C) (hip) 1. ∀x∃xB (hip)2. ¬∀x(B⇒C) 1(L.15b)M.P 2. ∀x∃xB⇒∃xB (K.1a)3. ∃x(B ∧¬C) 2(K.3)(L.19e) 3. ∃xB 1,2(M.P)4. B(c)∧¬C(c) 3 Regla C 4. ∀x∃xB⇒∃xB 1,3 T.D5. ∀x(B⇒ (C ∨D)) 1(L.15a)M.P 5. ∃xB (hip)6. B(c)⇒ (C(c)∨D(c)) 5(A.5)c libre M.P 6. ∀x∃xB 5(GEN)6. B(c)⇒ (¬C(c)⇒D(c)) def⇒ 7. ∃xB⇒∀x∃xB 5,7 T.D7. (B(c)∧¬C(c))⇒D(c) 6(L.19g) 8.∀x∃xB⇔∃xB 4,7(L.14b)8. D(c) 4,7(M.P)9. B(c) 4(L.15a)M.P10. B(c)∧D(c) 9,8(L.14a)11. B(c)∧D(c)⇒∃x(B(x)∧D(x)) (K.1b)12. ∃x(B(x)∧D(x)) 10, 11(M.P)12. ∃x(B ∧D) Notación13.[(∀x(B⇒ (C ∨D)))∧¬∀x(B⇒C)]⇒∃x(B ∧D) 1,12 T.D

(i) ⊢K(∀x((∀xB) ∨ C)) ⇔ ((∀xB) ∨ (∀xC))

1. (∀x((∀xB)∨C))⇔ (∀x((∀xB)∨C)) (L.16a)2. (∀x((∀xB)∨C))⇔ ((∀xB)∨ (∀xC)) (K.7a) xnoes libre en∀xB

(j) ⊢K(∃x((∀xB) ∧ C)) ⇔ ((∀xB) ∧ (∃xC))

1. (∃x((∀xB)∧C))⇔ (∃x((∀xB)∧C)) (L.16a)2. (∃x((∀xB)∧C))⇔ ((∀xB)∧ (∃xC)) (K.7c) xnoes libreen∀xB

(k) ⊢K(∀x(B ∨ C)) ⇒ ((∀xB) ∨ (∃xC))

1. ∀x(B ∨C) (hip)2. ∀x(B ∨C)⇒ (B ∨C) (K.1a)3. (B ∨C) 1,2(M.P)3. ¬B⇒C def⇒4. ∃x¬B⇒∃xC 3(K.2b)5. ¬∀xB⇒∃xC 4(K.3)6. ∀xB ∨∃xC def⇒Doble Neg.7. (∀x(B ∨C))⇒ ((∀xB)∨ (∃xC)) T.Deducción

(l) ⊢K ((∃xB) ∧ (∀xC)) ⇒ ∃x(B ∨ C)

1. (∀x(¬B ∨¬C))⇒ ((∀x¬B)∨ (∃x¬C)) (Ejer 2.13.k)2. ¬((∀x¬B)∨ (∃x¬C))⇒¬(∀x(¬B ∨¬C)) 1 (L.7)M.P3. (¬(∀x¬B)∧¬(∃x¬C))⇒¬(∀x¬(B ∧C)) 2D’Morgan3. ((∃xB)∧¬(∃x¬C))⇒ (∃x(B ∧C)) def ∃4. ((∃xB)∧ (∀xC))⇒ (∃x(B ∧C)) 3(K.3) Doble Neg.

27

2.14 Ejercicio.Si x no es libre en C y y no es libre en B.

(a) ⊢K(∀x∀y(B ∧ C)) ⇔ ((∀xB) ∧ ∀yC)

1. (∀x∀y(B ∧C))⇔ (∀x∀y(B ∧C)) (L.16a)2. (∀x∀y(B ∧C))⇔ (∀x(B ∧∀yC)) 1(K.7b) y no libre en B3. (∀x∀y(B ∧C))⇔ (∀x(∀yC ∧B)) 2(L.17e)4. (∀x∀y(B ∧C))⇔ (∀yC ∧∀xB) 3(K.7b) x no libre en C5. (∀x∀y(B ∧C))⇔ ((∀xB)∧∀yC) 4(L.17e)

(b) ⊢K(∃x∃y(B ∧ C)) ⇔ ((∃xB) ∧ ∃yC)

1. (∃x∃y(B ∧C))⇔ (∃x∃y(B ∧C)) (L.16a)2. (∃x∃y(B ∧C))⇔ (∃x(B ∧∃yC)) 1(K.7c) y no libre en B3. (∃x∃y(B ∧C))⇔ (∃x(∃yC ∧B)) 2(L.17e)4. (∃x∃y(B ∧C))⇔ (∃yC ∧∃xB) 3(K.7c) x no libre en C5. (∃x∃y(B ∧C))⇔ ((∃xB)∧∃yC) 4(L.17e)

(c) ⊢K (∀x∃y(B ∨ C)) ⇔ ((∀xB) ∨ ∃yC)

1. (∀x∃y(B ∨C))⇔ (∀x∃y(B ∨C)) (L.16a)2. (∀x∃y(B ∨C))⇔ (∀x(B ∨∃yC)) (K.7d) y no libre en B3. (∀x∃y(B ∨C))⇔ (∀x(∃yC ∨B)) 2(L.17d)4. (∀x∃y(B ∨C))⇔ (∃yC ∨∀xB) 3(K.7a) x no libre en C5. (∀x∃y(B ∨C))⇔ ((∀xB)∨∃yC) 4(L.17d)

2.15 Ejercicio.Sea Γ un conjunto de hipótesis.

(a) Si B es una sentencia y C es una fórmula tal que Γ, B ⊢K C ,

entonces Γ ⊢K B ⇒ C.Como B no tiene variables libres por ser sentencia, podemos aplicar Teorema deDeducción y tenemos Γ⊢KB⇒C.

(b) Si Γ, B, ¬C⊢K D ∧ ¬D en cuya prueba no se utiliza (GEN) sobrevariables libres de B y de C, entonces Γ ⊢K B ⇒ C.Como no se utiliza (GEN) sobre variables libres; Sea ¬C la Hipótesis de Reduccuiónal Absurdo por T.R.A tenemos Γ,B ⊢K C y T.Deducción Γ⊢KB⇒C.

28

2.16 Ejercicio.Sea C una sentencia tal que C no se puede demostrar en K. Justificar:

(a) K es consistente.Supongamos que K es inconsistente, luego K demuestra cualquier fórmula,particularmente Γ⊢K C, pero por hipótesis C no es demostrable en K, luegoentonces decimos que K es consistente.

(b) La teoría que resulta de añadir ¬C alos axiomas de K es consistente.Supongamos que K∪{¬C}⊢ C es inconsistente, entonces demuestra cualquier fórmulaparticularmente K∪{¬C}⊢ C y K∪{¬C}⊢¬C como C es una sentencia, por Teoremade Deducción tenemos

1. K ⊢¬C⇒¬C2. K ⊢¬C⇒C3. ¬¬C⇒¬¬C 1 (L.7)M.P4. ¬C ⇒¬¬C 2 (L.7)M.P5. K ⊢¬C ∨¬¬C (L.5)6. ¬¬C 3,4,5(L.9)7. C Doble Neg.

Por hipótesis C nose demuestra en K,por tantoK∪{¬C} esconsistente

2.17 Ejercicio.

(a) C ⊢K

(

∀x

B

)

C

1. C (hip)2. B⇒C 1(L.4)

3.(

∀x

B

)

C Proposición4.3

2.18 Ejercicio.

(a) Sea t libre para x enByC(K.10a) (K.10b)

⊢K

(

B(t) ∧

(

∀x

B(x)

)

C(x))

⇒ C(t) ⊢K

(

B ∧

(

∀x

B

)

C)

⇒ C

1. B(t)∧(

∀x

B(x)

)

C(x) (hip) 1.(

B(x)∧(

∀x

B(x)

)

C(x))

⇒C(x) (K.10a)

2. B(t) (L.15a)M.P x libreparaByC

3.(

∀x

B(x)

)

C(x) (L.15b)M.P 1.(

B ∧(

∀x

B

)

C)

⇒C Notación

3. ∀x(B(x)⇒C(x)) def(

∀x

B

)

4. ∀x(B(x)⇒C(x))⇒ (B(t)⇒C(t)) (A.5)5. (B(t)⇒C(t)) 3,4(M.P)6. C(t) 2,5(M.P)como no se utilizo GEN por T.D. tenemos

7.(

B(t)∧(

∀x

B(x)

)

C(x))

⇒C(t)

29

(K.10c) (K.10d)

⊢K(B(t) ∧ C(t)) ⇒

(

∃x

B(x)

)

C(x) ⊢K(B ∧ C) ⇒

(

∃x

B

)

C

1. B(t)∧C(t) (hip) 1.(B(x)∧C(x))⇒(

∃x

B(x)

)

C(x) (K.10c)

2. (B(t)∧C(t))⇒∃x(B(x)∧C(x)) (K.1b) x libreparaByC

3. ∃x(B(x)∧C(x)) 1,2(M.P) 1. (B ∧C)⇒(

∃x

B

)

C Notación

4.(

∃x

B(x)

)

C(x) 3(K.9)

como no se utilizo GEN por T.D.tenemos

5. (B(t)∧C(t))⇒(

∃x

B(x)

)

C(x)

(b)⊢K(∃xB) ⇒

[((

∀x

B

)

C)

⇒

(

∃x

B

)

C]

(c) ⊢K

((

∃x

B

)

C)

⇔

(

∃x

C

)

B

1. ∃xB (hip) 1. (B ∧C)⇔ (C ∧B) (L.17e)

2.(

∀x

B

)

C (hip) 2. ∃x(B ∧C)⇔∃x(C ∧B) 1(K.2d)

3. B(c) 1 Regla C 3.((

∃x

B

)

C)

⇔(

∃x

C

)

B 2(K.9)

4. ∀x(B⇒C) 2 def(

∀x

B

)

5. B(c)⇒C(c) (A.5)M.Pc libreenxparaB

6. C(c) 3,5(M.P)7. B(c)∧C(c) 3,6(L.14a)8. (B(c)∧C(c))⇒∃x(B(x)∧C(x))(K.1b)9. ∃x(B(x)∧C(x)) 7,8(M.P)

10(

∃x

B

)

C 9(K.9)

como no se utilizo GEN por T.D. 2 veces

11. (∃xB)⇒[((

∀x

B

)

C)

⇒(

∃x

B

)

C]

2.19 Ejercicio.(a)(K.11b)B ⇒ (C ⇒ D) ⊢K

((

∃x

B

)

C ⇒

(

∃x

B

)

D)

1. B⇒ (C⇒D) (hip)2. B⇒ (¬D⇒¬C)3. (B⇒¬D)⇒ (B⇒¬C) 2 Resultado de L4. ∀x(B⇒¬D)⇒∀x(B⇒¬C) 3(K.2a)

4.(

∀x

B

)

¬D⇒(

∀x

B

)

¬C def.(

∀x

B

)

5. ¬(

∀x

B

)

¬C⇒¬(

∀x

B

)

¬D 4(L.7)M.P

6.(

∃x

B

)

C⇒(

∃x

B

)

D

30

(K.11d) (K.11e)

B ⇒ (C ⇔ D) ⊢K

((

∃x

B

)

C)

⇔

(

∃x

B

)

D C ⇒ D ⊢K

((

∀x

B

)

C)

⇒

(

∀x

B

)

D

1. B⇒ (C⇔D) (hip) 1. C⇒D (hip)2. B⇒ (¬C⇔¬D) 1(L.16d) 2. (¬B ∨C)⇒ (¬B ∨D) 1(A.4)M.P

3.((

∀x

B

)

¬C)

⇔(

∀x

B

)

¬D 2(K.11c) 2. (B⇒C)⇒ (B⇒D) def ⇒

4.(

¬(

∀x

B

)

¬C)

⇔¬(

∀x

B

)

¬D 3(L.16d) 3. ∀x(B⇒C)⇒∀x(B⇒D) 2(K.2a)

5.((

∃x

B

)

C)

⇔(

∃x

B

)

D def(

∃x

B

)

4.((

∀x

B

)

C)

⇒(

∀x

B

)

D def(

∀x

B

)

(K.11g) (K.11h)

C ⇔ D ⊢K

((

∀x

B

)

C)

⇔

(

∀x

B

)

D C ⇔ D ⊢K

((

∃x

B

)

C)

⇔

(

∃x

B

)

D

1. C⇔D (hip) 1. C⇔D (hip)2. B⇒ (C⇔D) 1(L.4) 2. B⇒ (C ⇔D) 1(L.4)

3.((

∀x

B

)

C)

⇔(

∀x

B

)

D 2(K.11c) 3.((

∃x

B

)

C)

⇔(

∃x

B

)

D 2(K.11d)

(b) B ⇒ C ⊢K

((

∀x

C

)

D)

⇒

(

∀x

B

)

D (c) B ⇒ C ⊢K

((

∃x

B

)

D)

⇒

(

∃x

C

)

D

1. B⇒C (hip) 1. B⇒C (hip)2. ¬C ⇒¬B 1(L.7)M.P 2. ¬C ⇒¬B 1(L.7)M.P3. (D ∨¬C)⇒ (D ∨¬B) 2(A.4)M.P 3. (¬D ∨¬C)⇒ (¬D ∨¬B) 2(A.4)M.P4. (¬C ∨D)⇒ (¬B ∨D) 3(L.17d) 4.¬(¬D∨¬B)⇒¬(¬D ∨¬C) 3(L.7)M.P5. ∀x(¬C ∨D)⇒∀x(¬B ∨D) 4(K.2a) 4. (D ∧B)⇒ (D ∧C) def ∧5. ∀x(C⇒D)⇒∀x(B⇒D) def ⇒ 5. (B ∧D)⇒ (C ∧D) 4(L.17e)

6.((

∀x

C

)

D)

⇒(

∀x

B

)

D def(

∀x

B

)

6. ∃x(B ∧D)⇒∃x(C ∧D) 5(K.2b)

7.((

∃x

B

)

D)

⇒(

∃x

C

)

D 6(K.9)

(d) B ⇔ C ⊢K

((

∀x

B

)

D)

⇔

(

∀x

C

)

D (e) B ⇔ C ⊢K

((

∃x

B

)

D)

⇔

(

∃x

C

)

D

1. B⇔C (hip) 1. B⇔C (hip)2. B⇒C 1(L.15c)M.P 2. B⇒C 1(L.15d)M.P

3.(

∀x

C

)

D⇒(

∀x

B

)

D 2(Ejerc.2.19b) 3.(

∃x

B

)

D⇒(

∃x

C

)

D 2(Ejerc.2.19c)

4. C⇒B 1(L.15d)M.P 4. C ⇒B 1(L.15d)M.P

5.(

∀x

B

)

D⇒(

∀x

C

)

D 4(Ejerc.2.19b) 5.(

∃x

C

)

D⇒(

∃x

B

)

D 4(Ejerc.2.19c)

6.((

∀x

B

)

D)

⇔(

∀x

C

)

D 3,5(L.14b) 6.((

∃x

B

)

D)

⇔(

∃x

C

)

D 3,5(L.14b)

31

2.20 Ejercicio.Sea Γ un conjunto de fórmulas, Si existe una fórmula D tal que Γ,B,¬C ⊢KD∧¬Dy en esta prueba no se utiliza generalización sobre variables libres de B y C, entonces

Γ⊢K

(

∀x

B

)

C.

• Tenemos Γ,B,¬C ⊢KD∧¬D donde ¬C es una Hipótesis de reducción al Absurdo,por Teorema de Reducción al Absurdo Γ,B ,⊢K C, luego por la proposición 4.3tenemos Γ⊢K

(

∀x

B

)

C.

2.21 Ejercicio.Sea B(x) similar a B(y) y C(x) similar a C(y).

(a) ⊢K

((

∀x

B(x)

)

C(x))

⇔

(

(

∀y

B(y)

)

C(y)

)

1. ∀x(B(x)⇒C(x))⇔∀y(B(y)⇒C(y)) (K.4b(i)) por ser similares

2.((

∀x

B(x)

)

C(x))

⇔

(

(

∀y

B(y)

)

C(y)

)

1 def(

∀x

B

)

(b) ⊢K

((

∃x

B(x)

)

C(x))

⇔

(

(

∃y

B(y)

)

C(y)

)

1. ∃x(B(x)∧C(x))⇔∃y(B(y)∧C(y)) (K.4b(ii)) por se similares

2.((

∃x

B(x)

)

C(x))

⇔

(

(

∃y

B(y)

)

C(y)

)

1(K.9)

2.22 Ejercicio.(a)

(K.13b) ⊢K(∃xB) ⇒

[((

∃x

B

)

C)

⇔ C]

1. (∃xB)⇒[((

∀x

B

)

¬C)

⇔¬C]

(K.13a)

2. (∃xB)⇒[(

¬(

∀x

B

)

¬C)

⇔¬¬C]

1(L.16d)

3. (∃xB)⇒[((

∃x

B

)

C)

⇔C]

def(

∃x

B

)

, Doble neg.

(b)

(K.15a) ⊢K

((

∃x

B

)

(C ∧ D))

⇒

(((

∃x

B

)

C)

∧

(

∃x

B

)

D)

1.(

∃x

B

)

(C ∧D) (hip)

2. ∃x(B ∧ (C ∧D)) 1(K.9)3. ∃x((B ∧C)∧ (B ∧D)) tautología4. ∃x((B ∧C)∧ (B ∧D))⇒ (∃x(B ∧C)∧∃x(B ∧D)) (K.6a)5. ∃x(B ∧C)∧∃x(B ∧D) 3,4(M.P)

6.((

∃x

B

)

C)

∧(

∃x

B

)

D 5(K.9)

7.((

∃x

B

)

(C ∧D))

⇒((

(

∃x

B

)

C)

∧(

∃x

B

)

D)

1,6 T.Deducción

32

(K.15b) ⊢K

(((

∀x

B

)

C)

∨

(

∀x

B

)

D)

⇒

(

∀x

B

)

(C ∨ D)

1.(

∃x

B

)

(¬C ∧¬D)⇒((

(

∃x

B

)

¬C)

∧(

∃x

B

)

¬D)

(K.15a)

2. ¬[((

∃x

B

)

¬C)

∧((

∃x

B

)

¬D)]

⇒¬(

∃x

B

)

(¬C ∧¬D) 1(L.7)M.P

3.[

¬((

∃x

B

)

¬C)

∨¬((

∃x

B

)

¬D)]

⇒(

∀x

B

)

¬(¬C ∧¬D) 2,D’Morgan(K.3)

4.[((

∀x

B

)

¬¬C)

∨((

∀x

B

)

¬¬D)]

⇒(

∀x

B

)

(¬¬C ∨¬¬D) 3,(K.3)D’Morgan

5.[((

∀x

B

)

C)

∨((

∀x

B

)

D)]

⇒(

∀x

B

)

(C ∨D) 4 Doble neg.

(c) Sea x una variable que no es libre en C.

(K.16b) ⊢K(∃xB) ⇒

[((

∀x

B

)

(C ∧ D))

⇔

(

C ∧

(

∀x

B

)

D)]

1. ∃xB (hip)

2.((

∀x

B

)

(C ∧D))

⇔((

∀x

B

)

C ∧(

∀x

B

)

D)

(K.14a)

3.((

∀x

B

)

(C ∧D))

⇔(

C ∧(

∀x

B

)

D)

1,2(K.13a)

4. (∃xB)⇒[((

∀x

B

)

(C ∧D))

⇔(

C ∧(

∀x

B

)

D)]

1,3T.Deducción

(K.16c) ⊢K

((

∃x

B

)

(C ∧ D))

⇔

(

C ∧

(

∃x

B

)

D)

1.((

∀x

B

)

(¬C ∨¬D))

⇔(

¬C ∨(

∀x

B

)

¬D)

(K.16a)

2. ¬((

∀x

B

)

(¬C ∨¬D))

⇔¬(

¬C ∨(

∀x

B

)

¬D)

(L.16a)

3.((

∃x

B

)

¬(¬C ∨¬D))

⇔(

¬¬C ∧¬(

∀x

B

)

¬D)

(K.3)D’Morgan

4.((

∃x

B

)

(¬¬C ∧¬¬D))

⇔(

¬¬C ∧(

∃x

B

)

¬¬D)

D’Morgan (K.3)

5.((

∃x

B

)

(C ∧D))

⇔(

C ∧(

∃x

B

)

D)

Doble neg.

(d) Sea x una variable no libre en C y y una variable no libre en B.

(K.17b) ⊢K

((

∃x

B

)(

∃y

C

)

D)

⇔

((

∃y

C

)(

∃x

B

)

D)

1.((

∀x

B

)(

∀y

C

)

¬D)

⇔((

∀y

C

)(

∀x

B

)

¬D)

(K.17a)

2. ¬((

∀x

B

)(

∀y

C

)

¬D)

⇔¬((

∀y

C

)(

∀x

B

)

¬D)

1(K.16d)

3.((

∃x

B

)

¬(

∀y

C

)

¬D)

⇔((

∃y

C

)

¬(

∀x

B

)

¬D)

2(K.3)

4.((

∃x

B

)(

∃y

C

)

¬¬D)

⇔((

∃y

C

)(

∃x

B

)

¬¬D)

3(K.3)

5.((

∃x

B

)(

∃y

C

)

D)

⇔((

∃y

C

)(

∃x

B

)

D)

Doble neg.

33

(e) ⊢K (∃x) ⇔

[((

∀x

B

)

C)

⇒

(

∃x

B

)

C]

1.((

∀x

B

)

C)

⇒(

∃x

B

)

C (hip)

2. ∀x(B⇒C)⇒∃x(B ∧C) 1 def(

∀x

B

)

, (K.9)

3. ¬∀x(B⇒C)∨∃x(B ∧C) def ⇒4. ∃x(B ∧¬C)∨∃x(B ∧C) 3(K.3)(L.19e)5. ∃x((B ∧¬C)∨ (B ∧C)) 4(K.5b)6. ∃x(B ∧ (¬C ∨C)) 5(L.19c)7. ∃xB ∧∃x(¬C ∨C)) 6(K.6a)M.P8. ∃xB (L.15a)M.P

9.[((

∀x

B

)

C)

⇒(

∃x

B

)

C]

⇒∃xB 1,8 T.Deducción

10. (∃x)⇒[((

∀x

B

)

C)

⇒(

∃x

B

)

C]

Ejerc.2.18b

11. (∃x)⇔[((

∀x

B

)

C)

⇒(

∃x

B

)

C]

9,10 (L.14b)

2.23 Ejercicio.En cada caso, establezca un contraejemplo para verificar que las siguientesafirmaciones no son lógicamente validas.

(a)((

∀x

B

)

C)

⇒

(

∃x

B

)

C

Sean B8 (x <x) C 8 (x6 x)∀x((x < x)⇒ (x 6x))⇒∃x((x < x)∧ (x6 x))

(b)(

∃x

B

)

C ⇔ C cuando x no es libre en C

Sean B8 (x� x) C: =(x= x)∃x((x� x)∧ (x= x))⇔ (x= x))

(c)((

∀x

B

)

(C ∧ D))

⇔

(

C ∧

(

∀x

B

)

D)

cuando x no es libre en C

Sean B8 (x < 0) C 8 (x =2) D8 (x =0)∀x((x < 0)⇒ ((x =2)∧ (x= 0)))⇔ ((x=2)∧ (∀x((x < 0)⇒ (x= 0))))

(d)(

∃x

B

)

(C ∨ D) ⇔

(

C ∨

(

∃x

B

)

D)

Sean B8 (x� x) C 8 (x2 > 0) D8 (6 +x > 3)

∃x((x� x)∧ ((x2 > 0)∨ (6 + x > 3)))⇔ ((x2 > 0)∨∃x((x� x)∧ (6 +x > 3)))

2.24 Ejercicio.(a) Si x no es libre en C,

(i)⊢K

((

∀x

B

)

(C ⇒ D))

⇔

(

C ⇒

(

∀x

B

)

D)

1. (B⇒ (C⇒D))⇔ (C⇒ (B⇒D)) (L.19f)2. ∀x(B⇒ (C⇒D))⇔∀x(C⇒ (B⇒D)) 1 (K.2c)3. ∀x(B⇒ (C⇒D))⇔ (C⇒∀x(B⇒D)) 2(Ejerc.2.9a(i))

3.((

∀x

B

)

(C⇒D))

⇔(

C⇒(

∀x

B

)

D)

def(

∀x

B

)

34

(ii) ⊢K(∃xB) ⇒

[((

∃x

B

)

(C ⇒ D))

⇔

(

C ⇒

(

∃x

B

)

D)]

1. (∃xB)⇒[((

∃x

B

)

(¬C ∨D))

⇔(

¬C ∨(

∃x

B

)

D)]

(K.16d)

1. (∃xB)⇒[((

∃x

B

)

(C⇒D))

⇔(

C⇒(

∃x

B

)

D)]

def ⇒

(b) Si x no es libre en D,

(i) ⊢K

((

∀x

B

)

(C ⇒ D))

⇔

(((

∃x

B

)

C)

⇒ D)

1. (B⇒ (C⇒D))⇔ (¬B ∨ (¬C ∨D)) def ⇒2. (B⇒ (C⇒D))⇔ (D ∨ (¬B ∨¬C)) 1(L.19b)2. (B⇒ (C⇒D))⇔ (¬D⇒ (B⇒¬C)) def ⇒3. ∀x(B⇒ (C⇒D))⇔∀x(¬D⇒ (B⇒¬C)) (K.2c)4. ∀x(B⇒ (C⇒D))⇔ (¬D⇒∀x(B⇒¬C)) 3(Ejerc.2.9a(i))

4.((

∀x

B

)

(C⇒D))

⇔(

¬D⇒(

∀x

B

)

¬C)

def ⇒

5.((

∀x

B

)

(C⇒D))

⇔(

¬(

∀x

B

)

¬C⇒¬¬D)

(L.17f)

6.((

∀x

B

)

(C⇒D))

⇔((

(

∃x

B

)

C)

⇒D)

def(

∃x

B

)

, Doble neg.

(ii) ⊢K(∃xB) ⇒

[((

∃x

B

)

(C ⇒ D))

⇔

(((

∀x

B

)

C)

⇒ D)]

1. (∃xB)⇒[((

∃x

B

)

(¬D⇒¬C))

⇔(

¬D⇒(

∃x

B

)

¬C)]

(Ejerc.2.24a(ii))

2. (∃xB)⇒[((

∃x

B

)

(¬¬C⇒¬¬D))

⇔(

¬(

∃x

B

)

¬C ⇒¬¬D)]

(L.17f)

2. (∃xB)⇒[((

∃x

B

)

(¬¬C⇒¬¬D))

⇔(

¬¬(

∀x

B

)

¬¬C⇒¬¬D)]

def(

∃x

B

)

3. (∃xB)⇒[((

∃x

B

)

(C⇒D))

⇔((

(

∀x

B

)

C)

⇒D)]

Doble neg.

2.25 Ejercicio.

(a) ⊢K (∀xC) ⇒

(

∀x

B

)

C (b) ⊢K

((

∃x

B

)

C)

⇒ ∃xC

1. ∀xC (hip) 1.(

∃x

B

)

C (hip)

2. ∀xC⇒C (K.1) 2. ∃x(B ∧C) 1(K.9)3. C 1,2(M.P) 3. ∃xB ∧∃xC 2(K.6a)M.P4. B⇒C 3(L.4) 4. ∃xC 3(L.15b)M.P

5. ∀x(B⇒C) GEN 5.((

∃x

B

)

C)

⇒∃xC 1,4 T.D

6.(

∀x

B

)

C def(

∀x

B

)

7. ∀xC⇒(

∀x

B

)

C 1,6 T.D

35

(c) C ⇒ B ⊢K

((

∃x

B

)

C)

⇔ ∃xC (d) ¬C ⇒ B ⊢K

((

∀x

B

)

C)

⇔ ∀xC

1. C⇒B (hip) 1. ¬C⇒B (hip)2. ¬B⇒¬C 1(L.7)M.P 2. ¬B⇒C 1(L.7)M.P,Doble neg.3. (¬C ∨¬B)⇒ (¬C ∨¬C) 2(A,4)M.P 3. (¬B ∨C)⇒ (C ∨C) 2(A.4)M.P4. ¬(C ∧B)⇒¬(C ∧C) 3D’Morgan 3. (B⇒C)⇒C def ⇒5. ¬(B ∧C)⇒¬C 4(L.17e.c) 4. C ⇒ (B⇒C) (L.2)def⇒6. ¬¬C⇒¬¬(B ∧C) 6(L.7)M.P. 5. (B⇒C)⇔C 3,4(L.14b)7. C⇒ (B ∧C) Doble neg. 6. ∀x(B⇒C)⇔∀xC 5(K.2c)

8. ∃xC⇒∃x(B ∧C) 7(K.2b) 7.((

∀x

B

)

C)

⇔∀xC

9. (B ∧C)⇒C (L.15b)10. ∃x(B ∧C)⇒∃xC 9(K.2b)11. ∃x(B ∧C)⇔∃xC 8,10(L.14b)

12.((

∃x

B

)

C)

⇔∃xC 11.(K.9) (f) B ⊢K

((

∀x

B

)

C)

⇔ ∀xC

1. B (hip)

(e) B ⊢K

((

∃x

B

)

C)

⇔ ∃xC 2. ¬¬B 1 Doble neg.

3. (¬B ∨C)⇔C 2(L.20b)1. B (hip) 3. (B⇒C)⇔C def ⇒2. (B ∧C)⇔C 1(L.20a) 4. ∀x(B⇒C)⇔∀xC 3(K.2c)

3. ∃x(B ∧C)⇔∃xC 2(K.2d) 4.((

∀x

B

)

C)

⇔∀xC def(

∀x

B

)

3.((

∃x

B

)

C)

⇔∃xC def(

∃x

B

)

2.26 Ejercicio. Si x no es libre en C

(a) ⊢K

(

∀x

(

∀y

C

)

D)

⇔

(

∀y

C

)

∀xD

1. ∀x∀y(C⇒D)⇔∀y∀x(C ⇒D) (K.8a)1. ∀x∀y(C⇒D)⇔∀y∀x(¬C ∨D) def ⇒2. ∀x∀y(C⇒D)⇔∀y(¬C ∨∀xD) 1(K.7a)2. ∀x∀y(C⇒D)⇔∀y(C⇒∀xD) def ⇒

2.(

∀x

(

∀y

C

)

D)

⇔(

∀y

C

)

∀xD def(

∀x

B

)

(b) ⊢K

(

∃x

(

∃y

C

)

D)

⇔

(

∃y

C

)

∃xD

1.(

∀x

(

∀y

C

)

¬D)

⇔(

∀y

C

)

∀x¬D Ejerc.2.26a

2. ¬(

∀x

(

∀y

C

)

¬D)

⇔¬(

∀y

C

)

∀x¬D 1(L.16d)

3.(

∃x¬(

∀y

C

)

¬D)

⇔(

∃y

C

)

¬∀x¬D 2(K.3)(K.12)

4.(

∃x

(

∃y

C

)

¬¬D)

⇔(

∃y

C

)

∃x¬¬D 3(K.12)(K.3)

5.(

∃x

(

∃y

C

)

D)

⇔(

∃y

C

)

∃xD 4 Doble neg.

36

(c) ⊢K

(

∃x

(

∀y

C

)

D)

⇒

(

∀y

C

)

∃xD

1. ∃x∀y(C⇒D)⇒∀y∃x(C ⇒D) (K.8d)1. ∃x∀y(C⇒D)⇒∀y∃x(¬C ∨D) def ⇒2. ∃x∀y(C⇒D)⇒∀y(¬C ∨∃xD) 1 (K.7c)2. ∃x∀y(C⇒D)⇒∀y(C⇒∃xD) def ⇒

2.(

∃x

(

∀y

C

)

D)

⇒(

∀y

C

)

∃xD def(

∀x

B

)

(d) ⊢K

((

∃y

C

)

∀xD)

⇒ ∀x

(

∃y

C

)

D

1.(

∃x

(

∀y

C

)

¬D)

⇒(

∀y

C

)

∃x¬D Ejerc.2.26c

2. ¬(

∀y

C

)

∃x¬D⇒¬∃x

(

∀y

C

)

¬D 1(L.7)M.P

3.(

∃y

C

)

¬∃x¬D⇒∀x¬(

∀y

C

)

¬D 2(K.12)(K.3)

4.((

∃y

C

)

∀x¬¬D)

⇒∀x

(

∃y

C

)

¬¬D 3(K.3)(K.12)

5.((

∃y

C

)

∀xD)

⇒∀x

(

∃y

C

)

D 4 Doble neg.

2.27 Ejercicio.

(a) (I.1c) ⊢K (t = r ∧ r = s) ⇒ t = s

Probemos primero que ⊢K∀x∀y∀z(x= y⇒ (y = z⇒ x= z))Sean B(y, y)8 (y = z) y B(y, x)8 (x= z)1. y = x⇒ (y = z⇒x = z) (A.8)2. x= y⇒ y =x (I.1b)3. x= y⇒ (y = z⇒x = z) 2,1(L.1)4. ∀x∀y∀z(x = y⇒ (y = z⇒ x = z)) (GEN) 3 vecesSean x, y, z, variables que no aparecen en t, s, r

1. ∀x∀y∀z(x = y⇒ (y = z⇒ x = z)) ya probado2. ∀y∀z(t = y⇒ (y = z⇒ t= z)) 1(A.5)M.P3. ∀z(t= r⇒ (r = z⇒ t= z)) 2 (A.5)M.P4. (t= r⇒ (r = s⇒ t= s)) 3 (A.5)M.P5. (t= r∧ r = s)⇒ t= s 4(L.19g)

(b) Utilice el Lema I.2 para dar una prueba mas directa de (b) y (c) de Lema I.1

(I.1b)⊢K t = s⇒ s = t

1. t= s⇒ (t= t⇔ s= t) (I.2)2. (t= t⇔ s= t)⇒ (t= t⇒ s= t) (L.15c)3. t= s⇒ (t= t⇒ s= t) 1,2 (L.1)4. t= t⇒ (t= s⇒ s= t) 3(L.19f)

37

5. t= t (I.1a)6. (t= s⇒ s= t) 4,5(M.P)

(I.1c) (c) ⊢K ∃x(x = y)⊢K (t = r ∧ r = s) ⇒ t = s razonemos por R.A

Sean B(t, t)8 (r = s) y B(t, s)8 (t= s) 1. ¬∃x(x = y) hip de R.A1. r = t⇒ (r = s⇔ t= s) (I.2) 2. ∀y(x� y) 1(K.3)2. (r = s⇔ t= s)⇒ (r = s⇒ t = s) (L.15c) 3. (x� x) 2(A.1)M.P3. r = t⇒ (r = s⇒ t= s) 1,2(L.1) 4. x= x (A.7)(A.5)M.P4. t = r⇒ r = t (I.1b) de 3,4, por teorema de Reducción5. t = r⇒ (r = s⇒ t= s) 3,4 (L.1) al Absurdo y T.Deducción6. (t= r∧ r = s)⇒ t= s 5(L.19g) se tiene ⊢K ∃x(x= y)

(d) Si y es libre para x enB(x) (e) ⊢K t = s ⇔ s = t

⊢K(B(x) ∧ ¬B(y)) ⇒ x� y Sean t y s términos

1. x = y⇒ (B(x, x)⇒B(y, x)) (A.8) 1. t= s⇒ s= t (I.1b)2.¬(B(x, x)⇒B(y, x))⇒ x� y 1(L.7)M.P 2. s= t⇒ t= s (I.1b)3. (B(x, x)∧¬B(y, x))⇒ x� y 2(L.19e) 3. t= s⇔ s= t 1,2(L.14b)3. (B(x)∧¬B(y))⇒ x� y notación

2.28 Ejercicio.Sea t un término que no contiene la variable x y que es libre para x en B(x)

(a) ⊢K

((

∃x

x= t

)

B(x))

⇔ B(t)

veamos ⊢K∀y(¬B(y)⇒ (x = y⇒¬B(x)))

Sean B(x, x)8 (¬B(y, x)) y B(x, y)8 (¬B(x, x)) donde x, y variables que noaparecen en t.

1. x= y⇒ (¬B(y, x)⇒¬B(x, x)) (A.8)1. x= y⇒ (¬B(y)⇒¬B(x)) notación2. ¬B(y)⇒ (x = y⇒¬B(x)) (L.19f)3. ∀y(¬B(y)⇒ (x= y⇒¬B(x))) 2(GEN)

1. ¬B(t) (hip)2. ∀y(¬B(y)⇒ (x= y⇒¬B(x))) ya probado3. ¬B(t)⇒ (x= t⇒¬B(x)) 2 (A.5)4. x= t⇒¬B(x) 1,3(M.P)5. ∀x(x = t⇒¬B(x)) 4(GEN)

5.(

∀x

x = t

)

¬B(x) def(

∀x

B

)

6. ¬B(t)⇒(

∀x

x = t

)

¬B(x) 1,5T.Deducción. t un término que no contiene

la variable x y que es libre para x en B(x) por hip.

38

7.(

∀x

x = t

)

¬B(x) (hip)

7. ∀x(x = t⇒¬B(x)) def(

∀x

B

)

8. t= t⇒¬B(t) 7(A.5)M.P9. t= t (I.1a)10. ¬B(t) 8,9 (M.P)

11.(

∀x

x = t

)

¬B(x)⇒¬B(t) 7,10 T.Deducción.

12.(

∀x

x = t

)

¬B(x)⇔¬B(t) 6,11(L.14b)

13. ¬(

∀x

x = t

)

¬B(x)⇔¬¬B(t) 12(L.16d)

14.((

∃x

x = t

)

B(x))

⇔B(t) 13 def(

∃x

B

)

, Doble neg.

(b) ⊢K

((

∀x

x= t

)

B(x))

⇔ B(t)

1.((

∃x

x= t

)

¬B(x))

⇔¬B(t) Ejerc.2.28a

2. ¬((

∀x

x = t

)

B(x))

⇔¬B(t) 1(K.12)

3. ¬¬((

∀x

x = t

)

B(x))

⇔¬¬B(t) 2(L.16a)

4.((

∀x

x= t

)

B(x))

⇔B(t) 3 Doble neg.

2.29 Ejercicio. (Cambio de Variable)Sea t(x) un término (que depende de la variable x) que no contiene la variable y yque es libre para y en B(y). Sea T (y) la fórmula ∃x(y = t(x)).

(a) ⊢K

((

∀y

T (y)

)

B(y))

⇔ ∀xB(t(x))

1.(

∀y

T (y)

)

B(y) (hip)

1. ∀y(∃x(y = t(x))⇒B(y)) def(

∀x

B

)

2. ¬∀xB(t(x)) hip de R.A3. ∃x¬B(t(x)) 2(K.3)4. ¬B(t(a)) 3 Regla C.5. ∃x(t(a) = t(x))⇒B(t(a)) 1 (A.5)M.P6. ∃x(t(a) = t(x)) Ejerci.2.27c instansiación para téminos.7. B(t(a)) 6,5 (M.P)En 4 y 5 se genera contradición, por T.Reducción al Absurdo y T.Deducción tenemos

8.((

∀y

T (y)

)

B(y))

⇒∀xB(t(x))

9. ∀xB(t(x)) (hip)10. ¬∀y(∃x(y = t(x))⇒B(y)) hip de R.A11. ∃y¬(∃x(y = t(x))⇒B(y)) 10(K.3)12. ¬(∃x(c = t(x))⇒B(c)) 11 Regla C.13. ∃x(c = t(x))∧¬B(c) (L.19e)

39

14. ∃x(c = t(x)) 13(L.15a9M.P.15. c = t(b) 14 Regla C.16. ¬B(c) 13(L.15b)M.P.17. ¬B(t(b)) 15,16 sustitución por iguales18. B(t(b)) 9(A.5)M.P.De 17, 18 se genera contradicción, por T.Reducción al Absurdo y T.Deducción tenemos

19. ∀xB(t(x))⇒((

∀y

T (y)

)

B(y))

20.((

∀y

T (y)

)

B(y))

⇔∀xB(t(x)) 8, 19 (L.14b)

(b) ⊢K

((

∃y

T (y)

)

B(y))

⇔ ∃xB(t(x))

1.((

∀y

T (y)

)

¬B(y))

⇔∀x¬B(t(x)) Ejerc.2.29a

2. ¬((

∀y

T (y)

)

¬B(y))

⇔¬∀x¬B(t(x)) 1(L.16d)

3.((

∃y

T (y)

)

B(y))

⇔¬¬∃xB(t(x)) 2 def(

∃x

B

)

,(K.3)

4.((

∃y

T (y)

)

B(y))

⇔∃xB(t(x)) 3 Doble neg.

(c) Si t(x) es x, pruebe que los resultados anteriores prueban directamente K.4b

(K.4b(i))1. ∃x(y =x) Ejerc.2.27c.2. ∀y(∃x(y =x)⇒B(y))⇔∀xB(x) Ejerc.2.29a.3. ∀y¬(∃x(y = x)∧¬B(y))⇔∀xB(x) tautología.4. ∀y¬¬B(y)⇔∀xB(x) 1,3 eliminacion de la verdad en ∧5. ∀yB(y)⇔∀xB(x) 4 Doble neg.

(K.4b(ii))1. ∃x(y =x) Ejerc.2.27c.2. ∃x(∃x(y = x)∧B(y))⇔∃xB(x) Ejerc.2.29b.3. ∃xB(y)⇔∃xB(x) 2,1 eliminacion de la verdad en ∧

2.30 Ejercicio. (Cambio de Variable para Cuantificadores Acotados)Sea t(x) un término (que depende de la variable x) que no contiene la variable y y

que es libre para y enB(y). Sea T (y) la fórmula(

∃x

D(x)

)

(y = t(x)).

(a) ⊢K

((

∀y

T (y)

)

B(y))

⇔

(

∀x

D(x)

)

B(t(x))

1.(

∀y

T (y)

)

B(y) (hip)

2. ∀y(∃x(D(x)∧ y = t(x))⇒B(y)) def(

∀x

B

)

40

3. D(x) (hip)4. ∃x(D(x)∧ t(x) = t(x))⇒B(t(x)) 2 (A.5)M.P5. ∃x(t(x) = t(x))⇒B(t(x)) 3,4 eliminacion de la verdad en ∧6. (t(c)= t(c))⇒B(t(x)) 5 Regla C.7. t(c) = t(c) (I.1a)8. B(t(x)) 6,7(M.P)9. ∀x(D(x)⇒B(t(x))) 3,8T.Deducción,(GEN)En 1,9 por T.Deducción tenemos((

∀y

T (y)

)

B(y))

⇒∀x(D(x)⇒B(t(x)))((

∀y

T (y)

)

B(y))

⇒(

∀x

D(x)

)

B(t(x)) def(

∀x

B

)

10.(

∀x

D(x)

)

B(t(x)) (hip)

10. ∀x(D(x)⇒B(t(x))) def(

∀x

B

)

11. ¬∀y(∃x(D(x)∧ y = t(x))⇒B(y)) hip de R.A12. ∃y¬(∃x(D(x)∧ y = t(x))⇒B(y)) 11(K.3)13. (∃x(D(x)∧ a = t(x))∧¬B(a)) 12 Regla C. (L.19e)14. ∃x(D(x)∧ a= t(x)) 13(L.15a)M.P15. D(b)∧ a = t(b) 14 Rgla C.16. a= t(b) 15(L.15b)M.P17. ¬B(a) 13(L.15b)M.P18. ¬B(t(b)) 16,17 sustitución por iguales.19. D(b)⇒B(t(b)) 10 (A.5)M.P20. B(t(b)) 15(L.15aM.P) y M.P. con 19En 18, 20 se genera contradición, luego por T.de Reducción al Absurdoy T.Deducción entre 10,20.

21.(

∀x

D(x)

)

B(t(x))⇒(

∀y

T (y)

)

B(y)

22.((

∀y

T (y)

)

B(y))

⇔(

∀x

D(x)

)

B(t(x)) 9,21(L.14b)

(b) ⊢K

((

∃y

T (y)

)

B(y))

⇔

(

∃x

D(x)

)

B(t(x))

1.((

∀y

T (y)

)

¬B(y))

⇔(

∀x

D(x)

)

¬B(t(x)) Ejerc.2.30a.

2. ¬((

∀y

T (y)

)

¬B(y))

⇔¬(

∀x

D(x)

)

¬B(t(x)) (L.16a)

3.((

∃y

T (y)

)

B(y))

⇔(

∃x

D(x)

)

B(t(x)) 2 def(

∃x

B

)

2.31 Ejercicio.

⊢K ∀x∃!y(x = y)

1. (x = y)∧ (z = y) (hip)Sean B(x, x): =[(x = y)= (x= y)] y B(x, y)8 [(x= y) = (z = y)]

41

2. x= z⇒ (((x= y)= (x = y))⇒ ((x = y) = (z = y))) (A.8)3. ((x= y) = (x = y))⇒ (x= z⇒ ((x = y) = (z = y))) 2(L.19f)4. (x = y) = (x= y) (A.7) instansiación.5. x= z⇒ ((x = y) = (z = y)) 4,3(M.P)6.1. (x= y)∧ (y = z)⇒ (x = z) instansiación de lo ya mostrado para I.26. (x = y)∧ (z = y)⇒ (x= z) (L.17e)(L.19g)trans. con (I.b),(L.19g)(L.17e)7. (x = z) 1,6(M.P)8. (x = y) = (z = y) 5,7(M.P)9. ((x= y)∧ (z = y))⇒ ((x = y) = (z = y)) 1,8 T.Deducción10. ∀x∀z((x= y)∧ (z = y))⇒ ((x = y) = (z = y)) 9(GEN) dos veces11. ∃y(x = y) Ejerc.2.27c.12. ∃y(x = y)∧∀x∀z((x = y)∧ (z = y))⇒ ((x = y)= (z = y)) 10,11(L.14a)12. ∃!y(x= y) def ∃!13. ∀x∃!y(x = y) 12(GEN)

2.32 Ejercicio.

(a) ⊢K(∃!xC(x)) ⇔ ∃x∀y(C(y) ⇔ x = y)

1. ∃!xC(x) (hip)1. (∃xC(x))∧∀x∀y((C(x)∧C(y))⇒ x = y) def ∃!2. ∃xC(x) 1 (L.15a)M.P3. C(a) 2 Regla C.4. ∀x∀y((C(x)∧C(y))⇒ x= y) 1 (L.1b)M.P5. ∀y((C(a)∧C(y))⇒ a = y) 4(A.5)M.P.6. ∀y(C(y)⇒ a= y) 3,5 Eliminación de la verdad en ∧7. x= y⇒ (C(x, x)⇒C(y, x)) (A.8)7. x= y⇒ (C(x)⇒C(y)) notación8. ∀x∀y(x= y⇒ (C(x)⇒C(y))) 7(GEN) dos veces8. ∀x∀y(x= y⇒ (¬C(x)∨C(y))) def ⇒9. ∀y(a= y⇒ (¬C(a)∨C(y))) 8(A.5)M.P10. ∀y(a = y⇒ (C(y)) 9,3 Eliminación de la falsa en el antecedente, en ∨11. ∀y(C(y)⇒ a = y)∧∀y(a = y⇒ (C(y)) 6,10 (L.14a)12. ∀y((C(y)⇒ a= y)∧ (a = y⇒ (C(y))) 11(K.5a)12. ∀y((C(y)⇔ a= y)) def ⇔13. ∃x∀y((C(y)⇔ x= y)) 12(K.1b)M.P.14. (∃!xC(x))⇒∃x∀y(C(y)⇔ x = y) 1,13 T.Deducción

15. ∃x∀y(C(y)⇔ x= y) (hip)16. ∃x(∀y(C(y)⇒ x= y)∧∀y(x = y⇒ (C(y))) def ⇔, (K.5a)17. ∀y(C(y)⇒ d = y)∧∀y(d = y⇒ (C(y)) 16 Regla C.18. ∀y(d = y⇒ (C(y)) 17 (L.15b)M.P19. d = d⇒ (C(d)) 18(A.5)M.P20. C(d) 19(I.1a)M.P.

42

21. ∀y(C(y)⇒ d = y) 17 (L.15a)M.P22. C(d)∧∀y(C(y)⇒ d = y) 20,21 (L.14a)23. ∃x(C(x)∧∀y(C(y)⇒ x = y)) 22 (K.1b)M.P.24. ∃!xC(x) 23 (I.5a)25. ∃x∀y(C(y)⇔ x= y)⇒∃!xC(x) 15,24 T.Deducción.26. (∃!xC(x))⇔∃x∀y(C(y)⇔ x = y) 14, 25 (L.14a)