1 L³gica 0 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1 0 0 1 0 0 Inteligncia Artificial Docente: Andr© C. P. L. F. de Carvalho PAE: Everl¢ndio Fernandes

  • View
    231

  • Download
    4

Embed Size (px)

Text of 1 L³gica 0 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1 0 0 1 0 0 Inteligncia Artificial...

Recommending a Strategy

1Lgica

0 1 1 0 0 1 1 01 1 0 0 1 0 0 10 1 1 0 1 1 1 11 0 1 0 0 1 0 0Inteligncia ArtificialDocente: Andr C. P. L. F. de CarvalhoPAE: Everlndio FernandesMonitor: Anderson Silva22/04/201412Principais TpicosIntroduoNotaoRegras de infernciaProva de teoremasConcluso3LgicaSe todos que estudam e entendem IA so aprovados

Asdrbal estudou e entendeu IA

LogoAsdrbal ser aprovado4LgicaOrigem na filosofia gregaLogos: razoFilsofos a indagavam se o logos:Obedecia ou no a regrasPossua ou no normas, princpios e critrios para o seu funcionamentoLgica5LgicaCriada por Aristteles (388 AC 322 AC)Foi aluno da academia de PlatoQueria por ordens nos conceitos utilizados pelas pessoasEstabeleceu uma srie de normas rgidas para que concluses ou provas pudessem ser consideradas logicamente vlidas6Importante rea da matemticaAtraiu grande ateno no sculo XIX e comeo do sculo XX Procurava achar uma linguagem matemtica para discutir o mundoAinda existem vrios especialistas na rea, especialmente em computaoUtilizam lgica para resolver problemas de computaoLgica22/04/201467Lgica proposicionalAfirmaes so avaliadas como verdadeiras ou falsasLgica de predicadosAfirmaes contm variveis que denotam objetosLgica de segunda ordemPermite quantificar relaes entre variveis ( e )Lgica de ordem superiorAplica quantificadores a predicados e tem semntica mais forteExistem vrias lgicas22/04/201478Existem vrias lgicasLgica temporalLeva em conta aspectos temporaisLgica monotnicaVerdade de uma afirmao pode mudar quando novas informaes so obtidasLgica paraconsistentePermite contradiesLgica nebulosa (fuzzy)Um conceito pode ser pouco ou muito certoE muitas outras

9Lgica uma ferramenta importante em IABase de sistemas baseados em regrasRepresentam problemas utilizando regras do tipo se-entoPermite representar formalmente conhecimento, facilitando sua manipulaoAplicaes: Sistemas Baseados em Conhecimento ( Especialistas), Prova de Teoremas, Sistemas de DiagnsticoLgica22/04/2014910Linguagem para representao de conhecimentoVantagem: concisa e universalmente conhecidaDesvantagem: pode desviar a ateno da aplicao para lgica matemticaToda expresso lgica composta por:Sintaxe = formaSemntica = significado, interpretaoLgica22/04/20141011SintaxeComponentes lxicos:TermosPredicadosFrmulas atmicasLiteraisConectivos lgicos12Termo (smbolo):Pode ser:Objeto do mundo real (constante)VarivelFuno (utiliza termos como argumentos e retorna termo como resultado)Ex: casa, x, f-maior(joo, jos)Definies de sintaxe22/04/20141213Predicado: utiliza termos como argumentos e retorna valores V ou FEx: cidade ()Frmula atmica ::= predicado ([termo]) Um ou mais termos como argumentoEx: cidade (Santos), irmao(Joao, Jose)Literal := frmula atmica | frmula atmicaEx: estado(Santos)Definies de sintaxe22/04/20141314Conectivos lgicosOperadoresOperador de conjuno: Operador de disjuno: Operador de implicao: Operador de negao: Precedncia de avaliao: Definies de sintaxe22/04/201414Tabelas verdade15AB AF F FFVVF V FVVVV F FVFFV V VVVF16Tabelas verdadeOperador de implicao ()Implicao a partir de um antecedente falso implica em qualquer coisaExemplo:Se a lua redonda, ento a terra redonda (V)Se a lua redonda, ento a terra quadrada (F)Se a lua quadrada, ento a terra redonda (V)Se a lua quadrada, ento a terra quadrada (V)17

