Agentes Baseados na Lógica
Proposicional
Capítulo 7, AIMA 2ed.
Alzennyr Cléa G. Silva
Base de Conhecimento


Base de Conhecimento = conjunto de sentenças
representadas em uma linguagem formal.
Máquina de Inferência
Algoritmos independente do domínio
Base de conhecimento
Conteúdo específico do domínio
Instruções:
 TELL (construção da BC)
 ASK (resposta obtida a partir da BC)
 as vezes também RETRACT (revisão da BC)
MCI - Prof. Jacques Robin
Representação de Conhecimento
usando a Lógica
Definição

Uma sentença lógica não significa nada por si só...

É necessário estabelecer a correspondência entre fatos e
sentenças, fixando seu significado através de uma
interpretação da sentença.

Exemplo:
“O Papa já está no Rio”

mensagem secreta trocada entre dois agentes do FBI que
significa que os documentos sobre as armas atômicas do
Iraque (o Papa) foram entregues ao Pentágono (o Rio) a
salvo (já está).
MCI - Prof. Jacques Robin
Definição



Lógica é uma linguagem formal para representação
de informação
Sintaxe define as sentenças lógicas
Semântica define o significado das sentenças
MCI - Prof. Jacques Robin
Interpretação

Interpretação




uma sentença é verdadeira sob uma dada interpretação se o
“estado do mundo” (state of affairs) que ela representa se verifica.
Valor verdade depende da interpretação da frase e do estado do
mundo real que ela representa (ou modela)
Exemplo

“O papa está no Rio” pode ser verdade na interpretação
anteriormente dada se de fato, no mundo do FBI, tais
documentos foram recebidos pelo Pentágono a salvo.

“O papa está no Rio” , sob a interpretação “Papa = João Paulo
II”, “Rio = Cidade do Rio de Janeiro”, “está = verbo estar”, é falsa
pois ele está em Roma.
Nesta ótica, uma sentença pode ser:

válida, satisfazível ou insatisfazível.
MCI - Prof. Jacques Robin
Validade e Satisfatibilidade

Sentença válida (tautologia)


Sentença insatisfazível


verdade sob todas as possíveis interpretações em todos os
mundos possíveis.
 Ex. “No mundo Wumpus: existe um buraco em (1,2), ou não
existe um buraco em (1,2)” é sempre verdade, independente da
interpretação e do valor-verdade de “existe um buraco em (1,2)”
em qualquer mundo possível.
falsa sob todas as possíveis interpretações em todos os mundos
possíveis.
 Ex: sentenças contraditórias são insatisfazíveis: “existe um
buraco em (1,2), e não existe um buraco em (1,2)”
Sentença satisfazível

verdade para alguma interpretação em algum mundo
MCI - Prof. Jacques Robin
Validade e Satisfatibilidade
Sentenças
Válidas
Sentenças
Satisfazíveis
Sentenças
Insatisfazíveis
MCI - Prof. Jacques Robin
Derivabilidade (entailment)


Derivabilidade significa que uma sentença
segue logicamente de um conjunto de outras
sentenças:
Sentença  é derivável a partir da base de
conhecimento KB (conjunção de sentenças) sss
 é verdadeira em todos os mundos possíveis
onde KB é verdadeira.
MCI - Prof. Jacques Robin
Derivabilidade (entailment)
fatos
segue-se
fatos
Mundo
Representação
sentenças
deriva
sentenças
MCI - Prof. Jacques Robin
Raciocínio: Inferência em Computadores

O único conhecimento que o sistema tem sobre o mundo é aquele
explicitamente codificado na BC:



Então, como responder à pergunta


“Está OK mover o agente para (2,2)?”
Verificando a partir da BC se a sentença abaixo pode ser derivada


não sabem que interpretação foi dada às sentenças na BC, e
não sabem nada sobre o mundo, apenas o que existe na BC.
“(2,2) está OK”.
O processo de inferência deve mostrar que a sentença abaixo é válida


BC  ok(2,2)
“Se a BC é verdade, então (2,2) está OK”
MCI - Prof. Jacques Robin
Regras de Inferência

Modus Ponens:

E-eliminação:
   ,

1   2  ...   n
i/ diz que a
sentença  pode ser
deduzida da BC
constituída pelos i
E-introdução:
i
 1 ,  2 ,...,  n
 1   2  ...   n

Ou-introdução:
i
1 2 ...n

Eliminação de dupla negação:

Resolução unidade:

