Drogo

Ejercicios de L´gica inform´tica (2004–05)
o
a
Tema 2: Deducci´n natural proposicional
o
Jos´ A. Alonso Jim´nez
e
e

Grupo de L´gica Computacional
o
Dpto. de Ciencias de la Computaci´n e Inteligencia Artificial
o
Universidad de Sevilla
Sevilla, 8 de Marzo de 2005

2.2

Tema 2: Deducci´n natural proposicional
o

1. Implicaciones
1. p, p → q

q

1: p, p
2: q

qpremisas
e 1.2,1.1

2. p → q, q → r, p

1: p
2: q
3: r

r

q, q

r, p

3. p → (q → r), p → q, p

1
2
3
4

:
:
:
:

p
q
q
r

(q

r) , p

1: p

i24

(q

q → (p → r)

r)

q

p

premisa
supuesto

p
q
r

3:
4:
5:

premisas
supuesto
e 1.1,2
e 1.2,3

r

1: p

7: q

r

p
q
r

5. p → (q → r)

6:

q, p

p→r

q, q

5: p

2:r

r

4. p → q, q → r

2:
3:
4:

premisas
e 1.1,1.3
e 1.2,2

supuesto
e 1,3
e 4,2

r
r

(p

i35

r)

i26

premisas
e 1.2,1.3
e 1.1,1.3
e 3,2

LI 2004–05

LI 2004–05

Tema 2: Deducci´n natural proposicional
o

6. p → (q → r)

1: p

p

2:
3
4
5
6

(q

supuesto
e 2,3
e 1,3
e 5,4
i36

q)

(p

r)

i27

q→p

1: p
2:
3:premisa

q
p

4: q
8.

supuesto

r

8 : (p
7. p

premisa

r

p

7:

r)

q
p
q
q
r

:
:
:
:

(p → q ) → (p → r)

supuesto
hyp 1

p

i23

p → (q → p)

1:

p
q
p

2:
3:
4:

supuesto
supuesto
hyp 1

q

5: p

p
(q

9. p → q

1: p
2:

i23

p)

i14

(q → r) → (p → r)

q
q

premisa

r

supuesto

p
q
r

3:
4:
5:supuesto
e 1,3
e 2,4

p

r

7 : (q

r)

6:

i35

(p

r)

i26

2.3

2.4

Tema 2: Deducci´n natural proposicional
o

10. p → (q → (r → s))

1: p

(q

premisa
supuesto

q

3:

supuesto

p
q
r
s

:
:
:
:

(r
s

p

8:

s)

i47

(p

10 : r

supuesto
e 1,4
e 5,3
e 6,2

s

q

9:

11.

s))

r

2:

4
5
6
7

(r

r→ (q → (p → s))

s)

(q

(p

i38

s))

i29

(p → (q → r)) → ((p → q ) → (p → r))

1:

p
p

2:
3
4
5
6

(q

7:

p

8:

(p

r
(q

1 : (p

q)

(p
r))

r

q)

premisa

supuesto

p
q
p
r
q

((p

i27

p → (q → r)

q

6:
7:

r)

supuesto

4:
5:

9: p

i36

p

3:

8:

supuesto
e 2,3
e 1,3
e 5,4

r

12. (p → q ) →r

2:

supuesto

q)

9 : (p

supuesto

q
p
q
q
r

:
:
:
:

r)

supuesto
hyp 3

q

i45
e 1,6

r
(q

i37

r)

i28

(p

r))

i18

LI 2004–05

LI 2004–05

Tema 2: Deducci´n natural proposicional
o

2. Conjunciones
13. p, q

p∧q

1: p, q
2: p q
14. p ∧ q

premisas
i 1.1,1.2

p

1: p q
2: p
15. p ∧ q

premisa
e1

q

1: p q2: q

premisa
e1

16. p ∧ (q ∧ r)

1
2
3
4
5
6
7

:
:
:
:
:
:
:

p (q r)
qr
r
q
p
pq
(p q) r

17. (p ∧ q ) ∧ r

1
2
3
4
5
6
7

:
:
:
:
:
:
:

(p ∧ q ) ∧ r

premisa
e1
e2
e2
e1
i 5,4
i 6,3
p ∧ (q ∧ r)

(p q) r
r
pq
q
qr
p
p (q r)

18. p ∧ q

p→q

1: p q
2:
3:
4: p

premisa
e1
e1
e3
i 4,2
e3
i 6,5

premisa

p
qsupuesto
e1

q

i23

2.5

2.6

Tema 2: Deducci´n natural proposicional
o

19. (p → q ) ∧ (p → r)

1 : (p q) (p
2: p r
3: p q
4
5
6
7

:
:
:
:

(q r)

1: p

i47
(p → q ) ∧ (p → r)

(q r)

supuesto
e 1,2
e3

q

i24

p
qr
r

5: p

supuesto
e 1,6
e7

9: p r
10 : (p q) (p
21. p → (q → r)

:
:
:
:
:

premisa

p
qr
q

2:
3:
4:2
3
4
5
6

premisa
e1
e1
supuesto
e 2,4
e 3,4
i 6,5

20. p → (q ∧ r)

1: p

r)

p
r
q
qr

8: p

6:
7:
8:

p → (q ∧ r)

(q

r)

(p ∧ q ) → r

r)

pq
q
p
qr
r

7 : (p q)

i68
i 5,9

premisa
supuesto
e2
e2
e 1,4
e 5,3

r

i26

LI 2004–05

LI 2004–05

Tema 2: Deducci´n natural proposicional
o

22. (p ∧ q ) → r

p → (q → r)...