Lógica de
Predicados
Semântica
Interpretações mais elaboradas
do que as da Lógica Proposicional




De novo, associar significados a
símbolos sintáticos
Como fica isso, com variáveis,
quantificadores, predicados, funções??
H=(x)(y)p(x,y)
De que depende a interpretação da
fórmula acima?
Interpretações em Lógica de
Predicados - Predicados



Em 1º. lugar, do predicado p
Se I[p]= < (“menor que”), então
I[p(x,y)]=T D I[x]<I[y] D xI < yI
Interpretando informalmente os
quantificadores, temos que



I[H]= “para todo xI”, “existe um yI”
tal que xI<yI
I[H] é verdadeira ou falsa??
Interpretações em Lógica de
Predicados - Domínios

Ainda não dá pra determinar...



Se U =[0,) então I[H]=T


Quais os xI e yI a ser considerados?
Ou seja, que domínio U de xI e yI?
“para todo xI”, xIU, “existe um yI”, xIU,
tal que xI<yI
E a interpretação J, com U=(-,0],
J[p]= < , J[H]=???
Interpretações



Falsa! Porque se xJ=0, não existe yJ tal
que xJ,yJ U e xJ<yJ
Não é preciso ter as interpretações de
xJ e yJ para se ter I[H] e J[H]
Por quê??
Interpretações e
símbolos livres



Porque x e y não são símbolos livres em H
Só precisamos definir a interpretação do
símbolo livre p
E se G=(x)p(x,y), J[G]=???
Interpretações e
símbolos livres (cont.)

Para determinar J[G]...


dependemos de J[p] e J[y]
y é um símbolo livre

Se J[p] =  e J[y]=-5 => J[G]= F



“para todo xJ”, xJ(-,0], xJ-5
Porém, se yJ=0 => J[G]=T
... Dependemos do


Domínio de interpretação
Valor das interpretações dos símbolos livres
Formalizando: Interpretação de
váriáveis e funções



Extensão da interpretação proposicional
Há interpretações para termos e expressões
Se U é um conjunto não-vazio, uma
interpretação I na Lógica de Predicados é uma
função tal que:



O domínio de I é o conjunto de símbolos de função,
predicados e expressões
Para toda variável x, se I[x]=xI, então xIU
Para todo símbolo de função n-ário f, se I[f]=fI,
então fI é uma função n-ária em U

fI: U**n  U
Interpretação de predicados,
constantes e símbolos

Analogamente, para todo símbolo de
predicado n-ário p, se I[p]=pI, então pI é
um predicado n-ário em U


A interpretação de um predicado zero-ário
é igual à interpretação de seu símbolo


pI: U**n  {T,F}
Se I[P] = PI, então PI  {T,F}
A interpretação de uma função zero-ária é
igual à interpretação de uma constante

Se I[b] = bI, então bI  U
Interpretação de fórmulas –
não-quantificadas

Se E é uma expressão, I uma interpretação
sobre o domínio U. I[E] é dada por:


Se E=false, I[E]=I[false]=F (o mesmo com true)
Se E = f(t1,t2,...,tn) (um termo), então



I[E]= I[f(t1,t2,...,tn)]=fI(tI1,tI2,...,tIn),
onde I[f]=fI e para todo ti, I[ti]=tIi
Se E = p(t1,t2,...,tn) (um átomo), então


I[E]= I[p(t1,t2,...,tn)]=pI(tI1,tI2,...,tIn),
onde I[p]=pI e para todo ti, I[ti]=tIi
Interpretação de fórmulas –
não-quantificadas (cont.)

Se H é uma fórmula e E=H, então



I[E]=I[H]=T se I[H]=F e
I[E]=I[H]=F se I[H]=T
Se H e G são fórmulas, e E=(HvG), então


I[E]=I[HvG]=T se I[H]=T e/ou I[G]=T e
I[E]=I[HvG]=F se I[H]=F e I[G]=F
Interpretação de Expressões


Dados H=(p(x,y,a,b))  r(f(x),g(y)) e G=
p(x,y,a,b)  (q(x,y)^r(y,a))
A interpretação I, onde U=[0,)





