Abdução, Raciocínio por default e
Revisão de crenças
Daniel Moreira
João dos Prazeres
Priscila Saboia
Ontologies
Reasoning
Components
Agents
Simulations
Esquema
 Motivação
 Introdução
 Lembrete de abdução
 Introduzindo raciocínio por default
 Lembrete de revisão de crenças
 Raciocínio por default
 Abordagens
 NAF
 NAF
 Abdução
 Lógica-defaut
 NAF como raciocínio por default
 GLPs
 Sintaxe
 GLPs estratificados
 Semânticas declarativas




Completação de Clark
Semântica de conjuntos de resposta (SCR)
Semântica bem-fundamentada (SBF)
SCR X SBF
 Semânticas operacionais
 Resolução SLDNF
 Resolução SLG
 Abdução
 Aplicações práticas na IA
 Viés
 Positive Abductive Logic Programming (PALP)




Sintaxe
Semântica declarativa
Semântica operacional: SLDA
Tranformar GLPs em PALPs
 General Abductive Logic Programming (GALP)
 Semântica operacional: SLDNFA
 Raciocínio por default como abdução
 Abdução em CHRv
 Exemplo
 Revisão de Crença e Manutenção de Verdade






Sistemas de manutenção de verdade;
JTMS
JTMS e abdução
ATMS
ATMS e abdução
JTMS X ATMS
 Conclusão
Motivação
 O que fazer, dentro do contexto da IA - Simbólica, quando um agente não
possui conhecimento suficiente para deduzir informações necessárias à escolha
da sua próxima ação?
(CR1) primos(F1, F2)  irmaos(P1, P2)  pai(P1, F1)  pai(P2, F2)
(CF1) pai(joaquim, jose)
(CF2) pai(manoel, joao)
(CF3) primos(jose, joao)
(P1)  irmaos(joaquim, manoel)
???
 Raciocínio hipotético com informação parcial em ambientes parcialmente
observáveis.
Introdução: lembrete de abdução
Conhecimento
Prévio Causal
em Intenção
e(X)  co(X)  ch(X)
Conhecimento
Prévio em Extensão:
• Efeitos Observados
e(a), e(b), ...
• Causais Observadas
Incompletas
co(a), co(b), ...
Abdução
CPCI  CPEC  NCEC |= CPEE
Viés sobre Hipóteses:
ch(X)
Novo Conhecimento
em Extensão:
Causas Hipotéticas
ch(a), ch(b) ...
Introdução: lembrete de abdução (2)
 A partir de:
 Conhecimento prévio causal em intenção:
 loc(P, X, Y, T+1)  loc(P, X, Y, T)  move(P, X+1, Y, T)  mureta(X+1, Y)
Conhecimento prévio em extensão incompleto de causas:
 loc(player_1, 4, 1, 1)  move(player_1, 5, 1, 1)
 Conhecimento prévio em extensão de efeitos observados:
 loc(player_1, 4, 1, 2)
 Abduzir:
 Novo conhecimento em extensão de causa hipotética:
 mureta(5, 1)
Introduzindo raciocínio por default
 Uso de regras-default aplicadas se não geram contradições com a aplicação de
regras dedutivas.
(RD1)
(CR1)
(CR2)
(CF1)
(CF2)
voa(X)  ave(X)
ave(X) 
pinguim(X)
¬voa(X)  pinguim(X)
ave(picolino)
pinguim(picolino)
// regra default
// regra dedutiva
// regra dedutiva
// nova percepção
Conclusão por default
voa(picolino)
Nova conclusão
¬voa(picolino)
 Característica não-monotônica
Adição de nova informação pode impossibilitar a derivação de fatos antes deriváveis.
Introdução: lembrete de revisão de crença
 Tarefa de raciocínio necessária quando:
Recepção (sensorial ou comunicativa) de novos fatos confirmados contradiz
conclusão por default ou hipóteses abduzidas anteriormente.
 Tal contradição pode ser observada diretamente, ou indiretamente via dedução.
(RD1) ave(X)  bota_ovo(X) 
tem_bico(X)
(CR1) mamifero(X)  monotrema(X)
*(RI1) false  ave(X)  mamifero(X)
(CF1) bota_ovo(ornitorrinco)
(CF2) tem_bico(ornitorrinco)
(HD1) ave(ornitorrinco)
(CF4) mamifero(ornitorrinco)
(CF3) monotrema(ornitorrinco)
Conclusão por default
(HD1) ave(ornitorrinco)
tell(ave(ornitorrinco))
Recepção comunicativa
(CF3) monotrema(ornitorrinco)
tell(monotrema(ornitorrinco))
Dedução
(CF4) mamifero(ornitorrinco)
tell(mamifero(ornitorrinco))
Revisão de crença
retract(ave(ornitorrinco)).
* Cláusulas com a cabeça falsa são ditas restrições, sendo peculiares ao formalismo lógico PALP. Estas
serão melhor abordadas posteriormente.
Raciocínio por default: abordagens
 NAF (negation as failure – negação por falha): novo conectivo naf;
 Abdução: tarefa de raciocínio;
 Lógica-default: nova regra de inferência;
Ver AIMA, capítulo 10, seção 7, para maiores detalhes.
 Herança não-monotônica:
Elephant
+cor: branco
RoyalElephant
Clyde:RoyalElephant
Raciocínio por default: abordagens
 NAF (negation as failure – negação por falha): novo conectivo naf;
 Abdução: tarefa de raciocínio;
 Lógica-default: nova regra de inferência;
