08-Logica_na_Pratica

Prévia do material em texto

Proposições	
  	
  e	
  Inferências	
  na	
  
Prá2ca	
  
	
  
	
  
Lógica	
  na	
  prá2ca	
  
¨  Muitas	
  BCs	
  reais	
  não	
  tem	
  necessidade	
  da	
  capacidade	
  toda	
  de	
  
inferência	
  da	
  resolução	
  porque	
  todas	
  as	
  cláusulas	
  são	
  de	
  uma	
  
espécie	
  restrita.	
  	
  
¨  As	
  restrições	
  possíveis	
  variam	
  com	
  a	
  complexidade	
  necessária	
  
a	
  modelagem.	
  
¨  A	
  forma	
  mais	
  usada	
  de	
  lógica	
  restrita	
  são	
  as	
  clausulas	
  de	
  Horn.	
  
¨  Uma	
  cláusula	
  de	
  Horn	
  é	
  uma	
  disjunção	
  de	
  literais	
  dos	
  quais	
  no	
  
máximo	
  um	
  é	
  posi2vo	
  
−  Exemplos:	
  	
  
l  (¬l1,1	
  V	
  ¬brisa	
  V	
  b1,1)	
  é	
  uma	
  cláusula	
  de	
  Horn.	
  
l  (¬b1,1	
  V	
  p1,2	
  V	
  p2,1)	
  não	
  é	
  uma	
  cláusula	
  de	
  Horn.	
  
Cláusulas	
  de	
  Horn	
  
l  Cláusulas	
  de	
  Horn	
  são	
  importantes	
  por	
  3	
  razões:	
  
1) Podem	
  ser	
  escritas	
  como	
  uma	
  implicação	
  cuja	
  premissa	
  é	
  uma	
  conjunção	
  
de	
  literais	
  posi2vos	
  e	
  cuja	
  conclusão	
  é	
  um	
  único	
  literal	
  posi2vo:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
(l1,1	
  ٨۸ brisa)	
  à	
  b1,1	
  	
  ou	
  	
  b1,1	
  ß (l1,1	
  ٨۸ brisa)	
  	
  
2) A	
  inferência	
  com	
  cláusulas	
  de	
  Horn	
  pode	
  ser	
  feita	
  por	
  algoritmos	
  de	
  
encadeamento	
  para	
  frente	
  ou	
  para	
  trás.	
  
3) A	
  decisão	
  de	
  consequência	
  lógica	
  com	
  cláusulas	
  de	
  Horn	
  pode	
  ser	
  feita	
  
em	
  tempo	
  linear	
  em	
  relação	
  ao	
  tamanho	
  da	
  BC.	
  
4) Cláusulas	
  de	
  Horn	
  com	
  exatamente	
  um	
  literal	
  posi2vo	
  são	
  chamadas	
  de	
  
Cláusulas	
  Definidas	
  e	
  são	
  a	
  base	
  da	
  programação	
  em	
  lógica.	
  
Sintaxe	
  das	
  Cláusulas	
  Definidas	
  Proposicionais	
  
¨  Um	
  átomo	
  é	
  um	
  símbolo	
  começando	
  com	
  uma	
  letra	
  
minúsculas.	
  
¨  Uma	
  cláusula	
  definida	
  é	
  um	
  átomo	
  ou	
  uma	
  regra	
  na	
  forma	
  	
  h	
  
←	
  b	
  na	
  qual	
  h	
  é	
  um	
  átomo	
  (chamado	
  de	
  cabeça)	
  e	
  b	
  é	
  um	
  
corpo,	
  o	
  qual	
  é	
  um	
  átomo	
  ou	
  está	
  na	
  forma	
  b1	
  ∧ b2	
  na	
  qual	
  	
  	
  b1	
  
e	
  b2	
  são	
  corpos.	
  	
  
¨  Uma	
  cláusula	
  definida	
  sem	
  literais	
  nega2vos	
  é	
  um	
  fato.	
  
Semân2ca	
  das	
  Cláusulas	
  Definidas	
  
Proposicionais	
  
¨  Uma	
  interpretação	
  I	
  atribui	
  um	
  valor	
  de	
  verdade	
  para	
  cada	
  
átomo.	
  	
  
¨  Um	
  corpo	
  b1	
  ∧	
  b2	
  é	
  verdadeiro	
  em	
  I	
  se	
  b1	
  é	
  verdadeiro	
  em	
  I	
  e	
  
b2	
  é	
  verdadeiro	
  em	
  I.	
  	
  
¨  Uma	
  regra	
  h	
  ←	
  b	
  é	
  falsa	
  em	
  I	
  se	
  b	
  for	
  verdadeira	
  em	
  I	
  e	
  h	
  for	
  
falsa	
  em	
  I.	
  A	
  regra	
  é	
  verdadeira	
  caso	
  contrário.	
  	
  
¨  Uma	
  base	
  de	
  conhecimento	
  BC	
  é	
  verdadeira	
  em	
  I	
  se	
  e	
  
somente	
  se	
  cada	
  cláusula	
  em	
  BC	
  é	
  verdadeira	
  em	
  I.	
  
Procedimento	
  fundamental	
  de	
  prova	
  Bo^om-­‐up	
  	
  
¨  Uma	
  regra	
  de	
  derivação,	
  uma	
  forma	
  generalizada	
  de	
  Modus	
  
Ponens:	
  	
  
¤  Se	
  "h	
  ←	
  b1	
  ∧	
  …	
  ∧	
  bm"	
  é	
  uma	
  cláusula	
  na	
  base	
  de	
  conhecimento,	
  e	
  cada	
  
bi	
  foi	
  derivado,	
  então	
  h	
  pode	
  ser	
  derivado.	
  	
  
¨  Isto	
  é	
  o	
  encadeamento	
  para	
  frente	
  sobre	
  esta	
  cláusula.	
  
¤  (Essa	
  regra	
  também	
  cobre	
  o	
  caso	
  quando	
  m	
  =	
  0.)	
  
Procedimento	
  de	
  prova	
  Bo^om-­‐up	
  	
  
¨  KB	
  |─	
  g	
  se	
  g	
  ∈ C	
  no	
  final	
  deste	
  procedimento:	
  	
  
¨  C	
  ß	
  {}	
  	
  
¨  repeat	
  
¨  	
   selecione	
  a	
  cláusula	
  "h	
  ←	
  b1	
  ∧	
  …	
  ∧	
  bm"	
  na	
  BC	
  tal	
  que	
  	
  
¨  	
   	
   bi	
  ∈ C para	
  todos	
  os	
  i,	
  e	
  h	
  ∉ C	
  
¨  	
   C	
  ß	
  C	
  ∪ {h}	
  	
  
¨  un2l	
  nenhuma	
  cláusula	
  possa	
  ser	
  mais	
  selecionada.	
  
Exemplo:	
  encadeamento	
  para	
  frente	
  (bo^om-­‐up)	
  