I[x]=3,I[y]=2,I[a]=0,I[b]=1
I[p(x,y,z,w)]=T D xI*yI>zI*wI
I[q(x,y)]=T D xI<yI, I[r(x,y)]=T sse xI>yI
I[f(x)]=xI+1, I[g(x]=xI-2,
Lembrar que I[x]=xI

o objeto xI é o significado de x em I e xIN
Interpretação de Expressões –
Tabela verdade
Sintaxe
x y a b p(x,y,a,b) f(x) g(y) q(x,y)
r(y,a)
H G
Semântica
3 2 0 1 T
T
T



4
0
F
Observe que I[x]=3,..., I[H]=T,I[G]=T
As interpretações de f e g são elementos do
domínio de I (N)
As interpretações de H e G e dos átomos
p(x,y,a,b), q(x,y) e r(y,a) são valores de
verdade
F
Domínio de Interpretação

Seja I uma interpretação sobre N onde







I[a]=25, I[b]=5, I[f(x,y)]=xI/yI
I interpreta a constante a como 5
I interpreta f como a função divisão
Então I[f(a,b)]=5, pois I[f]=fI, onde fI: U*U  U
Porém, se I[c]=0, I[f(x,c)] não está definida!
Então o domínio de f é NxN*  Q (racionais)
=> Se o domínio de I for N, I[f] não pode ser
a função divisão
E para raiz quadrada??
Interpretação de fórmulas –
quantificadas





Se H é uma fórmula, x uma variável e I
uma interpretação sobre U
I[(x)H]=T D dU;<x <- d>I[H]=T
I[(x)H]=F D dU;<x <- d>I[H]=F
I[(x)H] =T D dU;<x <- d>I[H]=T
I[(x)H] =F D dU;<x <- d>I[H]=F

Onde <x <- d> significa “interpretação de
x como d” ou <x <- d>I[x]=d
Exemplo de Interpretação de
fórmulas quantificadas

I é uma interpretação sobre o conjunto de
alunos do CIn (aluno-CIn) tal que




I[p(x)]=T D xI é inteligente
H1= (x)p(x). O que é I[H1]=T?
I[H1]=T D I[(x)p(x)]=T
D daluno-CIn; d é inteligente
D daluno-CIn;pI(d)=T
D daluno-CIn;<x <- d>I[p(x)]=T
daluno-CIn, se x é interpretado como d

Então p(x) é interpretado como T
Exemplo de Interpretação de
fórmulas quantificadas (cont.)



I[H1]=F?
I[H1]=F
D I[(x)p(x)]=F
D daluno-CIn; d é burro
D daluno-CIn;pI(d)=F
D daluno-CIn;<x <- d>I[p(x)]=F
Nem todo aluno-CIn é inteligente


daluno-CIn;<x <- d>I[p(x)]=F
daluno-CIn, se x é interpretado como d

Então p(x) é interpretado como F
Exemplo 2 de Interpretação
de fórmulas quantificadas



H2= (x)p(x). O que é I[H2]=T?
I[H2]=T
D I[(x)p(x)]=T
D daluno-CIn; d é inteligente
D daluno-CIn;pI(d)=T
D daluno-CIn;<x <- d>I[p(x)]=T
daluno-CIn, se x é interpretado como d

Então p(x) é interpretado como T
Exemplo 2 de Interpretação de
fórmulas quantificadas (cont.)



I[H2]=F?
I[H2]=F
D I[(x)p(x)]=f
D daluno-CIn; d é burro
D daluno-CIn;pI(d)=F
D daluno-CIn;<x <- d>I[p(x)]=F
Não existe aluno-CIn inteligente


daluno-CIn;<x <- d>I[p(x)]=F
daluno-CIn, se x é interpretado como d

Então p(x) é interpretado como F
Exemplo 3 de Interpretação
de fórmulas quantificadas

Se I uma interpretação sobre N, tal que



I[x]=3,I[a]=5, I[y]=4,I[f]=+,I[p]=<
G=(x)p(x,y)
“Todo natural é menor que 4”
Exemplo 3 de Interpretação de
fórmulas quantificadas (cont.)



I[G]=F
D I[(x)p(x,y)]=F
D dN;<x <- d>I[p(x,y)]=F
D dN;d<4 é F, que é verdadeira
DI[G]=F é verdadeira
A interpretação de G segundo I é falsa
Não foi usada I[x]=3,

E sim a versão estendida <x <- d>
Exemplo 4 de Interpretação
de fórmulas quantificadas



E=(x) (y)p(x,y)
“Para todo natural x, existe outro natural y tal que
y>x”
I[E]=T
D I[(x)(y)p(x,y)]=T
D dN;<x <- d>I[(y)p(x,y)]=T
D dN, cN;<y <- c><x <- d>I[p(x,y)]=T
D “dN, cN; d<c é verdadeiro”, que é
verdadeira
DI[E]=T é verdadeira
Exemplo 4 de Interpretação de
fórmulas quantificadas (cont.)

I[E]=F
D I[(x) (y)p(x,y)]=F
D dN;<x <- d>I[(y)p(x,y)]=F
D dN, cN;<y <- c><x <- d>I[p(x,y)]=F
D dN, cN; d<c é falso
D dN, cN; d>=c é verdadeira, que é
falsa! (não existe um no. maior que todos!)
DI[E]=F é falso DI[E]=T
Ordem



A ordem das extensões é o inverso da ordem
dos quantificadores sintáticos na fórmula
A ordem dos quantificadores semânticos é a
mesma dos sintáticos
Não é preciso usar as interpretações I[x]=3 e
I[y]=4, pois x e y são ligadas

Usa-se a interpretação estendida

<y <- c><x <- d>I[p(x,y)] que não usa I[x] ou I[y]
Interpretação de conjunções
de fórmulas quantificadas


E1=E^G anteriores
I[E1]=F, pois I[G]=F e I[E]=T

Resolve-se I[E] e I[G] primeiro
Exemplo 5 de Interpretação
de fórmulas quantificadas

I em Q* (racionais, exceto o zero)



I[a]=1,I[b]=25,I[x]=13,I[y]=77,I[f]=/,I[p]=<
H1= (x)p(x,y)
I[H1]=T D I[(x)p(x,y)]=T
D dQ*<x <- d>I[p(x,y)]=T
D “dQ*, d<77 é verdadeiro”,
ou “d<77 é verdadeiro dQ*”, que é falsa!
D I[H1]=T é falsa D I[H1]=F
Exemplo 5 de Interpretação de
fórmulas quantificadas (cont.)

I[H1]=F D I[(x)p(x,y)]=F
D dQ*<x <- d>I[p(x,y)]=F
D “dQ*, d<77 é falso”,
ou “d<77 é falso para algum dQ*”, que é
verdadeira!
D I[H1]=F é verdadeira D I[H1]=F
Exemplo 6 de Interpretação
de fórmulas quantificadas


H2= (x)p(x,y)
I[H2]=T D I[(x)p(x,y)]=T
D dQ*<x <- d>I[p(x,y)]=T
D “dQ*, d<77 é verdadeiro”,
ou “d<77 é verdadeiro dQ*”, que é
verdadeira!
D I[H2]=T é verdadeira D I[H2]=T
Exemplo 6 de Interpretação de
fórmulas quantificadas (cont.)

I[H2]=F D I[(x)p(x,y)]=F
D dQ*<x <- d>I[p(x,y)]=F
D “dQ*, d<77 é falso”,
ou “d<77 é falso para todo dQ*”, que é falsa!
D I[H2]=F é falsa D I[H2]=T
Exemplo 7 de Interpretação
de fórmulas quantificadas







G=(x)(y)p(x,y)  p(b,f(a,b))
Para provar que I[G]=T por absurdo
I[G]=F D I[(x)(y)p(x,y)  p(b,f(a,b))]=F
D I[(x)(y)p(x,y)]=T e I[p(b,f(a,b))]= F
Mas I[p(b,f(a,b))] sse (25<(1/25)) que é falsa
E I[(x)(y)p(x,y)]=T
D dQ*, <y <-c><x <- d>I[p(x,y)]= T
D dQ*, dQ*; d<c, que é verdadeira
D I[(x)(y)p(x,y)]=T realmente
Então I[G]=F realmente
Não usamos I[x] e I[y] já que x e y estão ligadas em G
Exemplo 8 de Interpretação
de fórmulas quantificadas




H=(x)(y)p(x,y)  p(f(a,b),b)
Para provar que I[H]=T por absurdo
I[H]=F D I[(x)(y)p(x,y)  p(f(a,b),b)]=F
D I[(x)(y)p(x,y)]=T e I[p(f(a,b),b)]= F
Mas I[p(f(a,b),b)] sse ((1/25)<25) que é
verdadeira e contradiz I[p(f(a,b),b)]= F

que contradiz I[H]=F. Então I[H]=T
Exemplo 9 de Interpretação
de fórmulas quantificadas


H3= (x)(y)p(x,y)  p(x,y)
Só há variáveis livres de em H3 (x e y)

É preciso usar as interpretações


I[x]=13 e I[y]=77
I[p(x,y)]=T => I[H3]=T
Exemplo 10 de Interpretação
de fórmulas quantificadas


H4= (x)((y)p(x,y)  p(x,y))
Só y é livre em H4



É preciso usar a interpretação I[y]=77
I[H4]=F
D I[(x)((y)p(x,y)  p(x,y))]=F
D dQ*<x <- d>I[(y)p(x,y)]=T e
<x <- d> I[p(x,y))]=F
D dQ*,cQ*<y <-c><x <- d>I[p(x,y)]=T e
<x <- d>I[p(x,y))]=F
D dQ*,cQ*(d<c) é verdadeiro e (d<77) falso
I[H4]=F realmente
Exemplo 11 de Interpretação
de fórmulas quantificadas


E=(x)(y)p(x,y)  p(f(a,b),x)
Note que xI tal que (1/25)<xI



I[p(f(a,b),x)]=T e I[E]=T
Para provar que I[E]=T por absurdo
I[E]=F D I[(x)(y)p(x,y)  p(f(a,b),x)]=F


Mas I[(x)(y)p(x,y)]=T (exemplo anterior)
e I[p(f(a,b),x)] equivale a (1/25)<xI
Exemplo 11 de Interpretação de
fórmulas quantificadas - Conclusão

Nos casos em que (1/25)<xI



I[p(f(a,b),x)]=T, e temos uma contradição (era F)
I[E]=T
Nos casos em que (1/25)>=xI

I[E]=F
Façam os exercícios
do livro!!