Lógica para Computação - Lógica de Predicados: termos, Fórmulas atômicas, Escopo de um quantificador, Variável livre e ligada, Sentenças, etc  - aula13
29 pág.

Lógica para Computação - Lógica de Predicados: termos, Fórmulas atômicas, Escopo de um quantificador, Variável livre e ligada, Sentenças, etc - aula13


DisciplinaLógica para Computação754 materiais8.047 seguidores
Pré-visualização2 páginas
IF673 \u2013 Engenharia da Computação 
Cin/UFPE \u2013 Anjolina Grisi de Oliveira 
2 
Termos 
 Seja L uma assinatura. O conjunto de termos 
de L é definido indutivamente como a seguir: 
 
1. Todo símbolo c de constante de L é um 
termo; 
2. Toda variável é um termo; 
3. Para todo símbolo de função n-ária f de L, 
se t1,...,tn forem termos, então f(t1,...,tn) é 
um termo; 
4. Nada mais é um termo. 
TERMO FECHADO: NÃO CONTEM VARIÁVEL. 
3 
Termos: Fecho indutivo 
 Seja L uma assinatura. 
 
O conjunto de termos de L é o fecho indutivo 
do conjunto X = variáveis U destaques 
sob o conjunto dos símbolos de função f de L. 
4 
Fórmulas atômicas 
 Seja L uma assinatura. 
 
1. Se P é um símbolo de relação de L com aridade 
n, e t1,...,tn são termos de L, então P(t1,...,tn) é 
uma fórmula atômica. 
2. Se t1 e t2 são termos de L, então t1=t2 é uma 
fórmula atômica. 
 
5 
Escopo de um quantificador 
 1) \uf022x(P(x) \uf0ae \uf024yR(x,y)) 
 Qual o escopo de \uf022x? P(x) \uf0ae \uf024yR(x,y) 
 2) S(x) \uf0da \uf024z(P(z) \uf0d9 \uf022x(R(x,y) \uf0ae \uf024yR(y,x))) 
 Escopo de \uf024z: 
 Qual o escopo de \uf024y? R(x,y) 
 (P(z) \uf0d9 \uf022x(R(x,y) \uf0ae \uf024yR(y,x)) 
 Escopo de \uf022x: R(x,y) \uf0ae \uf024yR(y,x) 
 Escopo de \uf024y: R(y,x) 
6 
Variável livre e ligada 
 Definição : Uma ocorrência de uma variável em 
uma fórmula é ligada se e somente se ela está no 
escopo de um quantificador aplicado a ela. Ou ela 
é a ocorrência do quantificador. Uma ocorrência 
de uma variável numa fórmula é livre se e 
somente se essa ocorrência não é ligada. 
 Definição : Uma variável é livre numa fórmula se 
pelo menos uma ocorrência dela é livre na 
fórmula. Uma variável é ligada se pelo menos uma 
ocorrência dela é ligada 
7 
Exemplos 
 1) \uf022xP(x,y) 
 As duas ocorrências de x são ligadas. 
 A ocorrência de y é livre. 
 2) \uf022xP(x,y) \uf0d9 \uf022yQ(y) 
 Nesse exemplo notamos que uma variável pode ser 
ao mesmo tempo livre e ligada em uma fórmula. 
8 
Fórmulas bem formadas 
Uma fórmula bem formada da lógica de primeira ordem é 
definida recursivamente como a seguir: 
 
1. Um átomo (fórmula atômica) é uma fórmula; 
2. Se F e G são fórmulas, então \uf0d8(F),(F\uf0daG), (F\uf0d9G), 
(F\uf0aeG) e (F\uf0abG) são fórmulas; 
3. Se F é uma fórmula e x é uma variável livre em F, 
então \uf022xF e \uf024xF são fórmulas; 
4. Fórmulas são geradas apenas por um finito 
número de aplicação das regras acima. 
 
9 
Sentenças 
 Sentenças são fórmulas sem variáveis livres. 
 Dessa forma, uma sentença atômica é uma 
fórmula atômica sem variável. 
10 
Significado de uma sentença atômica 
 Seja L uma assinatura e \uf06a uma sentença atômica 
de L. O significado de \uf06a segundo uma interpretação 
de L numa estrutura A de assinatura L é 
determinado pelo resultado da interpretação sobre 
os termos de \uf06a e sobre o símbolo de relação de \uf06a. 
11 
Significado de uma sentença atômica 
0 
1 
2 
3 4 
A 
0 
2 
Assinatura de A: 
\u2022 Constantes: c1, c2 
\u2022 Relações: R(_,_), S(_,_), P(_) 
\u2022 Funções:f(_,_), g(_,_), h(_) 
Seja a seguinte interpretação: 
\u2022 c1
A 
 = 0, c2
A 
 = 2 
\u2022 RA = menor_que(_,_), 
\u2022 SA = divide(_,_), PA = primo(_) 
\u2022 fA = soma_mod5(_,_) 
\u2022gA = mult_mod5(_,_) 
\u2022 hA = quad_mod5(_) 
menor_que(_,_) 
primo(_) 
divide(_,_) 
quad_mod5(_) 
soma_mod5(_,_) 
mult_mod5(_,_) 
Seja \uf06a a fórmula R(f(c1,g(c1,c2)),g(f(c2,c2),c1)) 
\u2022 Qual o significado de \uf06a segundo a interpretação dada em A? 
\uf06aA = menor_que(soma_mod5(0,mult_mod5(0,2)),mult_mod5(soma_mod5(2,2),0)) 
 É falso 