Ver AIMA, capítulo 10, seção 7, para maiores detalhes.
 Herança não-monotônica:
Elephant
+cor: branco
RoyalElephant
+cor: branco
Clyde:RoyalElephant
Raciocínio por default: abordagens
 NAF (negation as failure – negação por falha): novo conectivo naf;
 Abdução: tarefa de raciocínio;
 Lógica-default: nova regra de inferência;
Ver AIMA, capítulo 10, seção 7, para maiores detalhes.
 Herança não-monotônica:
Elephant
+cor: branco
RoyalElephant
+cor: branco
Clyde:RoyalElephant
+cor: branco
Raciocínio por default: abordagens
 NAF (negation as failure – negação por falha): novo conectivo naf;
 Abdução: tarefa de raciocínio;
 Lógica-default: nova regra de inferência;
Ver AIMA, capítulo 10, seção 7, para maiores detalhes.
 Herança não-monotônica:
Elephant
+cor: branco
Nova
Percepção
RoyalElephant
+cor: cinza
Clyde:RoyalElephant
+cor: branco
Raciocínio por default: abordagens
 NAF (negation as failure – negação por falha): novo conectivo naf;
 Abdução: tarefa de raciocínio;
 Lógica-default: nova regra de inferência;
Ver AIMA, capítulo 10, seção 7, para maiores detalhes.
 Herança não-monotônica:
Elephant
+cor: branco
RoyalElephant
+cor: cinza
Clyde:RoyalElephant
+cor: cinza
NAF – Negação por falha
 Conectivo unário (naf) antes de um termo A;
 Ao encontrar premissa da forma naf A...
A máquina de inferência tenta deduzir A.
 Se consegue em tempo finito, deriva que naf A é falso;
 Se não consegue em tempo finito, deriva que naf A é verdadeiro.
 Semanticamente, naf é distinto da negação clássica , da lógica:
 A é verdadeiro sse BC |= A;
 naf(A) é verdadeiro sse BC| A;
onde BC é a base de conhecimento.
Exemplo de NAF
 Negação por falha funciona com hipótese do mundo fechado
(CR1)
(CR2)
(CF1)
(CF2)
ave(X)  tem_bico(X)  bota_ovo(X)  tem_pena(X)
mamifero(X)  naf(ave(X))
tem_bico(ornitorrinco)
bota_ovo(ornitorrinco)
(P1)  mamifero(ornitorrinco)
Exemplo de NAF
 Negação por falha funciona com hipótese do mundo fechado
(CR1)
(CR2)
(CF1)
(CF2)
ave(X)  tem_bico(X)  bota_ovo(X)  tem_pena(X)
mamifero(X)  naf(ave(X))
tem_bico(ornitorrinco)
bota_ovo(ornitorrinco)
(P1)  mamifero(ornitorrinco)
MI-NAF*: Verdadeiro.
* MI-NAF: máquina de inferência que implementa a negação por falha.
NAF como raciocínio por default
(CR1) voa(X)  ave(X)  naf(pinguim(X))
(CR2) ave(X) 
pinguim(X)
(CF1) ave(picolino)
(P1)  voa(picolino)
NAF como raciocínio por default
(CR1)
(CR2)
(CF1)
(CF3)
voa(X)  ave(X)  naf(pinguim(X))
ave(X) 
pinguim(X)
ave(picolino)
pinguim(picolino)
// nova percepção
(P1)  voa(picolino)
(P1)  voa(picolino)
MI-NAF*: Verdadeiro
* MI-NAF: máquina de inferência que implementa a negação por falha.
NAF como raciocínio por default
(CR1)
(CR2)
(CF1)
(CF3)
voa(X)  ave(X)  naf(pinguim(X))
ave(X) 
pinguim(X)
ave(picolino)
pinguim(picolino)
// nova percepção
(P1)  voa(picolino)
(P1)  voa(picolino)
MI-NAF*: Verdadeiro
MI-NAF*: Falso
 Característica não-monotônica
Adição de nova informação impossibilitou derivação de fatos antes deriváveis.
* MI-NAF: máquina de inferência que implementa a negação por falha.
GLPs: sintaxe abstrata
General Logic Program
GLP
Functor = 
*
Premisse
GLPClause
GLPPremisse
*
Functor = 
Literal
Conclusion
NegativeLiteral
Fact
Functor = naf
Arg
StratifiedGLP
CFOLAtomicFormula
*
CFOLTerm
1..*
Functor = 
Functor
GLPs sem ciclos de dependência entre predicados através de naf
PredicateSymbol
CFOLNonFunctionalTerm
context Fact inv Fact: Premisse -> size() = 1 and
Premisse.Literal.CFOLTerm = true
Functor
CFOLVariable
context GLPClause inv DC: Conclusion.CFOLAtomicFormula.CFOLTerm  false
CFOLFunctionalTerm
ConstantSymbol
FunctionSymbol
Exemplo de GLP
(CR1) ave(X)  homeotermico(X)  naf mamifero(X)
(CR2) mamifero(X)  homeotermico(X)  naf ave(X)
(CR3) mama(X)  mamifero(X)
(CR4) bota_ovo(X)  ave(X)
(CF1) mama(ornitorrinco)
(CF2) bota_ovo(ornitorrinco)
GLPs estratificados
 GLPs sem ciclos de dependência entre predicados através de naf