Tabela de equivalncia22/04/20141718QuantificadoresQuantificador universal x(expExpresso exp verdadeira para todo valor de xEx: x [pena (x) passaro (x)]Quantificador existencial x(expExpresso exp verdadeira para pelo menos um valor de xEx: x [poe_ovo (x) (passaro (x))]Sintaxe22/04/20141819Componente estruturalFrmula Bem Formada (FBF): expresso formada de acordo com a gramtica:FBF ::= Literal | FBF FBF | FBF FBF | FBF | FBF FBF | x (FBF) | x (FBF)Ex: (voa (pardal) pena (pardal)) passaro (pardal)FBF geralmente abreviado para expressoSintaxe22/04/20141920Sentena: FBF em que todas as variveis esto no escopo de quantificadoresEx: x[(voa (x) tem_pena (x) passaro(x)] Clusula: FBF formada por disjuno de literaisEx: passaro (pardal) irmao (joao, maria)Sintaxe22/04/20142021Relaciona termos e predicados de expresses lgicas a algo conhecidoAssocia termos a objetos de um domnio ou mundo (real ou imaginrio)Associa predicados a relaes de um mundo Semntica22/04/20142122Lgica X MundoMundoLgicasobre (A, B)PredicadosRelaosobreABTermosObjetosRelaes22/04/20142223Modelo: interpretao para um mundo de termos e predicados de uma expressoExpresso verdadeira para objetos e relaes de um mundo Axiomas: expresses previamente definidas como verdadeirasEx: passaro (pardal)Semntica22/04/20142324Teorema: Expresso que pode ser provada verdadeira a partir de um conjunto de axiomasSegue logicamente dos axiomasPor meio de um procedimento de provaProcedimento de provaAplica regras vlidas de inferncia aos axiomas e s expresses resultantesProva de teoremas22/04/20142425Regras vlidas de inferncia: Produzem novas expresses a partir das expresses existentesModelo das expresses anteriores tambm vlido para as novas expressesProva de teoremas22/04/20142526Inferncia um problema de buscaN inicial: Informao fornecida ao procedimento de provaN alvo ou objetivo:Concluso desejada Operadores que geram sucessores de ns: Aqueles que geram uma nova expresso aplicando alguma regra de infernciaProva de teoremas22/04/20142627Provar teorema diferente de:Provar que uma expresso vlida Verdadeira (V) para todas as interpretaes dos smbolosProvar que uma expresso satisfatria Verdadeira (V) para alguma possvel interpretao dos smbolosRegras de inferncia22/04/201427Regras de infernciaRegras de inferncia mais utilizadasModus ponensResoluoModus tolens

2829AA B

BEx: pena (pardal) pena (pardal) passaro (pardal)

passaro (pardal)Regra mais diretaModus ponens22/04/20142930ExerccioDadas as regras:Quem joga lixo na rua mal educadoQuem mal educado no pode viver em sociedadeQuem no pode viver em sociedade deveria viver em uma cavernaQuem vive em uma caverna fica loucoProvar por Modus Ponens que quem joga lixo na rua fica louco31 A BB C

A C Ex: bebe (Zuzu) estuda (Zuzu) estuda (Zuzu) dorme (Zuzu)

bebe (Zuzu) dorme (Zuzu)resolventeResoluo22/04/20143132Podem existir N disjunes em qualqueruma das clusulas (inclusive nenhuma) A BB C

A C Ex: pena (pardal) pena (pardal) passaro (pardal)

passaro (pardal)resolventeResoluo22/04/20143233A regra modus ponens um caso especial da regra da resoluo pena (pardal) pena (pardal) passaro (pardal) pena (pardal) pena (pardal) passaro (pardal)Resoluo22/04/20143334 A BB

AEx:pena (cachorro) passaro (cachorro) passaro (cachorro)

pena (cachorro)Regra modus tolens um caso especial da regra da Resoluo Modus tolens22/04/20143435Regra modus tolens um caso especial da regra da Resoluo pena (pardal) passaro (pardal) passaro (pardal)pena (pardal) pena (pardal) passaro (pardal)Resoluo22/04/20143536Modus tolens A BBA BBA BBA37Estratgias para provar teoremasProva por exausto: A partir dos axiomas, aplicar regras de inferncia sobre as expresses existentes Esperando eventualmente deduzir o teoremaProva por refutao: Provar que a negao do teorema no verdadeiraProva de teoremas22/04/201437381 - Assumir que a negao do teorema verdadeira2 - Mostrar que os axiomas juntos com a negao do teorema levam a uma contradio3 - Concluir que a negao do teorema no pode ser verdadeira, pois leva a uma contradio4 - Concluir que o teorema verdadeiro porque sua negao no pode ser verdadeiraPassos para prova por refutao22/04/20143839Dados os axiomas abaixo, prove que pardal um pssaro utilizando prova por refutaoAxiomas: a) pena (pardal) passaro (pardal)b) pena (pardal)Teorema:passaro (pardal)Exerccio22/04/201439401) Assumir que a negao do teorema verdadeirac) passaro (pardal)2) Mostrar contradio