C1 é um símbolo 
Lembrando que predicado não predica sobre objetos. Apenas verdadeiro e falso. P(___) 
12 
Modelo de uma sentença atômica 
 Seja L uma assinatura e A uma L-estrutura. 
Dizemos que A é um modelo de \uf06a sob uma 
determinada interpretação de L em A se \uf06aA for 
verdadeira. 
13 
Contra-modelo de uma sentença atômica 
 Seja L uma assinatura e A uma L-estrutura. 
Dizemos que A é um contra-modelo de \uf06a sob uma 
determinada interpretação \uf06aA , se \uf06aA for falsa. 
14 
Sentenças e estruturas 
 Vamos ver agora como passar de uma estrutura 
para um conjunto de sentenças que a descrevem. E 
como passar de um conjunto de sentenças para 
uma estrutura que satisfaz esse conjunto. 
1. De estrutura para sentenças 
2. De sentenças para estrutura 
Passos:
15 
De estrutura para sentenças 
0 
1 
2 
A 
0 
2 
Assinatura de A: 
\u2022 Constantes: a, b 
\u2022 Relações: R(_,_), P(_) 
\u2022 Funções:f(_,_), h(_) 
Seja a seguinte interpretação: 
\u2022 aA = 0, b
A 
 = 2 
\u2022 RA = menor_que(_,_), 
\u2022 PA = primo(_) 
\u2022 fA = soma_mod3(_,_) 
\u2022 hA = quad_mod3(_) 
menor_que(_,_) 
primo(_) 
quad_mod3(_) 
soma_mod3(_,_) 
 
R(a,h(b)), R(a,b), R(h(b),b)),... 
P(b), P(f(a,b)),.... 
f(a,h(b)) = h(b), f(a,b) = b, f(h(b),b) = a,... 
h(a) = a, h(h(b)) = h(b), h(b) =f(b,b),... 
 Se algum termo não pode ser representado com os destaques e funções, 
ele é acrescentado ao conjunto de destaques. 
 DESCRIÇÃO LÓGICA DE A 
Descreve apenas o que é verdadeiro. 
Quando tenho r(a, (h(b)) de significa que (a^A, h(b) ^A E ^A
Passando da matemática pra lógica 
16 
Diagrama positivo de uma estrutura 
 Seja A uma L-estrutura. O conjunto de todas 
sentenças atômicas de L que são verdadeiras sob 
uma determinada interpretação em A, ( ou seja, a 
descrição lógica de A) é chamado de diagrama 
positivo de A. 
O processo de construção do diagrama positivo se 
dá da seguinte forma: 
 (1) Para todo símbolo de relação n-ária R de L, inclua uma 
sentença atômica da forma R(t1,...tn) se os elementos 
(t1
A,...,tn
A) \uf0ce RA. 
 (2) Para todo símbolo de função n-ária f de L inclua uma 
sentença atômica da forma f(t1,...tn) = tn+1 se, f
A(t1
A,...,tn
A) = 
tAn+1 na estrutura A, onde t
A
1,...,t
A
n são representações dos 
elementos de A. 
Não existe fórmula negada, composta, variável, multiplicadores, 
17 
Extensão de uma estrutura 
 Seja A uma L-estrutura. Quando desejamos 
produzir o diagrama positivo de A e A tem 
elementos ``sem nome´´, definimos uma extensão 
de A, chamada A\u2019, que admite esses `` sem nome´´ 
como novos elementos destacados. 
 Isso significa dizer que a assinatura A\u2019 é L\u2019= L \uf0c8 {c1,...,cn}. 
 Onde cada ci é um símbolo de constante para representar o 
elemento ai. Às vezes abreviamos L \uf0c8 {c1,...,cn} como L(c). 
Assinatura anterior unida a essas constantes c 
18 
De sentenças para estrutura 
 Suponha que nos seja dado um conjunto de 
sentenças atômicas T numa linguagem L e 
desejamos construir uma estrutura que satisfaça 
todas as sentenças de T. Para construir essa 
estrutura, precisamos definir: 
1. Domínio 
2. Elementos destacados 
3. Predicados e relações 
4. Funções 
Ou seja, seja modelo pra todas elas 
Relação de equivalência lembra? . Da matemática discreta. Relação de equivalência R em A? R <= A cartesiano X A. Tem que ser transitava, simetria, reflexiva, aí será equivalente. É por aí que construiremos o domínio. 
19 
De sentenças para estrutura: domínio 
 Classe de equivalência de termos fechados. 
 
Definimos o representante da classe de equivalência de um 
dado termo t em relação ao conjunto de sentenças atômicas 
T como sendo todos os termos fechados t~ de L para os 
quais temos t = t~ no conjunto T. 
 O domínio da estrutura B que estamos construindo será 
definido pelo conjunto dos representantes das classes de 
equivalência dos termos fechados de L no conjunto T de 
sentenças atômicas. 
Classe de equivalência de 1 = 1 -1 3 -3... Acho que tá errado 
20 
De sentenças para estrutura: Relações 
 Para definir as relações