Lógica Predicados (sintaxe)

Prévia do material em texto

Lógica de Predicados
 Sintaxe
 Semântica
A linguagem da lógica de predicados
 Linguagem – sintaxe e semântica
 Extensão da lógica proposicional
 Inferências que não possuem representação adequada na 
lógica proposicional podem ser representadas na lógica 
de predicados
 Exemplo: 
Todo aluno de Computação é inteligente.
Luciano é aluno de Computação. Logo, Luciano é inteligente
 Como representar a palavra “todo”?
Alfabeto
 Símbolos de pontuação: ( , )
 Símbolo de verdade: true, false
 Conjunto de símbolos para variáveis: x, y, z, w, x1, y1, z1, w1, x2,...
 Conjunto de símbolos para funções: f, g, h, f1, g1, h1, f2, g2, ...
 Conjunto de símbolos para predicados: p, q, r, p1, q1, r1, p2, ... 
 Conectivos: ¬, ∧, ∨,→, ↔, ∀, ∃
Alfabeto
 Aridade 
 número inteiro não-negativo associado a cada 
símbolo para função ou predicado
 Variáveis
 não ocorrem na Lógica Proposicional
 Em programação lógica são utilizadas na 
determinação das respostas dos programas
 Funções e predicados
 maior poder de representação 
Alfabeto
 Constantes e símbolos proposicionais
 Se aridade=0, a função ou predicado tem zero 
argumento
 Funções com aridade nula são constantes
 Predicados com zero argumento são os símbolos 
proposicionais
 Conectivos
 Quantificadores – aumentam poder de representação
Elementos básicos da linguagem
 Resultado de uma interpretação
 Valor verdade
 Objeto
 A capital de Minas Gerais é BH?
 Qual a capital de Minas Gerais?
 Termos: sentenças que representam os objetos
 Variáveis são termos (a interpretação é um objeto)
 Função de termos é um termo (resultado da aplicação de 
uma função a um conjunto de termos é um termo)
 Variável x
 Constante “a” (função de 0 argumento, aplicada a 0 termo)
 f(x,a) – se for função binária é um termo
Exemplos de termos
 x, a (constante, função zero-ária)
 f(x,a) se e somente se f é binária
 g(y, f(x,a), c) se e somente se g é ternária
 +(9,10), -(9,5)
 h(x,y,z), considerada implicitamente como ternária
Elementos básicos da linguagem
 Átomos: expressões cuja interpretação é um valor verdade
 Símbolos de verdade são átomos
 Predicado de termos é um átomo
 P – predicado aplicado a 0 termos – símbolo 
proposicional é um átomo
Exemplos de átomos
 P (símbolo proposicional) 
 p(f(x,a),x) se e somente se p é binário
 q(x,y,z) considerado implicitamente como ternário
 Ex: >(9,10), =(9,+(5,4))
 interpretados como 9>10, 9=5+4
Elementos básicos da linguagem
 Fórmula
 Concatenação de átomos e conectivos
 São construídas a partir destas regras:
 Todo átomo é uma fórmula da Lógica de Predicados
 Se H é fórmula então (¬H) também é 
 Se H e G são fórmulas, então (H∨G) também é
 Se H é fórmula e x variável, então 
((∀x)H) e ((∃x)H) são fórmulas
 Expressão = termo ou fórmula
Elementos básicos da linguagem
 Subtermo
 Se E=x, então a variável x é subtermo de E
 Se E = f(t1,t2,...,tn) então ti e f(t1,t2,...,tn) são subtermos de 
E
 Se t1 é subtermo de t2 e t2 de E, então t1 também é 
subtermo de E
 Subfórmula - Se H é fórmula:
 H é uma subfórmula
 Se H=(¬G), então G é subfórmula de H
 Se H é do tipo (E∨G), (E∧G), (E→G) ou (E↔G), então E e G 
são subfórmulas de H
 Se x é uma variável e Q um quantificador, H=((Qx)G) então 
G e ((Qx)G) são subfórmulas de H
 Se G é subfórmula de H, então toda subfórmula de G 
