20-LPO_na_Pratica

Prévia do material em texto

LPO	
  NA	
  PRÁTICA	
  
	
  
	
  
Símbolos	
  de	
  função	
  e	
  Datalog	
  
¨  Muitas	
  vezes	
  queremos	
  referir-­‐se	
  a	
  indivíduos	
  em	
  termos	
  de	
  
componentes.	
  
¤  Exemplos:	
  16:55.	
  Sentenças	
  em	
  Inglês	
  .	
  	
  Um	
  lista	
  de	
  classe.	
  
¨  Estendemos	
  a	
  noção	
  de	
   .	
  	
  Para	
  que	
  um	
  termo	
  possa	
  ser	
  
f(t1,	
  ...,	
  tn)	
  quando	
  f	
  é	
  um	
   e	
  o	
  ti	
  são	
  termos.	
  
¨  Em	
  uma	
  interpretação	
  e	
  com	
  uma	
  atribuição	
  de	
  variável,	
  o	
  termo	
  
f(t1,	
  ...,	
  tn)	
  denota	
  um	
  indivíduo	
  no	
  domínio.	
  
¨  Um	
  símbolo	
  de	
  função	
  e	
  uma	
  constante	
  podem	
  se	
  referir	
  a	
  uma	
  
infinidade	
  de	
  indivíduos.	
  
¨  Símbolos	
  de	
  função	
  são	
  usados	
  para	
  definir	
  estruturas	
  de	
  dados.	
  
3 
	
  
Usando	
  símbolos	
  de	
  funções	
  
	
  
l  Para	
  definirmos	
  a	
  relação	
  before(T1, T2), que	
  é	
  verdadeira	
  se	
  T1	
  ocorre	
  
antes	
  de	
  T2
	
  em	
  um	
  dia.	
  
l  Definimos	
  os	
  símbolos	
  de	
  função	
  am(H,M)	
  e	
  pm(H,M) e	
  então	
  definimos	
  a	
  
relação. 
before(am(H1, M1), pm(H2, M2)). 
before(am(12, M1), am(H2, M2)) ß H2 < 12. 
before(am(H1, M1), am(H2, M2))ß H1 < H2 ∧ H2 < 12. 
before(am(H, M1), am(H, M2)) ß M1 < M2. 
before(pm(12, M1), pm(H2, M2)) ß H2 < 12. 
before(pm(H1, M1), pm(H2, M2)) ß H1 < H2 ∧ H2 < 12. 
before(pm(H, M1), pm(H, M2)) ß M1 < M2. 
4 
	
  
Procedimento	
  de	
  prova	
  com	
  símbolos	
  de	
  
funções	
  
	
  
l  A	
  diferença	
  dos	
  procedimentos	
  anteriores	
  é	
  que	
  a	
  classe	
  de	
  termos	
  é	
  
expandida	
  com	
  os	
  símbolos	
  de	
  funções.	
  
l  Com	
  símbolos	
  de	
  funções	
  existem	
  infinitamente	
  muitos	
  termos.	
  
.	
  	
  
¤  Temos	
  que	
  assegurar	
  que	
  o	
  critério	
  de	
  seleção	
  para	
  selecionar	
  as	
  cláusulas	
  
seja	
  imparcial.	
  
¤  Um	
   (fair)	
  é	
  aquele	
  que	
  qualquer	
  cláusula	
  que	
  
está	
  disponível	
  para	
  ser	
  escolhida	
  será	
  escolhida	
  em	
  algum	
  momento.	
  
¤  É	
  completo	
  somente	
  se	
  o	
  critério	
  de	
  seleção	
  for	
  imparcial.	
  
5 
	
  
Procedimento	
  de	
  prova	
  com	
  símbolos	
  de	
  
funções	
  
	
  
¤  Usa	
  o	
  unificador	
  mais	
  geral.	
  
¤  Temos	
  que	
  tomar	
  cuidado	
  com:	
  a	
  variável	
  X	
  não	
  unifica	
  com	
  o	
  
