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