Teste

INF2217

Exercícios 3

Marco A. Casanova

24/8/2009

(c) INF - PUC-Rio

1

Modelo
•

Para cada uma das sentenças abaixo, crie uma interpretação que satisfaça a sentença, mas não as outras duas:
(a) ∀x∀y∀z ((P(x,y) ∧ P(y,z)) ⇒ P(x,z))
(b) ∀x∀y ((P(x,y) ∧ P(y,x)) ⇒ x = y)
(c) ∀x∀y (P(x,y) ⇒ P(y,x))

(a),¬(b), ¬(c)

¬(a),(b), ¬(c)

¬(a), ¬(b), (c)

1

1

2

1

2

1

2

3

2

1

1

1

2

2

2

3

1
24/8/2009

2

2

3
(c) INF - PUC-Rio

2

1

Tradução
a)

Nenhum conjunto é um elemento dele próprio.
¬∃x(x∈x)

b)

Dados dois conjuntos x e y quaisquer, x é um subconjunto de y, denotado x ⊆ y, se e somente se todo elemento de x também é um elemento de y.
∀x∀y(x⊆y ⇔ ∀z(z∈x ⇒ z∈y))

c)

Dados dois conjuntos x e y quaisquer, x é igual a y, denotado x = y, se e somente se x é um subconjunto de y e y é um subconjunto de x.
∀x∀y(x=y ⇔ (x⊆y ∧ y⊆x))

d)

Dados três conjuntos x, y e z quaisquer, x é a união de y e z, denotado x = y ∪ z, se e somente se, todo elemento de x também é um elemento de y ou z, e todo elemento de y ou z é um elemento de x.
∀x∀y∀z(x=y∪z ⇔ ∀u(u∈x ⇒ u∈y ∨ u∈z) ∧ ∀u(u∈y ∨ u∈z ⇒ u∈x))

24/8/2009

(c) INF - PUC-Rio

3

Paradoxo do Barbeiro
•

Considere a seguinte afirmação: “Em uma certa cidade, a seguinte lei foi promulgada:
A. A cidade deverá ter um barbeiro oficial.
B. Todo cidadão que não se barbear, deverá ser barbeado pelo barbeiro oficial.
C. Todo cidadão que o barbeiro oficial barbear, não deverá barbear a si próprio.”

•

Mostre que é impossível existir um barbeiro oficial de tal forma que a lei seja satisfeita. Para tal, formalize a lei como uma teoria de 1ª ordem e mostre que toda interpretação da teoria que satisfaz
(B) não satisfaz (C) e vice-versa.

•

Linguagem de 1ª ordem:
B

símbolo predicativo unário tal que ‘cidadao(x)’ indica que x é um cidadão

barbeia

•

constante B para designar o barbeiro

cidadao

símbolo