Questões de Dedução

Prévia do material em texto

EXERCÍCIOS DAVID-PLUMMER 1/26 
 
Axiomatização do mundo de blocos 
 
Considere que você está considerando uma modelagem onde o seu universo é o “mundo dos 
blocos” formados por cubos, tetraedros e dodecaedros. Suponha que você tenha as seguintes 
definições para os predicados da FOL: 
Cube( x ) ≡ x é um cubo; Tet( x ) ≡ x é um tetraedro; 
Dodec( x ) ≡ x é um dodecaedro. 
SameShape( x , y ) ≡ x tem o mesmo formato que y 
As fórmulas seguintes são consideradas Axiomas desta modelagem. 
Axiomas Básicos dos Formatos. 
( 1 ) 
( 2 ) 
( 3 ) 
( 4 ) 
 
Axiomas Básicos do predicado binário SameShape 
( 5 ) 
( 6 ) 
( 7 ) 
( 8 ) 
( 9 ) 
( 10 ) 
 
EXERCÍCIOS DAVID-PLUMMER 2/26 
 
1 Questão 
 
a ) Explique o significado dos axiomas 1 , 2 e 3. 
b ) Explique o significa do axioma 4. 
c ) Explique o significa dos axiomas 6, 7 e 8. 
b ) Explique o significa dos axiomas 8, 9, 10.. 
 
2 Questão 
Prove pelo sistema formal dedutivo (caso o argumento seja válido) ou apresente um 
contraexemplo ( caso não seja válido). 
( 1 ) Considerando os axiomas. 
( 2 ) Não considerando os axiomas 
a ) 
 
b ) 
 
c ) 
 
d ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 3/26 
e ) 
 
f ) 
 
g) 
 
h ) 
 
i ) 
 
j ) 
 
k ) 1. Considere os axiomas. 2. Não considere os axiomas 
 
l ) 1. Considere os axiomas. 2. Não considere os axiomas 
EXERCÍCIOS DAVID-PLUMMER 4/26 
 
m ) 1. Considere os axiomas. 2. Não considere os axiomas 
 
n ) 1. Considere os axiomas. 2. Não considere os axiomas 
 
m ) 
 
n ) 
 
o ) 
 
p ) 
 
q ) 
EXERCÍCIOS DAVID-PLUMMER 5/26 
 
r ) 
 
s ) 
 
t ) 
 
u ) 
 
v ) 
 
x ) 
 
 
y ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 6/26 
w ) 
 
 
z ) 
 
 
 
 
 Introdução de novos predicados e axiomas no mundo dos blocos 
 
Para os itens seguintes considere que os blocos estão em um plano horizontal, e que cada 
bloco está posicionado em um ponto definido por uma dupla de números naturais; ou seja a 
posição de um bloco x pode ser ( 3, 5 ) que indica a ordenada e a abcissa do bloco. Considere 
também que os blocos podem ser classificados por três tamanhos: pequeno, médio, e grande. 
 
Definimos, então, os predicados 
FrontOf( x , y ) ≡ a ordenada de x é menor do que a ordenada de y 
Backof( x , y ) ≡ a ordenada de x é maior do que a ordenada de y 
LeftOf( x , y ) ≡ a abcissa de x é menor do que a abcissa de y 
Backof( x , y ) ≡ a abcissa de x é maior do que a abcissa de y 
Small( x ) ≡ x é pequeno 
Medium( x ) ≡ x é de tamanho médio 
Large( x ) ≡ x é grande 
 
E acrescentamos os axiomas para o mundo dos blocos: 
11 ) ∀ x ∀ y ( FrontOf ( x , y ) ↔ Backof( y, x ) ) 
12 ) ∀ x ∀ y ∀ z ( FrontOf( x, y ) ∧ Front( y , z ) → Front( x , z ) ) 
13 ) ∀ x ( ¬ Front( x , x ) ) 
EXERCÍCIOS DAVID-PLUMMER 7/26 
11 ) ∀ x ∀ y ( LeftOf( x , y ) ↔ RightOf( y, x ) ) 
12 ) ∀ x ∀ y ∀ z ( LeftOf ( x, y ) ∧ LeftOf ( y , z ) → LeftOf( x , z ) ) 
13 ) ∀ x ( ¬ LeftOf ( x , x ) ) 
14 ) ∀ x ( Small( x ) ∨ Medium( x ) ∨ Large( x ) ) 
15 ) ∀ x ( Small( x ) → ( ¬ Medium( x ) ∧ ¬ Large( x ) ) ) 
16 ) ∀ x ( Medium( x ) → ( ¬ Small( x ) ∧ ¬ Large( x ) ) ) 
17 ) ∀ x ( Large( x ) → ¬ Small( x ) ∧ ¬ Medium( x ) ) 
Repare que por esta modelagem, se os blocos a e b têm a mesma ordenada, então 
¬ FrontOf( a, b ) e ¬ BackOf( a, b ) 
Se têm a mesma abcissa, ¬ LeftOf( a, b ) e ¬ LeftOf( a, b ) 
Explique o significado de cada um dos axiomas novos. 
 