¨ BC:	
  
¨ a ß b ٨۸ c.	
  
¨ b ß d ٨۸ e.	
  
¨ b ß g ٨۸ e.	
  
¨ c ß e.	
  
¨ d.	
  
¨ e.	
  
¨ f ß a ٨۸ g. 
l  Encadeamento	
  para	
  frente	
  
para	
  BC	
  e	
  a	
  consulta	
  F:	
  
−  {	
  }	
  
−  {d}	
  
−  {d,	
  e}	
  
−  {d,	
  e,	
  b}	
  
−  {d,	
  e,	
  b,	
  c}	
  
−  {d,	
  e,	
  b,	
  c,	
  a}	
  
Exercício	
  
Consistência	
  (soundness)	
  do	
  procedimento	
  de	
  
prova	
  Bo^om-­‐up	
  
¨  Se	
  KB	
  |─	
  g	
  então	
  KB	
  |=	
  g.	
  	
  
¤  Suponha	
  que	
  exista	
  um	
  g	
  tal	
  que	
  BC	
  |─	
  g	
  e	
  BC	
  |≠	
  g.	
  	
  
¤  Então,	
  deve	
  haver	
  um	
  primeiro	
  átomo	
  adicionado	
  a	
  C	
  que	
  não	
  é	
  verdade	
  em	
  
todos	
  os	
  modelos	
  de	
  BC.	
  Chame-­‐o	
  de	
  h.	
  Suponha	
  que	
  h	
  não	
  é	
  verdade	
  no	
  
modelo	
  I	
  do	
  BC.	
  	
  
¤  Deve	
  haver	
  uma	
  cláusula	
  em	
  BC	
  de	
  forma	
  
¤  	
   h	
  ←	
  b1	
  ∧ ... ∧ bm	
  	
  
¤  	
   Cada	
  bi	
  é	
  verdadeiro	
  em	
  I.	
  h	
  é	
  falso	
  em	
  I.	
  Logo,	
  esta	
  cláusula	
  é	
  falsa	
  em	
  I.	
  	
  
Portanto	
  I	
  não	
  é	
  um	
  modelo	
  de	
  KB.	
  	
  
¤  Contradição.	
  
Ponto	
  fixo	
  
¨  O	
  C	
  gerado	
  ao	
  final	
  do	
  algoritmo	
  de	
  bo^om-­‐up	
  é	
  chamado	
  de	
  
um	
  ponto	
  fixo.	
  
¨  Deixe	
  I	
  ser	
  a	
  interpretação	
  em	
  que	
  cada	
  elemento	
  do	
  ponto	
  
fixo	
  é	
  verdadeiro	
  e	
  todo	
  outro	
  átomo	
  é	
  falso.	
  	
  
¨  I	
  é	
  um	
  modelo	
  de	
  KB.	
  	
  	
  
¨  	
   Prova:	
  	
  
¤ 	
  Suponha	
  que	
  h	
  ←	
  b1	
  ∧	
  …	
  ∧	
  bm	
  em	
  BC	
  é	
  falso	
  em	
  I.	
  	
  Então,	
  h	
  é	
  falso	
  e	
  
cada	
  bi	
  é	
  verdadeiro	
  em	
  I.	
  Assim,	
  h	
  pode	
  ser	
  adicionado	
  a	
  C.	
  
Contradizendo	
  o	
  fato	
  de	
  C	
  ser	
  o	
  ponto	
  fixo.	
  	
  
¨  I	
  é	
  chamado	
  de	
  um	
  modelo	
  mínimo.	
  
Completude	
  
¨  Se	
  BC	
  |=	
  g	
  então	
  BC	
  |─ g.	
  	
  
¤  Suponha	
  que	
  BC	
  |=	
  g.	
  Então,	
  g	
  é	
  verdade	
  em	
  todos	
  os	
  modelos	
  de	
  BC.	
  	
  
¤  Assim,	
  g	
  é	
  verdade	
  no	
  modelo	
  mínimo.	
  	
  
¤  Assim,	
  g	
  está	
  no	
  ponto	
  fixo.	
  	
  
¤  Assim,	
  g	
  é	
  gerado	
  pelo	
  algoritmo	
  bo^om-­‐up.	
  	
  
¤  Assim,	
  KB	
  |─	
  g.	
  
Procedimento	
  fundamental	
  de	
  prova	
  Top-­‐down	
  	
  
¨  Ideia:	
  Pesquise	
  para	
  trás	
  a	
  par2r	
  de	
  uma	
  consulta	
  para	
  determinar	
  se	
  ela	
  é	
  
uma	
  consequência	
  lógica	
  da	
  BC.	
  	
  
¨  Uma	
  cláusula	
  de	
  resposta	
  é	
  da	
  forma:	
  	
  
¨  	
   yes	
  ←	
  	
  a1	
  ∧	
  a2	
  ∧...	
  ∧	
  am	
  
¨  A	
  resolução	
  SLD	
  (Selec2ve	
  Linear	
  Definite)	
  desta	
  cláusula	
  de	
  resposta	
  sobre	
  
o	
  átomo	
  ai	
  com	
  a	
  cláusula:	
  	
  
¨  
 ai	
  ←	
  	
  b1	
  ∧ ...	
  ∧ bp	
  
¨  É	
  a	
  cláusula	
  resposta	
  
¨  
 yes	
  ←	
  	
  a1	
  ∧	
  	
  ...	
  ∧	
  ai-­‐1	
  ∧	
  b1	
  ∧	
  ...	
  ∧	
  bp	
  ∧	
  ai+1	
  ∧	
  ...	
  ∧	
  am	
  
Derivações	
  
¨  Uma	
  resposta	
  é	
  uma	
  cláusula	
  de	
  resposta	
  com	
  m	
  =	
  0.	
  Ou	
  seja,	
  
é	
  a	
  resposta	
  cláusula	
  yes	
  ←	
  .	
  	
  
¨  Uma	
  derivação	
  da	
  consulta	
  “?q1	
  ∧ ...	
  ∧ 	
  qk”	
  da	
  BC	
  é	
  uma	
  
sequência	
  de	
  cláusulas	
  resposta	
  γ0, γ1, …, γn tal	
  que	
  	
  
¤  γ0 é	
  a	
  cláusula	
  resposta	
  yes	
  ←	
  	
  q1	
  ∧ ...	
  ∧	
  qk	
  ,	
  	
  
¤  γi é	
  ob2da	
  por	
  meio	
  da	
  resolução	
  γi-1 com	
  uma	
  cláusula	
  na	
  BC,	
  e	
  	
  
¤  γn é	
  uma	
  resposta.	
  
Interpretador	
  Top-­‐down	
  de	
  Cláusulas	
  definidas	
  
¨  Para	
  resolver	
  a	
  consulta	
  ?q1	
  ∧ …	
  ∧	
  qk:	
  