femea(X)
 GLP estratificado:
femea(X)  mulher(X)
mulher(X)  humano(X)  naf(homem(X))
humano(X)  homem(x)
mulher(X)
humano(X)
homem(X)
 GLP não-estratificado:
femea(X)
femea(X)  mulher(X)
mulher(X)  humano(X)  naf(homem(X))
humano(X)  homem(X)
homem(X)  naf(mulher(X))
mulher(X)
humano(X)
naf
naf
homem(X)
naf
Semânticas declarativas de GLPs
 Completação de Clark;
 Semântica de conjuntos de resposta;
 Semântica bem-fundamentada
Completação de Clark para GLPs
 Mesmo algoritmo para DLPs, estendido para substituir nafs por negações
clássicas ¬
femea(X)  mulher(X)
mulher(X)  humano(X)  naf(homem(X))
humano(X)  homem(x)
X1(femea(X1)  X (X1 = X  mulher(X)))
X1(mulher(X1)  X (X1 = X  humano(X)  ¬homem(X)))
X1(humano(X1)  X (X1 = X  homem(X)))
X1(¬ homem(X1))
Completação de Clark para GLPs (2)
 Limitação
ligado(X)  aperta_botao(X)  naf(ligado(X))
X1(ligado(X1)  X(X1 = X  aperta_botao(X)  ¬ligado(X)))
Simplificado ligado(X) por p, X1 = X por a e aperta_botao(X) por b...
p  a  b  ¬p
Supondo p = a = b = Verdadeiro
Verdadeiro  Falso
 Solução: escrever GLPs estratificados.
Inconsistente!
Semântica de conjunto de respostas
 Modelos estáveis
Justificativa de um elemento E de um modelo Mh de Herbrand: elementos de Mh
formando o corpo de uma regra que conclui E;
 Modelo estável: modelo mínimo de Herbrand cujos elementos são todos justificados;
 Um programa lógico é consistente se possui um modelo estável.
anc(X, Y)  pai(X, Y)
anc(X, Z)  anc(X, Y)  pai(Y, Z)
pai(joaquim, jose)
pai(manoel, joaquim)
MHM =
{pai(manoel, joaquim), anc(manoel, joaquim), pai(joaquim, jose), anc(joaquim, jose),
anc(manoel, jose)}
Semântica de conjuntos de resposta (2)
 Certos GLPs apresentam mais de um modelo mínimo de Herbrand, que não são
estáveis.
ave(X)  homeotermico(X)  naf(mamifero(X)).
mamifero(X)  homeotermico(X)  naf(ave(X)).
mama(X)  mamifero(X).
homeotermico(ornitorrinco).
MHM1 = {homeotermico(ornitorrinco), ave(ornitorrinco)}
Semântica de conjuntos de resposta (2)
 Certos GLPs apresentam mais de um modelo mínimo de Herbrand, que não são
estáveis.
ave(X)  homeotermico(X)  naf(mamifero(X)).
mamifero(X)  homeotermico(X)  naf(ave(X)).
mama(X)  mamifero(X).
homeotermico(ornitorrinco).
MHM1 = {homeotermico(ornitorrinco), ave(ornitorrinco)}
MHM2 = {homeotermico(ornitorrinco), mamifero(ornitorrinco), mama(ornitorrinco)}
Semântica de conjuntos de resposta (2)
 Certos GLPs apresentam mais de um modelo mínimo de Herbrand, que não são
estáveis.
ave(X)  homeotermico(X)  naf(mamifero(X)).
mamifero(X)  homeotermico(X)  naf(ave(X)).
mama(X)  mamifero(X).
homeotermico(ornitorrinco).
MHM1 = {homeotermico(ornitorrinco), ave(ornitorrinco)}
MHM2 = {homeotermico(ornitorrinco), mamifero(ornitorrinco), mama(ornitorrinco)}
Semântica de conjuntos de resposta (3)
 Modelos estáveis em GLPs:
 Para obtê-los, reduz-se o programa P:
 1. Elimina-se todas as regras que possuam um literal naf(A), estando A em um dos modelos mínimos;
 2. Elimina-se todos os literais negativos das regras restantes.
P={
ave(X)  homeotermico(X)  naf(mamifero(X))
mamifero(X)  homeotermico(X)  naf(ave(X))
mama(X)  mamifero(X)
homeotermico(ornitorrinco)
}
MHM1 = {homeotermico(X), ave(ornitorrinco)}
R1(P, A = ave(X)) =
{
ave(X)  homeotermico(X)
mama(X)  mamifero(X)
homeotermico(ornitorrinco)
MHM(R1) = {homeotermico(ornitorrinco), ave(ornitorrinco)}
}
Semântica de conjuntos de resposta (3)
P={
ave(X)  homeotermico(X)  naf(mamifero(X))
mamifero(X)  homeotermico(X)  naf(ave(X))
mama(X)  mamifero(X)
homeotermico(ornitorrinco) }
MHM2 = {homeotermico(X), mamifero(ornitorrinco), mama(ornitorrinco)}
R2(P, A = mamifero(X)) =
{
mamifero(X)  homeotermico(X)
mama(X)  mamifero(X)
homeotermico(ornitorrinco)
MHM(R2) = {homeotermico(ornitorrinco), mamifero(ornitorrinco),
mama(ornitorrinco)}
}
Conjuntos de resposta e abdução
 Semanticamente, P significa um conjunto de respostas, dadas para cada possível
