| Inicial | Temas | Manuales | Ejercicios | Exámenes | Documentación

Tema 16: Razonamiento con información incompleta

Índice

1. Razonamiento por defecto

1.1. Ejemplo de razonamiento por defecto

  • Ejemplo de razonamiento por defecto

    El animal 1 es un pájaro
    Normalmente, los pájaros vuelan.
    Por tanto, el animal 1 vuela.

  • Programa p1.pl 

    pajaro(animal_1).
vuela(X) :-
   pajaro(X),
   normal(X).

  • Modelos del programa p1.pl 

    {pajaro(animal_1)}
{pajaro(animal_1), vuela(animal_1)}
{pajaro(animal_1), normal(animal_1), vuela(animal_1)}
  • Consecuencia
    P1 |= vuela(animal_1)

  • Programa p2.pl 

    :- dynamic anormal/1.

pajaro(animal_1).
vuela(X) :-
   pajaro(X),
   \+ anormal(X).
    • Sesión
    ?- vuela(animal_1).
true.

  • Grafo de resolución 

                 vuela(animal_1) 
                   | 
             pajaro(animal_1),
             not anormal(animal_1)  
                   |
             not anormal(animal_1)  
                   |
            +------+-------+
            |              |
anormal((animal_1),       {}
!,                        Respuesta = {}
fail
 |
Fallo

1.2. Extensión del conocimiento

  • Nuevo conocimiento

    El animal 1 es un avestruz.
    Los avestruces son pájaros que no vuelan.

  • Programa extendido (p3.pl) 

    :- dynamic anormal/1.

pajaro(animal_1).
avestruz(animal_1).
vuela(X) :- 
   pajaro(X),
   \+ anormal(X).
anormal(X) :- avestruz(X).

  • Sesión 

    ?- vuela(animal_1).
false.

1.3. Cancelación reglas por defectos mediante reglas específicas

  • Tipos de reglas:
    • Regla por defecto: "Normalmente, los pájaros vuelan".
    • Regla específica: "Los avestruces no vuelan".
  • Razonamiento monótono y no monótono
    • Un razonamiento es monótono si P1 |= C y P2 extiende a P1, entonces P2 |= C.
    • Un razonamiento es no monótono si P1 |= C y P2 extiende a P1, es posible P2 |=/= C.

  • Programa objeto (p4.pl). 

    defecto((vuela(X) :- pajaro(X))).

regla((pajaro(X) :- avestruz(X))).
regla(((\+ vuela(X)) :- avestruz(X))).

regla((avestruz(animal_1) :- true)).
regla((pajaro(animal_2) :- true)).

1.4. Metaintérprete para razonamiento con defectos

  • El metaintérprete está definido en el fichero razonamiento_por_defecto.pl.

  • explica(A,E) se verifica si E es una explicación de A usando las reglas y los defectos. Por ejemplo, 

    ?- [p4, razonamiento_por_defecto].
true.

?- explica(vuela(X),E).
X = animal_2,
E = [defecto((vuela(animal_2):-pajaro(animal_2))),
     regla((pajaro(animal_2):-true))] ;
false.

?- explica(\+ vuela(X),E).
X = animal_1,
E = [regla((\+vuela(animal_1):-avestruz(animal_1))),
     regla((avestruz(animal_1):-true))] ;
false.

    Su definición es 

    % explica(A,E) se verifica si E es una explicación de A usando las
% reglas y los defectos. 
explica(A,E) :-
   explica(A,[],E).

% Metaintérprete para las reglas y los defectos.
explica(true,E,E) :- !.
explica((A,B),E0,E) :- !,
   explica(A,E0,E1),
   explica(B,E1,E).
explica(A,E0,E) :-
   prueba(A,E0,E).         
explica(A,E0,[defecto((A:-B))|E]) :-
   defecto((A:-B)),
   explica(B,E0,E),
   \+ contradiccion(A,E).

% Metaintérprete para las reglas.
prueba(true,E,E) :- !.
prueba((A,B),E0,E) :- !,
   prueba(A,E0,E1),
   prueba(B,E1,E).
prueba(A,E0,[regla((A:-B))|E]) :-
   regla((A:-B)),
   prueba(B,E0,E).

% contradiccion(A,E) se verifica si la explicación E es contradictoria
% con A.
contradiccion(\+ A,E) :- !,
   prueba(A,E,_E1).
contradiccion(A,E) :-
   prueba(\+ A,E,_E).

1.5. Explicaciones de hechos contradictorios

  • Programa objeto (p5.pl) 

    defecto(((\+ vuela(X))  :- mamifero(X))).
defecto((vuela(X)       :- vampiro(X))).
defecto(((\+ vuela(X))  :- muerto(X))).

regla((mamifero(X)      :- vampiro(X))).
regla((vampiro(dracula) :- true)).
regla((muerto(dracula)  :- true)).

  • Sesión 

    ?- [p5, razonamiento_por_defecto].
true.

?- explica(vuela(dracula),E).
E = [defecto((vuela(dracula):-vampiro(dracula))),
     regla((vampiro(dracula):-true))] ;
false.

?- explica(\+ vuela(dracula),E).
E = [defecto((not vuela(dracula):-mamifero(dracula))),
     regla((mamifero(dracula):-vampiro(dracula))),
     regla((vampiro(dracula):-true))] ;
E = [defecto((not vuela(dracula):-muerto(dracula))),
     regla((muerto(dracula):-true))] ;
false.

1.6. Cancelación entre defectos mediante nombres

  • Programa objeto (p6.pl) 

    defecto(mamiferos_no_vuelan(X),(\+ vuela(X)   :- mamifero(X))).
defecto(vampiros_vuelan(X),    (vuela(X)       :- vampiro(X))).
defecto(muertos_no_vuelan(X),  (\+ vuela(X)   :- muerto(X))).

regla((mamifero(X)      :- vampiro(X))).
regla((vampiro(dracula) :- true)).
regla((muerto(dracula)  :- true)).

regla((\+ mamiferos_no_vuelan(X) :- vampiro(X))).
regla((\+ vampiros_vuelan(X)     :- muerto(X))).

  • Modificación de explica (en razonamiento_por_defecto_con_nombres.pl) 

    explica(A,E0,[defecto(Nombre)|E]) :-
   defecto(Nombre,(A:-B)),
   explica(B,E0,E),
   \+ contradiccion(Nombre,E),
   \+ contradiccion(A,E).

  • Sesión 

    ?- [p6, razonamiento_por_defecto_con_nombres].
true.

?- explica(vuela(dracula),E).
false.

?- explica(\+ vuela(dracula),E).
E = [defecto(muertos_no_vuelan(dracula)),
     regla((muerto(dracula):-true))] ;
false.

2. Razonamiento abductivo

2.1. Problema de la abducción

  • El problema de la abducción consiste en
    • Dados
      • un programa P lógico y
      • una observación O (un hecho básico en el lenguaje de P).
    • Encontrar
      • una explicación E (es decir, una lista de hechos atómicos en el lenguaje de P cuyos predicados no son cabezas de cláusulas de P) tal que O es consecuencia de la unión de P y E.

2.2. Abducción para programas definidos

  • Programa objeto (p7.pl) 

    europeo(X) <- español(X).
español(X) <- andaluz(X).
europeo(X) <- italiano(X).

  • Sesión 

    ?- [razonamiento_abductivo, p7].
true.

?- abduce(europeo(juan),E).
E = [andaluz(juan)] ;
E = [italiano(juan)] ;
false.

  • Metaintérprete para razonamiento abductivo 

    :- op(1200,xfx,<-).

abduce(O,E) :-
   abduce(O,[],E).

abduce(true,E,E) :- !.
abduce((A,B),E0,E) :- !,
   abduce(A,E0,E1),
   abduce(B,E1,E).
abduce(A,E0,E) :-
   (A <- B),
   abduce(B,E0,E).
abduce(A,E,E) :-
   member(A,E).
abduce(A,E,[A|E]) :-
   \+ member(A,E),
   abducible(A).   

abducible(A) :-
   \+ (A <- _B).

2.3. Abducción para programas generales

  • Problemas al aplicar abducción a programas indefinidos

    • Programa objeto (p8.pl) 

      vuela(X)   <- pajaro(X), \+ anormal(X).
anormal(X) <- avestruz(X).
pajaro(X)  <- avestruz(X).
pajaro(X)  <- palomo(X).

    • Sesión 

      ?- [razonamiento_abductivo, p8].
true.

?- abduce(vuela(animal_1),E).
E = [\+anormal(animal_1),avestruz(animal_1)] ;
E = [\+anormal(animal_1),palomo(animal_1)] ;
false.
    • Problemas:
      • Explicación contradictoria
      • Explicación con predicado no abducible

  • Razonamiento abductivo para programas generales 

    :- op(1200,xfx,<-).

abduce(O,E) :-
   abduce(O,[],E).

abduce(true,E,E) :- !.
abduce((A,B),E0,E) :- !,
   abduce(A,E0,E1),
   abduce(B,E1,E).
abduce(A,E0,E) :-
   (A <- B),
   abduce(B,E0,E).
abduce(A,E,E) :-
   member(A,E).
abduce(A,E,[A|E]) :-
   \+ member(A,E),
   abducible(A),   
   \+ abduce_not(A,E,E).
abduce(\+ A,E0,E) :-
   \+ member(A,E0),
   abduce_not(A,E0,E).

abduce_not((A,B),E0,E) :- !,
   abduce_not(A,E0,E);
   abduce_not(B,E0,E).
abduce_not(A,E0,E) :-
   setof(B,(A <- B),L),
   abduce_not_l(L,E0,E).
abduce_not(A,E,E) :-
   member(\+ A,E).
abduce_not(A,E,[\+ A|E]) :-   
   \+ member(\+ A,E),   
   abducible(A),   
   \+ abduce(A,E,E).
abduce_not(\+ A,E0,E) :-
   \+ member(\+ A,E0),
   abduce(A,E0,E).

abduce_not_l([],E,E).
abduce_not_l([B|R],E0,E) :-
   abduce_not(B,E0,E1),
   abduce_not_l(R,E1,E).

abducible(A) :-
   A \= (\+ _X),
   \+ (A <- _B).

  • Sesión con el programa objeto anterior 

    ?- [razonamiento_abductivo_general, p8].
true.

?- abduce(vuela(animal_1),E).
E = [\+avestruz(animal_1),palomo(animal_1)] ;
false.

3. Diagnóstico mediante abducción

  • Representación de un sumador 

             +----+
X ----+->|    |S
      |  |xor1|--+--+             
Y --+-|->|    |  |  |             +----+
    | |  +----+  |  +------------>|    |
    | |          |                |xor2|---Suma
Z --|-|-------+--|--------------->|    |
    | |       |  |   +----+       +----+
    | +-------|--|-->|    |A1
    |         |  |   |and1|---+      
    +---------|--|-->|    |   |   +----+      
              |  |   +----+   +-->|    |
              |  |                |or1 |---Acarreo
              |  |   +----+   +-->|    |   
              |  +-->|    |A2 |   +----+   
              |      |and1|---+   
              +----->|    |  
                     +----+

  • Definición del sumador (sumador1.pl) 

    sumador(X,Y,Z,Acarreo,Suma) :-
   xor(X,Y,S),
   xor(Z,S,Suma),
   and(X,Y,A1),
   and(Z,S,A2),
   or(A1,A2,Acarreo).

and(1,1,1). 
and(1,0,0).
and(0,1,0).
and(0,0,0).

or(1,1,1).
or(1,0,1).
or(0,1,1).
or(0,0,0).

xor(1,0,1). 
xor(0,1,1). 
xor(1,1,0). 
xor(0,0,0).

tabla :-
   format('X Y Z A S~n'),
   tabla2.
tabla2 :-
   member(X,[0,1]),
   member(Y,[0,1]),
   member(Z,[0,1]),
   sumador(X,Y,Z,A,S),
   format('~a ~a ~a ~a ~a~n',[X,Y,Z,A,S]),
   fail.
tabla2.

  • Sesión con el sumador 

    ?- [sumador1].
true.

?- tabla.
X Y Z A S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
true.

  • Modelo de fallo del sumador (sumador.pl) 

    sumador(X,Y,Z,Acarreo,Suma) <-
  xorg(xor1,X,Y,S),
  xorg(xor2,Z,S,Suma),
  andg(and1,X,Y,A1),
  andg(and2,Z,S,A2),
  org(or1,A1,A2,Acarreo).

xorg(_N,X,Y,Z) <- xor(X,Y,Z).
xorg(N,1,1,1)  <- fallo(N=f1).
xorg(N,0,0,1)  <- fallo(N=f1).
xorg(N,1,0,0)  <- fallo(N=f0).
xorg(N,0,1,0)  <- fallo(N=f0).

andg(_N,X,Y,Z) <- and(X,Y,Z).
andg(N,0,0,1)  <- fallo(N=f1).
andg(N,1,0,1)  <- fallo(N=f1).
andg(N,0,1,1)  <- fallo(N=f1).
andg(N,1,1,0)  <- fallo(N=f0).

org(_N,X,Y,Z) <- or(X,Y,Z).
org(N,0,0,1)  <- fallo(N=f1).
org(N,1,0,0)  <- fallo(N=f0).
org(N,0,1,0)  <- fallo(N=f0).
org(N,1,1,0)  <- fallo(N=f0).

xor(1,0,1) <- true.
xor(0,1,1) <- true.
xor(1,1,0) <- true.
xor(0,0,0) <- true.

and(1,1,1) <- true.
and(1,0,0) <- true.
and(0,1,0) <- true.
and(0,0,0) <- true.

or(1,1,1) <- true.
or(1,0,1) <- true.
or(0,1,1) <- true.
or(0,0,0) <- true.

  • Diagnóstico mediante abducción 

    diagnostico(Observacion,Diagnostico) :-
   abduce(Observacion,Diagnostico).

:- abolish(abducible,2).
abducible(fallo(_X)).

diagnostico_minimo(O,D) :-
   diagnostico(O,D),
   \+ ((diagnostico(O,D1),
        subconjunto_propio(D1,D))).

subconjunto_propio([],Ys):-
   Ys \= [].
subconjunto_propio([X|Xs],Ys):-
   select(Ys,X,Ys1),
   subconjunto_propio(Xs,Ys1).

  • Sesión de diagnóstico 

    ?- [diagnosticador_abductivo, sumador].
true.

?- diagnostico(sumador(0,0,1,1,0),D).
D = [fallo(or1=f1),fallo(xor2=f0)] ;
D = [fallo(and2=f1),fallo(xor2=f0)] ;
D = [fallo(and1=f1),fallo(xor2=f0)] ;
D = [fallo(and2=f1),fallo(and1=f1),fallo(xor2=f0)] ;
D = [fallo(xor1=f1)] ;
D = [fallo(or1=f1),fallo(and2=f0),fallo(xor1=f1)] ;
D = [fallo(and1=f1),fallo(xor1=f1)] ;
D = [fallo(and2=f0),fallo(and1=f1),fallo(xor1=f1)] ;
false.

?- diagnostico_minimo(sumador(0,0,1,1,0),D).
D = [fallo(or1=f1),fallo(xor2=f0)] ;
D = [fallo(and2=f1),fallo(xor2=f0)] ;
D = [fallo(and1=f1),fallo(xor2=f0)] ;
D = [fallo(and2=f1),fallo(and1=f1),fallo(xor2=f0)] ;
D = [fallo(xor1=f1)] ;
D = [fallo(or1=f1),fallo(and2=f0),fallo(xor1=f1)] ;
D = [fallo(and1=f1),fallo(xor1=f1)] ;
D = [fallo(and2=f0),fallo(and1=f1),fallo(xor1=f1)] ;
false.

4. Defectos mediante abducción

  • Traducción del programa objeto (p9.pl) 

    no_vuela(X) <- mamifero(X), \+ mamifero_volador(X).
vuela(X)    <- vampiro(X), \+ vampiro_no_volador(X).
no_vuela(X) <- muerto(X), \+ muerto_volador(X).

mamifero(X)      <- vampiro(X).
vampiro(dracula) <- true.
muerto(dracula)  <- true.

mamifero_volador(X)   <- vampiro(X).
vampiro_no_volador(X) <- muerto(X).

:- abolish(abducible,1).
abducible(mamifero_volador(_)).
abducible(vampiro_no_volador(_)).
abducible(muerto_volador(_)).

  • Sesión 

    ?- [razonamiento_abductivo_general, p9].
true.

?- abduce(vuela(X),E).
false.

?- abduce(no_vuela(X),E).
X = dracula,
E = [\+muerto_volador(dracula)] ;
false.

5. Bibliografía

| Inicial | Temas | Manuales | Ejercicios | Exámenes | Documentación

José A. Alonso Jiménez

Sevilla, 07 de abril del 2024

Licencia: Creative Commons.