¤  	
  ac	
  :=	
  “yes	
  ←	
  	
  q1	
  ∧ …	
  ∧	
  qk”	
  
¨  	
   repe2r	
  	
  
¨  	
   	
   selecione	
  o	
  átomo	
  ai	
  do	
  corpo	
  de	
  ac;	
  	
  
¨  	
   	
   escolha	
  a	
  cláusula	
  C	
  da	
  BC	
  com	
  ai	
  como	
  cabeça;	
  	
  
¨  	
   	
   subs2tua	
  ai	
  no	
  corpo	
  de	
  ac	
  pelo	
  corpo	
  de	
  C	
  	
  
¨  	
   até	
  que	
  ac	
  seja	
  uma	
  resposta.	
  
Escolha	
  não	
  determinís2ca	
  
¨  No	
  não-­‐determinismo	
  do	
  2po	
  não-­‐importa	
  se	
  uma	
  seleção	
  não	
  
conduzir	
  a	
  uma	
  solução,	
  não	
  faz	
  sen2do	
  tentar	
  outras	
  
alterna2vas.	
  Selecione.	
  
¨  No	
  não-­‐determinismo	
  do	
  2po	
  não-­‐sei	
  se	
  uma	
  escolha	
  não	
  
conduzir	
  a	
  uma	
  solução,	
  outras	
  escolhas	
  podem.	
  Escolha.	
  
Exemplo:	
  encadeamento	
  para	
  trás	
  (top-­‐down)	
  
¨ BC:	
  
¨ a ß b ٨۸ c.	
  
¨ b ß d ٨۸ e.	
  
¨ b ß g ٨۸ e.	
  
¨ c ß e.	
  
¨ d.	
  
¨ e.	
  
¨ f ß a ٨۸ g. 
l  Encadeamento	
  para	
  trás	
  para	
  BC	
  e	
  a	
  consulta	
  a:	
  
l  Para	
  provar	
  a	
  podemos	
  usar	
  a	
  cláusula	
  a	
  ß b ٨۸ c.	
  
Temos	
  que	
  provar	
  b ٨۸ c 	
  
l  Para	
  provar	
  b	
  podemos	
  usar	
  a	
  cláusula	
  b	
  ß d ٨۸ e.	
  	
  
Temos	
  que	
  provar	
  d	
  ٨۸ e ٨۸ c	
  
l  d	
  é	
  um	
  fato.	
  Temos	
  que	
  provar	
  	
  e ٨۸ c	
  
l  e	
  é	
  um	
  fato.	
  Temos	
  que	
  provar	
  	
  c	
  
l  Para	
  provar	
  c	
  podemos	
  usar	
  a	
  cláusula	
  c	
  ß e.	
  
Temos	
  que	
  provar	
  e.	
  
l  e	
  é	
  um	
  fato.	
  Então	
  provamos	
  A.	
  
Encadeamento	
  para	
  trás	
  (top-­‐down)	
  
¨ BC:	
  
¨ a ß b ٨۸ c.	
  
¨ b ß d ٨۸ e.	
  
¨ b ß g ٨۸ e.	
  
¨ c ß e.	
  
¨ d.	
  
¨ e.	
  
¨ f ß a ٨۸ g. 
l  Encadeamento	
  para	
  trás	
  para	
  BC	
  e	
  a	
  consulta	
  f:	
  
l  Para	
  provar	
  f	
  	
  podemos	
  usar	
  a	
  cláusula	
  	
  f	
  ß a ٨۸ g.	
  
Temos	
  que	
  provar	
  a ∧ g.	
  
l  Para	
  provar	
  a	
  podemos	
  usar	
  a	
  cláusula	
  a	
  ß b	
  ∧ c.	
  
Temos	
  que	
  provar	
  b	
  ∧ c	
  ∧ g	
  
l  Para	
  provar	
  b	
  podemos	
  usar	
  a	
  cláusula	
  	
  b	
  ß d	
  ∧ e	
  ou	
  a	
  
cláusula	
  b	
  ß g	
  ∧ e.	
  Vamos	
  tentar	
  por	
  b	
  ß d	
  ∧ e.	
  
Temos	
  que	
  provar	
  d	
  ∧ e	
  ∧ c	
  ∧ g	
  
l  d	
  é	
  um	
  fato.	
  Temos	
  que	
  provar	
  	
  e	
  ∧ c	
  ∧ g	
  
l  e	
  é	
  um	
  fato.	
  Temos	
  que	
  provar	
  	
  c	
  ∧ g	
  
l  Para	
  provar	
  c	
  podemos	
  usar	
  a	
  cláusula	
  	
  c	
  ß e.	
  Temos	
  
que	
  provar	
  e	
  ∧ g	
  
Encadeamento	
  para	
  trás	
  (top-­‐down)	
  
¨ BC:	
  
¨ a ß b ٨۸ c.	
  
¨ b ß d ٨۸ e.	
  
¨ b ß g ٨۸ e.	
  
¨ c ß e.	
  
¨ d.	
  
¨ e.	
  
¨ f ß a ٨۸ g. 
l  e	
  é	
  um	
  fato.	
  Temos	
  que	
  provar	
  g	
  
l  Não	
  existe	
  nenhuma	
  cláusula	
  que	
  tem	
  g	
  como	
  
conclusão.	
  A	
  prova	
  falha	
  por	
  este	
  caminho.	
  
l  Vamos	
  tentar	
  a	
  segunda	
  possibilidade	
  para	
  provar	
  b	
  
por	
  meio	
  de	
  b	
  ß g	
  ∧ e.	
  Temos	
  que	
  provar	
  e	
  ∧ c	
  ∧ g	
  
l  e	
  é	
  um	
  fato.	
  Temos	
  que	
  provar	
  	
  c	
  ∧ g	
  
l  Para	
  provar	
  c	
  podemos	
  usar	
  a	
  cláusula	
  	
  c	
  ß e.	
  
Temos	
  que	
  provar	
  e	
  ∧ g	
  
l  e	
  é	
  um	
  fato.	
  Temos	
  que	
  provar	
  g	
  
l  Não	
  existe	
  nenhuma	
  cláusula	
  que	
  tem	
  g	
  como	
  
conclusão.	
  A	
  prova	
  falha	
  por	
  este	
  caminho	
  também.	
  
Exemplo:	
  derivação	
  bem	
  sucedida	
  
Exemplo:	
  derivação	
  falha	
  
Grafo	
  de	
  pesquisa	
  para	
  uma	
  resolução	
  SLD	
  
Encadeamento	
  para	
  frente	
  e	
  para	
  trás	
  
l  Encadeamento	
  para	
  frente	
  à	
  raciocínio	
  orientado	
  a	
  dados	
  
−  O	
  foco	
  da	
  atenção	
  começa	
  com	
  os	
  dados	
  conhecidos	
  (fatos)	
  