termo	
  t	
  no	
  qual	
  X	
  ocorre,	
  e	
  ele	
  não	
  é	
  o	
  próprio	
  X.	
  
n  Suponha	
  que	
  o	
  símbolo	
  de	
  função	
  s	
  denota	
  a	
  função	
  sucessor,	
  onde	
  s(n)	
  
é	
  o	
  número	
  depois	
  de	
  n.	
  
n  Nesta	
  interpretação	
  não	
  existe	
  nenhum	
  	
  número	
  X	
  que	
  é	
  igual	
  ao	
  seu	
  
sucessor,	
  não	
  faz	
  sen]do	
  unificar	
  {X/s(X)}	
  
¤  Se	
  isso	
  for	
  permi]do	
  o	
  procedimento	
  de	
  prova	
  torna-­‐se	
  incorreto	
  
(unsound).	
  
Exemplo:	
  Listas	
  
¨  Uma	
  lista	
  é	
  uma	
  sequência	
  ordenada	
  de	
  elementos.	
  
¨  Vamos	
  usar	
  a	
  constante	
   	
  para	
  denotar	
  uma	
  lista	
  vazia	
  e	
  a	
  função	
  	
  	
  	
  	
  	
  	
  
	
  para	
  denotar	
  a	
  lista	
  com	
  o	
  primeira	
  elemento	
  H	
  e	
  o	
  resto	
  
da	
  lista	
  T.	
  N .	
  
¨  	
   	
  
¨  A	
  lista	
  que	
  contém	
  sue,	
  kim	
  e	
  é	
  randy	
  
 cons(sue,cons(kim,cons(randy,nil))) 
¨  	
   é	
  TRUE	
  se	
  a	
  lista	
  z	
  contém	
  os	
  elementos	
  de	
  X	
  
seguidos	
  pelos	
  elementos	
  de	
  Y	
  
	
  append(nil,Z,Z). 
 append(cons(A,X),Y,cons(A,Z))← append(X,Y,Z). 
7 
Procedimento	
  de	
  prova	
  top-­‐down	
  com	
  
símbolos	
  de	
  funções	
  
n  Considere	
  a	
  BC:	
  
append(c(A,X),Y,c(A,Z)) ß append(X,Y,Z)). 
append(nil,Z,Z). 
 
¤  Considere	
  a	
  query:	
  ?append(F,c(L,nil),c(l,c(i,c(s,c(t,nil))))). 
yes(F,L) ß append(F,c(L,nil),c(l,c(i,c(s,c(t,nil))))). 
 
¨  Resolve	
  com	
  append(c(A1,X1),Y1,c(A1,Z1)) ß append(X1,Y1, Z1)).	
  
Subs]tuição	
  {F/c(l,	
  X1),	
  Y1/c(L,	
  nil),	
  A1/l,	
  Z1/c(i,	
  c(s,	
  c(t,	
  nil)))}	
  
	
  
yes(c(l,X1),L) ß append(X1,c(L,nil),c(i,c(s,c(t,nil)))). 
	
  
¨  Resolve	
  com	
  append(c(A2,X2),Y2,c(A2,Z2)) ß append(X2,Y2,Z2)).	
  
Subs]tuição	
  {X1/c(i,	
  X2),	
  Y2/c(L,	
  nil),	
  A2/i,	
  Z2/c(s,	
  c(t,	
  nil))}	
  
	
  
yes(c(l,c(i,X2)),L) ß append(X2,c(L,nil),c(s,c(t,nil))). 
8 
Procedimento	
  de	
  prova	
  top-­‐down	
  com	
  
símbolos	
  de	
  funções	
  
yes(c(l,c(i,X2)),L) ß append(X2,c(L,nil),c(s,c(t,nil))). 
¤  Resolve	
  com	
  append(c(A3,X3),Y3,c(A3,Z3)) ß append(X3,Y3, Z3)). 
n  Subs]tuição	
  {X2/c(s,	
  X3),	
  Y3/c(L,	
  nil),	
  A3/s,	
  Z3/	
  c(t,	
  nil))}	
  
