Jefferson de Menezes(jmmf)
Ricardo Salomão(rssj2)
Alfabeto Simbólico
 Símbolos Lógicos:
, v, ->, ¬, ,
;
E A
V
1-) Operadores lógicos e quantificadores:
2-) Variáveis para objetos;
3-) Parênteses;
 Símbolos Não-Lógicos:
4-) Para cada estrutura um alfabeto simbólico diferente para
representar:
- destaques(por meio de constantes);
- relações e predicados;
- funções;
Termos
 TERMOS são objetos sintáticos que servem para
representar elementos do domínio em questão.
 É o conjunto de expressões de L que representam
objetos;
Termos(Definição Indutiva)
 Base:
1-) Toda variável é um termo;
2-) Todo símbolo de constante ‘c’ de L é um termo;
 Geradores:
3-) Se f for um símbolo de função de L de aridade n e
t1, t2,...tn forem termos de L, então f(t1, t2,...tn) é um termo;
4-) NADA MAIS É UM TERMO.
Termos(Definição Alternativa)
 Seja L uma assinatura. O conjunto dos termos de L é o
fecho indutivo do conjunto X = variáveis U constantes
sob o conjunto dos símbolos de função F de L.
Exs.: x, p, m, f(p), f(x), f(f(p)), ...
“Termo fechado: Um termo t é dito fechado se não
contém variáveis.”
Fórmulas Atômicas(Definição)
1-) Para todo símbolo de relação n-ária R de L (n ≥ 0), se
t1, t2,...tn forem termos, então R(t1, t2,...tn) é uma
fórmula atômica;
2-) Para todos os termos t1, t2,...tn de L, t1 = t2 é uma
fórmula atômica de L.
“Sentenças: Uma fórmula atômica é dita uma sentença
se não contém variáveis.”
Definição de Fórmula Bem Formada (FBF)
Seja L uma assinatura.
 I) Toda fórmula atômica é uma FBF;
 II) Se α é uma FBF então (¬α) também é uma FBF;
 III) Se α e β são FBF’s então (α
β), onde = { , v, ->},
V
também é uma FBF;
 IV) Se α é uma FBF então xα também é uma FBF;
A
 V) Se α é uma FBF então xα também é uma FBF;
 VI) NADA MAIS É FBF.
E
O que é Diagrama Positivo?
 Tão lembrados que uma assinatura L numa estrutura A
é a definição da composição da estrutura?
 Então, Diagrama Positivo consiste no conjunto de
TODAS as Sentenças Atômicas de L que são
verdadeiras em A.
Tá, e como eu faço isso?
 Você, primeiro, tem que achar alguma maneira de
poder representar o domínio da Estrutura A.
 Como o Diagrama positivo consiste de SENTENÇAS
ATÔMICAS, então vocês terão que mostrar alguma
representação de cada elemento do domínio, a partir
dos elementos de destaque
...
 Para isso, você vai ter que usar as funções que são
dadas na assinatura;
 E, obviamente, usar as relações nesta
 NÃO SE ESQUEÇAM DA IGUALDADE!!!
Exemplo:
 Estrutura A com Assinatura L:
 Domínio : {0 , 1, 2 };
 Funções : SomaMod3(_,_) , SucessorMod3(_);
 Relações: Primo(_), Divide(_,_) (Se o 1º termo é
dividido pelo 2º termo);
 Destaque: 1;
Resolvendo...
 Representação da assinatura:
 Funções : s3(_,_) (soma), suc3(_) (sucessor);
 Relações: P(_) (primo), D(_,_) (divide);
 Assinatura: b = 1;
Representando o domínio:
 1 = b;
 2 = suc3(b);
 0 = s3(b,suc3(b));
Agora, represente todas as
relações:
 Primo: Nesse caso só 2 é primo, então
 P(2) = P(suc3(b)) é adicionado
 Divide: Todo mundo divide 0 e divide 2, exceto 0, para
ambos os casos;
 só 1 que divide 1;
 D(0,1), D(0,2), D(1,1), D(2,1), D(2,2) =
 = D(s3(b,suc3(b)), b) , D(s3(b,suc3(b)), suc3(b)),
D(b,b), D(suc3(b), b), D(suc3(b), suc3(b));
Lembre-se também da Igualdade:
 2 = suc3(b) = s3(b,b)
 1 = b = suc3(suc3(suc3(b))) = s3(suc3(b), suc3(b)) =
s3(s3(b,b), s3(b,b))
 0 = s3(b,suc3(b)) = s3(suc3(b), b) = suc3(suc3(b))
AGORA SIM!!
 P(suc3(b));







suc3(suc3(b));
D(s3(suc3(b),b), b);
 suc3(b) = s3(b,b);
D(s3(suc3(b),b), suc3(b))  b = suc3(suc3(
suc3(b)));
D(b,b);
 b = s3(suc3(b),
D(suc3(b), b);
suc3(b));
D(suc3(b), suc3(b));
s3(b,suc3(b)) =
s3(suc3(b),b);
s3(b,suc3(b)) =
MODELO CANÔNICO
 O modelo canônico é quase o inverso do processo de
diagrama positivo.
 Quase porque a definição do domínio se dá por classes
de equivalência
 Lembrando-se de Matemática Discreta: “Classe de
equivalência é um termo o qual este se equivale a um
domínio em si”.
Tá e como eu faço isso?
 Para fazer isso, faça o seguinte:
 Veja todas as funções que aparecem e bote-as no
conjunto de funções;
 Veja todas as Relações que aparecem e bote-as no
conjunto de Relações
 Veja todos os elementos de destaque e bote-os no
conjunto de Destaque
Falta alguém né?
 Falta o domínio:
 Primeiro de tudo, faça também força bruta nisso
 Bote todo mundo que aparece, tanto nas Relações
como nas igualdades, que não são as Relações e ponhaas no como sendo classes de equivalência no conjunto
do domínio
 Depois, comece a “cortar” classes de equivalência do
domínio, a partir das igualdades
 Agora acabou? QUASE...
o que é que falta?
 Falta verificar se todas as possíveis combinações de
relações estão definidas
 Ex: Você tem uma função T binária, com constantes ‘a’,
‘b’
 Você vai ter que ver se há T(a,a), T(a,b), T(b,a), T(b,b).
Se tiver, beleza, senão verifique se há alguém que possa
ser representado por ‘a’ ou por ‘b’;
 Se não tiver, você pode supor que o domínio é infinito
Dúvidas?