Lista 4 - Cálculo de Predicados

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 4 — 2008
1. Obter a Forma Clausal e a Notac¸a˜o de Kowalski da seguinte fo´rmula:
(a) ∃x¬∀y((r(x, y) ∧ r(y, x) ∨ r(z, y))↔ ∀z¬∀u(r(y, z) ∨ r(z, u) ∧ r(u, y)))
(b) ∀x∀y(∃z(p(x, z) ∧ p(y, z))→ ∃u(q(x, y, u)))
(c) ∃x∀y(r(x, y)↔ ¬∃z∃u(r(y, z) ∧ r(z, u) ∨ r(u, y)))
(d) ¬∃x∀y(r(x, y) ∨ r(y, x))→ ¬∀z∀u(r(u, z) ∨ r(z, u) ∨ r(u, z))
(e) ¬∃x∀y((r(x, y) ∨ r(y, x))↔ ¬∀z∀u(r(y, z) ∨ r(z, u) ∧ r(u, y)))
(f) ∃x∀y¬(r(x, y)→ ¬∃z∃u(r(y, z) ∨ r(z, u) ∧ r(u, y)))
(g) ¬∃x∀y((r(x, y) ∨ r(y, x))↔ ¬∀z∀u(r(y, z) ∨ r(z, u) ∧ r(u, y)))
(h) ∃x¬∀y¬(r(x, y)→ ¬∃z∃u(r(y, z) ∨ r(z, u) ∧ r(u, y)))
(i) ∃x¬∀y((r(x, y) ∨ r(y, x))↔ ∀z¬∀u(r(y, z) ∨ r(z, u) ∨ r(u, y)))
(j) ∃x¬∀y((r(x, y) ∧ r(y, x))↔ ¬∀z∀u(r(y, z) ∧ r(z, u) ∧ r(u, y)))
2. Deduzir a conclusa˜o, a partir das premissas abaixo:
(a) As MeninasSuperPoderosas brigam com todas as pessoas ma´s. MacacoLoco faz
algumas coisas que sa˜o ilegais. Aqueles que fazem coisas ilegais sa˜o pessoas ma´s.
Se as MeninasSuperPoderosas brigam com algue´m e esse algue´m faz algo ilegal,
enta˜o esse algue´m termina na cadeia. Logo, MacacoLoco termina na cadeia.
e do esquema abreviador a seguir:
Briga(x) : MeninasSuperPoderosas brigam com x;
Faz(x,y) : pessoa x faz y;
PessoaMa´(x) : x e´ uma pessoa ma´;
Ilegal(x) : x e´ uma atividade ilegal;
Cadeia(x) : x termina na cadeia.
(b) ∀x∀y(h(x) ∧ d(y)→ f(x, y))
∀y(g(y)→ d(y))
r(def)
∀x∀y∀z(f(x, y) ∧ f(y, z)→ f(x, z))
∀y(g(y) ∧ (∀z(r(z)→ f(y, z)))
h(abc)
Logo, f(abc, def)
(c) ∀x∀y(cavalo(x) ∧ cachorro(y)→ mais rapido(x, y))
∃y(cao de caca(y) ∧ (∀z(coelho(z)→ mais rapido(y, z)))
∀y(cao de caca(y)→ cachorro(y))
∀x∀y∀z(mais rapido(x, y) ∧mais rapido(y, z)→ mais rapido(x, z))
cavalo(a)
coelho(c)
Logo, mais rapido(a, c)
(d) Ningue´m e´ adepto de Aristo´teles, a na˜o ser os teo´logos. Na˜o e´ verdade que haja
teo´logos na˜o interessados em e´tica, mas sustentando doutrinas para o bem do
homem. Assim, na˜o ha´ adeptos de Aristo´teles que deixem de interesar-se pela
e´tica.
(e) Todos os gauchos gostam de contar histo´rias; todos os que gostam de contar
histo´rias sa˜o interessantes. Lu´ıs Fernando Ver´ıssimo e´ gaucho. Logo, algue´m e´
gaucho e interessante.
(f) Somente os re´pteis sa˜o cobras. Algumas cobras sa˜o perigosas. Assim, nem todo
re´ptil deixa de ser perigoso.
(g) Qualquer ac¸a˜o e´ boa se e somente se for nem ego´ısta nem prejudicial. Existem
ac¸o˜es boas. Assim, nem toda ac¸a˜o e´ prejudicial.
(h) Todas as baleias sa˜o mamı´feros. Este animal e´ uma baleia; ale´m disso este animal
e´ aqua´tico. Logo, ha´ (animais) mamı´feros aqua´ticos.
(i) Basicamente, todos somos calmos ou nervosos, mas nem todos sa˜o nervosos. Con-
sequentemente, existem pessoas calmas e na˜o nervosas.
(j) Sempre que P e´ verdadeiro, Q e´ verdadeiro. Sempre que Q e´ verdadeiro, R e´
verdadeiro. Logo, sempre que P e´ verdadeiro, R e´ verdadeiro.
3. Encontre a sentenc¸a em Ca´lculo de Predicados que resulta no conjunto das seguintes
cla´usulas na Notac¸a˜o de Kowalski:
(a) ← r(a,y), r(y,z), r(z,u), r(u,y)
(b) r(a,y), r(y,f(y)) ←
(c) r(a,y), r(g(y),h(y)) ←
(d) r(a,y), r(i(y),y) ←
(a) r(b,c), r(c,v) ← r(a,b), r(b,a)
(b) r(b,c), r(v,b) ← r(a,b), r(b,a)
(c) r(a,b) ← r(b,z)
(d) r(b,a) ← r(b,z)
(e) r(a,b) ← r(z,f(z)), r(f(z),b)
(f) r(b,a) ← r(z,f(z)), r(f(z),b)
4. Justificar as seguintes deduc¸o˜es:
No¯ Sentenc¸a Racioc´ınio
(1) ¬∃x¬(Ax ∨ ¬Bx) Premissa
(2) ∀x((Ax ∨ Cx)→ Dx) Premissa
(3) ∀x(Ax ∨ ¬Bx)
(4) (Ax ∨ Cx)→ Dx
(5) Ax ∨ ¬Bx
(6) ¬Bx ∨ Ax
(7) Bx→ Ax
(8) ¬(Ax ∨ Cx) ∨Dx
(9) (¬Ax ∧ ¬Cx) ∨Dx
(10) Dx ∨ (¬Ax ∧ ¬Cx)
(11) (Dx ∨ ¬Ax) ∧ (Dx ∨ ¬Cx)
(12) Dx ∨ ¬Cx
(13) Dx ∨ ¬Ax
(14) ¬Ax ∨Dx
(15) Ax→ Dx
(16) Bx→ Dx
(17) ∀x(Bx→ Dx)
No¯ Sentenc¸a Racioc´ınio
(1) ∀x∀y(h(x) ∧ d(y)→ f(x, y)) Premissa
(2) ∀y(g(y)→ d(y)) Premissa
(3) r(def) Premissa
(4) ∀x∀y∀z(f(x, y) ∧ f(y, z)→ f(x, z)) Premissa
(5) ∀y(g(y) ∧ ∀z(r(z)→ f(y, z))) Premissa
(6) h(abc) Premissa
(7) (5) + I.U.
(8) (7) + simplificac¸a˜o
(9) (7) + simplificac¸a˜o
(10) (2) + I.U.
(11) d(y)
(12) (1) + I.U.
(13) h(abc) ∧ d(y)
(14)
(15) (3) + (9) + M.P.
(16)
(17) f(abc, y) ∧ f(y, def)→ f(abc, def)
(18) (16) + (17) + M.P.
No¯ Sentenc¸a Racioc´ınio
(1) ∀x(pm(x)→ bg(x)) Premissa
(2) Premissa
(3) ∀x∀y(fz(x, y) ∧ il(y)→ pm(x)) Premissa
(4) Premissa
(5) fz(ml, a) ∧ il(a)
(6)
(7) pm(ml)→ bg(ml)
(8) fz(ml, a) ∧ il(a)→ bg(ml)
(9)
(10) bg(ml) ∧ fz(ml, a) ∧ il(a) (5) + (9) + conjunc¸a˜o
(11) (4) + I.U.
(12) cd(ml) (10) + (11) + M.P.