View
212
Download
0
Embed Size (px)
1
IME- USP Leliane Nunes de Barros
Lgica de Primeira Ordem
Captulo 8
2
IME- USP Leliane Nunes de Barros
Lgica Proposicional
Linguagem declarativa sua semntica se baseia em uma relao-verdade entre sentenas e mundos possveis Capacidade de expresso para lidar com
informaes parciais, usando disjunes e negao
Linguagem composicional: o significado de suas sentenas uma funo do significado de suas partes. Exemplo: a verdade de depende da verdade de e de
3
IME- USP Leliane Nunes de Barros
Lgica Proposicional (LP)
Problemas: Falta de capacidade de expresso para
descrever de forma concisa um ambiente com muitos objetos. Exemplo:
B1,1 (P1,2 P2,1)B1,2 (P1,3 P2,2)B1,3 (P1,2 P1,4 P2,3)...
Linguagem natural: existe brisa nos quadrados adjacentes a poos
4
IME- USP Leliane Nunes de Barros
Lgica de Primeira Ordem (LPO)
Faz a suposio que o mundo constituido de objetos com certas propriedades ourelaes entre eles.
Objetos podem ser definidos em funo de outros objetos
5
IME- USP Leliane Nunes de Barros
LP versus LPO (FOL)
fatos
Objetos
Relaes Funes
Propriedades
LPO
LP
6
IME- USP Leliane Nunes de Barros
LP versus LPO
Compromissos ontolgicos: LP: existem fatos que so verdadeiros ou
falsos no mundo LPO: o mundo constituido de objetos com
certas relaes entre eles que so verdadeiras ou falsas
Outro exemplo de compromisso ontolgico: Lgica temporal: fatos so verdadeiros falsos
em instantes especficos do tempo e esses instantes (pontos ou intervalos) esto ordenados
7
IME- USP Leliane Nunes de Barros
Exemplos de objetos, relaes e funes
Objetos: pessoas, casas, nmeros, Lula, cores, anos, guerras, ...
Relaes unrias (ou propriedades): vermelho, redondo, falso, primo, ...
Relaes n-rias: irmo de, maior que, tem cor, pertence a, fica entre, ...
Funes: pai de, melhor amigo, terceiro
8
IME- USP Leliane Nunes de Barros
Objetos, relaes e funes
Quadrados vizinhos ao Wumpus so fedorentos
Objetos: quadrados, Wumpus Propriedade: fedorentos Relao: vizinhos
9
IME- USP Leliane Nunes de Barros
Modelos em LP e LPO LP: valores verdade atribuidos para os smbolos
proposicionais que ... ... tornam sentenas da KB verdadeiras
LPO: modelos contm objetos. O domnio de um modelo o conjunto de objetos que ele contm. Os objetos dos modelos podem estar relacionados de vrias maneiras e para essas relaes que so atribuidos valores verdade que ...
... tornam sentenas da KB verdadeiras
10
IME- USP Leliane Nunes de Barros
LPO Em LPO um literal contm termos
LP: W1,2LPO: Wumpus( linha, coluna)
Termos so expresses construdas a partir de smbolos constantes, variveis e smbolos de funes.
Termos so referncias aos objetos do modelo Smbolos constantes: A, B,C, Joo, Rei,
Presidente, Chefe, Professor. Cada constante nomeia um nico objeto.
Variveis: x, y, casa, percepo, linha . Cada varivel nomeia um conjunto de objetos.
11
IME- USP Leliane Nunes de Barros
LPO - Sintaxe
Smbolos de predicados (relaes) Especificam uma relao entre os objetos de um
modelo. Um predicado pode ser binrio ou n-rio. Ex.: Irmo(Lendro, Leonardo), Irmo(Leonardo,
Leandro). Irmo se refere ao conjunto de todas as duplas de objetos do modelo:
{ , , , , >}
12
IME- USP Leliane Nunes de Barros
LPO - Sintaxe
Smbolos de funes: Algumas relaes entre objetos so funcionais:
relacionam objetos com um outro objeto do modelo (def. de funo).
Exemplos: PaiDe(Leandro), IrmoDe(Leonardo), Idade(Leo), Altura(Ana)...
No modelo: conjunto de (n+1)-uplas, sendo o ltimo elemento, o valor da funo para os n primeiros elementos
13
IME- USP Leliane Nunes de Barros
Interpretao
Termos simples ou termos complexos (funes)
Predicados
objetos
relaes
14
IME- USP Leliane Nunes de Barros
LPO - Sintaxe
Sentenas atmicas:Declaram fatos. Formadas por um smbolo predicado
seguida por uma lista de termos entre parntesesirmo(Leandro, Leonardo)-pai(Joo, Pedro) ( funo: pai-de(Joo) )
A verdade de uma sentena atmica depende da interpretao e do modelo
Sentenas complexas:Uso dos conectivos lgicos. A semntica das sentenas
a mesma da LP
15
IME- USP Leliane Nunes de Barros
LPO - Sintaxe
Quantificadores: usados para expressar propriedades de colees inteiras de objetos, ao invs de enumerar cada um dos objetos pelo seu nome. LPO possue dois quantificadores:
Quantificador Universal () Quantificador Existencial ()
16
IME- USP Leliane Nunes de Barros
Quantificador Universal ()
Exemplo: Todos os gatos so mamferos
Gato(Mimi) ^Gato(Felix) ^Mamfero(Mimi) ^Mamfero(Felix) ^
x Gato(x) => Mamfero(x)Para todo x, se x um gato ento x mamfero
17
IME- USP Leliane Nunes de Barros
Quantificador Universal () x P, onde P qualquer sentena lgica,
afirma que P verdadeira para todo objeto x
Gato(Mimi) Mamfero(Mimi) ^Gato(Felix) Mamfero(Felix) ^Gato(Joo) Mamfero(Joo) ^Gato(Pedro) Mamfero(Pedro) ^
. define que todas essas sentenas so
verdadeiras!
18
IME- USP Leliane Nunes de Barros
Quantificador Existencial ()
Permite escrever uma sentena com objetos particulares sem citar o seu nome:
Felix tem uma irm que uma gata
x Irm(x,Felix) ^ Gata(x)Existe x, x irm de Felix e x uma gata
19
IME- USP Leliane Nunes de Barros
Quantificador Existencial ()
x P, onde P verdade para algum objeto no universo, por exemplo:
P x Irm(x,Felix) ^ Gata(x)Irm(Mimi, Felix) ^ Gato(Mimi) vIrm(Felix, Felix) ^ Gato(Felix) vIrm(Joo, Felix) ^ Gato(Joo) vIrm(Pedro, Felix) ^ Gato(Pedro) v
define que pelo menos uma dessas sentenas verdadeira
20
IME- USP Leliane Nunes de Barros
Quantificadores aninhados
x y Pai(x,y) Filho(y,x) x, y Irmo(x,y) Irmo(x,y)
Todo mundo ama algum x y Ama(x,y)
Existem pessoas que so amadas por todas y x Ama(x,y)
A ordem dos quantificadores importante x ( y P(x,y)) x (y P(x,y))
21
IME- USP Leliane Nunes de Barros
Conexes entre e
x Gosta(x, Cenouras) equivalente a
x Gosta(x,Cenouras)
x Gosta(x, Cenouras) equivalente a
x Gosta(x,Cenouras)
22
IME- USP Leliane Nunes de Barros
Igualdade
Outra maneira de se construir sentenas atmicas em LPO: uso do smbolo de igualdade para fazer com que
dois termos correspondam ao mesmo objetoPai(Joo) = Pedro
Um outro exemplo: x, y Irmo(x,Ricardo) Irmo(y,Ricardo) (x = y)
predicado
Lgica de Primeira Ordem com Igualdade
23
IME- USP Leliane Nunes de Barros
LPO - SintaxeSentena => SentenaAtmica |
(Sentena Conectivo Sentena) | Quantificador Varivel Sentena | Sentena |
SentenaAtmica => Predicado(Termo, ) | Termo = Termo
Termo => Funo(termo) |Constante |Varivel
Conectivo => | | | Quantificador => | Constante => A | X1 | Joo | Varivel => a | x | s | ...Predicados => Antes | TemCor | Chovendo | Funo => Mo | irmo | Resultado
24
IME- USP Leliane Nunes de Barros
Asseres e consultas em LPO
TELL(KB,Rei(Joo))TELL(KB, x Rei(x) Pessoa(x))
ASK(KB,Rei(Joo)) ? devolve verdadeiro.
ASK(KB,Pessoa(Joo)) ? devolve verdadeiro.
25
IME- USP Leliane Nunes de Barros
Asseres e consultas em LPOASK(KB, x Pessoa(x)) ?
devolve verdadeiro.
Esse tipo de consulta tambm pode fornecer um valor para x. Chamamos de substituio ou lista de unificaes a um conjunto de pares varivel/termos
ASK(KB, x Pessoa(x)) ? devolve {x/Joo}.
26
IME- USP Leliane Nunes de Barros
UnificaoProcesso de encontrar uma substituio de
variveis () que faz com que duas sentenas se tornem iguais Unifica(p,q) = sendo Subst(,p) = Subst(,q)
Exemplos: Unifica(Conhece(Joo,x), Conhece(x, Maria)) = falha
x no pode ser igual a Joo e Maria ao mesmo tempo Unifica(Conhece(Joo,x1), Conhece(x2, Maria) =
(x1/Maria, x2/Joo) Unifica(Conhece(x1,x2), Conhece(Joo, Maria) =
(x1/Joo, x2/Maria)
27
IME- USP Leliane Nunes de Barros
Extenses e variaes notacionais
Lgicas de ordem maior: podem quantificar relaes e no somente os objetos do domnio. Por exemplo:
x,y (x=y) (p p(x) p(y) ) dois objetos so iguais sse se todas as propriedades
aplicadas a eles so equivalentes, ou f,g (f=g) (x f(x) = g(x) )
duas funes so iguais sse elas possuirem o mesmo valor para todos os argumentos
28
IME- USP Leliane Nunes de Barros
Axiomas, Definies e Teoremas
Axiomas capturam fatos bsicos sobre um domnio usados para definir conceitos usados para provar teoremas
Fatos do dominio
Axiomas Definies
Teoremas
29
IME- USP Leliane Nunes de Barros
Axiomas, definies e teoremas Qual a quantidade de axiomas necessria
para definir um domnio? Qual a quantidade de predicados necessria
para definir um domnio? Existem muitos axiomas? Exemplo de
escolhas na modelagem de um domnio: x y Irmos(x,y) Irmos(y,x)
ou p Pai(p,Joo) ^ Pai(p,Pe