yes(c(l,c(i,c(s,X3))),L) ß append(X3,c(L,nil),c(t,nil)). 
¤  Escolhendo	
  a	
  primeira	
  cláusula	
  para	
  resolver	
  	
  
 append(c(A4,X4),Y4,c(A4,Z4)) ß append(X4,Y4, Z4)). 
n  Subs]tuição	
  {X3/c(t,	
  X4),	
  Y4/c(L,	
  nil),	
  A4/t,	
  Z4/nil}	
  
yes(c(l,c(i,c(s,c(t,X4)))),L) ß append(X3,c(L,nil),nil). 
¤  Não	
  existe	
  mais	
  nenhuma	
  cláusula	
  na	
  qual	
  a	
  cabeça	
  unifica	
  com	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
append(X3,c(L,nil),nil)	
  e	
  a	
  prova	
  falha	
  
9 
Procedimento	
  de	
  prova	
  top-­‐down	
  com	
  
símbolos	
  de	
  funções	
  
n  voltando....	
  
yes(c(l,c(i, c(s, X3))), L) ß append(X3, c(L, nil), c(t, nil)). 
n  E	
  escolhendo	
  a	
  segunda	
  cláusula:	
  append(nil , Z5, Z5)). 
n  Subs]tuição	
  {X3/nil),	
  Z5/c(t,	
  nil),	
  L/t}	
  
yes(c(l,c(i, c(s, nil))), t) ß . 
n  F	
  =	
  c(l,c(i,	
  c(s,	
  nil)))	
  e	
  	
  L	
  =	
  t	
  
10 
Exercícios	
  
¨  Considere	
  os	
  seguintes	
  fatos:	
  
	
  
Cachorros	
  são	
  animais.	
  Todos	
  os	
  animais	
  têm	
  prazer	
  com	
  a	
  
alimentação.	
  As	
  pessoas	
  gostam	
  dos	
  animais	
  que	
  elas	
  têm.	
  As	
  pessoas	
  
fazem	
  coisas	
  que	
  tragam	
  prazer	
  às	
  coisas	
  que	
  elas	
  gostam.	
  Fido	
  é	
  o	
  
cachorro	
  da	
  Maria.	
  
	
  
A.  Escreva	
  os	
  fatos	
  acima	
  como	
  um	
  conjunto	
  de	
  cláusulas	
  definidas.	
  
B.  Mostre	
  como	
  definir	
  uma	
  pergunta	
  que	
  ques]one:	
  “O	
  que	
  Maria	
  faz?”	
  
C.  Mostre	
  a	
  uma	
  derivação	
  SLD	
  para	
  a	
  pergunta	
  acima,	
  mostrando	
  as	
  
ligações	
  das	
  variáveis.	
  
11 
Exercícios	
  
l  Considere	
  o	
  seguinte	
  programa	
  lógico:	
  
	
  
F(nil, X,Y). 
f(cons(X,Y),W,Z) ß 
 f(Y,W,cons(X,Z)). 
	
  
l  Apresente	
  cada	
  uma	
  das	
  derivações	
  top-­‐down,	
  mostrando	
  as	
  
subs]tuições	
  para	
  a	
  pergunta:	
  
	
  
?f(cons(a,cons(b,cons(c,nil))),L,nil). 
Igualdade	
  
¨  Às	
  vezes,	
  dois	
  termos	
  denotam	
  o	
  mesmo	
  indivíduo.	
  
¨  Exemplo:	
  	
  
¤  Clark	
  Kent	
  e	
  Superman.	
  	
  
¤  4	
  ×	
  4	
  e	
  11	
  5.	
  	
  
¤  O	
  projetor	
  que	
  foiu]lizado	
  úl]ma	
  terça-­‐feira	
  e	
  este	
  projetor.	
  
¨  Em	
  LPO	
  podemos	
  usar	
  o	
   para	
  fazer	
  
