View
256
Download
4
Category
Preview:
Citation preview
1
Lógica
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 0
Inteligência Artificial
Docente: André C. P. L. F. de CarvalhoPAE: Everlândio FernandesMonitor: Anderson Silva
2
Principais Tópicos
Introdução Notação Regras de inferência Prova de teoremas Conclusão
3
Lógica
Se todos que estudam e entendem IA são aprovados
Asdrúbal estudou e entendeu IA
Logo
Asdrúbal será aprovado
9
Lógica é uma ferramenta importante em IA Base de sistemas baseados em regras
Representam problemas utilizando regras do tipo se-então
Permite representar formalmente conhecimento, facilitando sua manipulação
Aplicações: Sistemas Baseados em Conhecimento
( Especialistas), Prova de Teoremas, Sistemas de Diagnóstico
Lógica
10
Linguagem para representação de conhecimento Vantagem: concisa e universalmente
conhecida Desvantagem: pode desviar a atenção da
aplicação para lógica matemática Toda expressão lógica é composta por:
Sintaxe = forma Semântica = significado, interpretação
Lógica
11
Sintaxe Componentes léxicos:
Termos Predicados Fórmulas atômicas Literais Conectivos lógicos
12
Termo (símbolo): Pode ser:
Objeto do mundo real (constante) Variável Função (utiliza termos como argumentos
e retorna termo como resultado) Ex: casa, x, f-maior(joão, josé)
Definições de sintaxe
13
Predicado: utiliza termos como argumentos e retorna valores V ou F Ex: cidade ()
Fórmula atômica ::= predicado ([termo]) Um ou mais termos como argumento Ex: cidade (Santos), irmao(Joao, Jose)
Literal := fórmula atômica | fórmula atômica Ex: estado(Santos)
Definições de sintaxe
14
Conectivos lógicos Operadores
Operador de conjunção: Operador de disjunção: Operador de implicação: Operador de negação:
Precedência de avaliação:
Definições de sintaxe
Tabelas verdade
15
A B A
F F F F V V
F V F V V V
V F F V F F
V V V V V F
16
Tabelas verdade Operador de implicação ()
Implicação a partir de um antecedente falso implica em qualquer coisa
Exemplo: Se a lua é redonda, então a terra é redonda
(V) Se a lua é redonda, então a terra é quadrada
(F) Se a lua é quadrada, então a terra é redonda
(V) Se a lua é quadrada, então a terra é
quadrada (V)
17
Propriedades Expressão 1 Expressão 2 A B A B Comutatividade A B A A B AAssociatividade A B C) (A B ) C A B C) (A B ) C Distributividade A B C) (A B ) A
C) A B C) (A B ) A
C) De Morgan (A B ) A B (A B ) A B Anulação A A
Tabela de equivalência
18
Quantificadores Quantificador universalx(exp
Expressão exp é verdadeira para todo valor de x
Ex: x [pena (x) passaro (x)] Quantificador existencial x(exp
Expressão exp é verdadeira para pelo menos um valor de x
Ex: x [poe_ovo (x) (passaro (x))]
Sintaxe
19
Componente estrutural Fórmula Bem Formada (FBF): expressão
formada de acordo com a gramática: FBF ::= Literal | FBF FBF | FBF FBF | FBF
| FBF FBF | x (FBF) | x (FBF) Ex: (voa (pardal) pena (pardal)) passaro
(pardal) FBF é geralmente abreviado para expressão
Sintaxe
20
Sentença: FBF em que todas as variáveis estão no escopo de quantificadores Ex: x[(voa (x) tem_pena (x)
passaro(x)] Cláusula: FBF formada por
disjunção de literais Ex: passaro (pardal) irmao (joao,
maria)
Sintaxe
21
Relaciona termos e predicados de expressões lógicas a algo conhecido Associa termos a objetos de um
domínio ou mundo (real ou imaginário) Associa predicados a relações de um
mundo
Semântica
22
Lógica X MundoMundoLógica
sobre (A, B)
PredicadosRelação“sobre”
AB
Termos Objetos
Relações
23
Modelo: interpretação para um mundo de termos e predicados de uma expressão Expressão é verdadeira para objetos e
relações de um mundo Axiomas: expressões previamente
definidas como verdadeiras Ex: passaro (pardal)
Semântica
24
Teorema: Expressão que pode ser provada
verdadeira a partir de um conjunto de axiomas
Segue logicamente dos axiomas Por meio de um procedimento de prova
Procedimento de prova Aplica regras válidas de inferência aos
axiomas e às expressões resultantes
Prova de teoremas
25
Regras válidas de inferência: Produzem novas expressões a partir das
expressões existentes Modelo das expressões anteriores é
também válido para as novas expressões
Prova de teoremas
26
Inferência é um problema de busca Nó inicial:
Informação fornecida ao procedimento de prova
Nó alvo ou objetivo: Conclusão desejada
Operadores que geram sucessores de nós:
Aqueles que geram uma nova expressão aplicando alguma regra de inferência
Prova de teoremas
27
Provar teorema é diferente de: Provar que uma expressão é válida
Verdadeira (V) para todas as interpretações dos símbolos
Provar que uma expressão é satisfatória Verdadeira (V) para alguma possível
interpretação dos símbolos
Regras de inferência
Regras de inferência Regras de inferência mais
utilizadas Modus ponens Resolução Modus tolens
28
29
AA B
BEx: pena (pardal) pena (pardal) passaro (pardal)
passaro (pardal)
Regra mais direta
Modus ponens
30
Exercício Dadas as regras:
Quem joga lixo na rua é mal educado Quem é mal educado não pode viver em
sociedade Quem não pode viver em sociedade deveria
viver em uma caverna Quem vive em uma caverna fica louco
Provar por Modus Ponens que quem joga lixo na rua fica louco
31
A BB C
A C Ex: bebe (Zuzu) estuda (Zuzu) estuda (Zuzu) dorme (Zuzu)
bebe (Zuzu) dorme (Zuzu)resolvente
Resolução
32
Podem existir N disjunções em qualqueruma das cláusulas (inclusive nenhuma)
A BB C
A C Ex: pena (pardal) pena (pardal) passaro (pardal)
passaro (pardal)resolvente
Resolução
33
A regra modus ponens é um caso especial da regra da resolução pena (pardal)
pena (pardal) passaro (pardal)
pena (pardal) pena (pardal) passaro (pardal)
Resolução
34
A BB
A
Ex: pena (cachorro) passaro (cachorro) passaro (cachorro)
pena (cachorro)
Regra modus tolens é um caso especial da regra da Resolução
Modus tolens
35
Regra modus tolens é um caso especial da regra da Resolução pena (pardal) passaro (pardal)
passaro (pardal)
pena (pardal) pena (pardal) passaro (pardal)
Resolução
37
Estratégias para provar teoremas Prova por exaustão:
A partir dos axiomas, aplicar regras de inferência sobre as expressões existentes
Esperando eventualmente deduzir o teorema Prova por refutação:
Provar que a negação do teorema não é verdadeira
Prova de teoremas
38
1 - Assumir que a negação do teorema é verdadeira
2 - Mostrar que os axiomas juntos com a negação do teorema levam a uma contradição
3 - Concluir que a negação do teorema não pode ser verdadeira, pois leva a uma contradição
4 - Concluir que o teorema é verdadeiro porque sua negação não pode ser verdadeira
Passos para prova por refutação
39
Dados os axiomas abaixo, prove que pardal é um pássaro utilizando prova por refutação Axiomas:
a) pena (pardal) passaro (pardal)b) pena (pardal)
Teorema:passaro (pardal)
Exercício
40
1) Assumir que a negação do teorema é verdadeirac) passaro (pardal)
2) Mostrar contradiçãopena (pardal) passaro (pardal)
pena (pardal) passaro (pardal)
Contradiçãopassaro (pardal)passaro (pardal)
3 nil (cláusula vazia)
Exercício
41
Forma de reconhecer que um teorema foi provado: Esperar até resolução ser aplicada a
uma literal e sua negação Resultado é uma cláusula vazia (nil) Garante que o teorema foi provado
Refazer o exercício 1 utilizando prova por exaustão
Exercício
42
Dados os axiomas abaixo, provar por refutação 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)
Exercício 2
43
Dados os axiomas abaixo, prove que p é verdade usando prova por refutação Axiomas:
a) q rpb) spc) sqd) tre) q
Exercício 3
44
O que fazer para o caso abaixo? x[estudaIA(x) reprovaIA(x)]
Para usar resolução, os axiomas têm que estar na forma de cláusulas Necessário transformar axiomas
originais em axiomas equivalentes na forma de cláusulas
Observações
45
Transformar para a forma de cláusulas os axiomas: Um tijolo está sobre alguma coisa que
não é uma pirâmide Não existe nada que um tijolo esteja
sobre, que esteja sobre o tijolo Não existe nada que seja um tijolo e
não seja um tijolo
Exercício 4
Transformar para a forma de cláusulas os axiomas: Um tijolo está sobre
alguma coisa que não é uma pirâmide
Não existe nada que um tijolo esteja sobre, que esteja sobre o tijolo
Não existe nada que seja um tijolo e não 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)])]
46
Exercício 4
47
Escrevendo como uma expressão lógica:x[Tijolo(x) (y[Sobre(x, y) Piramide(y)]
y[Sobre(x, y) Sobre
(y,x)] y[Tijolo(y) Igual
(x,y)])]
Exercício 4
Exercício 4 Passo 1: eliminar implicações
Sabendo que (A B) ( Ax[Tijolo(x) (y[Sobre(x, y) Piramide(y)]
y[Sobre(x, y) Sobre
(y,x)] y[Tijolo(y) Igual
(x,y)])]
x[ Tijolo(x) (y[Sobre(x, y) Piramide(y)]
y[Sobre(x, y) Sobre (y,x)]
y[Tijolo(y)) Igual (x,y)])]
48
49
Passo 2: mover negações para as fórmulas atômicas
Exercício 4
50
Passo 2: mover negações para as fórmulas atômicas Sabendo que:
A A A A A A x[P(x)] x[ P(x)] x[P(x)] x[ P(x)]
Exercício 4
51
Passo 2: mover negações para as fórmulas atômicasx[ Tijolo(x) (y[Sobre(x, y) Piramide(y)]
y[Sobre(x, y) Sobre (y,x)]
y[Tijolo(y)) Igual (x,y)])]
x[ Tijolo(x) (y[Sobre(x, y) Piramide(y)]y[Sobre(x, y) Sobre
(y,x)]y[Tijolo(y) Igual (x,y)])]
Exercício 4
52
Passo 3: eliminar quantificadores existenciaisy[Sobre(x, y) Piramide(y)]
Para um objeto x particular, pode-se achar um objeto para y que torna a expressão verdadeira
Existe uma função que recebe x como argumento e retorna o y adequado
Não sabemos como a função funciona, mas sabemos que ela deve existir
Valor de y é uma função do valor das outras variáveis quantificadas
Sobre(x, Suporta (x)) Piramide (Suporta (x))
Exercício 4
53
Passo 3: eliminar quantificadores existenciaisx[Tijolo(x) (y[Sobre(x, y) Piramide(y)]
y[Sobre(x, y) Sobre (y,x)]y[Tijolo(y) Igual (x,y)])]
x[Tijolo(x) ((Sobre(x, Suporta(x)) Piramide(Suporta (x)))
y[Sobre(x, y) Sobre (y,x)]y[Tijolo(y) Igual (x,y)])]
Exercício 4
54
Passo 4: renomear variáveis quantificadas para evitar repetição de um quantificador universal Para que duas não tenham o mesmo nomex[Tijolo(x) ((Sobre(x, Suporta(x)) Piramide(Suporta
(x)))y[Sobre(x, y) Sobre (y,x)]y[Tijolo(y) Igual (x,y)])]
x[Tijolo(x) ((Sobre(x, Suporta(x)) Piramide(Suporta (x)))
y[Sobre(x, y) Sobre (y,x)]z[Tijolo(z) Igual (x,z)])]
Exercício 4
55
Passo 5: mover os quantificadores universais para a esquerdax[Tijolo(x) ((Sobre(x, Suporta(x)) Piramide(Suporta
(x)))y[Sobre(x, y) Sobre (y,x)]z[Tijolo(z) Igual (x,z)])]
xyz[Tijolo(x) ((Sobre(x, Suporta(x)) Piramide(Suporta (x)))
Sobre(x, y) Sobre (y,x))Tijolo(z) Igual (x,z)))]
Exercício 4
56
Passo 6: mover as disjunções para os literais (utilizar leis distributivas)x y z[Tijolo(x) ((Sobre(x, Suporta(x))
Piramide(Suporta (x))(Sobre(x, y) Sobre (y,x))(Tijolo(z) Igual (x,z)))]
x y z[(Tijolo(x) Sobre(x, Suporta(x))) Tijolo(x) Piramide(Suporta (x)))(Tijolo(x) Sobre(x, y) Sobre (y,x))(Tijolo(x) Tijolo(z) Igual (x,z))]
Exercício 4
57
Passo 7: eliminar as conjunçõesx y z[(Tijolo(x) Sobre(x, Suporta(x)))
Tijolo(x) Piramide(Suporta (x)))[Tijolo(x) Sobre(x, y) Sobre (y,x)][Tijolo(x) Tijolo(z) Igual (x,z)])]
x [Tijolo(x) Sobre(x, Suporta(x))] x Tijolo(x) Piramide(Suporta (x))]x y [Tijolo(x) Sobre(x, y) Sobre (y,x)]x z [Tijolo(x) Tijolo(z) Igual (x,z)]
Exercício 4
58
Passo 8: renomear as variáveis quantificadas para evitar repetição de um quantificador universal Para que duas não tenham o mesmo
nome x [Tijolo(x) Sobre(x, Suporta(x))] x Tijolo(x) Piramide(Suporta (x))]x y [Tijolo(x) Sobre(x, y) Sobre (y,x)]x z [Tijolo(x) Tijolo(z) Igual (x,z)]
x [Tijolo(x) Sobre(x, Suporta(x))] w Tijolo(w) Piramide(Suporta (w))]u y [Tijolo(u) Sobre(u, y) Sobre (y,u)]v z [Tijolo(v) Tijolo(z) Igual (v,z)]
Exercício 4
59
Passo 9: Eliminar os quantificadores universais
x [Tijolo(x) Sobre(x, Suporta(x))] w Tijolo(w) Piramide(Suporta (w))]u y [Tijolo(u) Sobre(u, y) Sobre (y,u)]vz [Tijolo(z) Tijolo(z) Igual (v,z)]
Tijolo(x) Sobre(x, Suporta(x)) Tijolo(w) Piramide(Suporta (w)) Tijolo(u) Sobre(u, y) Sobre (y,u)Tijolo(z) Tijolo(z) Igual (v,z)
Exercício 4
60
1) Eliminar implicações2) Mover negações para fórmulas atômicas3) Eliminar quantificadores existenciais4) Renomear variáveis quantificadas para
evitar repetição de um quantificador universal
5) Mover quantificadores universais para a esquerda
6) Mover disjunções para os literais7) Eliminar conjunções8) Renomear variáveis quantificadas para
evitar repetição de um quantificador universal
9) Eliminar quantificadores universais
Algoritmo para transformação
61
1) Negar o teorema a ser provado, e adicionar o resultado à lista de axiomas
2) Colocar a lista de axiomas na forma de cláusulas3) Enquanto existirem pares de cláusulas não
resolvidasEncontrar cláusulas resolvíveis e
resolvê-lasAdicionar resultado à lista de cláusulasSe nil for produzido, parar e relatar que
o teorema é verdadeiro
4) Parar e relatar que o teorema é falso
Algoritmo para prova por Refutação
62
Sejam os axiomas representando a figura abaixo Sobre (B, A) Sobre (A, mesa)
Provar que B está acima da mesa Acima (B, mesa)
Exercício 5
BA
63
Criar novas expressões que reflitam as restrições conhecidas x y [Sobre (x,y) Acima (x,y)]x y z [Acima (x,y) Acima (y,z) Acima
(x,z)] Necessário por na forma de cláusulas
as duas expressões universalmente quantificadas
Exercício 5
64
Criar novas expressões que reflitam as restrições conhecidas x y [Sobre (x,y) Acima (x,y)]x y z [Acima (x,y) Acima (y,z) Acima
(x,z)] Necessário por na forma de cláusulas
as duas expressões universalmente quantificadasSobre (u, v) Acima (u,v)
Acima (x,y) Acima (y,z) Acima (x,z)
Exercício 5
65
Cláusulas iniciaisSobre (u,v) Acima (u,v)
(1)Acima (x,y) Acima (y,z) Acima (x,z)
(2)Sobre (B,A)
(3)Sobre (A,mesa) (4)Acima (B,mesa)
(5) Prova
Acima (B,y) Acima (y,mesa) Acima (B,mesa) (2)Acima (B,mesa) (5) Acima (B,y) Acima (y,mesa) (6)
Exercício 5
66
ProvaSobre (y,mesa) Acima (y,mesa) (1)Acima (B,y) Acima (y,mesa) (6)Sobre (y,mesa) Acima (B,y) (7)
Sobre (B,y) Acima (B,y) (1)Sobre (y,mesa) Acima (B,y) (7)Sobre (B,y) Sobre (y,mesa) (8)
Exercício 5
67
Prova Sobre (B,A) (3)Sobre (B,A) Sobre (A,mesa) (8)Sobre (A,mesa) (9)
Sobre (A,mesa) (4)Sobre (A,mesa) (9)
(10)Nil
Exercício 5
69
Dados os axiomas:Pai (João, José) Pai (José, Pedro)
Provar que Avo (João, Pedro) é verdade
Exercício 6
70
Dados os axiomas:Pai (João, José) Pai (José, Pedro)
Provar que Avo (João, Pedro) é verdade
Sugestão: x y z [Pai(x, y) Pai(y, z) Avox, z]
Exercício 6
Exercício 7 Dado que:
Todos os cães uivam à noite Qualquer pessoa que tenha algum gato não
terá ratos Quem tem sono leve, não tem nada que
uiva à noite João tem um cão ou um gato
Provar que Se João tem sono leve, então João não tem
nenhum rato71
Exercício 7 Fórmula Bem Formada (FBF): x [Cao (x) Uiva (x)]
xy [Tem (x,y) Gato (y) z [Tem(x,z) Rato (z)]]
x [DormeCedo (x) y [Tem (x,y) Uiva (y)]]x [Tem(Joao, x) [Gato (x) Cao (x)]]DormeCedo (x) z [Tem (Joao,z) Rato (z)]]
72
73
Planejamento Diagnóstico Monitoramento Prova de teoremas Interpretação de textos
Aplicações
74
Lógica Terminologia Regras de inferência Prova de Teoremas
Manipulação simbólica Colocar expressões na forma de
cláusulas Estratégias para prova por resolução
Conclusão
André de Carvalho - ICMC/USP 75
Perguntas
Recommended