Lógica de Primeira Ordem Capítulo 8 - ime.usp.br leliane/IAcurso2006/slides/Aula9-FOL-I-2006.pdf2

  • View
    212

  • Download
    0

Embed Size (px)

Text of Lógica de Primeira Ordem Capítulo 8 - ime.usp.br leliane/IAcurso2006/slides/Aula9-FOL-I-2006.pdf2

  • 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