declarações	
  dizendo	
  que	
  dois	
  termos	
  se	
  referem	
  ao	
  mesmo	
  
objeto:	
  
¤  pai(joão)=henrique 
¤  O	
  objeto	
  referido	
  por	
  pai(joão) e	
  o	
  objeto	
  referido	
  por	
  
henrique	
  são	
  iguais.	
  	
  
Igualdade	
  
13 
¨  O	
  termo	
  básico	
  t1	
  é	
   ao	
  termo	
  básico	
  t2,	
  escrito	
   ,	
  é	
  
verdade	
  na	
  interpretação	
  I	
  se	
  t1	
  e	
  t2	
  denotam	
  o	
  mesmo	
  
indivíduo	
  na	
  interpretação	
  I.	
  
¨  O	
  símbolo	
  de	
  igualdade	
  também	
  pode	
  ser	
  empregado	
  com	
  a	
  
negação	
  para	
  insis]r	
  no	
  fato	
  de	
  que	
  termos	
   são	
  o	
  mesmo	
  
objeto:	
  
¤  ∃X,Y irmão(X,ricardo) ٨۸ irmão(Y,ricardo) ٨۸ ¬(X = Y) 
¨  chair1	
  =	
  chair2	
  
¨  chair_on_right	
  =	
  chair2	
  
¨  chair_on_right	
  não	
  é	
  similar	
  a	
  chair2,	
   	
  a	
  chair2.	
  
A	
  igualdade	
  não	
  significa	
  similaridade	
  
Por	
  que	
  igualdade	
  	
  importante?	
  
¨  Em	
  um	
  consultório	
  médico,	
  o	
  médico	
  quer	
  saber	
  se	
  um	
  
paciente	
   que	
  ele	
  viu	
  na	
  semana	
  passada	
  
(ou	
  é	
  sua	
  irmã	
  gêmea).	
  
¨  Em	
  uma	
  inves]gação	
  criminal,	
  a	
  polícia	
  pretende	
  determinar	
  
se	
  alguém	
   que	
  a	
  pessoa	
  que	
  cometeu	
  
algum	
  crime.	
  
¨  Ao	
  comprar	
  um	
  interruptor	
  para	
  subs]tuição,	
  um	
  eletricista	
  
pode	
  querer	
  saber	
  se	
  ele	
  foi	
  construído	
  na	
   em	
  
que	
  os	
  interruptores	
  que	
  não	
  eram	
  confiáveis.	
  (E	
  se	
  é	
  um	
  
do	
  que	
  o	
  que	
  foi	
  subs]tuído	
  em	
  um	
  
momento	
  anterior).	
  
¨  Sem	
  afirmações	
  de	
  igualdade,	
  a	
  única	
  coisa	
  que	
  é	
  igual	
  a	
  um	
  
termo	
  básico	
  é	
  ele	
  mesmo.	
  
	
  Isso	
  pode	
  ser	
  capturado	
  como	
  se	
  você	
  ]vesse	
  a	
  afirmação	
  	
  	
  	
  	
  
	
  X	
  =	
  X.	
  A	
  igualdade	
  explícita	
  nunca	
  precisa	
  ser	
  usada.	
  
¨  Se	
  você	
  permi]r	
  afirmações	
  de	
  igualdade,	
  é	
  necessário	
  
derivar	
  o	
  que	
  decorre	
  delas.	
  Ou	
  se:	
  
¤  Axioma]za	
  a	
  igualdade	
  como	
  qualquer	
  outro	
  predicado,	
  ou	
  se	
  
¤  Constrói	
  máquinas	
  de	
  inferência	
  para	
  fins	
  específicos	
  para	
  a	
  igualdade	
  
Permi]ndo	
  afirma]vas	
  de	
  igualdade	
  
 X = X. 
 X = Y ← Y = X. 
 X = Z ← X = Y ∧ Y = Z. 