3 Questão 
 
Prove pelo sistema formal dedutivo (caso o argumento seja válido) ou apresente um 
contraexemplo ( caso não seja válido). 
( 1 ) Considerando apenas os axiomas originais 
(trate os novos predicados como não definidos na modelagem) . 
( 2 ) Considerando também os axiomas novos. 
 
a ) 
 
b) 
 
c ) 
EXERCÍCIOS DAVID-PLUMMER 8/26 
 
d ) 
 
e ) 
 
 
f ) 
 
g ) 
 
h ) 
 
EXERCÍCIOS DAVID-PLUMMER 9/26 
i ) 
 
j ) 
 
k ) 
 
 
l ) 
 
m ) 
 
n ) 
 
o ) 
EXERCÍCIOS DAVID-PLUMMER 10/26 
 
p ) 
 
q ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 11/26 
r ) 
 
s ) 
 
t ) 
 
u ) 
 
v ) 
 
x ) 
 
w ) 
 
EXERCÍCIOS DAVID-PLUMMER 12/26 
y ) 
 
A primeira premissa indica a inserção de uma constante afim de afirmar: 
Se existe um cubo grande, use a constante c como nome de um deles; 
se não existe cubo grande, a constante pode nomear qualquer outro objeto. 
Este tipo de premissa é denominada de testemunha de Henkin. 
 
z ) 
 
z1) 
 
z2 ) 
 
z3) 
 
z4 ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 13/26 
z5 ) 
 
z6 ) 
 
z7 ) 
 
 
 
EXERCÍCIOS DAVID-PLUMMER 14/26 
 
4 Questão 
 
Prove pelo sistema formal dedutivo (caso a fórmula seja válida) ou apresente um 
contraexemplo ( caso não seja válida). 
( 1 ) Considerando todos os axiomas de 1 até 17. 
( 2 ) Não considerando os axiomas 
 
a ) 
b ) 
c ) 
d ) 
e ) 
f ) 
g ) 
h ) 
i ) 
j ) 
k ) ∀ x ( x = x ) 
l ) 
m ) 
n ) 
o ) 
p ) 
q ) 
EXERCÍCIOS DAVID-PLUMMER 15/26 
 
5 Questão 
Prove que a sentença abaixo é equivalente à conjunção dos axiomas relativos a SameShape 
 
 
 
 
EXERCÍCIOS DAVID-PLUMMER 16/26 
 
6 Questão 
As fórmulas abaixo não são válidas. 
Apresente um contraexemplo para cada uma delas. 
 
 
 
EXERCÍCIOS DAVID-PLUMMER 17/26 
7 Questão 
Prove pelo sistema formal dedutivo (caso o argumento seja válido) ou apresente um 
contraexemplo ( caso não seja válido). 
Os nomes não têm nenhum significado a priori. Você pode substituí-los pelas iniciais em 
maiúsculas. 
a ) 
 
b ) 
 
c ) 
 
d ) 
 
e ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 18/26 
f ) 
 
g ) 
 
h ) 
 
i ) 
 
 
ji ) 
 
k ) 
 
l ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 19/26 
m ) 
 
n ) 
 
o ) 
 
 
 
EXERCÍCIOS DAVID-PLUMMER 20/26 
Introdução de novos predicados e axiomas no mundo dos blocos 
 
Nesta questão consideramos que mais quatro predicados foram introduzidos: 
Adjoins( x , y ) ≡ x está do lado de y 
(x e y têm a mesma abcissa ou x e y têm a mesma ordenada, e x ≠ y ) 
SameSize( x , y ) ≡ x têm o mesmo tamanho que y 
Larger( x , y ) ≡ x é maior do que y 
Smaller( x , y ) ≡ x é menor do que y 
SameColor( x , y ) ≡ x e y têm a mesma cor 
 
Para dar conta do significado que supomos existir no mundo dos blocos, precisamos 
acrescentar mais axiomas: 
18) ∀ x ∀ y ( Adjoins( x , y ) ↔ Adjoins( y , x ) ) 
 