pena (pardal) passaro (pardal)pena (pardal) passaro (pardal)Contradio passaro (pardal)passaro (pardal)2.3nil (clusula vazia)Exerccio22/04/20144041Forma de reconhecer que um teorema foi provado:Esperar at resoluo ser aplicada a uma literal e sua negaoResultado uma clusula vazia (nil)Garante que o teorema foi provadoRefazer o exerccio 1 utilizando prova por exaustoExerccio22/04/20144142Dados os axiomas abaixo, provar por refutao que Asdrubal vai passar Axiomas: a) Estuda (Asdrubal)b) le (Asdrubal) sabido (Asdrubal) b) le (Asdrubal) limpo (Asdrubal) c) sabido (Asdrubal) passar (Asdrubal)d) estuda (Asdrubal) le (Asdrubal)Teorema:passar (Asdrubal)Exerccio 222/04/20144243Dados os axiomas abaixo, prove que p verdade usando prova por refutaoAxiomas: a) q r pb) s pc) s qd) t re) qExerccio 322/04/20144344O que fazer para o caso abaixo?x[estudaIA(x) reprovaIA(x)]Para usar resoluo, os axiomas tm que estar na forma de clusulasNecessrio transformar axiomas originais em axiomas equivalentes na forma de clusulasObservaes22/04/20144445Transformar para a forma de clusulas os axiomas:Um tijolo est sobre alguma coisa que no uma pirmideNo existe nada que um tijolo esteja sobre, que esteja sobre o tijoloNo existe nada que seja um tijolo e no seja um tijoloExerccio 422/04/201445Transformar para a forma de clusulas os axiomas:Um tijolo est sobre alguma coisa que no uma pirmideNo existe nada que um tijolo esteja sobre, que esteja sobre o tijoloNo existe nada que seja um tijolo e no seja um tijolo

x[Tijolo(x)

( y[Sobre(x, y) Piramide(y)]

y[Sobre(x, y) Sobre (y,x)]

y[Tijolo(y) Igual (x,y)])]

46Exerccio 447Escrevendo como uma expresso lgica:x[Tijolo(x) (y[Sobre(x, y) Piramide(y)] y[Sobre(x, y) Sobre (y,x)] y[Tijolo(y) Igual (x,y)])]Exerccio 422/04/201447Exerccio 4Passo 1: eliminar implicaesSabendo que (A B) ( Ax[Tijolo(x) (y[Sobre(x, y) Piramide(y)] y[Sobre(x, y) Sobre (y,x)