Exercícios resolvidos de Lógica Computacional - lista 1 (Ayala)

Prévia do material em texto

Soluc¸o˜es da Primeira Lista de Exerc´ıcios - Lo´gica
Computacional
Universidade de Bras´ılia - UnB
Instituto de Cieˆncias Exatas
Departamento de Ciencia da Computac¸a˜o - CIC
Andre´ Figueira Lourenc¸o
Fa´bio Henrique da Silva
Mauricio Ayala Rinco´n
1. Aplique as regras de precedeˆncia colocando o maior nu´mero de pareˆnteses poss´ıvel nas fo´rmulas abaixo:
(a) ¬p ∧ q → r
(¬p) ∧ q → r
((¬p) ∧ q)→ r
(((¬p) ∧ q)→ r)
(b) (p→ q) ∧ ¬(r ∨ p→ q)
(p→ q) ∧ (¬((r ∨ p)→ q))
((p→ q) ∧ (¬((r ∨ p)→ q)))
(c) (p→ q)→ (r → s ∨ t)
(p→ q)→ (r → (s ∨ t))
((p→ q)→ (r → (s ∨ t)))
(d) p ∨ (¬q → p ∧ r)
p ∨ ((¬q)→ p ∧ r)
p ∨ ((¬q)→ (p ∧ r))
(p ∨ ((¬q)→ (p ∧ r)))
(e) p ∨ q → ¬p ∧ r
p ∨ q → (¬p) ∧ r
(p ∨ q)→ ((¬p) ∧ r)
((p ∨ q)→ ((¬p) ∧ r))
(f) p ∨ q → ¬q
p ∨ q → (¬q)
(p ∨ q)→ (¬q)
((p ∨ q)→ (¬q))
(g) p∨ q∧ r e´ problema´tica, pois a associativi-
dade de ambos os sinais e´ a mesma, assim
na˜o e´ poss´ıvel determinar qual sinal deve
ser tratado primeiro.
1
2. Prove a validade das seguintes sequentes:
(a) (p ∧ q) ∧ r, s ∧ t ` q ∧ s
(p ∧ q) ∧ r
p ∧ q ∧e1
q
∧e2 s ∧ ts ∧e1
q ∧ s ∧i
(b) p ∧ q ` q ∧ p
p ∧ q
q
∧e2 p ∧ qp ∧e1
q ∧ p ∧i
(c) (p ∧ q) ∧ r ` p ∧ (q ∧ r)
(p ∧ q) ∧ r
(p ∧ q) ∧e1
p
∧e1
(p ∧ q) ∧ r
(p ∧ q) ∧e1
q
∧e2 (p ∧ q) ∧ rr ∧e2
q ∧ r ∧i
p ∧ (q ∧ r) ∧i
(d) p→ (p→ q), p ` q
p→ (p→ q) p
p→ q → e p
q
→ e
(e) q → (p→ r), ¬r, q ` ¬p
q → (p→ r) q
p→ r → e [p]u
r
→ e ¬r
⊥ ¬e
¬p ¬i, u
(f) ` (p ∧ q)→ p
[p ∧ q]u
p
∧e1
(p ∧ q)→ p → i, u
(g) p ` q → (p ∧ q)
p [q]u
p ∧ q ∧i
q → (p ∧ q) → i, u
(h) p ` (p→ q)→ q
[p→ q]u p
q
→ e
(p→ q)→ q → i, u
(i) (p→ r) ∧ (q → r) ` (p ∧ q)→ r
(p→ r) ∧ (q → r)
p→ r ∧e1
[p ∧ q]u
p
∧e1
r
→ e
(p ∧ q)→ r → i, u
(j) q → r ` (p→ q)→ (p→ r)
[p→ q]u [p]v
q → e q → r
r → e
p→ r → i, v
(p→ q)→ (p→ r) → i, u
(k) p→ (q → r), p→ q ` p→ r
p→ (q → r) [p]u
q → r → e
p→ q [p]u
q
→ e
r
→ e
p→ r → i, u
∗
*Aqui utilizamos a mesma suposic¸a˜o duas
vezes que, ao ser descarregada, descarrega
tambe´m todas suas co´pias.
(l) p→ q, r → s ` p ∨ r → q ∨ s
[p ∨ r]u
[p]v p→ q
q
→ e
q ∨ s ∨i
[r]t r → s
s
→ e
q ∨ s ∨i
q ∨ s ∨e, v, t
p ∨ r → q ∨ s → i, u
2
(m) p ∨ q ` r → ((p ∨ q) ∧ r)
[r]u (p ∨ q)
((p ∨ q) ∧ r) ∧i
r → ((p ∨ q) ∧ r) → i, u
(n) (p ∨ (q → p)) ∧ q ` p
(p ∨ (q → p)) ∧ q
p ∨ (q → p) ∧e1 [p]u
[q → p]v
(p ∨ (q → p)) ∧ q
q
∧e2
p
→ e
p
∨e, u, v
(o) p→ q, r → s ` p ∧ r → q ∧ s
[p ∧ r]u
p
∧e1 p→ q
q
→ e
[p ∧ r]u
r
∧e2 r → s
s
→ e
q ∧ s ∧i
p ∧ r → q ∧ s → i, u
(p) p→ q ` ((p ∧ q)→ p) ∧ (p→ (p ∧ q))
[p ∧ q]v
p
∧e1
(p ∧ q)→ p → i, v
[p]u
[p]u p→ q
q
→ e
p ∧ q ∧i
p→ (p ∧ q) → i, u
((p ∧ q)→ p) ∧ (p→ (p ∧ q)) ∧i
(q) ` q → (p→ (p→ (q → p)))
[q]u [p]v
q ∧ p ∧i
p
∧e2
q → p → i, u
p→ (q → p) → i, v [p]x
(p→ (q → p)) ∧ p ∧i
p→ (q → p) ∧e1
p→ (p→ (q → p)) → i, x [q]y
(p→ (p→ (q → p))) ∧ q ∧i
p→ (p→ (q → p)) ∧e1
q → (p→ (p→ (q → p))) → i, y
(r) p→ (q ∧ r) ` (p→ q) ∧ (p→ r)
p→ (q ∧ r) [p]u
q ∧ r → e
q
∧e1
p→ q → i, u
p→ (q ∧ r) [p]v
q ∧ r → e
r
∧e2
p→ r → i, v
(p→ q) ∧ (p→ r) ∧i
(s) (p→ q) ∧ (p→ r) ` p→ (q ∧ r)
(p→ q) ∧ (p→ r)
p→ q ∧e1 [p]u
q
→ e
(p→ q) ∧ (p→ r)
p→ r ∧e2 [p]u
r
→ e
q ∧ r ∧i
p→ (q ∧ r) → i, u
(t) ` (p→ q)→ ((r → s)→ (p ∧ r → q ∧ s)))
[p→ q]u
[p ∧ r]v
p
∧e1
q
→ e [r → s]
x
[p ∧ r]v
r
∧e2
s
→ e
q ∧ s ∧i
(p ∧ r)→ (q ∧ s) → i, v
(r → s)→ (p ∧ r → q ∧ s) → i, x
(p→ q)→ ((r → s)→ (p ∧ r → q ∧ s)) → i, u
(u) p→ q ` ¬q → ¬p
p→ q [¬q]u
¬p MT
¬q → ¬p → i, u
(v) p ∨ (p ∧ q) ` p
p ∨ (p ∧ q) [p]u
[p ∧ q]v
p
∧e1
p
∨e, u, v
3
(w) r, p→ (r → q) ` p→ (q ∧ r)
p→ (r → q) [p]u
r → q → e r
q
→ e
r
q ∧ r ∧i
p→ (q ∧ r) → i, u
(x) p→ (q ∨ r), q → s, r → s ` p→ s
p→ (q ∨ r) [p]u
q ∨ r → e
q → s [q]v
s
→ e r → s [r]
t
s
→ e
s
∨e, v, t
p→ s → i, u
(y) (p ∧ q) ∨ (p ∧ r) ` p ∧ (q ∨ r)
(p ∧ q) ∨ (p ∧ r)
[p ∧ q]u
p
∧e1 [p ∧ r]
v
p
∧e1
p
∨e, u, v
(p ∧ q) ∨ (p ∧ r)
[p ∧ q]x
q
∧e2
q ∨ r ∨i
[p ∧ r]t
r
∧e2
q ∨ r ∨i
q ∨ r ∨e, x, t
p ∧ (q ∨ r) ∧i
*Aqui repetimos duas suposic¸o˜es ja´ feitas ([p∧ q] e [p∧ r]) em outro local da prova. Note, pore´m, que as
novas suposic¸o˜es levam outros nomes e sa˜o consideradas diferentes das anteriores. Isso ocorre porque as
antigas ja´ foram descarregadas, assim, na˜o podemos repet´ı-las. Uma forma de perceber isso e´ trac¸ar uma
caixa que engloba as suposic¸o˜es de sua origem ate´ o ponto em que sa˜o descarregadas. Dessa forma, so´ e´
poss´ıvel a ocorreˆncia de caixas dentro de outras caixas e, caso hajam caixas que se interceptam, sabemos
que a prova na˜o esta´ correta.
3. Para os argumentos a seguir, mostre os que sa˜o va´lidos e os que na˜o sa˜o:
(a) ¬p→ ¬q ` q → p
¬p→ ¬q
[p]u
¬¬q ¬¬i
¬¬p MT
p
¬¬e
q → p → i, u
(c) ¬p, p ∨ q ` q
p ∨ q
[p]u ¬p
⊥ ¬e
q ⊥e [q]v
q
∨e, u, v
(b) ¬p ∨ ¬q ` ¬(p ∧ q)
¬p ∨ ¬q
[p ∧ q]u
p
∧e1 [¬p]x
⊥ ¬e
[p ∧ q]u
q
∧e2 [¬q]y
⊥ ¬e
⊥ ∨e, x, y
¬(p ∧ q) ¬i, u
4
(d) p ∨ q, ¬q ∨ r ` p ∨ r
p ∨ q
[p]u
p ∨ r ∨i
¬q ∨ r
[¬q]a [q]x
⊥ ¬e
r ⊥e [r]b
r
∨e, a, b
q → r → i, x [q]v
r
→ e
p ∨ r ∨i
p ∨ r ∨e, u, v
(e) p→ (q ∨ r), ¬q, ¬r ` ¬p
p→ (q ∨ r) [p]x
q ∨ r → e
¬q [q]u
⊥ ¬e
¬r [r]v
⊥ ¬e
⊥ ∨e, u, v
¬p ¬i, x
(f) ¬p ∧ ¬q ` ¬(p ∨ q)
[p ∨ q]x
¬p ∧ ¬q
¬p ∧e1 [p]u
⊥ ¬e
¬p ∧ ¬q
¬q ∧e2 [q]v
⊥ ¬e
⊥ ∨e, u, v
¬(p ∨ q) ¬i, x
(g) p ∧ ¬p ` (¬(r → q)) ∧ (r → q)
p ∧ ¬p
p
∧e1 p ∧ ¬p¬p ∧e2
⊥ ¬e
(¬(r → q)) ∧ (r → q) ⊥e
p ¬p p ∧ ¬p r → q ¬(r → q) ∧ (r → q)
T F F T F
T F F F F
F T F T F
F T F T F
*Para ser va´lida, sempre que as premissas forem
verdadeiras a conclusa˜o tambe´m deve ser verda-
deira, aqui na˜o ha´ nenhuma ocorreˆncia de T na
premissa nem na conclusa˜o, portanto, a sequente
e´ va´lida.
(h) p→ q, s→ t ` (p ∨ s)→ (q ∧ t)
p q s t p→ q s→ t (p ∨ s)→ (q ∧ t)
T T F F T T F©
F F T T T T F©
*A sequente na˜o e´ va´lida, pois em duas situac¸o˜es as premissas sa˜o T enquanto a conclusa˜o e´ F.
(i) ¬(¬p ∨ q) ` p
[¬p]u
¬p ∨ q ∧i ¬(¬p ∨ q)
⊥ ¬e
p
PBC, u
5
4. Prove a validade dos argumentos a seguir:
(a) ¬p→ p ` p
¬p→ p [¬p]u
p
→ e
[¬p]u
⊥ ¬e
p
PBC, u
(b) ¬p ` p→ q
[p]u ¬p
⊥ ¬e
q ⊥e
p→ q → i, u
(c) p ∨ q, ¬q ` p
p ∨ q [p]u
[q]v ¬q
⊥ ¬e
p ⊥e
p
∨e, u, v
(d) ` ¬p→ (p→ (p→ q))
[¬p]u [p]v
⊥ ¬e
q ⊥e
p→ q → i, v [p]t
(p→ q) ∧ p ∧i
p→ q ∧e1
p→ (p→ q) → i, t
¬p→ (p→ (p→ q)) → i, u
(e) ¬(p→ q) ` q → p
[p]u [¬p]v
⊥ ¬e
q ⊥e
p→ q → i, u ¬(p→ q)
⊥ ¬e
p
PBC, v
[q]t
p ∧ q ∧i
p
∧e1
q → p → i, t
(f) p→ q ` ¬p ∨ q
p ∨ ¬p LEM
p→ q [p]u
q
→ e
¬p ∨ q ∨i
[¬p]v
¬p ∨ q ∨i
¬p ∨ q ∨e, u, v
(g) ` (¬p ∨ q)→ (p→ q)
[¬p ∨ q]y
[¬p]u [p]v
⊥ ¬e
q ⊥e
p→ q → i, v
[p]x [q]t
p ∧ q ∧i
q
∧e2
p→ q → i, x
p→ q ∨e, u, t
(¬p ∨ q)→ (p→ q) → i, y
(h) p→ (q ∨ r), ¬q, ¬r ` ¬p
p→ (q ∨ r) [p]u
q ∨ r → e
[q]v ¬q
⊥ ¬e
[r]t ¬r
⊥ ¬e
⊥ ∨e, v, t
¬p ¬i, u
(i) (c ∧ n)→ t, (h ∧ ¬s), (h ∧ ¬(s ∨ c))→ p ` (n ∧ ¬t)→ p
h ∧ ¬s
h
∧e1
[s ∨ c]x
[s]u
h ∧ ¬s
¬s ∧e2
⊥ ¬e
[c]v
[n ∧ ¬t]y
n
∧e1
c ∧ n ∧i (c ∧ n)→ t
t
→ e [n ∧ ¬t]
y
¬t ∧e2
⊥ ¬e
⊥
∨e, u, v
¬(s ∨ c) ¬i, x
h ∧ ¬(s ∨ c) ∧i (h ∧ ¬(s ∨ c))→ p
p
→ e
(n ∧ ¬t)→ p
→ i, y
6
(j) i) ¬(r ∨ s→ q) ∧ (r ∨ s→ q) ` (p→ q) ∧ ¬(p→ q)
¬(r ∨ s→ q) ∧ (r ∨ s→ q)
¬(r ∨ s→ q) ∧e1
¬(r ∨ s→ q) ∧ (r ∨ s→ q)
(r ∨ s→ q) ∧e2
⊥ ¬e
(p→ q) ∧ ¬(p→ q) ⊥e
ii) (p→ q) ∧ ¬(p→ q) ` ¬(r ∨ s→ q) ∧ (r ∨ s→ q)
(p→ q) ∧ ¬(p→ q)
p→ q ∧e1
(p→ q) ∧ ¬(p→ q)
¬(p→ q)
∧e2
⊥ ¬e
¬(r ∨ s→ q) ∧ (r ∨ s→ q) ⊥e
(k) q ` (p ∧ q) ∨ (¬p ∧ q)
p ∨ ¬p LEM
[p]u q
p ∧ q ∧i
(p ∧ q) ∨ (¬p ∧ q) ∨i[¬p]v q
¬p ∧ q ∧i
(p ∧ q) ∨ (¬p ∧ q) ∨i
(p ∧ q) ∨ (¬p ∧ q)
∨e, u, v
(l) ¬(p ∧ q) ` ¬p ∨ ¬q
p ∨ ¬p LEM
q ∨ ¬q LEM
[p]x [q]u
p ∧ q ∧i ¬(p ∧ q)
⊥ ¬e
¬p ∨ ¬q ⊥e
[¬q]v
¬p ∨ ¬q ∨i
¬p ∨ ¬q ∨e, u, v
[¬p]y
¬p ∨ ¬q ∨i
¬p ∨ ¬q ∨e, x, y
(m) p ∧ q → r ` (p→ r) ∨ (q → r)
[r]a [p]t
r ∧ p ∧i
r ∧e1
p→ r → i, t
(p→ r) ∨ (q → r) ∨i
p ∨ ¬p LEM
(p ∧ q)→ r [¬r]b
¬(p ∧ q) MT
[p]g [q]m
p ∧ q ¬i
⊥ ¬e
¬q ¬i,m
¬p ∨ ¬q ∨i
[¬p]h
¬p ∨ ¬q] ∨i
¬p ∨ ¬q ∨e, g, h
[¬p]x [¬r]d
¬p ∧ ¬r ∧i
¬p ∧e1
¬r → ¬p → i, d [p]k
¬¬r MT
r ¬¬e
p→ r → i, k
(p→ r) ∨ (q → r) ∨i
[¬q]y [¬r]f
¬q ∧ ¬r ∧i
¬q ∧e1
¬r → ¬q → i, f [q]l
¬¬r MT
r ¬¬e
q → r → i, l
(p→ r) ∨ (q → r) ∨i
(p→ r) ∨ (q → r) ∨e, x, y
(p→ r) ∨ (q → r) ∨e, a, b
7
Soluc¸a˜o alternativa:
(p→ r) ∨ ¬(p→ r) LEM
[p→ r]a
(p→ r) ∨ (q → r) ∨i
[¬(p→ r)]b
[p]u [q]t
p ∧ q ∧i (p ∧ q)→ r
r → e
p→ r → i, u
⊥ ¬e
r ⊥e
q → r → i, t
(p→ r) ∨ (q → r) ∨i
(p→ r) ∨ (q → r) ∨e, a, b
(n) p ∧ q ` ¬(¬p ∨ ¬q)
[¬p ∨ ¬q]x
[¬p]u
p ∧ q
p
∧e1
⊥ ¬e
[¬q]v
p ∧ q
q
∧e2
⊥ ¬e
⊥ ∨e, u, v
¬(¬p ∨ ¬q) ¬i, x
(o) ¬(¬p ∨ ¬q) ` p ∧ q
p ∨ ¬p LEM
[p]u [¬p]x
⊥ ¬e
¬p ∨ ¬q ⊥e
[¬p]v
¬p ∨ ¬q ∨i
¬p ∨ ¬q
∨e, u, v
¬(¬p ∨ ¬q)
⊥
¬e
p
PBC, x
q ∨ ¬q LEM
[q]a [¬q]y
⊥ ¬e
¬p ∨ ¬q ⊥e
[¬q]b
¬p ∨ ¬q ∨i
¬p ∨ ¬q ∨e, a, b ¬(¬p ∨ ¬q)
⊥
¬e
q
PBC, y
p ∧ q ∧i
(p) p→ q ` ¬p ∨ q
i) Com LEM:
q ∨ ¬q LEM
[q]u
¬p ∨ q ∨i
p→ q [¬q]v
¬p MT
¬p ∨ q ∨i
¬p ∨ q ∨e, u, v
ii) Sem LEM:
[q]a
q ∨ ¬q ∨i [¬(q ∨ ¬q)]b
⊥ ¬e
¬q ¬i, a
q ∨ ¬q ∨i [¬(q ∨ ¬q)]b
⊥ ¬e
q ∨ ¬q PBC
[q]u
¬p ∨ q ∨i
p→ q [¬q]v
¬p MT
¬p ∨ q ∨i
¬p ∨ q ∨e, u, v
8
(q) ` (p→ q) ∨ (q → r)
(p→ q) ∨ ¬(p→ q) LEM
[(p→ q)]a
(p→ q) ∨ (q → r) ∨i
[p]u [q]v
p ∧ q ∧i
q
∧e2
p→ q → i, u [¬(p→ q)]b
⊥ ¬e
r ⊥e
q → r → i, v
(p→ q) ∨ (q → r) ∨i
(p→ q) ∨ (q → r) ∨e, a, b
(r) p→ q, ¬p→ r, ¬q → ¬r ` q
p ∨ ¬p LEM
p→ q [p]x
q
→ e
q ∨ r ∨i
¬p→ r [¬p]y
r
→ e
q ∨ r ∨i
q ∨ r ∨e, x, y [q]u
[r]v
¬¬r ¬¬i ¬q → ¬r
¬¬q MT
q
¬¬e
q
∨e, u, v
(s) p→ q, r → ¬t, q → r ` p→ ¬t
[p]u p→ q
q
→ e
q → r
r
→ e
r → ¬t
¬t → e
p→ ¬t → i, u
(t) (p→ q)→ r, s→ ¬p, t, (¬s ∧ t)→ q ` r
s→ ¬p
[p]u
¬¬p ¬¬i
¬s MT t
¬s ∧ t ∧i (¬s ∧ t)→ q
q
→ e
p→ q → i, u (p→ q)→ r
r
→ e
(u) (s→ p) ∨ (t→ q) ` (s→ q) ∨ (t→ p)
(s→ p) ∨ (t→ q)
[s→ p]u [s]x
p → e
p ∨ q ∨i
[t→ q]v [t]y
q → e
p ∨ q ∨i
p ∨ q ∨e, u, v
[p]b
t→ p → i, y
(s→ q) ∨ (t→ p) ∨i
[q]a
s→ q → i, x
(s→ q) ∨ (t→ p) ∨i
(s→ q) ∨ (t→ p) ∨e, a, b
9
(v) (p ∧ q)→ r, r → s, q ∧ ¬s ` ¬p
[p]u
q ∧ ¬s
q
∧e1
p ∧ q ∧i (p ∧ q)→ r
r
→ e
r → s
s
→ e q ∧ ¬s¬s ∧e2
⊥ ¬e
¬p ¬i, u
5. Suponha por absurdo que
√
2 e´ um nu´mero racional, enta˜o pode ser escrito como frac¸a˜o da forma k/l
com inteiros k e l 6= 0. Elevando ambos os lados ao quadrado, obtemos 2 = k2/l2 ou, equivalentemente,
2l2 = k2. Podemos supor que quaisquer fatores iguais a 2 em comum em k e l foram cancelados. Mas
temos que k2 e´ par, ou seja, k2 e´ divis´ıvel por 2, pois 2l2 o e´, e portanto k tambe´m o e´, ja que o quadrado
de um nu´mero par e´ par. Logo k = 2n e 2l2 = (2n)2 = 4n2 com n pertencente aos nu´meros inteiros,
obtendo l2 = 2n2 o que torna l2 um nu´mero par, pelos mesmos motivos do caso anterior. Que e´ uma
contradic¸a˜o, pois todos fatores iguais a 2 em comum nos dois termos foram cancelados. Portanto
√
2 e´
irracional.
10
6. Construa a tabela-verdade para ¬p∨ q e verifique que ela coincide com a tabela-verdade para p→ q.
p q ¬p ¬p ∨ q p→ q
T T F T T
T F F F F
F T T T T
F F T T T
7.
(a) φ : ((p→ q)→ p)→ p
p q p→ q (p→ q)→ p φ
T T T T T
T F F T T
F T T F T
F F T F T
*φ e´ uma tautologia.
(b) φ : (¬p ∧ q)→ (p ∧ (q ∨ ¬r))
p ¬p q r ¬r ¬p ∧ q q ∨ ¬r p ∧ (q ∨ ¬r) φ
T F T T F F T T T
T F T F T F T T T
T F F T F F F F T
T F F F T F T T T
F T T T F T T F F
F T T F T T T F F
F T F T F F F F T
F T F F T F T F T
(c) φ : p ∨ (¬(q ∧ (r → q)))
p q r r → q q ∧ (r → q) ¬(q ∧ (r → q)) φ
T T T T T F T
T T F T T F T
T F T F F T T
T F F T F T T
F T T T T F F
F T F T T F F
F F T F F T T
F F F T F T T
11
(d) φ : (p ∧ q)→ (p ∨ q)
p q p ∧ q p ∨ q φ
T T T T T
T F F T T
F T F T T
F F F F T
*φ e´ uma tautologia.
(e) φ : ((p→ ¬q)→ ¬p)→ q
p ¬p q ¬q p→ ¬q (p→ ¬q)→ ¬p φ
T F T F F T T
T F F T T F T
F T T F T T T
F T F T T T F
(f) φ : (p→ q) ∨ (p→ ¬q)
p q ¬q p→ q p→ ¬q φ
T T F T F T
T F T F T T
F T F T T T
F F T T T T
*φ e´ uma tautologia.
(g) φ : ((p→ q)→ p)→ p
p q p→ q (p→ q)→ p φ
T T T T T
T F F T T
F T T F T
F F T F T
*φ e´ uma tautologia.
(h) φ : ((p ∨ q)→ r)→ ((p→ r) ∨ (q → r))
p q r p ∨ q p→ r q → r (p ∨ q)→ r (p→ r) ∨ (q → r) φ
T T T T T T T T T
T T F T F F F F T
T F T T T T T T T
T F F T F T F T T
F T T T T T T T T
F T F T T F F T T
F F T F T T T T T
F F F F T T T T T
*φ e´ uma tautologia.
(i) φ : (p→ q)→ (¬p→ ¬q)
p ¬p q ¬q p→ q ¬p→ ¬q φ
T F T F T T T
T F F T F T T
F T T F T F F
F T F T T T T
12
8. φ : ¬((q → ¬p) ∧ (p→ (r ∨ q)))
p q ¬p r q → ¬p r ∨ q p→ (r ∨ q) φ
T T F T F T T T
T T F F F T T T
T F F T T T T F
T F F F T F F T
F T T T T T T F
F T T F T T T F
F F T T T T T F
F F T F T F T F
* Na˜o e´ va´lida, mas e´ satisfat´ıvel.
9.
(a) ¬p ∨ (q → p) ` ¬p ∧ q
p ¬p q q → p ¬p ∨ (q → p) ¬p ∧ q
T F T T T© F©
T F F T T© F©
F T T F T T
F T F T T© F©
(b) ¬r → (p ∨ q), r ∧ ¬q ` r → q
p q ¬q r ¬r p ∨ q ¬r → (p ∨ q) r ∧ ¬q r → q
T T F T F T T F T
T T F F T T T F T
T F T T F T T© T© F©
T F T F T T T F T
F T F T F T T F T
F T F F T T T F T
F F T T F F T© T© F©
F F T F T F F F T
(c) p→ (q → r) ` p→ (r → q)
p q r q → r r → q p→ (q → r) p→ (r → q)
T T T T T T T
T T F F T F T
T F T T F T© F©
T F F T T T T
F T T T T T T
F T F F T T T
F F T T F T T
F F F T T T T
13
(d) ¬p, p ∨ q ` ¬q
p ¬p q p ∨ q ¬q
T F T T F
T F F T T
F T© T T© F©
F T F F T
(e) p→ (¬q ∨ r), ¬r ` ¬q → ¬p
p ¬p q ¬q r ¬q ∨ r ¬r p→ (¬q ∨ r) ¬q → ¬p
T F T F T T F T T
T F T F F F T F T
T F F T T T F T F
T F F T F T T© T© F©
F T T F T T F T T
F T T F F F T T T
F T F T T T F T T
F T F T F T T T T
10.
(a) � (p→ q) ∨ (q → r)
p q r p→ q q → r (p→ q) ∨ (q → r)
T T T T T T
T T F T F T
T F T F T T
T F F F T T
F T T T T T
F T F T F T
F F T T T T
F F F T T T
* Vale, pois todas as avaliac¸o˜es da fo´rmula sa˜o T (tautologia).
(b) � ((q → (p ∨ (q → p))) ∨ ¬(p→ q))→ p. Chamemos φ : q → (p ∨ (q → p):
p q q → p p ∨ (q → p) φ p→ q ¬(p→ q) (φ ∨ ¬(p→ q)) (φ ∨ ¬(p→ q))→ p
T T T T T T F T T
T F T T T F T T T
F T F F F T F F T
F F T T T T F T F©
* Na˜o vale, pois ha´ uma avaliac¸a˜o F.
14