−  Pode	
  ser	
  usado	
  por	
  um	
  agente	
  para	
  derivar	
  conclusões	
  a	
  par2r	
  das	
  percepções	
  
de	
  entrada,	
  não	
  necessariamente	
  com	
  uma	
  consulta	
  específica	
  focada.	
  
l  Encadeamento	
  para	
  trás	
  à	
  raciocínio	
  orientado	
  por	
  metas	
  
−  É	
  ú2l	
  para	
  responder	
  perguntas	
  específicas:	
  “O	
  que	
  eu	
  devo	
  fazer	
  agora?”	
  ou	
  
“Onde	
  estão	
  minhas	
  chaves?”	
  
−  Com	
  frequência	
  o	
  custo	
  é	
  muito	
  menor	
  do	
  que	
  o	
  custo	
  linear	
  no	
  tamanho	
  da	
  
base	
  de	
  conhecimento,	
  porque	
  foca	
  somente	
  fatos	
  relevantes.	
  
l  Um	
  agente	
  deve	
  dividir	
  o	
  trabalho	
  fazendo	
  EpF	
  para	
  derivar	
  fatos	
  
que	
  tem	
  probabilidade	
  de	
  serem	
  relevantes	
  para	
  consultas	
  que	
  
serão	
  resolvidas	
  por	
  EpT.	
  
24	
   Modelagem	
  de	
  problema	
  em	
  Lógica	
  
Problemas	
  de	
  representação	
  de	
  conhecimento	
  
¨  Agentes	
  que	
  operam	
  em	
  um	
  ambiente	
  dinâmico	
  requerem	
  
informações	
  em	
  tempo	
  de	
  execução.	
  
Conhecimento	
  de	
  background	
  e	
  observações	
  
¨  Uma	
  observação	
  é	
  um	
  pedaço	
  de	
  informação	
  recebido	
  dos	
  
usuário,	
  sensores	
  ou	
  outras	
  fontes	
  de	
  conhecimento	
  em	
  
tempo	
  de	
  execução.	
  
¨  Um	
  conjunto	
  de	
  observações	
  é	
  uma	
  conjunção	
  de	
  átomos.	
  	
  
¨  Em	
  muitos	
  frameworks	
  de	
  raciocínio	
  as	
  observações	
  são	
  
adicionadas	
  ao	
  conhecimento	
  de	
  background	
  em	
  outros	
  não	
  
(abdução,	
  aprendizagem,	
  etc.).	
  
Usuários	
  como	
  fonte	
  de	
  conhecimento	
  
¨  Exemplo:	
  no	
  domínio	
  elétrico:	
  
¤  O	
  que	
  o	
  construtor	
  de	
  casas	
  deve	
  sabe?	
  	
  
¤  O	
  que	
  um	
  ocupante	
  da	
  casadeve	
  saber?	
  	
  
¨  Não	
  se	
  pode	
  esperar	
  que	
  os	
  usuários	
  forneçam	
  conhecimento	
  
voluntariamente:	
  
¤  Eles	
  não	
  sabem	
  quais	
  informações	
  são	
  necessárias.	
  	
  
¤  Eles	
  não	
  sabem	
  qual	
  vocabulário	
  usar.	
  
¨  Uma	
  ontologia	
  que	
  especifique	
  o	
  significado	
  dos	
  símbolos	
  e	
  uma	
  
interface	
  gráfica	
  (para	
  permi2r	
  que	
  o	
  usuário	
  indique	
  o	
  que	
  é	
  
verdadeiro)	
  podem	
  ajudar	
  a	
  resolver	
  o	
  problema	
  de	
  vocabulário.	
  
Pergunte	
  ao	
  usuário	
  (Ask-­‐the-­‐user)	
  
¨  Os	
  usuários	
  podem	
  fornecer	
  observações	
  para	
  o	
  sistema.	
  Eles	
  
podem	
  responder	
  a	
  perguntas	
  específicas.	
  	
  
¨  Átomos	
  askable	
  são	
  aqueles	
  que	
  um	
  usuário	
  deve	
  ser	
  capaz	
  de	
  
observar.	
  
¨  Existem	
  3	
  2pos	
  de	
  obje2vos	
  no	
  procedimento	
  de	
  prova	
  top-­‐down:	
  
1.  Obje2vos	
  para	
  os	
  quais	
  não	
  se	
  espera	
  que	
  o	
  usuário	
  saiba	
  a	
  resposta.	
  
2.  Átomos	
  askable	
  que	
  podem	
  ser	
  úteis	
  na	
  prova.	
  	
  
3.  Átomos	
  askable	
  para	
  os	
  quais	
  o	
  usuário	
  já	
  tenha	
  fornecido	
  informações.	
  	
  
¨  O	
  procedimento	
  de	
  prova	
  top-­‐down	
  pode	
  ser	
  modificado	
  para	
  
solicitar	
  informação	
  ao	
  usuário	
  sobre	
  os	
  átomos	
  askable	
  para	
  os	
  
quais	
  ele	
  ainda	
  não	
  forneceu	
  informações.	
  
Explicação	
  no	
  nível	
  de	
  conhecimento	
  
¨  Perguntas	
  COMO	
  podem	
  ser	
  usadas	
  para	
  perguntar	
  como	
  um	
  
átomo	
  foi	
  provado.	
  	
  
¤  Elas	
  fornecem	
  a	
  regra	
  usada	
  para	
  provar	
  o	
  átomo.	
  	
  
¤  Você	
  pode	
  perguntar	
  COMO	
  um	
  elemento	
  do	
  corpo	
  daquelas	
  regras	
  foi	
  
provado.	
  	
  
¤  Isso	
  permite	
  ao	
  usuário	
  explorar	
  a	
  prova.	
  	
  
¨  Perguntas	
  POR	
  QUE	
  podem	
  ser	
  usadas	
  para	
  perguntar	
  por	
  que	
  
uma	
  pergunta	
  foi	
  feita	
  .	
  	
  
¤  Elas	
  fornecem	
  a	
  regra	
  com	
  o	
  átomo	
  askable	
  no	
  corpo.	
  	
  
¤  Você	
  pode	
  perguntar	
  POR	
  QUE	
  a	
  regra	
  na	
  cabeça	
  foi	
  perguntada.	
  
Depuração	
  no	
  nível	
  de	
  conhecimento	
  
¨  Há	
  quatro	
  2pos	
  de	
  erros	
  não	
  sintá2cos	
  que	
  podem	
  surgir	
  em	
  
sistemas	
  baseados	
  em	
  regras:	
  	
  
1.  Uma	
  resposta	
  incorreta	
  é	
  produzida:	
  	
  
n  Um	
  átomo	
  que	
  é	
  falso	
  na	
  interpretação	
  pretendida	
  é	
  derivado.	
  	
  
2.  Alguma	
  resposta	
  não	
  produzida:	
  	
  
n  A	
  prova	
  falhou	
  quando	
  ela	
  deveria	
  ter	
  2do	
  sucesso.	
  Alguns	
  átomo	
  
