lista6TableauxGab TAbleaux, LOgica de primeira ordem puc rio

Prévia do material em texto

Lógica para Computação
2016.1 – Lista 6
Exercícios para P2
Profs. Cecilia Englander e Guilherme Lima
1. Verifique, através de tableaux, se as fórmulas abaixo são tautologias ou não.
(a) ∃y∀x(F y→ Fx)
Solu
p
ßão: É tautologia.
(b) ∃xP (x,x)→∃x∃yP (x, y)
Solu
p
ßão: É tautologia.
(c) ∃x∃yR(x, y)→∃xR(x,x)
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a,b}, R = {(a,b)}
(d) (∃xP (x)→∀xQ(x))→∀x(P (x)→Q(x))
Solu
p
ßão: É tautologia
(e) ¬∃yP (y)→ (∀y(∃xP (x)→ P (y)))
Solu
p
ßão: É tautologia
(f) ∀x(P (x)∧Q(x))→ (∀xP (x)∧∀xQ(x))
Solu
p
ßão: É tautologia
(g) ∀x(P (x)∨C )→ (∀xP (x)∨C )
Solu
p
ßão: É tautologia
(h) ∃x(P (x)→Q(x))→ (∀xP (x)→∀xQ(x))
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a,b}, P = {a,b},Q = {b}
(i) ∃y∀xP (x, y)→∀x∃yP (x, y)
Solu
p
ßão: É tautologia.
(j) ∀x∃yP (x, y)→∃y∀xP (x, y)
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a,b}, P = {(a,b), (b,a)}
(k) ∃x(P (x)→Q(x))→ (∃xP (x)→∃xQ(x))
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a,b}, P = {b},Q = {}
(l) ∀x∀y(x = y→ y = x)
Solu
p
ßão: É tautologia.
(m) ∀x∀y((B(x)∨B(y))→ x = y)→∀x∀y((B(x)∧B(y))→ f (x)= f (y))
Solu
p
ßão: É tautologia.
(n) ∀x((L(x,a)∧x = a))→∀xL(x,b)
Solu
p
ßão: É tautologia.
(o) ∀xL(x,x)→∀x∀y(L(x, y)→ x = y)
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a,b}, L = {(a,a), (b,b), (a,b)}
(p) ∀x∀y∀z∀w((R(x, y)∧R(z,w))→ (y 6= z∨R(x,w)))
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a,b,c,d}, R = {(a,b), (b,d), (a,d)}
(q) ∀x∀y(P (x, y)→R(x, f (y)))→∃x(P (x,x)→∃yR(x, y))
Solu
p
ßão: É tautologia.
(r) ∀xP (x)→∀xP ( f (x))
Solu
p
ßão: É tautologia.
(s) ∀xL(x, f (x))→∃xL( f (x),x)
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a}, L = {(a,b)}, f = {(a,b)}
(t) (∀x∀y(P (x, y)→R(x, f (y)))∧∃x(P (x,x)→∃yR(y, f (x))))→∃x∃yR(x, f (y))
Solu
p
ßão: Não é tautologia. Contra-exemplo: D = {a}, P = {}, R = {}, f = {(a,a)}