¨  Para	
  cada	
  símbolo	
  de	
  função	
  n-­‐aria	
  f	
  existe	
  uma	
  regra	
  da	
  forma	
  
 f(X1, . . . , Xn) = f(Y1, . . . , Yn) ← 
 X1 = Y1 ∧ ・ ・ ・ ∧ Xn = Yn. 
¨  Para	
  cada	
  símbolo	
  de	
  predicado	
  n-­‐ario	
  p,	
  existe	
  uma	
  regra	
  na	
  forma	
  
 p(X1, ...,Xn) ← 
 p(Y1, ...,Yn) ∧ X1 = Y1 ∧ ・ ・ ・ ∧ Xn = Yn. 
Axioma]zando	
  a	
  igualdade	
  
Raciocinador	
  especial	
  para	
  igualdade	
  
:	
  se	
  você	
  tem	
  t1	
  =	
  t2,	
  então	
  você	
  pode	
  subs]tuir	
  
qualquer	
  ocorrência	
  de	
  t1	
  por	
  t2.	
  
¤  Trate	
  a	
  igualdade	
  como	
  uma	
   ,	
  subs]tuindo	
  iguais	
  por	
  
iguais.	
  
¤  Você	
  seleciona	
  uma	
   para	
  cada	
  indivíduo	
  e	
  
reescrever	
  todas	
  as	
  outras	
  representações	
  nesta	
  representação.	
  
¨  Exemplo:	
  trate	
  a	
  sequência	
  de	
  dígitos	
  como	
  a	
  representação	
  
canônica	
  de	
  um	
  número.	
  
¨  Exemplo:	
  use	
  o	
  RA	
  de	
  um	
  aluno	
  como	
  a	
  representação	
  canônica	
  
para	
  os	
  alunos.	
  
¨  A	
  convenção	
  de	
  que	
  os	
  termos	
  básicos	
  diferentes	
  denotam	
  
indivíduos	
  diferentes	
  é	
  o	
  pressuposto	
  de	
  nomes	
  exclusivos	
  
(UNA).	
  
¨  Para	
  cada	
  par	
  de	
  termos	
  básicos	
  dis]ntos	
  t1	
  e	
  t2,	
  assumir	
  	
  	
  	
  	
  	
  	
  	
  
t1	
  ≠	
  t2,	
  onde	
  ”≠"	
  significa	
  "não	
  igual".	
  
¤  Exemplo:	
  Para	
  cada	
  par	
  de	
  cursos,	
  você	
  não	
  quer	
  ter	
  que	
  afirmar,	
  
math302	
  =	
  psyc303,	
  ...	
  
¨  Problemas:	
  Às	
  vezes,	
  a	
  pressuposição	
  de	
  nomes	
  exclusivos	
  é	
  
inadequada,	
  por	
  exemplo,	
  3	
  +	
  7	
  ≠	
  2	
  ×	
  5	
  é	
  errado.	
  
	
  
Pressuposição	
  de	
  Nomes	
  exclusivos	
  (UNA)	
  
¨  c	
  ≠	
  c’	
  para	
  cada	
  constante	
  dis]nta	
  c	
  e	
  c’.	
  
¨  f(X1,	
  .	
  .	
  .	
  ,	
  Xn)	
  ≠	
  g(Y1,	
  .	
  .	
  .	
  ,	
  Ym)	
  para	
  cada	
  símbolo	
  de	
  função	
  f	
  e	
  
g.	
  
¨  f(X1,	
  .	
  .	
  .	
  ,	
  Xn)	
  ≠	
  f	
  (Y1,	
  .	
  .	
  .	
  ,	
  Yn)	
  ←	
  Xi	
  ≠	
  Yi,	
  para	
  cada	
  símbolo	
  de	
  
função	
  f.	
  Existe	
  n	
  instancias	
  deste	
  esquema	
  para	
  cada	
  
símbolo	
  de	
  função	
  n-­‐ary	
  f	
  (um	
  para	
  cada	
  i	
  tal	
  que	
  1	
  ≤	
  i	
  ≤	
  n).	
  