verdadeiro	
  em	
  par2cular	
  não	
  foram	
  derivados.	
  	
  
3.  O	
  programa	
  entrou	
  em	
  um	
  loop	
  infinito.	
  	
  
4.  O	
  sistema	
  faz	
  perguntas	
  irrelevantes.	
  
Depurando	
  respostas	
  incorretas	
  
¨  Suponha	
  que	
  o	
  átomo	
  g	
  foi	
  provado	
  mas	
  é	
  falso	
  na	
  
interpretação	
  pretendida,	
  i.e.	
  temos	
  um	
  erro	
  falso-­‐posi2vo.	
  
¨  Deve	
  haver	
  uma	
  regra	
  g	
  ←	
  a1	
  ˄	
  …	
  ˄	
  ak	
  na	
  base	
  de	
  
conhecimento	
  que	
  foi	
  usada	
  para	
  provar	
  g.	
  
¨  Das	
  duas	
  uma:	
  	
  
¤  Um	
  dos	
  ai	
  é	
  Falso	
  na	
  interpretação	
  pretendida	
  ou	
  	
  
¤  Todos	
  o	
  ai	
  são	
  verdadeiros	
  na	
  interpretação	
  pretendida.	
  	
  
¨  Respostas	
  incorretas	
  podem	
  ser	
  depuradas	
  apenas	
  
respondendo	
  perguntas	
  “yes/no”.	
  
Respostas	
  ausentes	
  
¨  Se	
  o	
  átomo	
  g	
  é	
  verdadeiro	
  na	
  interpretação	
  pretendida,	
  mas	
  
não	
  pode	
  ser	
  provado,	
  i.e.	
  temos	
  um	
  erro	
  falso-­‐nega2vo.	
  
¨  Das	
  duas	
  uma:	
  	
  
¤  Existe	
  uma	
  regra	
  g	
  ←	
  	
  a1	
  ∧ …	
  ∧	
  ak	
  que	
  deve	
  ter	
  2do	
  êxito.	
  Mas	
  com	
  o	
  ela	
  
falhou	
  algum	
  dos	
  átomos	
  do	
  seu	
  corpo	
  (que	
  devia	
  ser	
  verdadeiro)	
  é	
  
falso	
  e,	
  portanto,	
  devemos	
  depurá-­‐lo	
  recursivamente.	
  
¤  Não	
  há	
  nenhuma	
  regra	
  apropriada	
  para	
  g.	
  	
  
Exemplo:	
  ambiente	
  elétrico	
  
Restrições	
  de	
  integridade	
  
¨  No	
  domínio	
  elétrico,	
  o	
  que	
  se	
  pode	
  fazer	
  se	
  podemos	
  prever	
  
que	
  uma	
  luz	
  deve	
  estar	
  acesa,	
  mas	
  observamos	
  que	
  ela	
  não	
  
está?	
  O	
  que	
  podemos	
  concluir?	
  	
  
¨  Iremos	
  expandir	
  o	
  idioma	
  de	
  cláusula	
  definidas	
  para	
  incluir	
  
restrições	
  de	
  integridade	
  (que	
  são	
  regras	
  que	
  implicam	
  em	
  
Falso).	
  	
  
¨  Isso	
  permi2rá	
  que	
  2remos	
  conclusões	
  de	
  uma	
  contradição.	
  	
  
Cláusulas	
  de	
  Horn	
  completas	
  
¨  Uma	
  restrição	
  de	
  integridade	
  é	
  uma	
  cláusula	
  de	
  forma	
  	
  
¨  	
   false	
  ←	
  	
  a1	
  ∧ ...	
  ∧	
  ak	
  
¤  na	
  qual	
  de	
  os	
  ai	
  são	
  átomos	
  e	
  false	
  é	
  um	
  átomo	
  especial	
  que	
  é	
  falso	
  em	
  
todas	
  as	
  interpretações.	
  	
  
¨  Uma	
  cláusula	
  de	
  Horn	
  completa	
  é	
  uma	
  cláusula	
  definida	
  ou	
  
uma	
  restrição	
  de	
  integridade.	
  
Conclusões	
  nega2vas	
  
¨  Negações	
  podem	
  ser	
  derivadas	
  de	
  uma	
  BC	
  de	
  cláusulas	
  de	
  
Horn.	
  	
  
¨  A	
  negação	
  de	
  α,	
  escrito	
  ←α	
  é	
  uma	
  fórmula	
  que	
  	
  
¤  É	
  verdadeira	
  na	
  interpretação	
  I	
  se	
  α é	
  falsa	
  em	
  I,	
  e	
  
¤  É	
  falsa	
  na	
  interpretação	
  I	
  se	
  α for	
  verdadeiro	
  em	
  I.	
  	
  
¨  Exemplo:	
  
¨  	
   	
   	
   	
  
Conclusões	
  disjun2va	
  
¨  Disjunções	
  podem	
  ser	
  derivadas	
  de	
  uma	
  BC	
  de	
  cláusula	
  de	
  
Horn.	
  
¨  A	
  disjunção	
  de	
  α e β,	
  escrito	
  α ∨ β,	
  é:	
  
¤  Verdadeira	
  na	
  interpretação	
  I	
  se	
  α é	
  verdadeira	
  em	
  I	
  ou	
  β é	
  verdadeira	
  
em	
  I	
  (ou	
  ambas	
  são	
  verdadeiras	
  em	
  I).	
  	
  
¤  Falsa	
  na	
  interpretação	
  I	
  se	
  α e	
  β são	
  ambos	
  falsos	
  em	
  I.	
  	
  
¨  Exemplo:	
  
¨  	
   	
   	
   	
  
Perguntas	
  e	
  respostas	
  em	
  BCs	
  em	
  Cláusulas	
  de	
  
Horn	
  
¨  Um	
  assumable	
  é	
  um	
  átomo	
  cuja	
  negação	
  você	
  está	
  preparado	
  
para	
  aceitar	
  como	
  parte	
  de	
  uma	
  resposta	
  (disjun2va).	
  	
  
¨  Um	
  conflito	
  de	
  uma	
  BC	
  é	
  um	
  conjunto	
  de	
  assumables	
  que,	
  
dada	
  a	
  BC,	
  implica	
  em	
  Falso.	
  	
  
¨  Um	
  conflito	
  mínimo	
  é	
  um	
  conflito	
  que	
  nenhum	
  subconjunto	
  
estrito	
  é	
  também	
  um	
  conflito.	
  
Exemplo	
  de	
  conflito	
  
¨  Exemplo: Se {c, d, e, f, g, h} são assumables	
  
¨  	
   	
   	
  
¨  {c, d} é um conflito (mínimo)	
  
¨  {c, e} é umconflito (mínimo)	
  
¨  {c, d, e, h} é um conflito
Usando	
  conflitos	
  para	
  diagnós2co	
  
