Ex comentados demonstracoes

Prévia do material em texto

Demonstrações 
Exemplos 
 
Lógica para Computação 
 Profa. Mônica Py 
 
 
Demonstrações - Mônica Py 
Demonstração 
!   Vamos acompanhar exemplos de 
como podemos elaborar estratégias 
para montar uma sequência de 
demonstração e provar que um 
argumento é válido. (Seção 2.5 do 
Livro) 
 
!   Exemplos: 
1. P → (Q ∧ R), P |⎯ P ∧ Q 
2. (P ∧ Q) → (R ∧ S), ¬¬P, Q |⎯ S 
3. P ∨ (Q ∧ R), (P ∨ Q) → S |⎯ P ∨ S 
4. A → (B ∨ C), ¬B, ¬C |⎯ ¬A 
5. B ↔ A, (B ∧ C) → (E ∨ Q), 
 (B ∧ A) → C, ¬E, B |⎯ Q 
Demonstrações - Mônica Py 
Regras de Inferência 
Demonstrações - Mônica Py 
Regras de Equivalência 
Demonstrações - Mônica Py 
Regras Derivadas 
Demonstrações - Mônica Py 
Exemplo 1 
P → (Q ∧ R), P |⎯ P ∧ Q 
Demonstrações - Mônica Py 
 
P → (Q ∧ R), P |⎯ P ∧ Q 
1. P → Q ∧ R hip. 
2. P hip. 
3. Q ∧ R 1,2, mp 
4. Q 3, sp 
5. P ∧ Q 2,4, cj 
Exemplo 1 
Demonstrações - Mônica Py 
Exemplo 2 
(P ∧ Q) → (R ∧ S), 
¬¬P, Q |⎯ S 
Demonstrações - Mônica Py 
1. (P ∧ Q) → (R ∧ S) hip. 
2. ¬¬P hip 
3. Q hip 
4. P 2, dn 
5. P ∧ Q 3,4, cj 
6. R ∧ S 1,5, mp 
7. S 6, sp 
(P ∧ Q) → (R ∧ S), 
¬¬P, Q |⎯ S 
Exemplo 2 
Demonstrações - Mônica Py 
 
Exemplo 3 
P ∨ (Q ∧ R), (P ∨ Q) → S 
|⎯ P ∨ S 
Demonstrações - Mônica Py 
P ∨ (Q ∧ R), (P ∨ Q) → S 
|⎯ P ∨ S 
1. P ∨ (Q ∧ R) hip. 
2. (P ∨ Q) → S hip 
3. (P ∨ Q) ∧ (P ∨ S) 1,dist 
4. P ∨ Q 3, sp 
5. S 2,4, mp 
6. P ∨ S 5, ad 
Exemplo 3 
Demonstrações - Mônica Py 
 
Exemplo 4 
A → (B ∨ C), ¬B, 
¬C |⎯ ¬A 
Demonstrações - Mônica Py 
A → (B ∨ C), ¬B, 
¬C |⎯ ¬A 
1. A → (B ∨ C) hip. 
2. ¬B hip 
3. ¬C hip. 
4. ¬B ∧ ¬C 2,3, cj 
5. ¬(B ∨ C) 4, demor 
6. ¬A 1,5, mt 
Exemplo 4 
Demonstrações - Mônica Py 
 
Exemplo 5 
B ↔ A, (B ∧ C) → (E ∨ Q), 
 (B ∧ A) → C, ¬E, B |⎯ Q 
Demonstrações - Mônica Py 
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,9, cj 
11. E ∨ Q 2,10, mp 
12. Q 4,11, sd 
Exemplo 5 
B ↔ A, (B ∧ C) → (E ∨ Q), 
 (B ∧ A) → C, ¬E, B |⎯ Q