Ex resolvidos

Prévia do material em texto

Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
Exemplos de Dedução Natural
Para acompanhar as respostas de cada argumento, tenha em mãos o material com as regras de inferência
e de equivalência.
1. (P ∨R)→ (D ∧ ¬C) ` R→ (¬C ∨ E)
Resposta:
1 (P ∨R)→ (D ∧ ¬C) hip
2 |R hip− pc
3 |P ∨R 2, ad
4 |D ∧ ¬C 1, 3,mp
5 |¬C 4, sp
6 |¬C ∨ E 5, ad
7 R→ (¬C ∨ E) 2− 6, pc
2. ¬P ∧Q,R→ P ` ¬P ∧ ¬R
Resposta:
1 ¬P ∧Q hip.
2 R→ P hip.
3 ¬P 1, sp
4 ¬R 2, 3,mt
5 ¬P ∧ ¬R 3, 4, cj
Resposta:
1 ¬P ∧Q hip.
2 R→ P hip.
3 ¬P 1, sp
4 |R hip− raa
5 |P 2, 4,mp
6 |P ∧ ¬P 3, 5, cj
7 ¬R 4− 6, raa
8 ¬P ∧ ¬R 3, 7, cj
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
3. A→ (R↔ (B ∨ T )), C ∨ L,L→ A ` ¬C → (B → R)
Resposta:
1 A→ (R↔ (B ∨ T )) hip
2 C ∨ L hip
3 L→ A ∨R hip
4 |¬C hip− pc
5 ||B hip− pc
6 ||L 2, 4, sd
7 ||A 3, 6,mp
8 ||R↔ (B ∨ T ) 1, 7,mp
9 ||(B ∨ T )→ R 8,E↔
10 ||B ∨ T 5, ad
11 ||R 9, 10,mp
12 |B → R 5− 11, pc
13 ¬C → (B → R) 4− 12, pc
4. T → N, T ∨ F,E → ¬F,¬N ` ¬E
Resposta:
1 T → N hip
2 T ∨ F hip
3 E → ¬F hip
4 ¬N hip
5 |T hip− raa
6 |N 1, 5,mp
7 |N ∧ ¬N 4, 6, cj
8 ¬T 5− 7, raa
9 F 2, 8, sd
10 |E hip− raa
11 |¬F 3, 10,mp
12 |F ∧ ¬F 9, 11, cj
13 ¬E 10− 12, raa
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
5. ¬A ∧B,B → (A ∨ C) ` C
Resposta:
1 ¬A hip
2 B hip
3 B → (A ∨ C) hip
4 A ∨ C 2, 3,mp
5 ¬(¬A) ∨ C 4, dn
6 ¬A→ C 5, cond
7 C 1, 6,mp
6. B ↔ A, (B ∨ C)→ (E ∨Q), (B ∧ A)→ C,¬E,B ` Q
Resposta:
1 B ↔ A hip
2 (B ∨ C)→ (E ∨Q) hip
3 (B ∧A)→ C hip
4 ¬E hip
5 B hip
6 B → A 1, E↔
7 A 5, 6,mp
8 B ∧A 5, 7, cj
9 C 3, 8,mp
10 B ∨ C 5, ad
11 E ∨Q 2, 10,mp
12 Q 4, 11, sd
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
7. ¬(P ∧B)→ ¬T, T ∨ (¬¬A ∧ ¬C), A→ ¬E,¬(P ∧B) ` (A→ ¬E) ∧ ¬E
Resposta:
1 ¬(P ∧B)→ ¬T hip
2 T ∨ (¬¬A ∧ ¬C) hip
3 A→ ¬E hip
4 ¬(P ∧B) hip
5 ¬T 1, 4,mp
6 ¬¬A ∧ ¬C 2, 5, sd
7 ¬¬A 6, sp
8 A 7, dn
9 ¬E 3, 8,mp
10 (A→ ¬E) ∧ ¬E 3, 9, cj
8. (¬B → ¬A)↔ (C ∨D), D,¬B,A ∨ (T ∨ ¬¬Q) ` (T ∨ ¬¬Q) ∨R
Resposta:
1 (¬B → ¬A)↔ (C ∨D) hip
2 D hip
3 ¬B hip
4 A ∨ (T ∨ ¬¬Q) hip
5 (C ∨D)→ (¬B → ¬A) 1, E↔
6 C ∨D 2, ad
7 ¬B → ¬A 5, 6,mp
8 ¬A 3, 7,mp
9 T ∨ ¬¬Q 4, 8, sd
10 (T ∨ ¬¬Q) ∨R 9, ad
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
9. ¬¬A ∧ (B → C), E ∧D, ((B → C) ∧ (D ∨ F ))→ G ` (G ∧ A) ∧ E
Resposta:
1 ¬¬A ∧ (B → C) hip
2 E ∧D hip
3 ((B → C) ∧ (D ∨ F ))→ G hip
4 B → C 1, sp
5 D 2, sp
6 D ∨ F 5, ad
7 (B → C) ∧ (D ∨ F ) 4, 6, cj
8 G 3, 7,mp
9 E 2, sp
10 ¬¬A 1, sp
11 A 10, dn
12 G ∧A 8, 11, cj
13 (G ∧A) ∧ E 9, 12, cj
10. G→ ¬N,¬N → ¬P ` G→ ¬P
Resposta:
1 G→ ¬N hip
2 ¬N → ¬P hip
3 |G hip− pc
4 |¬N 1, 3,mp
5 |¬P 2, 4,mp
6 G→ ¬P 3− 5, pc
11. C → ¬F ` ¬(C ∧ F )
Resposta:
1 C → ¬F hip
2 |C ∧ F hip− raa
3 |C 2, sp
4 |¬F 1, 3,mp
5 |F 2, sp
6 |F ∧ ¬F 4, 5, cj
7 ¬(C ∧ F ) 2− 6, raa
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
12. F → R ` ¬F ∨R
Resposta:
1 F → R hip
2 |¬(¬F ∨R) hip− raa
3 ||F hip− raa
4 ||R 1, 3,mp
5 ||¬F ∨R 4, ad
6 ||¬F ∨R ∧ ¬(¬F ∨R) 2, 5, cj
7 |¬F 3− 6, raa
8 |¬F ∨R 7, ad
9 |(¬F ∨R) ∧ ¬(¬F ∨R) 2, 8, cj
10 ¬¬(¬F ∨R) 2− 9, raa
11 ¬F ∨R 10, dn
13. ¬(P → G), P → N,G ` N
Resposta:
1 ¬(P → G) hip
2 P → N hip
3 G hip
4 |¬N hip− raa
5 ||P hip− pc
6 |||¬G hip− raa
7 |||G ∧ ¬G 3, 6, cj
8 ||¬¬G 6− 7, raa
9 ||G 8, dn
10 |P → G 5− 9, pc
11 |(P → G) ∧ ¬(P → G) 1, 10, cj
12 ¬¬N 4− 11, raa
13 N 12, dn
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
14. ¬P ∨ (Q ∨R),¬¬P ∧ ¬Q,R→ D ` D
Resposta:
1 ¬P ∨ (Q ∨R) hip
2 ¬¬P ∧ ¬Q hip
3 R→ D hip
4 (¬P ∨Q) ∨R 1, ass
5 ¬(¬P ∨Q) 2, demor
6 R 4, 5, sd
7 D 3, 6,mp
15. A↔ Q,F ↔ R,A ∧R ` F ∧Q
Resposta:
1 A↔ Q hip
2 F ↔ R hip
3 A ∧R hip
4 A→ Q 1, E↔
5 R→ F 2, E↔
6 A 3, sp
7 R 3, sp
8 Q 4, 6,mp
9 F 5, 7,mp
10 F ∧Q 8, 9, cj
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
16. P → (A↔ B), C ∨D,D → ¬¬P,¬C ∧B ` A
Resposta:
1 P → (A↔ B) hip
2 C ∨D hip
3 D → ¬¬P hip
4 ¬C ∧B hip
5 ¬C 4, sp
6 D 2, 5, sd
7 ¬¬P 3, 6,mp
8 P 7, dn
9 A↔ B 1, 8,mp
10 B → A 9, E↔
11 B 4, sp
12 A 10, 11,mp
17. P ∧Q,P → R,R ∧ S → ¬T,Q→ S ` ¬T
Resposta:
1 P ∧Q hip.
2 P → R hip.
3 R ∧ S → ¬T hip.
4 Q→ S hip.
5 P 1, sp
6 Q 1, sp
7 R 2, 5,mp
8 S 4, 6,mp
9 R ∧ S 7, 8, cj
10 ¬T 3, 9,mp
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
18. P → ¬Q ∧R,P, S → Q,S ∨ T ` T
Resposta:
1 P → ¬Q ∧R hip.
2 P hip.
3 S → Q hip.
4 S ∨ T hip.
5 ¬Q ∧R 1, 2,mp
6 ¬Q 5, sp
7 ¬S 3, 6,mt
8 T 4, 7, sd
19. (E ∨ ¬B)→ (¬S ∨ T ), E,¬S → L, T → ¬C, (L ∨ ¬C)→ A ` A
Resposta:
1 (E ∨ ¬B)→ (¬S ∨ T ) hip.
2 E hip.
3 ¬S → L hip.
4 T → ¬C hip.
5 (L ∨ ¬C)→ A hip.
6 |¬A hip− raa
7 |¬(L ∨ ¬C) 5, 6,mt
8 |¬L ∧ ¬¬C 7, demor
9 |¬L 8, sp
10 |E ∨ ¬B 2, add
11 |¬S ∨ T 1, 10,mp
12 |¬¬S 3, 9,mt
13 |T 11, 12, sd
14 |¬C 4, 13,mp
15 |¬¬C 8, sp
16 |¬¬C ∧ ¬C 14, 15, cj
17 ¬¬A 6− 16, raa
18 A 17, dn
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
20. ¬F ∨ ¬G,¬F → Z,¬G→ ¬R, (Z ∨ ¬R)→ (U → P ),¬P ` ¬U
Resposta:
1 ¬F ∨ ¬G hip.
2 ¬F → Z hip.
3 ¬G→ ¬R hip.
4 (Z ∨ ¬R)→ (U → P ) hip.
5 ¬P hip
6 |¬(Z ∨ ¬R) hip− raa
7 |¬Z ∧ ¬¬R 6, demor
8 |¬¬R 7, sp
9 |¬¬G 3, 8,mt
10 |¬G ∨ ¬F 1, com
11 |¬F 9, 10, sd
12 |Z 2, 11,mp
13 |¬Z 7, sp
14 |Z ∧ ¬Z 12, 13, cj
15 ¬¬(Z ∨ ¬R) 6− 14, raa
16 Z ∨ ¬R 15, dn
17 U → P 4, 16,mp
18 ¬U 5, 17,mt
21. R→ P ∧Q,¬P ∨ ¬Q,R ∨ S ` S
Resposta:
1 R→ P ∧Q hip.
2 ¬P ∨ ¬Q hip.
3 R ∨ S hip.
4 |R hip− raa
5 |P ∧Q 1, 4,mp
6 |¬(P ∧Q) 2, demor
7 |(P ∧Q) ∧ ¬(P ∧Q) 5, 6, cj
8 ¬R 4− 7, raa
9 S 3, 8, sd
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
22. (P → Q)→ R,¬R, (¬P ∨Q) ∨ S ` S
Resposta:
1 P → Q)→ R hip.
2 ¬R, hip.
3 (¬P ∨Q) ∨ S hip.
4 |¬S hip− raa
5 |S ∨ (¬P ∨Q) 3, com
6 |¬P ∨Q 4, 5, sd
7 |P → Q 6, cond
8 |R 1, 7,mp
9 |R ∧ ¬R 2, 8, cj
10 ¬¬S 4− 9, raa
11 S 10, dn
23. ¬(P ∧Q)→ (R→ S), R ∧ ¬S,Q→ T ` T
Resposta:
1 ¬(P ∧Q)→ (R→ S) hip.
2 R ∧ ¬S hip.
3 Q→ T hip.
4 |¬(P ∧Q) hip− raa
5 |R→ S 1, 4,mp
6 |R 2, sp
7 |S 5, 6,mp
8 |¬S 2, sp
9 |S ∧ ¬S 7, 8, cj
10 ¬¬(P ∧Q) 4− 9, raa
11 P ∧Q 10, dn
12 Q 11, sp
13 T 3, 12,mp
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
24. P ∨Q→ R,¬R,Q ∨ (¬S ∨ T ) ` S → T
Resposta:
1 P ∨Q→ R hip.
2 ¬R hip.
3 Q ∨ (¬S ∨ T ) hip.
4 |S hip− pc
5 ||Q hip− raa
6 ||P ∨Q 5, ad
7 ||R 1, 6,mp
8 ||R ∧ ¬R 2, 7, cj
9 |¬Q 5− 8, raa
10 |¬S ∨ T 3, 9, sd
11 |¬¬S 4, dn
12 |T 10, 11, sd
13 S → T 4− 12, pc
25. ¬P ∨Q,¬S → ¬R,P ∨ (R ∧ T ) ` Q ∨ S
Resposta:
1 ¬P ∨Q hip.
2 ¬S → ¬R hip.
3 P ∨ (R ∧ T ) hip.
4 P → Q 1, cond
5 |P hip− pc
6 |Q 4, 5,mp
7 |Q ∨ S 6, ad
8 P → (Q ∨ S) 5− 7, pc
9 |R ∧ T hip− pc
10 |R 9, sp
11 |¬¬R 10, dn
12 |¬¬S 2, 11,mt
13 |S 12, dn
14 |Q ∨ S 13, ad
15 (R ∧ T )→ (Q ∨ S) 9− 14, pc
16 Q ∨ S 3, 8, 15,E∨
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
26. ¬P ∨ ¬Q→ R,R→ S ` ¬S → P
Resposta:
1 ¬P ∨ ¬Q→ R hip.
2 R→ S hip.
3 |¬S hip− pc
4|¬R 2, 3,mt
5 |¬(¬P ∨ ¬Q) 1, 4,mt
6 |¬¬P ∧ ¬¬Q 5, demor
7 |¬¬P 6, sp
8 |P 7, dn
9 ¬S → P 3− 8, pc
27. Q→ P, T ∨ S,Q ∨ ¬S ` ¬(P ∨R)→ T
Resposta:
1 Q→ P hip.
2 T ∨ S hip.
3 Q ∨ ¬S hip.
4 |¬(P ∨R) hip− pc
5 |¬P ∧ ¬R 4, demor
6 |¬P 5, sp
7 |¬Q 1, 6,mt
8 |¬S 3, 7, sd
9 |S ∨ T 2, com
10 |T 8, 9, sd
11 ¬(P ∨R)→ T 4− 10, pc
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
28. P ∧Q↔ ¬R,¬R→ ¬P,¬Q→ ¬R ` Q
Resposta:
1 P ∧Q↔ ¬R hip.
2 ¬R→ ¬P hip.
3 ¬Q→ ¬R hip.
4 |¬R hip− raa
5 |¬P 2, 4,mp
6 |¬P ∨ ¬Q 5, ad
7 |¬(P ∧Q) 6, demor
8 |¬R→ P ∧Q 1,E↔
9 |¬¬R 7, 8,mt
10 |R 9, dn
11 |R ∧ ¬R 4, 10, cj
12 ¬¬R 4− 11, raa
13 ¬¬Q 3, 12,mt
14 Q 13, dn
29. (P ∧Q) ∨ (P ∧R) ` P ∧ (Q ∨R)
Resposta:
1 (P ∧Q) ∨ (P ∧R) hip.
2 |P ∧Q hip− pc
3 |P 2, sp
4 |Q 2, sp
5 |Q ∨R 4, ad
6 |P ∧ (Q ∨R) 3, 5, cj
7 (P ∧Q)→ (P ∧ (Q ∨R)) 2− 6, pc
8 |P ∧R hip− pc
9 |P 8, sp
10 |R 8, sp
11 |Q ∨R 10, ad
12 |P ∧ (Q ∨R) 9, 11, cj
13 (P ∧R)→ (P ∧ (Q ∨R)) 8− 12, pc
14 P ∧ (Q ∨R) 1, 7, 13,∨E
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
30. ¬P ∨ ¬Q ` ¬(P ∧Q)
Resposta:
1 ¬P ∨ ¬Q hip.
2 |¬P hip− pc
3 ||P ∧Q hip− raa
4 ||P 3, sp
5 ||P ∧ ¬P 2, 4, cj
6 |¬(P ∧Q) 3− 5, raa
7 ¬P → ¬(P ∧Q) 2− 6, pc
8 |¬Q hip− pc
9 ||P ∧Q hip− raa
10 ||Q 9, sp
11 ||Q ∧ ¬Q 8, 10, cj
12 |¬(P ∧Q) 9− 11, raa
13 ¬Q→ ¬(P ∧Q) 8− 12, pc
14 ¬(P ∧Q) 1, 7, 13,∨E
31. ¬(P ∧B)→ ¬T, T ∨ (¬¬A ∧ ¬C), A→ ¬E,¬(P ∧B) ` (A→ ¬E) ∧ ¬E
Resposta:
1 ¬(P ∧B)→ ¬T hip
2 T ∨ (¬¬A ∧ ¬C) hip
3 A→ ¬E hip
4 ¬(P ∧B) hip
5 ¬T 1, 4,mp
6 ¬¬A ∧ ¬C 2, 5, sd
7 ¬¬A 6, sp
8 A 7, dn
9 ¬E 3, 8,mp
10 (A→ ¬E) ∧ ¬E 3, 9, cj
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
32. ¬¬A ∧ (B → C), E ∧D, ((B → C) ∧ (D ∨ F ))→ G ` (G ∧ A) ∧ E
Resposta:
1 ¬¬A ∧ (B → C) hip
2 E ∧D hip
3 ((B → C) ∧ (D ∨ F ))→ G hip
4 B → C 1, sp
5 D 2, sp
6 D ∨ F 5, ad
7 (B → C) ∧ (D ∨ F ) 4, 6, cj
8 G 3, 7,mp
9 E 2, sp
10 ¬¬A 1, sp
11 A 10, dn
12 G ∧A 8, 11, cj
13 (G ∧A) ∧ E 9, 12, cj
33. P → (A↔ B), C ∨D,D → ¬¬P,¬C ∧B ` A
Resposta:
1 P → (A↔ B) hip
2 C ∨D hip
3 D → ¬¬P hip
4 ¬C ∧B hip
5 ¬C 4, sp
6 D 2, 5, sd
7 ¬¬P 3, 6,mp
8 P 7, dn
9 A↔ B 1, 8,mp
10 B → A 9,E↔
11 B 4, sp
12 A 10, 11,mp
Disciplina: 093915 – Lógica
Ano/semestre: /
Créditos: 4 Hora-aula: 60
Área Temática: Fundamentos da Computação
Prof.: Mônica
34. (¬B ∧ ¬C)→ (D → C),¬B,C → B ` ¬D
Resposta:
1 (¬B ∧ ¬C)→ (D → C) hip
2 ¬B hip
3 C → B hip
4 ¬B → ¬C 3, cont
5 ¬C 2, 4,mp
6 ¬B ∧ ¬C 2, 5, conj
7 D → C 1, 6,mp
8 D → B 3, 7, sh
9 ¬B → ¬D 8, cont
10 ¬D 2, 9,mp
35. (P ∧Q)→ R,R→ S, T → ¬U, T,¬S ∨ U ` ¬(P ∧Q)
Resposta:
1 (P ∧Q)→ R hip
2 R→ S hip
3 T → ¬U hip
4 T hip
5 ¬S ∨ U hip
6 ¬U 3, 4,mp
7 ¬S 5, 6, sd
8 ¬R 2, 7,mt
9 ¬(P ∧Q) 1, 8,mt
36. P ∨Q→ R,R ∨Q→ (P → (S ↔ T )), P ∧ S ` S ↔ T
Resposta:
1 P ∨Q→ R hip
2 R ∨Q→ (P → (S ↔ T )) hip
3 P ∧ S hip
4 P 3, sp
5 P ∨Q 4, ad
6 R 1, 5,mp
7 R ∨Q 6, ad
8 P → (S ↔ T ) 2, 7,mp
9 S ↔ T 4, 8,mp