Sintaxe e Semântica na Lógica de Predicados

Jefferson de Menezes(jmmf)Ricardo Salomão(rssj2)

Alfabeto SimbólicoSímbolos Lógicos:

1-) Operadores lógicos e quantificadores: , v, ->, ¬, , ;

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;

V A E

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, ->}, também é uma FBF;IV) Se α é uma FBF então xα também é uma

FBF;V) Se α é uma FBF então xα também é uma

FBF;VI) NADA MAIS É FBF.

V

A

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ãoP(2) = P(suc3(b)) é adicionadoDivide: 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!!

MODELO CANÔNICOO 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ênciaLembrando-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 nissoBote todo mundo que aparece, tanto nas Relações

como nas igualdades, que não são as Relações e ponha-as 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 definidasEx: 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?