¨  Suponha	
  que	
  o	
  usuário	
  seja	
  capaz	
  de	
  observar	
  se	
  uma	
  luz	
  está	
  acesa	
  ou	
  apagada	
  e	
  se	
  uma	
  tomada	
  
elétrica	
  está	
  com	
  energia	
  ou	
  não.	
  	
  
¨  A	
  luz	
  não	
  pode	
  estar	
  acesa	
  e	
  apagada	
  ao	
  mesmo	
  tempo.	
  Uma	
  tomada	
  não	
  pode	
  estar	
  com	
  energia	
  e	
  
sem	
  ao	
  mesmo	
  tempo:	
  	
  
¨  	
   false	
  ←	
  dark_l1	
  &	
  lit_l1.	
  	
  
¨  	
   false	
  ←	
  dark_l2	
  &	
  lit_l2.	
  	
  
¨  	
   false	
  ←	
  dead_p1	
  &	
  live_p2.	
  
¨  Suponha	
  que	
  os	
  componentes	
  individuais	
  estão	
  funcionando	
  corretamente:	
  	
  
¨  	
   Assumable	
  ok_l1.	
  
¨  	
   Assumable	
  ok_s2.	
  
¨  	
   ...	
  	
  
¨  Suponha	
  que	
  os	
  interruptores	
  s1,	
  s2	
  e	
  s3	
  estão	
  todos	
  na	
  posição	
  de	
  ligado:	
  	
  
¨  	
   up_s1.	
  up_s2.	
  up_s3.	
  
Ambiente elétrico
Representando o ambiente elétrico
Diagnó2co	
  
¨  	
  	
  
Diagnósticos
¨  Um	
  diagnós2co	
  baseado	
  em	
  consistência	
  é	
  um	
  conjunto	
  de	
  
assumables	
  que	
  tem	
  pelo	
  menos	
  um	
  elemento	
  em	
  cada	
  conflito.	
  	
  
¨  Um	
  diagnós2co	
  mínimo	
  é	
  um	
  diagnós2co	
  tal	
  que	
  nenhum	
  
subconjunto	
  é	
  também	
  um	
  diagnós2co.	
  
¨  Intui2vamente,	
  um	
  dos	
  diagnós2cos	
  mínimos	
  deve	
  ser	
  válido.	
  Um	
  
diagnós2co	
  é	
  válido	
  se	
  todos	
  seus	
  elementos	
  são	
  falsos.	
  	
  
¨  Exemplo:	
  Para	
  o	
  exemplo	
  seguinte	
  há	
  sete	
  diagnós2cos	
  mínimos:	
  
{ok_cb1},	
  {ok_s1,	
  ok_s3},	
  {ok_s1,	
  ok_l2},	
  {ok_s2,	
  ok_s3},...	
  
Relembrando:	
  Iden2ficação	
  de	
  consequências	
  
top-­‐down	
  
¨  Para	
  resolver	
  a	
  consulta ?q1	
  ∧ ...	
  ∧	
  qk	
  :	
  	
  
¨  ac:	
  =	
  “yes	
  ←	
  	
  q1	
  ∧ ...	
  ∧	
  qk”	
  
¨  repeat	
  	
  
¨  	
   selecione	
  o	
  átomo	
  ai	
  do	
  corpo	
  do	
  ac;	
  	
  
¨  	
   escolher	
  a	
  cláusula	
  C	
  na	
  BC	
  com	
  ai	
  como	
  cabeça;	
  	
  
¨  	
   subs2tuir	
  ai	
  no	
  corpo	
  da	
  ac	
  pelo	
  corpo	
  de	
  C	
  
¨  un2l	
  ac	
  ser	
  uma	
  resposta.	
  
Implementando a identificação de 
conflito: top-down 
¨  A	
  consulta	
  é	
  false.	
  	
  
¨  Não	
  selecione	
  um	
  átomo	
  que	
  é	
  assumable.	
  	
  
¨  Parar	
  quando	
  todos	
  os	
  átomos	
  no	
  corpo	
  da	
  consulta	
  
generalizada	
  são	
  assumable:	
  	
  
¤  Este	
  é	
  um	
  conflito	
  
Exemplo
Iden2ficando	
  conflitos	
  bo^om-­‐up	
  
¨  Conclusões são pares 〈a, A〉, onde a é um átomo e A é 
um conjunto de assumables que implicam a. 	
  
¨  Inicialmente, o conjunto de conclusão C =	
  {〈a,	
  {a}〉: a é um 
assumable}. 	
  
¨  Se houver uma regra h ← b1	
  ∧ …	
  ∧ bm	
  tal que, para cada bi existe alguns Ai tal que 〈bi,	
  Ai〉	
  ∈	
  C, então 〈h,	
  A1	
  ∪	
  …	
  ∪	
  Am〉 pode ser adicionado a C. 	
  
¤  Se 〈a, A1〉 e 〈a, A2〉 estão em C, onde A1	
  ⊂	
  A2, então 〈a, A2〉 pode ser removido de C. 	
  
¤  Se 〈false,	
  A1〉	
  e 〈a, A2〉 estão em C, onde A1 ⊆ A2, então 〈a, A2〉 pode ser removido de C.
Iden2ficando	
  conflitos	
  bo^om-­‐up:	
  código	
  
¨ C := {〈a, {a}〉: a é um assumable}	
  
¨ repeat	
  
¨  
selecione a cláusula “h ← b1 ∧ … ∧ bm" em T tal que:	
  
¨  
〈bi, A〉 ∈ C para todo i e	
  
¨  
não exista 〈h, A´〉 ∈ C ou 〈false, A´〉 ∈ C	
  
¨  
tal que A´ ⊆ A onde A = A1 ∪ … ∪ Am;	
  
¨  
C := C ∪ {〈h, A〉}	
  
¨  
Remova qualquer elemento de C que possa ser 
podado	
  
¨ until não seja mais possível selecionar ninguém.
Hipótese do conhecimento completo 
(CKA)
¨  Muitas	
  vezes	
  você	
  quer	
  assumir	
  que	
  seu	
  conhecimento	
  é	
  completo.	
  	
  
¨  Exemplo:	
  	
  
¤  Você	
  pode	
  indicar	
  quais	
  interruptores	
  estão	
  ligados	
  e	
  o	
  agente	
  pode	
  assumir	
  
que	
  os	
  outros	
  interruptores	
  estão	
  desligados.	
  	
  
¨  Exemplo:	
  	
  
¤  Suponha	
  que	
  um	
  banco	
  de	
  dados	
  dos	
  alunos	
  que	
  estão	
  matriculados	
  em	
  um	
  
curso	
  está	
  completo.	
  	
  
¨  Sob	
  a	
  hipótese	
  de	
  conhecimento	
  completo,	
  o	
  sistema	
  é	
  não-­‐