¨  f(X1,	
  .	
  .	
  .	
  ,	
  Xn)	
  ≠	
  c	
  para	
  cada	
  símbolo	
  de	
  função	
  f	
  e	
  constante	
  c.	
  
¨  t	
  ≠	
  X	
  para	
  cada	
  termo	
  t	
  no	
  qual	
  X	
  parece	
  (no	
  qual	
  t	
  não	
  é	
  o	
  
termo	
  X).	
  
Axioma]zando	
  a	
  desigualdade	
  para	
  a	
  UNA	
  
¨  A	
  desigualdade	
  não	
  é	
  apenas	
  um	
  outro	
  predicado.	
  Há	
  um	
  
número	
  infinito	
  de	
  respostas	
  para	
  X	
  ≠	
  f	
  (Y).	
  
¨  Se	
  você	
  tem	
  um	
  subobje]vo	
  t1	
  ≠	
  t2,	
  para	
  termos	
  de	
  t1	
  e	
  t2,	
  
existem	
  três	
  casos:	
  
¤  t1	
  e	
  t2	
  não	
  se	
  unificam.	
  Neste	
  caso,	
  t1	
  ≠	
  t2	
  é	
  bem-­‐sucedido.	
  
¤  t1	
  e	
  t2	
  são	
  idên]cos	
  inclusive	
  com	
  as	
  mesmas	
  variáveis	
  nas	
  mesmas	
  
posições.	
  Aqui	
  t1	
  ≠	
  t2	
  falha.	
  
¤  Caso	
  contrário,	
  há	
  exemplos	
  de	
  t1	
  ≠	
  t2	
  que	
  tem	
  sucesso	
  e	
  casos	
  de	
  	
  	
  	
  	
  	
  	
  
t1	
  ≠	
  t2	
  que	
  falham.	
  
Procedimento	
  Top-­‐down	
  e	
  a	
  UNA	
  
¨  Lembre-­‐se:	
  na	
  resolução	
  SLD	
  você	
  pode	
  selecionar	
  qualquer	
  
subgoal	
  no	
  corpo	
  de	
  uma	
  cláusula	
  de	
  resposta	
  para	
  resolver	
  a	
  
seguir.	
  
:	
  só	
  selecionar	
  a	
  desigualdade	
  quando	
  ela	
  puder	
  ter	
  
sucesso	
  ou	
  falhar,	
  caso	
  contrário,	
  selecione	
  outro	
  
subgoal.	
  Assim,	
  você	
  estará	
   	
  as	
  metas	
  de	
  
desigualdade.	
  
¨  Se	
  só	
  restarem	
  as	
  submetas	
  de	
  desigualdade,	
  e	
  nenhuma	
  
falha,	
  a	
  consulta	
  será	
  bem-­‐sucedida.	
  
Implementando	
  a	
  UNA	
  
 não_em(X,[]). 
 não_em(X,[H|T]) ← X = H ∧ não_em(X,T). 
 bom_curso(C) ← curso(C) ∧ passou_analise(C). 
 curso(cs312). 
 curso(cs444). 
 curso(cs322). 
 passou_analise(C) ← algo_complicado(C). 
 
?não_em(C,[cs312,cs322,cs422,cs310,cs402]) ∧ bom_curso(C). 
Exemplo	
  de	
  desigualdade	
  
¨  Às	
  vezes	
  você	
  quer	
  assumir	
  que	
  um	
  banco	
  dedados	
  está	
  
completo.	
  Qualquer	
  fato	
  não	
  mencionado	
  é	
  falso.	
  
¤  Exemplo:	
  Supondo	
  que	
  um	
  banco	
  de	
  dados	
  de	
  relações	
  de	
  enrolled	
  
está	
  completo,	
  você	
  pode	
  definir	
  um	
  empty_course.	
  
¨  O	
  SRR	
  de	
  cláusulas	
  definidas	
  é	
   :	
  	
  
¤  A	
  adição	
  de	
  novas	
  clausulas	
  não	
  invalida	
  a	
  conclusão	
  anterior.	
  