Resolução:    ,        ,   

 
 

   ,

  
MCI - Prof. Jacques Robin
Propriedades da Inferência

A inferência pode ter várias propriedades...


Corretude (sound)


gera apenas sentenças válidas
Completude


Corretude, completude, composicionalidade, monotonicidade e
localidade.
gera todas as sentenças válidas
Composicionalidade

o significado de uma sentença é uma função do significado de
suas partes.
 B1-2 significa: existe um buraco na caverna (1,2)
 B2-3 significa: existe um buraco na caverna (2,3)
 B1-2  B2-3 significa composicionalmente: existe um buraco
na caverna (1,2) e um outro na caverna (2,3)
 Não composicionalmente, B1-2  B2-3 poderia significar: hoje
é feriado e é o dia do funcionário público
MCI - Prof. Jacques Robin
Lógica: Inferência

Uma Lógica é dita monotônica quando



Tudo que era verdade continua sendo depois de uma inferência
se BC1 |= a então (BC1 U BC2) |= a
todas as sentenças derivadas da BC original são ainda
derivadas da BC composta pelas novas sentenças inferidas



e.g., Lógica Proposicional e de Primeira Ordem.
contra-exemplo: Teoria da Probabilidade
Localidade


regras como Modus Ponens:
 Se  é verdade e    é verdade, então  é verdade
são ditas locais porque sua premissa só necessita ser comparada com
uma pequena porção da BC (2 sentenças).
MCI - Prof. Jacques Robin
Lógica: Inferência


Localidade e composicionalidade são centrais na
construção de sistemas por possibilitar
modularidade.
Modularidade favorece a reusabilidade e a
extensibilidade do sistema.
MCI - Prof. Jacques Robin
Validade de sentenças

A validade pode ser verificada de duas maneiras



Tabelas-Verdade
Regras de inferência
Tabelas-Verdade

ex. Validade de ((P  H)   H)  P ?
(P  H) ((P  H)   H) ((P  H)   H)  P
P
H
F
F
F
F
T
F
T
T
F
T
T
F
T
T
T
T
T
T
F
T
MCI - Prof. Jacques Robin
Validade de sentenças

Regras de inferência:

uma regra de inferência é sound (preserva a verdade) se
a conclusão é verdade em todos os casos onde as
premissas são verdadeiras.
((P  H)   H)  P ?
((P   H)  (H   H))  P
((P   H)  false)  P
(P   H)  P
(P   H)  P
P  H  P
True  H
True
MCI - Prof. Jacques Robin
Complexidade



Checar se um conjunto de sentenças é satisfazível é um problema NPcompleto
 tabela verdade para uma sentença envolvendo n símbolos tem 2n
colunas (exponencial!)
Cláusulas de Horn
 Classe de sentenças úteis que permitem inferência em tempo
polinomial
 P1  P2  P3  ...  Pn  Q
 ou,  P1   P2   P3  ...   Pn  Q
 é usada em Prolog
2 casos especiais das cláusulas de Horn
 Fatos, quando n = 1 e P1 = true
 true  Q, ou simplesmente Q
 Restrições de integridades, quando Q = false
 P1  P2  P3  ...  Pn  F
 ou,  P1   P2   P3  ...   Pn
 não são permitidas em Prolog
MCI - Prof. Jacques Robin
Formalização de Agentes Baseados
na Lógica Proposicional
BC para o Mundo do Wumpus

A Base de Conhecimento consiste em:




sentenças representando as percepções do agente
sentenças válidas derivadas a partir das sentenças das percepções
regras utilizadas para derivar novas sentenças a partir das sentenças
existentes
Símbolos:
 Ax-y-t significa que “o agente está na caverna (x,y), no instante t”






Bx-y significa que “existe um buraco na caverna (x,y)”
Wx-y significa que “o Wumpus está na caverna (x,y)”
Ox-y significa que “o ouro está na caverna (x,y)”
bx-y significa que “existe brisa na caverna (x,y)”
fx-y significa que “existe fedor na caverna (x,y)”
lx-y significa que “existe luz na caverna (x,y)”
MCI - Prof. Jacques Robin
BC para o Mundo do Wumpus

Com base nas percepções do estado abaixo, a
BC deverá conter as seguintes sentenças:
 f1-1
 f2-1
f1-2
 b1-1
b2-1
 b1-2
4
3
2
1
W!
f
ok
A
V
ok
1
ok
b V
ok
2
B!
3
4
MCI - Prof. Jacques Robin
BC para o Mundo do Wumpus