monotônico,	
  pois	
  a	
  adição	
  de	
  novas	
  cláusulas	
  pode	
  invalidar	
  uma	
  
conclusão	
  anterior.	
  
Fechamento	
  de	
  uma	
  base	
  de	
  conhecimento	
  
¨  Suponha	
  que	
  as	
  regras	
  de	
  um	
  átomo	
  são:	
  
n 	
  	
  
¤  	
  	
  a	
  ←	
  b1.	
  
¤  	
  	
  ...	
  	
  
¤  	
  	
  a	
  ←	
  bn.	
  
¨  A	
  quais	
  são	
  equivalente	
  a:	
  
¤  	
  	
  a	
  ←	
  b1	
  ∨	
  ...	
  bn.	
  
¨  Sob	
  a	
  Hipótese	
  de	
  Conhecimento	
  Completo	
  (CKA),	
  se	
  a	
  é	
  verdadeiro,	
  um	
  
dos	
  bi	
  deve	
  ser	
  verdadeiro:	
  	
  
¤  	
  	
  a	
  →	
  b1	
  ∨ ...	
  bn.	
  
¨  Sobre	
  a	
  CKA,	
  as	
  cláusulas	
  para	
  a	
  representam	
  o	
  Fechamento	
  (comple2on)	
  
de	
  Clark:	
  	
  
¤  	
  	
  a	
  ↔	
  b1	
  ∨...	
  bn.	
  
Fechamento	
  de	
  Clark	
  de	
  uma	
  BC	
  
¨  O	
  Fechamento	
  de	
  Clark	
  de	
  uma	
  base	
  de	
  conhecimento	
  
consiste	
  do	
  fechamento	
  de	
  cada	
  átomo	
  da	
  base.	
  	
  
¨  Um	
  átomo	
  sem	
  cláusulas	
  tem	
  seu	
  fechamento	
  como:	
  
¨  	
   	
   a	
  ↔	
  false.	
  	
  
¨  Pode-­‐se	
  interpretar	
  negações	
  no	
  corpo	
  de	
  cláusulas.	
  	
  
¤  ~a	
  significa	
  que	
  a	
  é	
  false	
  sob	
  a	
  suposição	
  de	
  conhecimento	
  completo	
  
(CKA).	
  
¨  	
   Isto	
  é	
  conhecido	
  como	
  negação	
  como	
  falha.	
  
Interpretador	
  bo^om-­‐up	
  de	
  negação	
  como	
  de	
  
falha	
  
¨ C	
  :=	
  {}	
  
¨ repeat	
  
¨  	
  this	
  
¨  	
  selecione	
  r	
  ∈	
  BC	
  tal	
  que	
  
¨  	
  	
  r	
  é	
  “h	
  	
  ←	
  b1	
  ∧ …	
  ∧ bm"	
  
¨  	
  	
  bi	
  ∈C	
  para	
  todo	
  i,	
  e	
  
¨  	
  	
  h	
  ∉	
  C;	
  
¨  	
  C	
  :=	
  C	
  ∪	
  {h}	
  
¨  	
  or	
  
¨  	
  selecione	
  h	
  tal	
  que	
  para	
  toda	
  regra	
  “h	
  ←	
  	
  b1	
  ∧ …	
  ∧	
  bm"	
  ∈ BC	
  
¨  	
  	
  para	
  algum	
  bi,	
  	
  ~bi	
  ∈	
  C	
  
¨  	
  	
  ou	
  algum	
  bi	
  =	
  ~g	
  e	
  g	
  ∈ C	
  
¨  	
  C	
  :=	
  C	
  ∪	
  {~h}	
  
¨ un2l	
  que	
  não	
  seja	
  possível	
  mais	
  seleções	
  
Exemplo	
  de	
  Negação	
  como	
  falha	
  
Procedimento de prova Top-Down de 
negação como falha
¨  Se	
  a	
  prova	
  é	
  para	
  uma	
  falha,	
  você	
  pode	
  concluir	
  ~a.	
  
¨  Falha	
  pode	
  ser	
  definida	
  recursivamente:	
  	
  
¨  	
   suponha	
  que	
  você	
  tem	
  regras	
  para	
  o	
  átomo	
  a:	
  	
  
¨  
 a ← b1	
  
¨  
 ...	
  
¨  
 a ← bn	
  
¨  	
   se	
  cada	
  corpo	
  bi	
  falhar,	
  a	
  falha.	
  	
  
¨  	
   Um	
  corpo	
  falhará	
  se	
  uma	
  das	
  conjunções	
  no	
  corpo	
  falhar.	
  
¨  Observe	
  que	
  vocêprecisa	
  de	
  ter	
  falha	
  finita.	
  	
  
¤  Exemplo:	
  p	
  ←	
  	
  p.	
  
Procedimento	
  de	
  prova	
  Top-­‐down	
  para	
  negação	
  
como	
  falha	
  
¨  1:	
  non-­‐determinis2c	
  procedure	
  NAFTD(KB,Query)	
  	
  
¨  2:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Inputs:	
  KB	
  #	
  um	
  conjunto	
  de	
  cláusulas	
  que	
  pod	
  incluir	
  negação	
  como	
  falha	
  
¨  3:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Query	
  #	
  um	
  conjunto	
  de	
  literais	
  para	
  provar	
  
¨  4:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Output	
  
¨  5:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  yes	
  se	
  a	
  completude	
  de	
  KB	
  entails	
  Query	
  e	
  fail	
  caso	
  contrário	
  
¨  6:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Local	
  
¨  7:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  G	
  #	
  é	
  um	
  conjunto	
  de	
  literais	
  
¨  8:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  G	
  ←	
  Query	
  	
  
¨  9:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  repeat	
  
¨  10:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  select	
  literal	
  l∈G	
  	
  
¨  11:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  if	
  (l	
  é	
  da	
  forma	
  ~a)	
  then	
  	
  
¨  12:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  if	
  (NAFTD(KB,a)	
  fails)	
  then	
  	
  
¨  13:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  G	
  ←G	
  \	
  {l}	
  	
  
¨  14:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  else	
  
¨  15:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  fail	
  	
  
¨  16:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  else	
  
¨  17:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  choose	
  cláusula	
  l	
  ←	
  B	
  da	
  KB	
  	
  
¨  18:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  troque	
  l	
  com	
  B	
  em	
  G	
  
¨  19:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  un2l	
  G={}	
  	
  
¨  20:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  return	
  yes	
  
57	
   Inferência	
  proposicional	
  efe2va	
  
Algoritmo	
  DPLL	
  (Davis-­‐Putnam-­‐Logemann-­‐Loveland)	
  
¨  Determine	
  se	
  uma	
  frase	
  de	
  entrada	
  lógica	
  proposicional	
  (em	
  FNC)	
  
é	
  sa2sfazível.	
  	
  	
  	
  
¨  Melhorias	
  sobre	
  a	
  enumeração	
  de	
  tabela	
  de	
  verdade:	
  	
  