também é subfórmula de H
Elementos básicos da linguagem
 Todo subtermo ou subfórmula é uma subexpressão
 Literal em lógica de predicados é um átomo ou sua 
negação
 Uma fórmula está na forma normal disjuntiva (fnd ou DNF, 
em inglês) se é uma disjunção de conjunções de literais
 Uma fórmula está na forma normal conjuntiva (fnc ou CNF, 
em inglês) se é uma conjunção de disjunções de literais
Ordem de precedência
 Maior precedência: ¬
 Intermediária superior: ∀, ∃
 Intermediária inferior: ∧, ∨
 Precedência inferior: →, ↔
Correspondência entre quantificadores
 Seja uma fórmula H e uma variável x
Os quantificadores existencial ∃ e universal ∀ se relacionam 
pelas correspondências:
((∀x)H) = ¬((∃x)(¬H))
((∃ x)H) = ¬((∀x)(¬H))
 ∀(x) Gosta(x,Banana)⇔ ¬ ∃(x) ¬Gosta(x,Banana)
 Todo x gosta de banana, sse não existe x que não gosta 
de banana
 Qualquer quantificador pode ser definido a partir do outro
Escopo do quantificador
 Abrangência de seu uso nas subfórmulas
 Se E é uma fórmula na Lógica de Predicados
 Se ((∀x)H) é subfórmula de E
 o escopo de (∀x) é H
 Se ((∃x)H) é subfórmula de E
 o escopo de (∃x) é H
 Exemplo
 G=(∀x)(∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1))
 O escopo de (∀x) é (∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1))
 O escopo de (∃y) é ((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1))
 O escopo de (∀z) é p(x,y,w,z)
 O escopo de (∀y) é q(z,y,x,z1))
Ocorrência livre e ligada
 Se x é uma variável e E uma fórmula, uma ocorrência de x 
em E é
 Ligada, se x está no escopo de um quantificador (∀x) 
ou (∃x) em E
 Livre, se não for ligada
 G=(∀x)(∃y)((∀z)p(x,y,w,z) → (∀y)q(z,y,x,z1))
Variável livre e ligada
 Se x é uma variável e E uma fórmula que contém x. x é
 Ligada em E, se existir uma ou mais ocorrências ligadas 
de x em E 
 Livre em E, se existir uma ou mais ocorrências livres de 
x em E
 No exemplo anterior, z é livre e ligada!
 G=(∀x)(∃y)((∀z)p(x,y,w,z) → (∀y)q(z,y,x,z1))
Símbolos livres
 Símbolos livres de uma fórmula são suas variáveis livres, 
símbolos de função e de predicado
 Tudo menos os conectivos, variáveis dos 
quantificadores, símbolos de verdade e de pontuação
 G=(∀x)(∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1))
 Conjunto de símbolos livres é {w,z,z1,p,q}
Fórmulas fechadas
 Fórmulas fechadas não possuem variáveis livres
 Exemplos:
 G=(∀x)(∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1))
 Não é fórmula fechada
 G1=(∀w)(∀z)(∀z1)(∀x)(∃y) ((∀z)p(x,y,w,z)→(∀y)q(z,y,x,z1)) 
 Variáveis ligadas: w,y,z,z1,x
 Fórmula fechada!
Fecho de uma fórmula
 Se H é fórmula da Lógica de Predicados e {x1, x2, ..., xn} é o 
conjunto das variáveis livres em H
 O fecho universal de H, (∀*)H, é (∀x1)(∀x2)...(∀xn)
 G=(∀x)(∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1))
 G1=(∀w)(∀z)(∀z1)(∀x)(∃y) ((∀z)p(x,y,w,z)→(∀y)q(z,y,x,z1)) 
 G1 é o fecho universal de G
 O fecho existencial de H, (∃*)H, é (∃x1)(∃x2)...(∃xn)
 G2=(∃w)(∃z)(∃z1)(∀x)(∃y) ((∀z)p(x,y,w,z)→(∀y)q(z,y,x,z1))
 Se H é fechada, como não possui variáveis livres, seus 
fechos universal e existencial são iguais a H
H=(∀*)H=(∃*)H
	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