redução de P.
R1(P, ave(X)):
{homeotermico(ornitorrinco), ave(ornitorrinco)} | ave(ornitorrinco)
(supondo ave(ornitorrinco) = Verdadeiro)
+
R2(P, mamifero(X)):
{mamifero(ornitorrinco), homeotermico(ornitorrinco), mama(ornitorrinco)} |
mamifero(ornitorrinco)
(supondo mamifero(ornitorrinco) = Verdadeiro)
Conjuntos de resposta e abdução
 Semanticamente, P significa um conjunto de respostas, dadas para cada possível
redução de P.
R1(P, ave(X)):
{homeotermico(ornitorrinco), ave(ornitorrinco)} | ave(ornitorrinco)
(supondo ave(ornitorrinco) = Verdadeiro)
+
R2(P, mamifero(X)):
{mamifero(ornitorrinco), homeotermico(ornitorrinco), mama(ornitorrinco)} |
mamifero(ornitorrinco)
(supondo mamifero(ornitorrinco) = Verdadeiro)
Semântica bem-fundamentada
 Adota a lógica ternária.
 Lógica ternária:
Valores-verdade:
 Falso = 0;
 Indefinido = ½;
 Verdadeiro = 1.
(Re)Definições das fórmulas lógicas:
¬F = 1 – F
F  G = min(F, G)
F  G = max(F, G)
F  G = se F < G então 0 senão 1
F  G = se F = G então 1 senão 0
Semântica bem-fundamentada (2)
 Lógica ternária (continuação)
P Q P
Q
PQ
PQ
PQ
PQ
T
F
F
T
T
T
T
T F
F
T
F
T
F
F
U
F
U
U
T
F
U
T
T
F
F
T
T
T
F
T
T
F
F
T
T
U
T
U
F
U
T
T
T
U
F
U
T
T
T
U F
U
T
F
U
F
U
U
U
U
U
U
T
U
Tabela-verdade:
F
Semântica bem-fundamentada (3)
 Estende a idéia de modelos estáveis;
 Permite o valor INDEFINIDO U para termos ground que não são absolutamente
Falsos nem Verdadeiros.
ave(X)  homeotermico(X)  naf(mamifero(X))
mamifero(X)  homeotermico(X)  naf(ave(X))
mama(X)  mamifero(X)
homeotermico(ornitorrinco)
ME = {homeotermico(ornitorrinco) = T, mamifero(ornitorrinco) = U,
ave(ornitorrinco) = U, mama(ornitorrinco) = U, todos os demais termos falsos}
 Semântica operacional baseada em SBF: responde a perguntas gerais com
Verdadeiro (T), Falso (F) ou Indefinido (U).
Semântica de conjuntos de resposta X
Semântica bem-fundamentada
Semântica de conjuntos de resposta
 Booleana;
 Vários modelos;
 Crédula:
Semântica bem-fundamentada
 Ternária
 Modelo único;
 Cética:
 Define a semântica em termos de
suposições sobre fatos não
fundamentados (abdução).
 Assume que fatos não
fundamentados são indefinidos.
SCR:
a  b  naf c
c  d  naf a
b
d
{a, b, d} | a
a
b, d c
{c, b, d} | c
SBF:
{b, d} verdadeiros
{a, c} indefinidos
GLPs: semânticas operacionais
 Resolução SLDNF (implementa a semântica declarativa da
completação de Clark);
 Resolução SLG (implementa a semântica declarativa bemfundamentada).
Resolução SLDNF
 Combinação de resolução SLD para resolver literais positivos, e negação por
falha finita para resolver literais negativos.
 Resolução SLD para resolver literais positivos...
Encadeamento para trás, com regra específica de seleção de termos nas premissas
das cláusulas a serem resolvidas, em tempo linear.
+
 Negação por falha finita para resolver literais negativos...
 naf A é VERDADEIRO sse  A tem uma árvore SLD com falha finita;
 naf A é FALSO sse  A tem uma refutação SLD com substituição-resposta
computada vazia (i. e. sem substituir todos os argumentos do literal por
constantes).
Exemplo de resolução SLDNF
alicerce(X)  sobre(Y, X)  no_chao(X)
no_chao(X)  naf(fora_do_chao(X))
fora_do_chao(X)  sobre(X, Y)
acima(X, Y)  sobre(X, Y)
acima(X, Y)  sobre(X, Z)  acima(Z, Y)
sobre(c, b)
sobre(b, a)
 Pergunta:  alicerce(X)
C
B
A
Exemplo de resolução SLDNF (2)
 fora_do_chao(b)
 alicerce(X)
 sobre(b, Y0)
 sobre(Y0, X), no_chao(X)
 no_chao(b)
 naf(fora_do_chao(b))
FF
 no_chao(a)
 naf(fora_do_chao(a))
 fora_do_chao(a)
 sobre(a, Y0)
FF
Limitações da resolução SLDNF
 Pergunta:  naf(sobre(X, Y))
 “Quais são os blocos X e Y em que X não está sobre Y?”
 sobre(X, Y)
 naf(sobre(X, Y))
 sobre(c, b)
???
 sobre(b, a)
X=b, Y=a*
X=c, Y=b*
* Não são uma substituição-resposta computada vazia...
 Resposta: Nenhuma (stuck)...
 Esta situação chama-se floundering.
