Logica Predicados (semântica)

Prévia do material em texto

Lógica de Predicados
 Sintaxe
 Semântica
Lógica de Predicados
 Associar significados a símbolos sintáticos
 Como fica se agora existem variáveis, quantificadores, 
predicados, funções??
 H=(∀x)(∃y)p(x,y)
 De que depende a interpretação da fórmula H?
Interpretação
 Depende do predicado p
 Se I[p]= < (“menor que”), então
I[p(x,y)]=T ⇔ I[x]<I[y] ⇔ 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ção
 Seguindo a interpretação...
– Quais os xI e yI a ser considerados?
– Ou seja, que domínio U de xI e yI?
 Se U =[0,∞) então I[H]=T
“para todo xI”, xI∈U, “existe um yI”, yI∈U, tal que xI<yI
 E a interpretação J, com U=(-∞,0], J[p]= < , J[H]=???
Interpretação
 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ê??
 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ção
 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
Interpretação de variá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: Un  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
pI: Un  {T,F}
 A interpretação de um predicado zero-ário (aridade=0) é 
igual à interpretação de seu símbolo
Se I[P] = PI, então PI ∈ {T,F} 
 A interpretação de uma função zero-ária (função de 0 
argumentos) é igual à interpretação de uma constante
Se I[b] = bI, então bI ∈ U
Interpretação de fórmulas
 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
 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 ⇔ xI*yI>zI*wI
I[q(x,y)]=T ⇔ xI<yI, I[r(x,y)]=T sse xI>yI
I[f(x)]=xI+1, I[g(y)]=yI-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
 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
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 4 0 F T T F
 H=(¬p(x,y,a,b))  r(f(x),g(y)) 
 G= p(x,y,a,b)  (q(x,y)∧r(y,a))
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 25 e a constante “b ” 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! 
 => Se o domínio de I for N, I[f] não pode ser a função 
divisão
 
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∈U; <x ← d>I[H]=T
I[(∀x)H]=F ⇔ ∃d∈U; <x ← d>I[H]=F
I[(∃x)H] =T ⇔ ∃d∈U; <x ← d>I[H]=T
I[(∃x)H] =F ⇔ ∀d∈U; <x ← d>I[H]=F
Onde <x ← d> significa “interpretação de x como d” ou 
<x ← d>I[x]=d
Exemplo 1
 I é uma interpretação sobre o conjunto de alunos de CCO 
(aluno-CCO) tal que 
 I[p(x)]=T ⇔ xI é rico
 H1= (∀x)p(x). O que significa dizer que I[H1]=T?
 I[H1]=T ⇔ I[(∀x)p(x)]=T
⇔ ∀d ∈ aluno-CCO; d é rico 
⇔ ∀d ∈ aluno-CCO; pI(d)=T 
⇔ ∀d ∈ aluno-CCO; <x ← d>I[p(x)]=T

 ∀d∈aluno-CCO, se x é interpretado como d
 Então p(x) é interpretado como T
Exemplo 1
 I[H1]=F?
 I[H1]=F (É falso que todo aluno de CCO é rico. Então 
existe algum aluno pobre?)
⇔ I[(∀x)p(x)]=F 
⇔ ∃d ∈ aluno-CCO; d é pobre
⇔ ∃d ∈ aluno-CCO; pI(d)=F 
⇔ ∃d ∈ aluno-CCO; <x ← d>I[p(x)]=F
 Nem todo aluno-CCO é rico
 ∃d ∈ aluno-CCO;<x ← d>I[p(x)]=F

 ∃d ∈ aluno-CCO, se x é interpretado como d
 Então p(x) é interpretado como F
Exemplo 2
 H2= (∃x)p(x). O que é I[H2]=T?
 I[H2]=T (Existe aluno de CCO que é rico)
⇔ I[(∃x)p(x)]=T 
⇔ ∃d ∈ aluno-CCO; d é rico 
⇔ ∃d ∈ aluno-CCO; pI(d)=T 
⇔ ∃d ∈ aluno-CCO; <x ← d>I[p(x)]=T

 ∃d ∈ aluno-CCO, se x é interpretado como d
 Então p(x) é interpretado como T
Exemplo 2
 I[H2]=F?
 I[H2]=F (É falso que existe aluno de CCO que é rico. 
Então é falso que existe aluno rico, logo todo aluno é 
pobre)
⇔ I[(∃x)p(x)]=F 
⇔ ∀d ∈ aluno-CCO; d é pobre 
⇔ ∀d ∈ aluno-CCO; pI(d)=F 
⇔ ∀d ∈ aluno-CCO; <x ← d>I[p(x)]=F
 Não existe aluno-CCO rico
 ∃d ∈ aluno-CCO;<x ← d>I[p(x)]=F

 ∀d∈aluno-CCO, se x é interpretado como d
 Então p(x) é interpretado como F
Exemplo 3
 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)
 “Para todo número natural x, x<4”
 I[G]=F 
⇔ I[(∀x)p(x,y)]=F 
⇔ ∃d ∈ N; <x ← d>I[p(x,y)]=F
⇔ ∃d ∈ N; d<4 é falso, que é verdadeira
⇔ I[G]=F é verdadeira
 A interpretação de G segundo I é falsa
