Teste

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (478 palavras )
  • Download(s) : 0
  • Publicado : 21 de maio de 2012
Ler documento completo
Amostra do texto
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 asoutras 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

21

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 ey 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ãode 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ívelexistir 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) evice-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...
tracking img