19) ∀ x ∀ y ( Adjoins( x , y ) → FrontOf( x , y ) ∨ BackOf( x, y ) ) 
 
20) ∀ x ∀ y ( Adjoins( x , y ) → LeftOf( x , y ) ∨ RightOf( x, y ) ) 
 
21) ∀ x ( ¬ Adjoins( x , x ) ) 
 
22) ∀ x ∀ y ( SameSize( x , y ) ↔ SameSize( y , x ) ) 
 
23) ∀ x ∀ y ∀ z( SameSize( x , y ) ∧ SameSize( y , z ) → SameSize( x , z) ) 
 
24) ∀ x ( SameSize( x , x ) ) 
 
25) ∀ x ∀ y ( SameSize( x , y ) → 
 
26) ( ( Small( x ) ∧ Small( y ) ) ∨ ( Medium( x ) ∧ Medium( y ) ) ∨ ( Large( x ) ∧ Large( y ) ) ) 
 
27) ∀ x ∀ y ( SameSize( x , y ) → 
( ( Cube( x ) ∧ Cube( y ) ) ∨ ( Tet( x ) ∧ Tet( y ) ) ∨ ( Dodec( x ) ∧ Dodec( y ) ) ) 
 
28) ∀ x ∀ y ( SameCol( x , y ) ↔ SameCol( y , x ) ) 
 
29) ∀ x ∀ y ∀ z( SameCol( x , y ) ∧ SameCol( y , z ) → SameCol( x , z) ) 
 
30) ∀ x ( SameCol( x , x ) ) 
 
31) ∀ x ∀ y ( Larger( x , y ) → ¬ Larger( y , x ) ) 
 
32) ∀ x ∀ y ( SameSize( x , y ) ↔ ¬ Larger( x , y ) ) 
EXERCÍCIOS DAVID-PLUMMER 21/26 
 
33) ∀ x ∀ y ( Larger( x , y ) → 
 ( Small( y ) ∧ Medium( x ) ) ∨ ( Small( y ) ∧ Large( x ) ) ∨ ( Medium( y ) ∧ Large( x ) ) ) 
 
34) ∀ x ∀ y ( Smaller ( x , y ) → ¬ Smaller ( y , x ) ) 
 
35) ∀ x ∀ y ( SameSize( x , y ) ↔ ¬ Smaller ( x , y ) ) 
 
36) ∀ x ∀ y ( Smaller ( x , y ) → 
( ( Small( x ) ∧ Medium( y ) ) ∨ ( Small( x ) ∧ Large( y ) ) ∨ ( Medium( x ) ∧ Large( y ) ) ) 
 
37) ∀ x ∀ y ( Larger( x , y ) ↔ ¬ Smaller ( x , y ) ) 
 
38) ∀ x ∀ y ( Larger( x , y ) ∨ Smaller( x , y ) ∨ SameSize( x, y ) ) 
 
EXERCÍCIOS DAVID-PLUMMER 22/26 
 
8 Questão 
Explique cada um dos axiomas relacionados com o predicado Adjoins 
 
9 Questão 
Explique cada um dos axiomas relacionados somente com os predicados SameSize ou SameCol 
(disjunção inclusiva aqui) 
 
10 Questão 
Explique cada um dos axiomas relacionados somente com o predicado SameSize e os 
predicados de definição de “formato”. 
 
11 Questão 
Explique cada um dos axiomas relacionados somente com o predicado binário Larger e os 
predicados unários de caracterização de “tamanho”. 
 
12 Questão 
Explique cada um dos axiomas relacionados somente com o predicado binário Smaller e os 
predicados unários de caracterização de “tamanho”. 
 
13 Questão 
Explique cada um dos axiomas relacionados somente com os predicados binários de 
caracterização de “tamanho”. 
 
 
EXERCÍCIOS DAVID-PLUMMER 23/26 
14 Questão 
 
Prove pelo sistema formal dedutivo (caso o argumento seja válido) ou apresente um 
contraexemplo ( caso não seja válido). 
( 1 ) Considerando todos os axiomas ( de 1 até 38 ) 
( 2 ) Não considerando os axiomas 
 
a ) 
 
b ) 
 
c ) 
 
d ) 
 
e ) 
 
 
 
EXERCÍCIOS DAVID-PLUMMER 24/26 
f ) 
 
g ) 
 
h ) 
 
 
 i ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 25/26 
 
j ) 
 
k ) 
 
l ) 
 
m ) 
 
n ) 
 
 
EXERCÍCIOS DAVID-PLUMMER 26/26 
 
o ) 
 
 
p )