Exemplo 4
 E=(∀x) (∃y)p(x,y)
 “Para todo natural x, existe outro natural y tal que x<y”
 I[E]=T 
 ⇔ I[(∀x)(∃y)p(x,y)]=T 
 ⇔ ∀d∈N; <x ← d>I[(∃y)p(x,y)]=T
 ⇔ ∀d∈N, ∃c∈N; <y ← c><x ← d>I[p(x,y)]=T 
 ⇔ “∀d∈N, ∃c∈N; d<c é verdadeiro”, que é verdadeira
 ⇔ I[E]=T é verdadeira
Exemplo 4
 Supondo I[E]=F 
 ⇔ I[(∀x) (∃y)p(x,y)]=F 
 ⇔ ∃d∈N;<x ← d>I[(∃y)p(x,y)]=F
 ⇔ ∃d∈N, ∀c∈N;<y ← c><x ← d>I[p(x,y)]=F 
 ⇔ ∃d∈N, ∀c∈N; d<c é falso 
 ⇔ ∃d∈N, ∀c∈N; d>=c é verdadeira, que é falsa! 
(não existe um número maior que todos!)
 ⇔ I[E]=F é falso 
 ⇔ I[E]=T
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
 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 ⇔ I[(∀x)p(x,y)]=T 
 ⇔ ∀d∈Q*, <x ← d>I[p(x,y)]=T
 (Depende da variável livre y)
 ⇔ “∀d∈Q*, d<77 é verdadeiro”, 
 ou “d<77 é verdadeiro ∀d∈Q*”, que é falsa, pois é 
 possível escolher d=80.
 ⇔ I[H1]=T é falsa 
 ⇔ I[H1]=F
Exemplo 5
 Supondo I[H1]=F ⇔ I[(∀x)p(x,y)]=F 
 ⇔ ∃d∈Q*, <x ← d>I[p(x,y)]=F
 ⇔ “∃d∈Q*, d<77 é falso”, 
ou “d<77 é falso para algum d∈Q*”, que é verdadeira!
 ⇔ I[H1]=F é verdadeira 
 ⇔ I[H1]=F
Exemplo 6
 H2= (∃x)p(x,y) 
 I[H2]=T ⇔ I[(∃x)p(x,y)]=T 
 ⇔ ∃d∈Q*, <x ← d>I[p(x,y)]=T
 ⇔ “∃d∈Q*, d<77 é verdadeiro”, 
ou “d<77 é verdadeiro ∃d∈Q*”, que é verdadeira!
 ⇔ I[H2]=T é verdadeira 
 ⇔ I[H2]=T
Exemplo 6
 Supondo I[H2]=F⇔ I[(∃x)p(x,y)]=F 
 ⇔ ∀d∈Q*, <x ← d>I[p(x,y)]=F
 ⇔“∀d∈Q*, d<77 é falso”, 
ou “d<77 é falso para todo d∈Q*”, que é falsa!
 ⇔ I[H2]=F é falsa 
 ⇔ I[H2]=T
Exemplo 7
 I em Q* (racionais, exceto o zero)
I[a]=1,I[b]=25,I[x]=13,I[y]=77,I[f]=/,I[p]=<
 G=(∀x)(∃y)p(x,y)  p(b,f(a,b))
 Supondo I[G]=F ⇔ I[(∀x)(∃y)p(x,y)  p(b,f(a,b))]=F
 ⇔ I[(∀x)(∃y)p(x,y)]=T e I[p(b,f(a,b))]= F
 I[p(b,f(a,b))] sse (25<(1/25)) que é falsa
 I[(∀x)(∃y)p(x,y)]=T
 ⇔ ∀d∈Q*, ∃c∈Q*; <y ← c><x ← d>I[p(x,y)]= T
 ⇔ “∀d∈Q*, ∃c∈Q*; d<c é verdadeiro”, que é verdadeira 
 ⇔ 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
 H=(∀x)(∃y)p(x,y)  p(f(a,b),b)
 Supondo I[H]=F ⇔ I[(∀x)(∃y)p(x,y)  p(f(a,b),b)]=F
 ⇔ 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
 I em Q* (racionais, exceto o zero)
I[a]=1,I[b]=25,I[x]=13,I[y]=77,I[f]=/,I[p]=<
 H3= (∀x)(∃y)p(x,y)  p(x,y)
 Existem ocorrências livres de x e y em H3
 É preciso usar as interpretações 
I[x]=13 e I[y]=77
 I[p(x,y)]=T => I[H3]=T
Exemplo 10
 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 
 ⇔ I[(∀x)((∃y)p(x,y)  p(x,y))]=F
 ⇔ ∃d∈Q*, <x ← d>I[(∃y)p(x,y)  p(x,y)]=F (Implicação!)
 ⇔ ∃d∈Q*, <x ← d>I[(∃y)p(x,y)]=T e <x ← d> I[p(x,y))]=F
 ⇔ ∃d∈Q*, ∃c∈Q*<y ← c><x ← d>I[p(x,y)]=T e <x ←d>I[p(x,y))]=F
 ⇔ “∃d∈Q*,∃c∈Q*,(d<c) é verdadeiro e (d<77) é falso”
(A afirmação é verdadeira. Basta fazer d=100 e c =200)
 I[H4]=F realmente
Exercício
 I em Q* (racionais, exceto o zero)
I[a]=1,I[b]=25,I[x]=13,I[y]=77,I[f]=/,I[p]=<
 E=(∀x)(∃y)p(x,y)  p(f(a,b),x)
 Nos casos em que (1/25)<xI 
 I[p(f(a,b),x)]=T, e temos uma contradição 
 I[E]=T
 Nos casos em que (1/25)>=xI
 I[E]=F
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31