![Page 1: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/1.jpg)
PD Tema 2: Deducción natural proposicional
Lógica informática (2015–16)Tema 2: Deducción natural proposicional
José A. Alonso JiménezAndrés Cordón Franco
María J. Hidalgo Doblado
Grupo de Lógica ComputacionalDepartamento de Ciencias de la Computación e I.A.
Universidad de Sevilla
1 / 28
![Page 2: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/2.jpg)
PD Tema 2: Deducción natural proposicional
Tema 2: Deducción natural proposicional
1. Reglas de deducción natural
2. Reglas derivadas
3. Resumen de reglas de deducción natural
2 / 28
![Page 3: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/3.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Tema 2: Deducción natural proposicional
1. Reglas de deducción naturalReglas de la conjunciónReglas de la doble negaciónRegla de eliminación del condicionalRegla derivada de modus tollens (MT)Regla de introducción del condicionalReglas de la disyunciónRegla de copiaReglas de la negaciónReglas del bicondicional
2. Reglas derivadas
3. Resumen de reglas de deducción natural 3 / 28
![Page 4: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/4.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas de la conjunción
Reglas de la conjunciónI Regla de introducción de la conjunción:
F G∧i
F ∧ GI Reglas de eliminación de la conjunción:
F ∧ G∧e1
F
F ∧ G∧e2
GI Ejemplo: p ∧ q, r ` q ∧ r :
1 p ∧ q premisa
2 r premisa
3 q ∧e2 1
4 q ∧ r ∧i 2, 3I Adecuación de las reglas de la conjunción:
I ∧i : {F , G} |= F ∧ GI ∧e1 : F ∧ G |= FI ∧e2 : F ∧ G |= G
4 / 28
![Page 5: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/5.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas de la doble negación
Reglas de la doble negaciónI Regla de eliminación de la doble negación:
¬¬F¬¬e
FI Regla de introducción de la doble negación:
F¬¬i
¬¬FI Ejemplo: p,¬¬(q ∧ r) ` ¬¬p ∧ r :1 p premisa
2 ¬¬(q ∧ r) premisa
3 ¬¬p ¬¬i 1
4 q ∧ r ¬¬e 2
5 r ∧e2 4
6 ¬¬p ∧ r ∧i 3, 5
I Adecuación de las reglas de la doble negación:I ¬¬e : {¬¬F} |= FI ¬¬i : {F} |= ¬¬F 5 / 28
![Page 6: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/6.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Regla de eliminación del condicional
Regla de eliminación del condicionalI Regla de eliminación del condicional:
F F → G→ e
GI Ejemplo: ¬p ∧ q,¬p ∧ q → r ∨ ¬p ` r ∨ ¬p:1 ¬p ∧ q premisa
2 ¬p ∧ q → r ∨ ¬p premisa
3 r ∨ ¬p →e 1, 2I Ejemplo: p, p → q, p → (q → r) ` r :
1 p premisa
2 p → q premisa
3 p → (q → r) premisa
4 q →e 1, 2
5 q → r →e 1, 3
6 r →e 4, 5I Adecuación de la eliminación del condicional: {F , F → G} |= G
6 / 28
![Page 7: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/7.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Regla derivada de modus tollens (MT)
Regla derivada de modus tollens (MT)I Regla derivada de modus tollens:
F → G ¬GMT
¬FI Ejemplo: p → (q → r), p,¬r ` ¬q:
1 p → (q → r) premisa
2 p premisa
3 ¬r premisa
4 q → r →e 1, 2
5 ¬q MT 3, 4I Ejemplo: ¬p → q,¬q ` p:
1 ¬p → q premisa
2 ¬q premisa
3 ¬¬p MT 1, 2
4 p ¬¬e 3
7 / 28
![Page 8: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/8.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Regla de introducción del condicional
Regla de introducción del condicional
I Regla de introducción del condicional:
F...G
→ iF → G
I Ejemplo: p → q ` ¬q → ¬p:1 p → q premisa
2 ¬q supuesto
3 ¬p MT 1, 2
4 ¬q → ¬p →i 2− 3
I Adecuación de la regla de introducción del condicional:Si F |= G , entonces |= F → G .
8 / 28
![Page 9: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/9.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Regla de introducción del condicional
Regla de introducción del condicionalI Ejemplo: ¬q → ¬p ` p → ¬¬q:
1 ¬q → ¬p premisa
2 p supuesto
3 ¬¬p ¬¬i 2
4 ¬¬q MT 1, 3
5 p → ¬¬q →i 2− 4
I Ejemplo (de teorema): ` p → p:1 p supuesto
2 p → p →i 1− 1
9 / 28
![Page 10: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/10.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Regla de introducción del condicional
Regla de introducción del condicionalI Ejemplo: ` (q → r)→ ((¬q → ¬p)→ (p → r)):
1 q → r supuesto
2 ¬q → ¬p supuesto
3 p supuesto
4 ¬¬p ¬¬i 3
5 ¬¬q MT 2, 4
6 q ¬¬e 5
7 r →e 1, 6
8 p → r →i 3− 7
9 (¬q → ¬p)→ (p → r) →i 2− 8
10 (q → r)→ ((¬q → ¬p)→ (p → r)) →i 1− 9 10 / 28
![Page 11: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/11.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas de la disyunción
Reglas de la disyunciónI Reglas de introducción de la disyunción:
F∨i1
F ∨ G
G∨i2
F ∨ G
I Regla de eliminación de la disyunción:F ∨ G
F...H
G...H
∨eHI Ejemplo: p ∨ q ` q ∨ p:
1 p ∨ q premisa
2 p supuesto
3 q ∨ p ∨i2 2
4 q supuesto
5 q ∨ p ∨i1 4
6 q ∨ p ∨e 1, 2− 3, 4− 511 / 28
![Page 12: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/12.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas de la disyunción
Reglas de la disyunciónI Ejemplo: q → r ` p ∨ q → p ∨ r :
1 q → r premisa
2 p ∨ q supuesto
3 p supuesto
4 p ∨ r ∨i1 3
5 q supuesto
6 r →e 1, 5
7 p ∨ r ∨i2 6
8 p ∨ r ∨e 2, 3− 4, 5− 7
9 p ∨ q → p ∨ r →i 2− 8
12 / 28
![Page 13: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/13.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Regla de copia
Regla de copiaI Ejemplo (usando la regla hyp): ` p → (q → p):
1 p supuesto
2 q supuesto
3 p hyp 1
4 q → p →i 2− 3
5 p → (q → p) →i 1− 4
13 / 28
![Page 14: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/14.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas de la negación
Reglas de la negaciónI Extensiones de la lógica para usar falso:
I Extensión de la sintaxis: ⊥ es una fórmula proposicional.I Extensión de la semántica: I(⊥) = 0 en cualquier interpretación I.
I Reglas de la negación:
I Regla de eliminación de lo falso:⊥⊥e
FI Regla de eliminación de la negación:
F ¬F¬e
⊥I Adecuación de las reglas de la negación:
I ⊥ |= FI {F ,¬F} |= ⊥
14 / 28
![Page 15: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/15.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas de la negación
Reglas de la negaciónI Ejemplo: ¬p ∨ q ` p → q:
1 ¬p ∨ q premisa
2 p supuesto
3 ¬p supuesto
4 ⊥ ¬e 2, 3
5 q ⊥e 4
6 q supuesto
7 q ∨e 1, 3− 5, 6− 6
8 p → q →i 2− 7
15 / 28
![Page 16: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/16.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas de la negación
Reglas de la negaciónI Regla de introducción de la negación:
F...⊥¬i
¬FI Adecuación: Si F |= ⊥, entonces |= ¬F .I Ejemplo: p → q, p → ¬q ` ¬p:
1 p → q premisa
2 p → ¬q premisa
3 p supuesto
4 q →e 1, 3
5 ¬q →e 2, 3
6 ⊥ ¬e 4, 5
7 ¬p ¬i 3− 616 / 28
![Page 17: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/17.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas del bicondicional
Reglas del bicondicionalI Regla de introducción del bicondicional:
F → G G → F↔ i
F ↔ GI Ejemplo: p ∧ q ↔ q ∧ p:1 p ∧ q supuesto
2 p ∧e1 1
3 q ∧e2 1
4 q ∧ p ∧i 2, 3
5 p ∧ q → q ∧ p →i 1− 4
6 q ∧ p supuesto
7 q ∧e2 6
8 p ∧e1 6
9 p ∧ q ∧i 7, 8
10 q ∧ p → p ∧ q →i 6− 9
11 p ∧ q ↔ q ∧ p ↔i 5, 1017 / 28
![Page 18: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/18.jpg)
PD Tema 2: Deducción natural proposicionalReglas de deducción natural
Reglas del bicondicional
Reglas del bicondicionalI Eliminación del bicondicional:
F ↔ G↔ e1
F → G
F ↔ G↔ e2
G → FI Ejemplo: p ↔ q, p ∨ q ` p ∧ q:
1 p ↔ q premisa
2 p ∨ q premisa
3 p supuesto
4 p → q ↔e1 1
5 q →e 4, 3
6 p ∧ q ∧i 3, 5
q supuesto
q → p ↔e2 1
p →e 4′, 3′
p ∧ q ∧i 3′, 5′
7 p ∧ q ∨e 2, 3− 6, 3′ − 6′
18 / 28
![Page 19: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/19.jpg)
PD Tema 2: Deducción natural proposicionalReglas derivadas
Tema 2: Deducción natural proposicional
1. Reglas de deducción natural
2. Reglas derivadasRegla del modus tollensRegla de introducción de doble negaciónRegla de reducción al absurdoLey del tercio excluido
3. Resumen de reglas de deducción natural
19 / 28
![Page 20: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/20.jpg)
PD Tema 2: Deducción natural proposicionalReglas derivadas
Regla del modus tollens
Reglas de modus tollensI Regla derivada de modus tollens (MT):
F → G ¬GMT
¬FI Derivación:
1 F → G premisa
2 ¬G premisa
3 F supuesto
4 G →e 1, 3
5 ⊥ ¬e 2, 4
6 ¬F ¬i 2− 4
20 / 28
![Page 21: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/21.jpg)
PD Tema 2: Deducción natural proposicionalReglas derivadas
Regla de introducción de doble negación
Regla de introducción de doble negaciónI Regla de introducción de la doble negación:
F¬¬i
¬¬FI Derivación:
1 F premisa
2 ¬F supuesto
3 ⊥ ¬e 1, 2
4 ¬¬F ¬i 2− 3
21 / 28
![Page 22: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/22.jpg)
PD Tema 2: Deducción natural proposicionalReglas derivadas
Regla de reducción al absurdo
Regla de reducción al absurdo (RAA)I Regla de reducción al absurdo:
¬F...⊥
RAAF
I Derivación:1 ¬F → ⊥ premisa
2 ¬F supuesto
3 ⊥ →e 1, 2
4 ¬¬F ¬i 2− 3
5 F ¬e ¬4
22 / 28
![Page 23: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/23.jpg)
PD Tema 2: Deducción natural proposicionalReglas derivadas
Ley del tercio excluido
Ley del tercio excluido (LEM)I Ley del tercio excluido (LEM):
LEMF ∨ ¬F
I Derivación:1 ¬(F ∨ ¬F ) supuesto
2 F supuesto
3 F ∨ ¬F ∨i1 2
4 ⊥ ¬e 1, 3
5 ¬F ¬i 2− 4
6 F ∨ ¬F ∨i2 5
7 ⊥ ¬e 1, 6
8 F ∨ ¬F RAA 1− 723 / 28
![Page 24: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/24.jpg)
PD Tema 2: Deducción natural proposicionalReglas derivadas
Ley del tercio excluido
Reglas derivadas: ley del tercio excluido (LEM)I Ejemplo: p → q ` ¬p ∨ q:
1 p → q premisa
2 p ∨ ¬p LEM
3 p supuesto
4 q →e 1, 3
5 ¬p ∨ q ∨i2 4
6 ¬p supuesto
7 ¬p ∨ q ∨i1 6
8 ¬p ∨ q ∨e 2, 3− 5, 6− 7
24 / 28
![Page 25: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/25.jpg)
PD Tema 2: Deducción natural proposicionalResumen de reglas de deducción natural
Tema 2: Deducción natural proposicional
1. Reglas de deducción natural
2. Reglas derivadas
3. Resumen de reglas de deducción natural
25 / 28
![Page 26: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/26.jpg)
PD Tema 2: Deducción natural proposicionalResumen de reglas de deducción natural
Resumen de reglas de deducción naturalIntroducción Eliminación
∧F G
∧iF ∧ G
F ∧ G∧e1
F
F ∧ G∧e2
G
∨F∨i1
F ∨ G
G∨i2
F ∨ G F ∨ G
F...H
G...H
∨eH
→
F...G
→ iF → G
F F → G→ e
G
26 / 28
![Page 27: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/27.jpg)
PD Tema 2: Deducción natural proposicionalResumen de reglas de deducción natural
Resumen de reglas de deducción naturalIntroducción Eliminación
¬
F...⊥¬i
¬F
F ¬F¬e
⊥
⊥⊥⊥e
F
¬¬¬¬F
¬¬eF
↔F → G G → F
↔ iF ↔ G
F ↔ G↔ e1
F → G
F ↔ G↔ e2
G → FI Adecuación y completitud del cálculo de deducción natural.
27 / 28
![Page 28: Lógica informática (2015 16) - Tema 2: Deducción natural …jalonso/cursos/li/temas/tema-2.pdf · 2015. 9. 12. · PD Tema 2: Deducción natural proposicional Lógicainformática(2015–16)](https://reader036.vdocumento.com/reader036/viewer/2022071411/610734be50258f3ca43896ff/html5/thumbnails/28.jpg)
PD Tema 2: Deducción natural proposicionalBibliografía
Bibliografía1. C. Badesa, I. Jané y R. Jansana Elementos de lógica formal.
(Ariel, 2000).Cap. 16: Cálculo deductivo.
2. R. Bornat Using ItL Jape with X (Department of ComputerScience, QMW, 1998).
3. J.A. Díez Iniciación a la Lógica, (Ariel, 2002).Cap. 4: Cálculo deductivo. Deducibilidad.
4. M. Huth y M. Ryan Logic in computer science: modelling andreasoning about systems. (Cambridge University Press, 2000)
Cap. 1: Propositional logic.5. E. Paniagua, J.L. Sánchez y F. Martín Lógica computacional
(Thomson, 2003)Cap. 3.6: El método de la deducción natural.
28 / 28