O agente também tem algum conhecimento prévio
sobre o ambiente, e.g.:


se uma caverna não tem fedor, então o Wumpus não
está nessa caverna, nem está em nenhuma caverna
adjacente.
O agente terá uma regra para cada caverna no seu
ambiente
R1:  f1-1   W1-1   W1-2   W2-1
R2:  f2-1   W1-1   W2-1   W2-2   W3-1
R3:  f1-2   W1-1   W1-2   W2-2   W1-3

O agente também deve saber que, se existe fedor em
(1,2), então deve haver um Wumpus em (1,2) ou em
alguma caverna adjacente:
R4: f1-2  W1-3  W1-2  W2-2  W1-1
MCI - Prof. Jacques Robin
Modelos



Modelos: mundos estruturados formalmente nos quais
sentenças podem ser avaliadas
m é modelo de uma sentença  se  é verdadeira em m.
M(): conjunto de todos os modelos de .
M()
Então KB  
sse
M(KB)  M()
MCI - Prof. Jacques Robin
Modelos – Mundo Wumpus

Ex: o Mundo de Wumpus é um modelo da sentença
“B1-2” sob a interpretação de que existe um buraco
na caverna (1,2).

Podem existir muitos modelos para “B1-2”, basta
que eles tenham um buraco em (1,2).
MCI - Prof. Jacques Robin
Checagem de Modelo – Mundo Wumpus
MCI - Prof. Jacques Robin
Checagem de Modelo – Mundo Wumpus
KB = regras do mundo wumpus + observações
MCI - Prof. Jacques Robin
Checagem de Modelo – Mundo Wumpus
KB = regras do mundo wumpus + observações
 1 = “[1,2] é seguro”, KB   1 , provado pela checagem do modelo
MCI - Prof. Jacques Robin
Checagem de Modelo – Mundo Wumpus
KB = regras do mundo wumpus + observações
MCI - Prof. Jacques Robin
Checagem de Modelo – Mundo Wumpus
KB = regras do mundo wumpus + observações
 2 = “[2,2] é seguro”, KB   2
MCI - Prof. Jacques Robin
Encadeamento Para Frente e Para Trás

Forma Horn


KB = conjunção de cláusulas Horn
Cláusula horn =


Símbolo; ou
Conjunção de símbolos  símbolo
e.g.
MCI - Prof. Jacques Robin
Encadeamento Para Frente

Idéia: descarte qualquer regra cujas premissas são satisfeitas
na KB, adicione sua conclusão à KB, até que a regra procurada
seja encontrada.
MCI - Prof. Jacques Robin
Encadeamento Para Frente (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Frente (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Frente (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Frente (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Frente (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Frente (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Frente (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás

Idéia: para provar Q por BC,
cheque se Q já é conhecido, ou
prove por BC todas as premissas de alguma
regra concluindo Q.
Cuidados:



Evite loops: cheque se novo sub-objetivo já está na pilha de
objetivos
Evite trabalho repetido: cheque se novo sub-objetivo
1.
Já foi provada como true, ou
2.
Já falhou.
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento Para Trás (exemplo)
MCI - Prof. Jacques Robin
Encadeamento para Frente x Encadeamento
para Trás
• EF é dirigida pelos dados, fc. Automático, processamento não
consciente. Pode fazer muito trabalho irrelevante para o objetivo
procurado
• ET é dirigido pelo objetivo, apropriado para resolução de
problemas.
e.g. “Onde estão minhas chaves?”
Envolve backtracking, pode ser caro, mais muitas vezes bem de
complexidade sub-linear no tamanho da BC
• EF pode ser usado para pré-calcular cache de objetivos
freqüentes
Adequação depende:
• da naturalidade de formalizar o problema a partir de dados ou do objetivo
• da necessidade de encontrar apenas uma ou todas as soluções
MCI - Prof. Jacques Robin
Considerações Finais





Agentes Lógicos aplicam regras de inferência na BC para
derivar novas sentenças;
Encadeamento PF e PT são lineares para cláusulas Horn;
Lógica Proposicional:
 Não é capaz de atender a questões como: “qual ação
devo tomar?”
 Pode apenas responder questões como: “devo ir em
frente?”, “devo virar para esquerda?”, etc.
Lógica proposicional não possui mecanismos para generalizar
proposições;
Proposições são dependentes do tempo e o tamanho das
proposições pode assumir grandes dimensões.
MCI - Prof. Jacques Robin