Lista3 Regras de Inferencia Matemática Discreta

Prévia do material em texto

Lista 3 de Matemática Discreta I
Simone Ribeiro
1. Demonstre as seguintes proposições. Use como regras de inferência apenas o
modus ponens, o modus tollens e a lei da conjunção. Indique as regras usadas em
cada passagem.
(a) P, P→ (Q ∨ R), (Q ∨ R)→ S ` S.
(b) P→ Q, Q→ R, ∼ R ` ∼ P.
(c) P, P→ Q ` P ∧Q.
2. A demomstração seguinte deduz R das premissas P ∨ Q, P → R e Q → R. Falta
colocar as justificativas de cada passo. Complete a demonstração, sabendo que
além das regras de inferência, se usa também a equivalência A→ B⇐⇒∼ A ∨ B.
1 P ∨Q,
2 P→ R,
3 Q→ R,
4 ∼ P→ Q,
5 ∼ P→ R,
6 R,
3. Dada a premissa P ∧Q, deduza P ∨Q.
4. Tomando como premissas que P→ Q, Q→ R e R→ P, deduza formalmente que
P↔ Q.
5. Indicar a(s) regra(s) de inferência que justifica(m) a validade das seguintes de-
duções.
(a) P→ Q ` (P→ Q)∨ ∼ R.
(b) ∼ P ∧ (Q→ R) ` ∼ P.
(c) P→ Q, Q→∼ R ` P→∼ R.
(d) P→ Q ∨ R ` P→ P ∧ (Q ∨ R).
1
2
6. Demonstrar o argumento P→ (Q→ R), P→ Q, P ` R
7. Demonstrar o argumento P→ Q, (P ∧Q)→ R, ∼ (P ∧ R, ` ∼ P.
8. Demonstrar o argumento P ∨Q→ R, R ∨Q→ (P→ (S↔ T)), P ∧ S ` S↔ T.
9. Demonstrar o argumento P→ Q, (P→ R)→ S ∨Q, P ∧Q→ R, ∼ S ` Q.
10. Demonstrar o argumento P→ R, Q→ S, ∼ R, (P ∨Q) ∧ (R ∨ S) ` S.
11. Demonstrar o argumento P→ Q, Q→ R, R→ S, ∼ S, P ∨ T ` T.
12. Demonstrar o argumento (P → Q) ∧ (R → S), T → U, U → V, ∼ Q∨ ∼ V ` ∼
P∨ ∼ T.
13. Use redução ao absurdo para mostrar a validade do argumento (P→ Q)∨ (R∧ S),
∼ Q, ` P→ S.
14. Use redução ao absurdo para mostrar a validade do argumento (P→ Q), (Q↔ S),
T ∨ (R∧ ∼ S) ` P→ T.