BCC101
Matemática Discreta I
Lógica de Predicados
Álgebra e Dedução
1
Álgebra de Predicados
∀x. ¬P(x) = ¬∃x. P(x)
∃x. ¬P(x) = ¬∀x. P(x)
{∃DeMorgan}
{∀DeMorgan}
∀x. P(x) ∧∀x. Q(x) =∀x. (P(x) ∧Q(x)) {∀Dist}
∃x. P(x) ∨∃x. Q(x) = ∃x.(P(x) ∨Q(x)) {∃Dist}
(∀x. P(x)) ∧Q = ∀x. (P(x) ∧ Q)
(∀x. P(x)) ∨Q = ∀x. (P(x) ∨ Q)
(∃x. P(x)) ∧Q = ∃x. (P(x) ∧Q)
(∃x. P(x)) ∨Q = ∃x. (P(x) ∨Q)
se x não ocorre
livre em Q
... mais as equações da
álgebra booleana
2
Raciocínio Equacional com Predicados
Teorema
( (x. P(x))  (y. Q(y)) ) = (x. y. P(x)  Q(y) )
 Prova
(x. P(x))  (y. Q(y))
= ((x. P(x)))  (y. Q(y))
= (x. P(x))  (y. Q(y))
= x. ( (P(x))  (y. Q(y)) )
= x. ( (y. Q(y))  (P(x)) )
= x. y. ( Q(y)  (P(x)) )
= x. y. ( (P(x))  Q(y) )
= x. y. ( P(x)  Q(y) )
{implicação}
{∀ DeMorgan}
{∃Dist}
{ comut}
{y não ocorre em P(x)}
{ comut}
{implicação}
qed
3
Exercícios
Prove a seguinte equivalência:
 x.P(x)  y. ¬Q(y) = ¬ x. P(x)  Q(x)
4
Regras de Inferência
p(y) {y arbitrária}
------{I}
x. p(x)
{y pode ser substituída por x em p}
x e y são variáveis
w é um termo
x. p(x) {universo não vazio}
--{E}
p(w)
p(w) {w pode ser substituída por x em p}
------{I}
x. p(x)
x. p(x)
p(y) |– z {y não é livre em z}
------{E}
z
Esta regra provoca descarga
de hipótese
... mais as regras de inferência
do cálculo proposicional
5
Variáveis Arbitrárias
 Em uma prova, uma variável é arbitrária se ela não
ocorre livre em nenhuma hipótese não descartada
 Exemplos
x. F(x)
{E}
F(p)
p é arbitrária? Sim
G(p, q)
{∃I}
∃y. G(p, y)
p é arbitrária? Não
descarregada
P(x)  Q
{EL}
P(x)
{I}
P(x)  Q  P(x)
{I}
x. (P(x)  Q  P(x))
x é arbitrária? Sim
6
Uma Prova fácil - para esquentar ...
usando {I} e {E}
Teorema (comuta)
x. y. F(x,y) |– y. x. F(x,y)
prova
x.p(x) {…….}
{E}
p(w)
x.y.F(x,y) { ok }
{E}
faz papel de p(x)
y.F(p,y) { ok }
{E}
na regra {E}
F(p,q) { p arbitrária }
{I}
x. F(x,q) { q arbitrária }
p(y) {y arb.}
{I}
{I}
y. x. F(x,y)
x.p(x)
7
Eliminação do Existencial
semelhante a {E}
Teorema
x. P(x), x. P(x)Q(x) |– x. Q(x)
Prova
x. P(x)Q(x) { ok }
{E}
P(y)
P(y)Q(y)
{E}
Q(y)

{I}
x. P(x)
x. Q(x)
{E}
x. Q(x) {y não é livre em x.Q(x)}
x. F(x) F(y) |– A {y não é livre em A}
{E}
A
x.Q(x) faz papel de
A na regra {E}
8
Uma Prova Incorreta
Teorema Ruim
x. P(x), x. (P(x)Q(x)) |– x. Q(x)
Suposta prova
x. (P(x)Q(x))
{E}
Problema é aqui
P(y)
P(y)Q(y)
{E}
Q(y)
{I}
x. P(x)
x. Q(x)
{E}
x. Q(x)
y é livre nessa hipótese
Portanto, {I} não é usada de
maneira adequada.
F(y) {y arbitrária}
{I}
x. F(x)
9
Quantificador Universal move para fora
mas não pode ser movido para dentro
Teorema
x.y.F(x, y) |– y.x. F(x, y)
y. F(x, y) { ok }
y. p(y) { …… }
{E}
{E}
F(x, y) { ok }
p(w)
{I}
x. F(x, y) {y arb}
{I}
x.y.F(x, y)
y. x. F(x, y)
{E}
y.x.F(x, y)
p(w) {x é variável nova }
{I}
x. p(x)
x. p(x)
p(x) |– z {x não livre em z}
{E}
p(y) {y arb}
z
{I}
10
x. p(x)
Exercícios
Prove os seguintes sequentes:
 x.P(x)  x. Q(x) |– x. P(x)  Q(x)
 x.P(x)  Q(x), x.P(x) |– x. Q(x)
11