Deduccion Natural

Introducci´on a la deducci´on natural

Daniel Clemente Laboreo

Agosto 2004 (revisado en Mayo 2005)

´ Indice

1. Antes de nada... 3

1.1. Qui´en soy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2. Por qu´e escribo esto . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. A qui´en va dirigido . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4. Licencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2. Conceptos b´asicos 4

2.1. Formalizaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2. S´ımbolos usados . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3. Precedencia de los operadores . . . . . . . . . . . . . . . . . . . . 6

3. Deducci´on natural 7

3.1. Para qu´e sirve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.2. Para qu´e no sirve . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.4. Notaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4. Las reglas 9

4.1. Iteraci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2. Introducci´on de la conjunci´on . . . . . . . . . . . . . . . . . . . . 10

4.3. Eliminaci´on de la conjunci´on . . . . . . . . . . . . . . . . . . . . 10

4.4. Introducci´on de la implicaci´on . . . . . . . . . . . . . . . . . . . . 11

4.5. Eliminaci´on de la implicaci´on . . . . . . . . . . . . . . . . . . . . 11

4.6. Introducci´on de la disyunci´on . . . . . . . . . . . . . . . . . . . . 11

4.7. Eliminaci´on de la disyunci´on . . . . . . . . . . . . . . . . . . . . 12

4.8. Introducci´on de la negaci´on . . . . . . . . . . . . . . . . . . . . . 13

4.9. Eliminaci´on de la negaci´on . . . . . . . . . . . . . . . . . . . . . . 13

4.10. No hay m´as reglas . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1

5. Ejercicios explicados 14

5.1. Uno muy sencillo. P, P ⇒ Q ⊢ P ∧ Q . . . . . . . . . . . . . . . 14

5.2. Algo m´as complicado. P ∧ Q ⇒ R, Q ⇒ P, Q ⊢ R . . . . . . . . 15

5.3. Empezando a suponer cosas. P ⇒ Q, Q ⇒ R ⊢ P ⇒ Q ∧ R . . . 16

5.4. Usando la iteraci´on. P ⊢ Q ⇒ P . . . . . . . . . . . . . . . . . . 17

5.5. Reducci´on al absurdo. P ⇒ Q, ¬Q ⊢ ¬P . . . . . . . . . . . . . 17

5.6. Con subdemostraciones. P ⇒ (Q ⇒ R) ⊢ Q ⇒ (P ⇒ R) . . . . . 18

5.7. Uno de prueba por casos. P ∨ (Q ∧ R) ⊢ P ∨ Q . . . . . . . . . . 19

5.8. Uno para pensar. L ∧M ⇒ ¬P, I ⇒ P, M, I ⊢ ¬L . . . . . . . 20

5.9. El lado izquierdo vac´ıo. ⊢ P ⇒ P . . . . . . . . . . . . . . . . . . 21

5.10. Suponer lo contrario. ⊢ ¬(P ∧ ¬P) . . . . . . . . . . . . . . . . . 22

5.11. ´Este parece sencillo. ⊢ P ∨ ¬P . . . . . . . . . . . . . . . . . . . 22

5.12. Uno interesante. P ∨ Q, ¬P ⊢ Q . . . . . . . . . . . . . . . . . . 23

5.13. ´Este me lo pusieron en un examen. A ∨B, A ⇒ C, ¬D ⇒ ¬B ⊢

C ∨ D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.14. Uno “corto”. A ⇐⇒ B ⊢ (A ∧ B) ∨ (¬A ∧ ¬B) . . . . . . . . . . . 26

6. Cosas incorrectas 27

6.1. Introducci´on y eliminaci´on de “lo que me venga bien” . . . . . . . 27

6.2. Iterar algo de una subdemostraci´on no accesible . . . . . . . . . . 27

6.3. Colocar mal los par´entesis . . . . . . . . . . . . . . . . . . . . . . 29

6.4. Acabar dentro de una subdemostraci´on . . . . . . . . . . . . . . 29

6.5. Saltarse pasos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

7. Complic´andolo un poco m´as 30

7.1. Reglas de cierto y falso . . . . . . . . . . . . . . . . . . . . . . . . 30

7.1.1. Introducci´on de cierto . . . . . . . . . . . . . . . . . . . . 30

7.1.2. Eliminaci´on de falso . . . . . . . . . . . . . . . . . . . . . 30

7.2. Reglas de cuantificadores . . . . . . . . . . . . . . . . . . . . . . 31

7.2.1. Qu´e es eso . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7.2.2. Introducci´on del existencial . . . . . . . . . . . . . . . . . 31

7.2.3. Eliminaci´on del

...