C
B
A
Limitações da resolução SLDNF (2)
 Mais exemplos:
termina(X)  naf(em_loop(X))
em_loop(X)  em_loop(X)
 termina(X)
 em_loop(X)
 naf(em_loop(X))
 em_loop(X)

mulher(X)  naf(homem(X))
homem(X)  naf(mulher(X))
 mulher(X)
 homem(X)
 naf(homem(X))
 naf(mulher(X))
Resolução SLG:
programação em lógica tabelada
 Pilha de objetivos substituída por tabela de objetivos e respostas;
 Para cada objetivo, tabela guarda:
 Ponteiro para objetivo que o chamou;
 Ponteiro para alguma variação sua:
 Renomeação de variáveis, por exemplo p(f(X),Y)  p(f(A),B);
 Cláusula instanciada cuja conclusão unifica com o referido objetivo;
 Posição da clásusula no programa;
 Todas as suas respostas.
gid
goal
1a
anc(A,dan)
2a
parent(A,dan)
vg
cg
1a
instantiated rule
rn
anc(A,dan) :- parent(A,dan)
C1
parent(fay,dan)
C3
answers
A = fay
Resolução SLG:
programação em lógica tabelada (2)
 Para provar objetivo G:




Procura por variação G’ na tabela;
Se há alguma, utiliza resposta de G´ como resposta de G
Senão, encadeia para trás G, de modo a obter a primeira resposta para G;
Depois de encontrar tal resposta (ou falhar) :
 Armazena-a na tabela;
 Faz backtrack para encontrar outras respostas e também armazená-las;
 Continua a prova com a próxima premissa para o objetivo de chamada.
gid
goal
1a
anc(A,dan)
2a
parent(A,dan)
vg
cg
1a
instantiated rule
rn
anc(A,dan) :- parent(A,dan)
C1
parent(fay,dan)
C3
answers
A = fay
Abdução
 Programa
 loc(P, X, Y, T+1)  loc(P, X, Y, T)  move(P, X+1, Y, T)  mureta(X+1, Y)
 loc(player_1, 4, 1, 1)  move(player_1, 5, 1, 1)
Observação
 loc(player_1, 4, 1, 2)
IC
 false  loc(P,X,Y,T)  mureta(X, Y)
Explicação
 mureta(5, 1)
Aplicações práticas da abdução em IA
 Diagnóstico de Falha (Diagnóstico médico):
 P : descreve o comportamento “normal” do sistema;
 O : comportamento que está anormal;
 E : componente anormal que explica esse comportamento anormal do sistema.
 Visão de Alto Nível:
 O : descrições parciais dos objetos;
 E : são os objetos a serem reconhecidos.
 Raciocínio Default:
 O : conclusões;
 E : suposições acreditadas por default .
 Planejamento:
 O : estado a ser alcançado;
 E : planos .
Viés sobre hipóteses abdutivas: objetivos
 E – um conjunto de átomos que explicam O;
 Viés restringe explicações:
Encontrar explicações que atendam a restrições de integridade;
Encontrar causas mais profundas (básicas), no lugar de causas
intermediárias, efeitos dessas causas profundas;
Encontrar um número mínimo de causas que expliquem o máximo de
observações;
Considerar apenas instâncias de um conjunto pré-definido de predicados
chamado de abduzíveis.
 Geralmente escolhidos dentro dos predicados sem definição intencional na base de
conhecimento
 Podem ser priorizados em níveis de preferências
Viés sobre hipóteses abdutivas:
causas básicas e mínimas

Exemplo:
grama-molhada  choveu-ontem-noite
grama-molhada  regador-ligado
sapatos-molhados  grama-molhada
 Para a observação sapatos-molhados :
 Causas básicas
{grama-molhada} não é básica
{choveu-ontem-noite} e {regador-ligado} são básicas.
 Causas mínimas
{choveu-ontem-noite, regador-ligado} não é mínima.
{choveu-ontem-noite} e {regador-ligado} são mínimas.
Viés sobre hipóteses abdutivas:
restrições de integridade
 Excluir hipóteses que:
 Violam diretamente um conjunto pré-definido de restrições de integridades
 Cuja inclusão na base de conhecimento permite deduzir fatos que violam uma dessas
restrições
 Exemplo:
At(Wumpus(x))  At(Wumpus(y))  x = y
sprinkler  choveu  false
Viés sobre hipóteses abdutivas: minimização
 Excluir conjunto de hipóteses que podem ser explicadas em termos de (i.e.,
deduzidas a partir de) outras hipóteses igualmente válidas
 Exemplo: grassIsWet, quando sabemos sprinkler-was-on
 Preferir conjunto de hipóteses com maior número de efeitos observados
(corroboração)
 Exemplo: formigasDeAsas corrobora chuva e não sprinkler
 Preferir conjunto de hipóteses mais geral
 Preferir conjunto de hipóteses mais conciso: quanto menos pre-requisitos, mais
plausível é que as hipóteses sejam verdade.
PALP – Positive Abductive Logic Program
 Uma teoria Abductive Logic Program é uma tripla (P, A, I), onde:
P é o programa
A são os predicados abduzíveis
I são as restrições de integridade
 Se tivermos um goal G e  (um subconjunto de A que possui explicações para G):