¨  Com	
  o	
  pressuposto	
  de	
  conhecimento	
  completo	
  ele	
  passa	
  a	
  
ser	
   :	
  	
  
¤  Uma	
  conclusão	
  pode	
  ser	
  invalidada	
  ao	
  adicionar	
  mais	
  cláusulas.	
  
Pressuposição	
  do	
  Conhecimento	
  Completo	
  (CKA)	
  	
  	
  
¨  Suponha que as regra para o átomo a são: 
 a ← b1. 
 ... 
 a ← bn. 
 ou equivalentemente: a ← b1 ∨ ... ∨ bn. 
¨  Sobre a CKA, se a é verdade, um dos bi deve ser verdade: 
 a → b1 ∨ ... ∨ bn. 
¨  Sobre a CKA, as cláusulas para a significam a 
: 
 a ↔ b1 ∨ ... ∨ bn. 
CKA:	
  Caso	
  proposicional	
  
¨  Exemplo: Considere a relação definida por: 
 estudante(maria). 
 estudante(joão). 
 estudante(ying). 
¨  A CKA especifica que este três são os únicos alunos: 
 estudante(X) ↔ X = maria ∨ X = joão ∨ X = ying. 
¨  Para concluir ¬estudante(alan), você tem que pode provar 
 alan ≠ mary ^ alan ≠ john ∧ alan ≠ ying 
¨  Isto requer a pressuposição de nomes exclusivos (UNA).	
  
CKA:	
  Banco	
  de	
  dados	
  básico	
  
¨  A de uma cláusula: 
 p(t1, ... , tk) ← B. 
¨  É a cláusula: 
 p(V1,..., Vk) ← ∃W1 ... ∃Wm V1 = t1 ∧ … ∧ Vk = tk ∧ B. 
¨  Na qual V1, … ,Vk são k variáveis diferentes das 
presentes na cláusula original. 
¨  W1, … , Wm são as variáveis originais na cláusula.	
  
Forma	
  Normal	
  de	
  Clark	
  
¨  A forma normal de Clark de: 
 sala(C,sala208) ← 
 curso_cc(C) ∧ matriculado(C,E) ∧ E < 120. 
¨  é: 
 sala(X,Y) ← ∃C ∃E X = C ∧ Y = sala208 ∧ curso_cc(C) 
 ∧ matriculado(C,E) ∧ E < 120. 
Exemplo:	
  Forma	
  normal	
  de	
  Clark	
  
¨  Coloque todas as cláusulas para p na forma normal de Clark, com 
o mesmo conjunto de variáveis introduzidas: 
 p(V1, ... , Vk) ← B1. 
 … 
 p(V1, ... , Vk) ← Bn. 
¨  Isto é o mesmo que: p(V1, ... , Vk) ← B1 ∨ ... ∨ Bn. 
¨  A completude de Clark de p é a equivalência: 
 p(V1, ... , Vk) ↔ B1 ∨ ... ∨ Bn. 
¨  Isto é, p(V1, ... , Vk) é verdade se, e somente se, um dos Bi é 
verdadeiro, e cada uma das variáveis é universalmente 
quantificada.	
  
Completude	
  de	
  Clark	
  de	
  um	
  predicado	
  
¨  Dada a função membro (que denota se um elemento é 
membro de uma lista): 
 membro(X, [X|T]). 
 membro(X, [H|T]) ← membro(X, T). 
¨  Sua completude é: 
 membro(X, Y) ↔ (∃T Y = [X|T]) ∨ 
 (∃H ∃T Y = [H|T] ∧ membro(X, T)). 
Exemplo	
  da	
  completude	
  de	
  Clark	
  
¨  A	
   de	
  uma	
  base	
  de	
  conhecimento	
  consiste	
  
da	
  completude	
  de	
  cada	
  símbolo	
  de	
  predicado,	
  juntamente	
  com	
  
os	
  axiomas	
  para	
  igualdade	
  e	
  desigualdade.	
  	
  
