Lista2

Prévia do material em texto

Pontif´ıcia Universidade Cato´lica do Parana´
Centro de Cieˆncias Exatas e de Tecnologia
Departamento de Informa´tica
Programa de Aprendizagem em Lo´gica Matema´tica
Prof. Bra´ulio Coelho A´vila
Lista 2 — 2008
1. Para cada sentenc¸a a seguir deve-se:
(a) Encontrar a sua forma canoˆnica. Simplificar a sentenc¸a somente permitindo os
s´ımbolos: ¬, ∨ e ∧;
(b) Encontrar a mais simplificada: Forma Normal Disjuntiva, Forma Normal Con-
juntiva, Notac¸a˜o Clausal e Notac¸a˜o de Kowalsky (utilizar manipulac¸a˜o sinta´tica);
(c) Verificar se e´ um teorema. Fazer a prova atrave´s da Negac¸a˜o do Teorema e
demonstrar utilizando a a´rvore de Resoluc¸a˜o (utilizar manipulac¸a˜o sinta´tica):
i. p ∧ ¬(q ∨ r) → (r ∨ p) ∨ q → s
ii. ¬(p ∧ (q ∨ r)) → ((¬q ∨ ¬r) → ¬p)
iii. p ∧ (q → r) → s↔ (p ∨ r)
iv. (¬p ∧ q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r)
v. (q → ¬p) ↔ ((p→ ¬r) → ¬r)
vi. (p ∧ q) ∨ q ∧ ¬(q ∨ r → r) ↔ s
vii. ¬r ∨ (p ∧ r) ↔ r → ¬p ∨ q
viii. (p→ q) → r → ((r ∨ p) ∨ q)
ix. ¬((p→ q ∧ r) → ((¬q ∨ ¬r) → ¬p))
x. (p ∨ (q ∧ r)) → (p ∨ s→ (q → ((p ∨ s) ∧ q)))
xi. (p→ q) → (q ∨ r) ↔ ¬(p ∨ r)
xii. (q ∨ r) ↔ ((p→ ¬q) → r)
xiii. (p→ r) ↔ ((q ∨ r) → (p→ r))
xiv. ¬(p ∨ q) ∧ q ↔ ¬(p ∨ r)
xv. (p→ q ∧ ¬p) → ¬q ↔ ¬(p ∨ r)
xvi. ¬(p ∨ q) ↔ ¬p ∧ q ↔ r ∨ s
xvii. p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r)
xviii. p→ ¬q ↔ ((¬q ∨ ¬r) → ¬p)
xix. ¬(p ∧ q) ↔ (p→ q ∧ ¬p) → ¬q
xx. (p ∧ q) ∨ q ↔ p ∨ (¬p ∧ q ∧ r)
xxi. p ∧ ¬(q ∨ r) ↔ (¬q ∨ ¬r) → ¬p
xxii. ¬(p ∧ (q ∨ r)) ↔ (p→ q ∧ ¬p)
xxiii. (q → ¬p) ↔ ((p→ ¬r) → (¬r → q))
xxiv. p ∧ ¬(q ∨ r) ↔ (r ∨ p) ∨ q → s
xxv. (p ∧ (q ∨ r)) ↔ ((¬q ∨ ¬r) → ¬p)
xxvi. p ∧ (q → r) → s↔ (p ∨ r)
xxvii. (¬p ∧ q ∧ r) → (p ∨ q) ↔ (p ∨ r)
xxviii. (¬p ∧ ¬r) → ¬(p ∨ r) ↔ (q ∧ p)
xxix. (q → ¬p) ↔ (q ∧ p) → (p→ ¬r)
xxx. p↔ ¬(q ∨ r) → (¬q ∨ ¬r) ↔ ¬p
2. Verificar se a sentenc¸a abaixo e´ um teorema. Fazer a prova atrave´s da Negac¸a˜o da
Tese e demonstrar utilizando a a´rvore de Resoluc¸a˜o (utilizar manipulac¸a˜o sinta´tica):
(a) (p ∨ (q ∧ r)) ∨ ¬r ∧ (p ∨ s ∨ (q → ¬r ∧ ((p ∨ s) ∧ q))) |= s→ ¬p ∨ q
(b) q ∧ s→ q ∨ ¬r → (¬q ∨ ¬r) ∧ ¬p |= ¬(p→ ¬r) ∨ ¬s
(c) ((¬p ∨ q) ∧ ¬r ∨ s) ∧ ¬t |= ¬p ∨ ¬r ∨ ¬t
(d) (p ∨ (q ∧ r)) → (p ∨ s→ (q → ((p ∨ s) ∧ q))) |= p→ ¬r ∨ ¬s
(e) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r) |= ¬p ∨ r ∨ ¬q
(f) (p→ p) → r, (r ∨ q) → s |= s
(g) (p ∧ q) → r, (q ∧ r) → s |= (p ∧ q) → s
(h) p→ (q → r), q → (r → ¬q) |= ¬p ∨ ¬q
(i) s→ (t ∨ ¬u), u→ (¬t ∨ r), (s ∧ u) → ¬r |= ¬s ∨ ¬u
(j) ¬p→ (q ∧ r), s→ ¬r |= s→ p
(k) (p ∨ q) → (r ∧ s), (s ∨ t) → u, p ∨ t |= u
(l) ¬p→ (q ∧ r), q → p, r → ¬p |= p
(m) (r ∨ s) → t, (p ∨ q) → t, r ∨ p |= t
(n) (p ∨ q) → r, (¬p ∨ s) → t |= r ∨ t
(o) (p ∨ q) → (r ∧ s), (s ∨ t) → (p ∧ ¬p) |= ¬p
(p) (r → (s→ r)) → t |= t
(q) q → (t ∧ u), (q ∧ u) → (p↔ ¬p) |= ¬q
(r) (q ∨ r) → (s ∧ t), (t ∨ u) → (p ∨ ¬s), (p ∨m) → ¬(q ∧ t) |= ¬q
(s) (r ∧ s) ↔ (p ∧ q), r → s, q → p |= r ↔ q
(t) t→ ((m ∨ n) → (p ∧ q)), u→ ((q ∨ r) → (s ∧ ¬n)) |= (t ∧ u) → ¬n
(u) p→ ((q ∨ ¬q) → (s ∨ t)), t→ ¬(r ∨ ¬r) |= p→ s
(v) p→ ((q → q) → r), r → ((s→ (t→ s)) → (u ∧ ¬u)) |= ¬p