P U  |= G
P U  |= I
P U  é consistente
PALPs: sintaxe abstrata
Premisse
Positive Abductive Logic Program
PALPPremisse
Functor = 
PALP
Functor = 
*
PALPClause
*
Conclusion
CFOLAtomicFormula
*
Functor
IntegrityConstraint
Fact
CFOLTerm
Arg
1..*
PredicateSymbol
Abducible
CFOLNonFunctionalTerm
CFOLFunctionalTerm
context PALPClause inv Abducibles: not Conclusion.isKindOf(Abducible)
Functor
context Fact inv Fact: Premisse -> size() = 1 and
Premisse.CFOLAtomicFormula.CFOLTerm = true
context IntegrityConstraint inv IC: Conclusion.CFOLAtomicFormula.CFOLTerm = false
CFOLVariable
ConstantSymbol
FunctionSymbol
Semântica declarativa de PALP
 Modelo Estável Generalizado:
Programa abdutivo (P,A,I), onde  um subconjunto de A
M() é um modelo estável generalizado de (P,A,I), sse:
 M() é um modelo estável de P  , e
 M() ╞ I
  é uma explicaçaõ abdutiva de uma observação Q sse:
 M() é um modelo estável generalizado de (P,A,I), e
M() ╞ Q
 Exemplo 1:
Seja P: p  a
qb
Seja A = {a, b}
Seja I = p  q
Seja Q = p
Então M(1)={a, p} e M(2)={a,b,p,q} são Modelos Estáveis Generalizados de (P,A,I).
Portanto 1 = {a} e 2 = {a,b} são hipóteses abdutivas de p.
Semântica declarativa de PALP (2)
 Exemplo 2: O = faulty(a) . A = broken, fuse, melted_fuse
(1.1)
(1.2)
(1.3)
(1.4)
(1.5)
(1.6)
faulty(L)  lamp(L), broken(L).
faulty(L)  lamp(L), current_break(L).
current_break(L)  fuse(L, F), melted_fuse(F).
current_break(L)  general_power_failure.
lamp(a).
lamp(b).
 Temos:
 M(1) = {broken(a), lamp(a), faulty(a)} para 1 = {broken(a)}
 M(2) = {fuse(a, ), melted_fuse(), current_break(a), lamp(a), faulty(a)} para
2 = {fuse(a, ), melted_fuse()}
 M(3) = {current_break(a), lamp(a), general_power_failure} não é um modelo
estável generalizado para 3 = {general_power_failure}
SLDA – Semântica operacional de PALP
 SLDA é uma extensão de SLD para abdução, onde um conjunto de fórmulas atômicas  é
suposto verdadeiro para conseguir O dado P:
 P + E |- O
 SLDA constrói uma refutação: <G0, 0>, ..., <Gi, i>, ..., <Gn, n>
 Onde passos ou de resolução ou de abdução são utilizados para gerar cada conjunto.
 Para o exemplo, A = {broken, fuse, melted_fuse, general_power_failure}
(1.1)
(1.2)
(1.3)
(1.4)
(1.5)
(1.6)
faulty(L)  lamp(L), broken(L).
faulty(L)  lamp(L), current_break(L).
current_break(L)  fuse(L, F), melted_fuse(F).
current_break(L)  general_power_failure.
lamp(a).
lamp(b).
SLDA – Semântica operacional de PALP
Faulty(a)
(1.1)
(1.2)
Lamp(a), broken(a)
Lamp(a), current_break(a)
(1.5)
(1.5)
broken(a)
(i)
current_break(a)
(1.3)
 = {broken(a)}