1.  Terminação	
  rápida	
  
1.  A	
  cláusula	
  é	
  verdadeira	
  se	
  qualquer	
  literal	
  é	
  verdadeiro.	
  	
  
2.  Uma	
  sentença	
  é	
  falsa	
  se	
  qualquer	
  cláusula	
  é	
  false.	
  	
  	
  	
  
2.  Heurís2ca	
  do	
  símbolo	
  puro:	
  	
  
1.  Símbolos	
  puros	
  sempre	
  aparecem	
  com	
  o	
  mesmo	
  "sinal"	
  em	
  todas	
  as	
  
cláusulas.	
  	
  	
  
2.  E.g.,	
  nas	
  três	
  cláusulas	
  (A	
  ∨	
  ←B),	
  (←B	
  ∨	
  	
  ←C),	
  (C	
  ∨	
  A)	
  A	
  e	
  B	
  são	
  puros,	
  C	
  é	
  
impuro.	
  	
  	
  
3.  Fazer	
  um	
  literal	
  de	
  puro	
  símbolo	
  verdadeiro.	
  	
  
n 	
  	
  
3.  Heurís2ca	
  da	
  cláusula	
  de	
  unidade:	
  	
  
1.  Cláusula	
  de	
  unidade:	
  apenas	
  um	
  literal	
  na	
  cláusula	
  	
  
2.  O	
  literal	
  único	
  de	
  uma	
  cláusula	
  de	
  unidade	
  deve	
  ser	
  verdadeiro.	
  
Algor2mo	
  DPLL	
  
Algoritmo	
  WalkSAT	
  
¨  Algoritmo	
  de	
  busca	
  local,	
  incompleto.	
  
¨  Função	
  de	
  avaliação:	
  a	
  heurís2ca	
  de	
  conflito	
  mínimo	
  de	
  
minimizar	
  o	
  número	
  de	
  cláusulas	
  insa2sfeitas.	
  
¨  Equilíbrio	
  entre	
  avidez	
  e	
  aleatoriedade.	
  
The	
  WalkSAT	
  algorithm	
  
Problemas	
  de	
  diŠcil	
  sa2sfazibilidade	
  
¨  Considere	
  sentenças	
  aleatórias	
  em	
  3-­‐FNC	
  e.g.,	
  
¨  	
   (←D	
  ∨	
  ←B	
  ∨	
  C)	
  ∧	
  (B	
  ∨	
  ←A	
  ∨	
  ←C)	
  ∧	
  (←C	
  ∨	
  	
  ←B	
  ∨	
  E)	
  ∧	
  (E	
  
∨	
  ←D	
  ∨	
  B)	
  ∧	
  (B	
  ∨	
  E	
  ∨	
  ←C)	
  
¤  m	
  =	
  número	
  de	
  cláusulas	
  
¤  n	
  =	
  número	
  de	
  símbolos	
  
¤  Problemas	
  diŠceis	
  parecem	
  se	
  agregar	
  perto	
  de	
  m/n	
  =	
  4.	
  3	
  (ponto	
  
crí2co)	
  
Problemas	
  de	
  diŠcil	
  sa2sfazibilidade	
  
Problemas	
  de	
  diŠcil	
  sa2sfazibilidade	
  
¨  Mediana	
  do	
  tempo	
  de	
  execução	
  para	
  100	
  sentenças	
  sa2sfazíveis	
  aleatórias	
  
3-­‐FNC,	
  n	
  =	
  50	
  
Agentes	
  baseados	
  em	
  inferência	
  no	
  mundo	
  do	
  
Wumpus	
  
¨  Um	
  agente	
  de	
  mundo	
  do	
  Wumpus	
  usando	
  lógica	
  proposicional:	
  
¤  ←P1,1	
  	
  
¤  ←W1,1	
  	
  
¤  Bx,y	
  ⇔	
  (Px,y+1	
  ∨	
  Px,y-­‐1	
  ∨	
  Px+1,y	
  ∨	
  Px-­‐1,y)	
  	
  
¤  Sx,y	
  ⇔	
  (Wx,y+1	
  ∨	
  Wx,y-­‐1	
  ∨	
  Wx+1,y	
  ∨	
  Wx-­‐1,y)	
  
¤  W1,1	
  ∨	
  W1,2	
  ∨	
  …	
  ∨	
  W4,4	
  	
  
¤  ←W1,1	
  ∨	
  ←W1,2	
  	
  
¤  ←W1,1	
  ∨	
  ←W1,3	
  	
  
¤  …	
  
¨  ⇒ 64	
  símbolos	
  dis2ntos	
  de	
  proposição	
  64	
  à	
  155	
  frases	
  
¨  KB	
  contém	
  frases	
  "Šsicas"	
  por	
  cada	
  casa.	
  
¨  Para	
  cada	
  tempo	
  t	
  e	
  cada	
  local	
  [x,	
  y],	
  
¨  	
   Lx,y	
  ∧	
  OlhandoParaDireitat	
  ∧	
  ParaFrente⇒	
  Lx+1,y	
  	
  
¨  Rápida	
  proliferação	
  de	
  cláusula.	
  
Limitação	
  de	
  expressividade	
  da	
  lógica	
  
proposicional	
  
t	
  t	
  
Resumo	
  
¨  Agentes	
  lógicos	
  aplicam	
  inferência	
  a	
  uma	
  base	
  de	
  conhecimento	
  para	
  derivar	
  novas	
  
informações	
  e	
  tomar	
  decisões.	
  
¨  Conceitos	
  básicos	
  de	
  lógica:	
  	
  
¤  Sintaxe:	
  estrutura	
  formal	
  da	
  sentenças	
  
¤  Semân2ca:	
  verdade	
  das	
  sentenças	
  wrt	
  modelos	
  
¤  Entailment:	
  verdade	
  necessária	
  de	
  uma	
  sentença	
  dado	
  outra	
  	
  
¤  inferência:	
  derivação	
  de	
  sentenças	
  a	
  par2r	
  de	
  outras	
  
¤  solidez:	
  derivações	
  produzem	
  somente	
  implicações	
  de	
  sentenças	
  
¤  completude	
  :	
  derivações	
  podem	
  produzir	
  tudo	
  vinculadas	
  sentenças	
  
¨  Mundo	
  do	
  Wumpus	
  requer	
  a	
  capacidade	
  de	
  representar	
  informações	
  
parciais	
  e	
  negadas,	
  raciocínio	
  por	
  casos,	
  etc.	
  	
  
¨  Resolução	
  é	
  completa	
  para	
  alógica	
  proposicional.	
  
¨  Encadeamento	
  para	
  a	
  frente	
  e	
  para	
  trás	
  são	
  em	
  tempo	
  linear	
  e	
  completos	
  
para	
  cláusulas	
  de	
  Horn.	
  
¨  Falta	
  poder	
  expressivo	
  a	
  lógica	
  proposicional.