¨  Se	
  você	
  ]ver	
  um	
  predicado	
  p	
  definido	
  pela	
  base	
  de	
  
conhecimento	
  sem	
  cláusulas,	
  sua	
  completude	
  é	
  p	
  ↔	
  false.	
  Isto	
  
é	
  ¬p.	
  	
  
¨  Você	
  pode	
  interpretar	
  negações	
  nos	
  corpos	
  da	
  cláusulas.	
  ∼p	
  
significa	
  que	
  p	
  é	
  falso	
  sobre	
  a	
  pressuposição	
  de	
  conhecimento	
  
completo.	
  Isso	
  é	
  chamado	
  de	
   .	
  
Completude	
  de	
  Clark	
  de	
  uma	
  BC	
  
¨  Anteriormente	
  não	
  poderíamos	
  definir	
  curso_vazio(C)	
  a	
  par]r	
  
de	
  um	
  banco	
  de	
  dados	
  de	
  fatos	
  matriculado(S,C).	
  	
  
¨  Isso	
  pode	
  ser	
  definido	
  usando	
  negação	
  como	
  falha:	
  	
  
 curso_vazio(C) ← 
 curso(C) ˄ 
 ∼tem_matriculados(C). 
	
  
 tem_matriculados(C) ← 
 matriculado(S,C). 
Usando	
  negação	
  como	
  falha 	
  	
  
C ß {} 
repita 
 ou selecione “h ← b1 ˄ … ˄ bm” ∈ BC tal que: 
 bi ∈ C para todo i, e h ∉ C; 
 C ß C ∪ {h} 
 ou selecione h tal que: 
 para cada regra “h ← b1 ˄ … ˄ bm” 
 ou para algum bi, ∼bi ∈ C 
 ou algum bi = ∼g e g ∈ C 
 C ß C ∪ {∼h} 
até que não seja mais possível fazer seleções 
Procedimento	
  de	
  prova	
  BoPom-­‐up	
  para	
  
negação	
  como	
  falha	
  
 
 p ← q ∧ ∼r. 
 p ← s. 
 q ← s. 
 r ← t. 
 t. 
 s ← w. 
Exemplo	
  de	
  Negação	
  como	
  falha	
  
¨  Se a prova para a falha, você pode concluir ∼a. 
¨  Falha e sucesso podem ser definidos recursivamente: 
¤  Suponha que você tenha as regras para o átomo a: 
 a ← b1 
... 
 a ← bn 
	
  
	
  Se	
  cada	
  corpo	
  bi	
  falha,	
  a	
  falha.	
  
	
  Se	
  um	
  corpo	
  bi	
  é	
  bem-­‐sucedido,	
  a	
  é	
  bem	
  sucedido.	
  
¨  Um	
  corpo	
  falha	
  se	
  uma	
  das	
  conjunções	
  no	
  corpo	
  falha.	
  	
  
	
  	
  Um	
  corpo	
  é	
  bem-­‐sucedido	
  se	
  todas	
  as	
  conjunções	
  são	
  bem	
  sucedidas.	
  
¨  Se	
  a	
  falhar,	
  ∼a	
  é	
  bem-­‐sucedido.	
  Se	
  a	
  bem-­‐sucedido	
  ∼a	
  falha.	
  
Procedimento	
  Top-­‐Down	
  para	
  Negação	
  
como	
  falha	
  
¨  Exemplo: 
¤  Existe	
  apenas	
  uma	
  resposta	
  para	
  a	
  pergunta	
  ?p(X),	
  ou	
  seja	
  	
  	
  X=	
  c.	
  
¨  Nas	
  chamadas	
  para	
  a	
  negação	
  como	
  falha	
  com	
  variáveis	
  
livres,	
  você	
  precisa	
   	
  os	
  obje]vos	
  com	
  negação	
  como	
  
falha	
  que	
  contenham	
  variáveis	
  até	
  que	
  as	
  variáveis	
  se	
  tonem	
  
ligadas.	
  
Variáveis	
  livre	
  na	
  negação