fuse(a, F), melted_fuse(F)
(ii)
 = {fuse(a, }
melted_fuse(F)
(1.4)
general_power_failure
(iv)
 = {general_power_failure}
Transformar GLPs em PALPs
Transformar GLP P em PALP <P*, A*, I*>:
 p P, definir novo predicado p* dual negado de p
 A* = {p* | pP}
 P* = P com todos os literais naf p substituidos por p*
 I* = {(p  p*) | pP, p* A*}  {p  p* | pP, p* A*}
 I não é uma restrição de integridade de Horn. É uma fórmula clássica da lógica
de primeira ordem
GALP – General Abductive Logic Program
 Conjunto de abduzíveis pode conter predicados negados por falha
 Interpretação abdutiva de NAF:
 Literais negados com naf são hipóteses abdutivas negativas
 Válidas se satisfazem um conjunto de restrições de integridades
 Melhor compreendido através da semântica operacional: SLDNFA
SLDNFA – Semântica operacional de GALP
 SLDNFA é similar a SLDA, derivando nos passos de refutação:
 Se um goal é positivo, ele funciona como SLDA
 Se um goal é negativo, ele apenas adota o passo de resolução e não o passo de
abdução.
 A árvore de falha (que é do SLD) de um literal negativo deve ser reconsiderada
toda vez que um passo de abdução adiciona um predicado abduzível a 
Raciocínio por default como abdução
 Tanto regras default quando predicados abduzíveis são maneiras de completar
uma base de conhecimento certo parcial com conhecimento incerto
 Podemos chegar a mesma conclusão com uma máquina de inferência abdutiva,
inserindo um novo predicado que representa a regra default.
 O novo predicado é abduzível
 E uma nova regra é inserida na base, de onde podemos concluir por abdução
(A1)
(C1)
(C2)
(C3)
(C4)
(C5)
(C6)
abducible(ave-voa)
voa(X)  ave(X)
ave(X)  pinguim(X)
¬voa(X)  pinguim(X)
ave(picolino)
ave-voa(x)
voa(x)  ave(X)  ave-voa(x)
Chegamos a mesma conclusão por abdução
voa(picolino)
Abdução em CHR
 Seja um programa abdutivo (P, A, I), sua transformação em um programa CHR
C(P, A, I) é:
Para cada p  P | p é intencional, escrevemos uma regra de simplificação, chamada
Regra de Definição de p. Exemplo:
parent(P, C)  father(P, C).
parent(P, C)  mother(P, C).
Se torna:
parent(P, C)  father(P, C)  mother(P, C)
Para cada p  P | p é extencional, escrevemos uma regra de propagação, chamada
Regra de Fechamento de p. Exemplo:
father(P, C).
Se torna:
father(P, C)  (P=john  C=mary)  (P=john  C=peter)
Abdução em CHR (2)
CP tem uma regra de propagação chamada Regra de Introdução Extensional, listando
todos os fatos de todos os predicados extensionais.
Exemplo:
facts  father(john, mary)  father(john, peter)
 mother(jane, mary)  person(john, male)...
Restrições de Integridade são regras de propagação. Exemplo:
father(F1, C)  father(F2, C)  F1 = F2.
A Regra de Fechamento é deixada de lado quando o predicado é abduzível
Exemplo de abdução em CHR
john (male)
pai
paul (male)
jane (female)
pai
peter (male)
mãe
mary (female)
Exemplo de abdução em CHR (2)
% Definition Rules
R1@ parent(P,C)  father(P,C)  mother(P,C).
R2@ sibling(C1,C2)  C1≠C2  parent(P,C1)  parent(P,C2).
% Extensional Introduction Rule
R3@ facts  father(john, mary)  father(john, peter)  mother(jane,
mary)  person(john, male)  person(peter,male)  person(jane,female) 
person(mary,female)  person(paul,male).
% Closing Rules
R4@ father(X,Y)  (X=john  Y=mary)  (X=john  Y=peter).
R5@ mother(X,Y)  (X=jane  Y=mary).
R6@ person(X,Y)  (X=john  Y=male)  (X=peter  Y=male)  (X=jane 
Y=female)  (X=mary  Y=female)  (X=paul  Y=male).
% Integrity Constraints
R7@ father(F1,C)  father(F2,C)  F1=F2.
R8@ mother(M1,C)  mother(M2,C)  M1=M2.
R9@ person(P,G1)  person(P,G2)  G1=G2.
R10@ father(F,C)  person(F,male)  person(C,S).
R11@ mother(M,C)  person(F,female)  person(C,G).
Exemplo de abdução em CHR (3)
 Sejam father e mother abduzíveis. G = sibling(paul, mary)
R1@ parent(P,C)  father(P,C)  mother(P,C).
R2@ sibling(C1,C2)  C1≠C2  parent(P,C1)  parent(P,C2).
R6@ Person(X,Y)  (X=john  Y=male)  (X=peter  Y=male)  (X=jane 
Y=female)  (X=mary  Y=female)  (X=paul  Y=male).
R7@ father(F1,C)  father(F2,C)  F1=F2.
R8@ mother(M1,C)  mother(M2,C)  M1=M2.
R9@ person(P,G1)  person(P,G2)  G1=G2.
R10@ father(F,C)  person(F,male)  person(C,S).
R11@ mother(M,C)  person(F,fmale)  person(C,G).
Exemplo de abdução em CHR (4)
Rule
RDCS
BICS
r2
father(john, mary)  father(john, peter)  mother(jane, mary)  person(john, male) 
person(peter,male)  person(jane,female)  person(mary,female)  person(paul,male) 
sibling(paul, mary).
true
r1a
father(john, mary)  father(john, peter)  mother(jane, mary)  person(john, male) 
person(peter,male)  person(jane,female)  person(mary,female)  person(paul,male) 
parent(P, paul)  parent(P, mary).
paul≠mary
^true
r1a
father(john, mary)  father(john, peter)  mother(jane, mary)  person(john, male) 
person(peter,male)  person(jane,female)  person(mary,female)  person(paul,male) 
person(mary,female)  person(paul,male)  father(P, paul)  parent(P, mary).
paul≠mary
^true
r7
father(john, mary)  father(john, peter)  mother(jane, mary)  person(john, male) 
person(peter,male)  person(jane,female)  person(mary,female)  person(paul,male) 
person(mary,female)  person(paul,male)  father(P, paul)  father(P, mary).
paul≠mary
^true
father(john, mary)  father(john, peter)  mother(jane, mary)  person(john, male) 
person(peter,male)  person(jane,female)  person(mary,female)  person(paul,male) 
person(mary,female)  person(paul,male)  father(P, paul)  father(P, mary).
paul≠mary ^
P=john ^ true
Revisão de crenças: manutenção de verdade
 Quando fazer revisão de crenças
Fatos deduzidos se mostram incorretos em face de um novo fato recebido.
 Utiliza retract(old fact) em decorrência de tell(new fact).
 Porém, surge o problema da manutenção da verdade.
 O que foi deduzido a partir do fato retirado, tem que ser por sua vez retirado.
 Sistemas de manutenção de verdade (TMSs) devem resolver essas
complicações.
Revisão de crenças:
manutenção de verdade (2)
Exemplo:
(R1) estaEm(Player,X)  segurando(B)  estaEm(B,X)
(F1) estaEm(player_1,5)
(F2) segurando(bola)
(F3) estaEm(bola,5)
// F1 e F2
tell(BC,estaEm(player_1,6))
retract(BC,estaEm(player_1,5))
 Precisamos retrair também estaEm(bola,5)
Sistemas de manutenção de verdade
Resolvedor de problemas
Base de Conhecimento
Estado de Crenças
Inferências
TMS
Nós
Nogoods
 Cada inferência realizada pelo resolvedor é informada ao TMS e
armazenada como uma justificativa ( p  p1,...,pn )
 Um TMS registra nogoods que expressam suposições(q1,...,qn) que não
devem ocorrer juntas ( ¬ [q1,...,qn] )
 O TMS deve determinar que proposições podem ser derivadas do conjunto
de justificativas sem violar os nogoods.
JTMS - Manutenção da verdade
baseada em justificativa
 Abordagem JTMS (Justification-Based Truth Maintenance System):
 Cada proposição na KB é anotada com uma justificativa (as proposições a partir
da qual ela foi inferida)
P  P1,...,Pn, ~Pn+1,...,~Pm
 Cada proposição é rotulada IN ou OUT
 P pode ser derivado(é IN - esta em KB) se P1,...,Pn podem ser derivados(são IN)
e Pn+1,...,Pm (são OUT - não estão em KB) não podem ser derivados
Exemplo de JTMS
 Atualização de rótulos
p  ~q
q  ~r
JTMS é informado que p é verdadeiro
p
q
OUT IN
r
OUT
Exemplo de JTMS
 Atualização de rótulos
p  ~q
q  ~r
p
OUT IN
IN
JTMS é informado que p é verdadeiro
q
r
OUT
Exemplo de JTMS
 Atualização de rótulos
p  ~q
q  ~r
p
OUT IN
IN
JTMS é informado que p é verdadeiro
q
OUT
r
OUT
Exemplo de JTMS
 Atualização de rótulos
p  ~q
q  ~r
p
OUT IN
IN
JTMS é informado que p é verdadeiro
q
r
OUT
OUT IN
Exemplo de JTMS
 Atualização de rótulos
p  ~q
q  ~r
p
q
OUT IN
IN
r
OUT
OUT IN
JTMS informa ao resolvedor de problemas o novo estado de crenças:
P – IN, q – OUT e r - IN
JTMS e abdução
pq
r  ~q
q  ~r
nogood = p
ConjuntoIN_1 = {p,q}
ConjuntoIN_2 = {r}
 JTMS como um programa abdutivo com abordagem do naf
 Justificativas = cláusulas do programa
 ~pn
= naf pn
 nogood
= IC
JTMS e abdução (2)
pq
r  ~q
q  ~r
pq
r  naf(q)
q  naf(r)
nogood = p
ConjuntoIN_1 = {p,q}
ConjuntoIN_2 = {r}
IC
= p
ME1 = {p,q}
ME2 = {r}
É possível utilizar a semântica declarativa de GALPs para entender o
significado de um JTMS.
ATMS - Manutenção da verdade
baseada em suposição
 Abordagem ATMS (Assumption-Based Truth Maintenance System):
 Cada proposição na BC é anotada com um conjunto de justificativas (cada
justificativa é um conjunto de proposições que torna verdade a proposição)
P  Q1,...,Qn
P  R1,...,Rn
 P é derivado se Q1,...,Qn são derivados ou R1,...,Rn são derivados
 Quando o contexto é alterado, para saber se um fato é ou não acreditado basta
verificar se um dos conjuntos de suas proposições está contido no contexto
 Contexto: tudo o que é acreditado no momento.
Exemplo de ATMS
 Exemplo
1. p  a,b
2. p  b,c,d
3. q  a,c
4. q  d,e
Nogood (a,b,e)
 Nova justificativa
 r  p,q





ATMS registrará:
r  a,b,c
//
r  b,c,d,e
//
r  a,b,d,e
//
r  a,b,c,d
//
1 e 3 | é registrado
2 e 4 | é registrado
1 e 4 | Nogood (a,b,e)
2 e 3 | tem o mesmo valor de r  a,b,c
ATMS e abdução
 1. Dado:
Programa lógico abdutivo P (P é um PALP);
Efeito observado G;
Conjunto de hipóteses abdutivas Δ;
Restrições de integridade I.
 2. Tem-se:
P U Δ |= G;
P U G satisfaz I.
 3. Similar ao registro computado pelo ATMS:
G  Δ
 Exemplo:
r  a,b,c
r  a  b  c
JTMS X ATMS
 Rótulos dos nós
JTMS Acreditado ou Não acreditado (IN ou OUT).
ATMS Conjunto de conjuntos mínimos de nós que devem estar contidos no contexto
para o nó ser acreditado.
 Tratamento de múltiplas alternativas
JTMS É necessário acrescentar ou remover premissas e depois tornar a calcular
todos os rótulos dos nós da rede.
ATMS Altera-se o contexto, que representa aquilo em que se acredita, e para saber
se se acredita num nó basta ver se um dos conjuntos de nós do seu rótulo está
contido no contexto. Neste aspecto, é muito melhor do que o JTMS.
Conclusão
 Raciocínio por default e revisão de crenças baseada em manutenção de verdade
podem ser vistos como casos particulares de abdução.
 Abdução pode ser implementada em CHRV.
 Raciocínio por default e revisão de crenças podem ser implementados em CHRV,
se devidamente mapeados para o framework abdutivo!!