/* Exemples de clause:*/ cl1([-occ(gauche, croix, p1), -occ(droite, rond, p1), gagne(p1)]). cl2([-occ(droite, rond, p2), -occ(gauche, rond, p2), gagne(p2)]). cl3([-occ(gauche, rond, p2), -occ(droite, rond, p2), gagne(p2)]). %cl1([-occ(gauche,croix,P),-occ(_,croix,P),-occ(_,Y,P),-occ(droite,Y,P),gagne(P)]). bouquet1([bouquet(1),-contient(1,f1), -contient(1, f2), -rose(f1), -jaune(f1), -narcisse(f2), -blanche(f2)]). bouquet2([bouquet(2), -contient(2, f3), -contient(2, f4), -jonquille(f3), -jaune(f3), -rose(f4), -blanche(f4)]). bouquet3([bouquet(3), -contient(3, f5), -contient(3, f6), -jonquille(f5), -rose(f6), -blanche(f6)]). bouquetC1([bouquet(1),-contient(1,f1), -contient(1, f2), -fleur(rose,f1), -jaune(f1), -fleur(narcisse, f2), -blanche(f2), -inf(jonquille, narcisse), -inf(narcisse, narcisse)]). bouquetC2([bouquet(2), -contient(2, f3), -contient(2, f4), -fleur(jonquille, f3), -jaune(f3), -fleur(rose, f4), -blanche(f4), -inf(jonquille, narcisse),-inf(narcisse, narcisse)]). bouquetC3([bouquet(3), -contient(3, f5), -contient(3, f6), -fleur(jonquille, f5), -fleur(rose, f6), -blanche(f6), -inf(jonquille, narcisse)]). carte1([-couleur('Pique', a1), -couleur('Carreau', a2), -couleur('Carreau', a3), -hauteur('As', a1), -hauteur('As', a2), -hauteur('10', a3), paire(a1, a2)]). carte2([-couleur('Pique', b1), -couleur('Carreau', b2), -couleur('Trefle', b3), -hauteur('Roi', b1), -hauteur('Roi', b2), -hauteur('Roi', b3), paire(b1, b2), paire(b2, b3), paire(b1, b3), brelan(b1, b2, b3)]). carte3([-couleur('Coeur', c1), -couleur('Coeur', c2), -couleur('Trefle', c3), -hauteur('Dame', c1), -hauteur('Valet', c2), -hauteur('Dame', c3), paire(c1, c3)]). /* Exemples avec connaissance */ cs1([-forme(a, carre), -couleur(a, rouge), classe(a, c)]). cs2([-forme(b, triangle), -couleur(b, vert), classe(b, c)]). cc1([-forme(a, carre), -couleur(a, rouge), classe(a, c), -inf_(triangle,polygone), -inf_(carre, polygone)]). cc2([-forme(b, triangle), -couleur(b, vert), classe(b, c), -inf_(carre, polygone), -inf_(triangle,polygone)]). cc3([-forme(b, cercle), -couleur(b, vert), classe(b, c), -inf_(carre, polygone), -inf_(triangle,polygone)]). ccl1([-forme(a, carre), -couleur(a, rouge), classe(a, c), -inf_(carre, polygone), -inf_(triangle,polygone)]). ccl2([-forme(b, triangle), -couleur(b, vert), classe(b, c), -inf_(carre, polygone), -inf_(triangle,polygone)]). ccls1([-forme(a, carre), -couleur(a, rouge), classe(a, c)]). ccls2([-forme(b, triangle), -couleur(b, vert), classe(b, c)]). /* exemples de Bongard */ ex_2015_1([-carre(a), -triangle(b), -contient(b, a), -contient(o1, b), pos(o1)]). ex_2015_2([-carre(c), -carre(d), -contient(d, c), -contient(o2, c), pos(o2)]). ex_2015_3([-carre(e), -cercle(f), -triangle(g), -contient(f, e), -contient(o3, f), -contient(o3, g), pos(o3)]). ex_2015_1_ref([-forme(carre, a), -forme(triangle, b), -contient(b, a), -contient(o1, b), pos(o1), -inf(carre, polygone), -inf(triangle, polygone)]). ex_2015_2_ref([-forme(carre, c), -forme(carre, d), -contient(d, c), -contient(o2, c), pos(o2), -inf(carre, polygone), -inf(triangle, polygone)]). ex_2015_3_ref([-forme(carre, e), -forme(cercle, f), -forme(triangle, g), -contient(f, e), -contient(o3, f), -contient(o3, g), pos(o3), -inf(carre, polygone), -inf(triangle, polygone)]). b1([pos(1), - contient(1,o1), -contient(1,o2), -triangle(o1), -pointe(o1,down), -circle(o2)]). b2([pos(2), - contient(2,o3), -triangle(o3), -pointe(o3,down)]). b3([pos(b1), -contient(b1,o1), -contient(o1,o2), -triangle(o1), -carre(o2)]). b5([pos(b2), -contient(b2,o3), -carre(o3), -contient(o3, o4), -carre(o4)]). b6([pos(b1), -contient(b1,o1), -contient(o1,o2), -triangle(o1), -pointe(o1, down), -carre(o2)]). b7([pos(b2), -contient(b2,o3), -carre(o3), -contient(o3, o4), -cercle(o4), -contient(b2, o5), -triangle(o5)]). c1([pos(1), -contient(1,o1), -contient(o1,o2), -triangle(o1), -carre(o2)]). c2([pos(2), -contient(2,o3), -carre(o3), -contient(o3, o4), -carre(o4), -contient(2, o5), -triangle(o5), -contient(o5, o6), -cercle(o6)]). c3([pos(3), -contient(3,o7), -carre(o7), -contient(o7, o8), -carre(o8)]). /* exemples de Bongard 2 */ bb3([pos(b1), -contient(b1,o1), -contient(o1,o2), -triangle(o1), -carre(o2), -sup(carre(X), polygone(X)), -sup(triangle(Y), polygone(Y))]). bb5([pos(b2), -contient(b2,o3), -carre(o3), -contient(o3, o4), -carre(o4), -sup(carre(X), polygone(X)), -sup(triangle(Y), polygone(Y))]). bo3([pos(b1), -contient(b1,o1), -contient(o1,o2), -forme(triangle, o1), -forme(carre, o2), -sup(carre, polygone), -sup(triangle, polygone)]). bo5([pos(b2), -contient(b2,o3), -forme(carre, o3), -contient(o3, o4), -forme(carre, o4), -sup(carre, polygone), -sup(triangle, polygone)]). b4([pos(b2), -contient(b2,o3), -carre(o3), -contient(o3, o4), -carre(o4), -contient(b2, o5), -triangle(o5), -contient(o5, o6), -cercle(o6)]). /* exemples de Bongard 2 */ nb3([pos(b1), -contient(b1,o1), -contient(b1, o2), -dans(o1,o2), -forme(triangle, o1), -forme(carre, o2)]). nb4([pos(b2), -contient(b2,o3), -forme(carre, o3), -contient(b2, o4), -dans(o3, o4), -forme(carre, o4), -contient(b2, o5), -forme(triangle, o5), -contient(b2, o6), -dans(o5, o6), -forme(cercle, o6)]). nb5([pos(b2), -contient(b2,o3), -contient(b2, o4), -forme(carre, o3), -dans(o3, o4), -forme(carre, o4)]). nbb3([pos(b1), -contient(b1,o1), -contient(b1, o2), -dans(o1,o2), -forme(triangle, o1), -forme(carre, o2), -sup(carre, polygone), -sup(triangle, polygone)]). nbb4([pos(b2), -contient(b2,o3), -forme(carre, o3), -contient(b2, o4), -dans(o3, o4), -forme(carre, o4), -contient(b2, o5), -forme(triangle, o5), -contient(b2, o6), -dans(o5, o6), -forme(cercle, o6), -sup(carre, polygone), -sup(triangle, polygone)]). nbb5([pos(b2), -contient(b2,o3), -contient(b2, o4), -forme(carre, o3), -dans(o3, o4), -forme(carre, o4), -sup(carre, polygone), -sup(triangle, polygone)]). c11([pos(1), -contient(1,o1), -contient(1,o2), -dans(o1, o2), -triangle(o1), -carre(o2)]). c12([pos(2), -contient(2,o3), -carre(o3), -contient(2, o4), -dans(o3, o4), -carre(o4), -contient(2, o5), -triangle(o5), -contient(2, o6), -dans(o5, o6), -cercle(o6)]). c13([pos(3), -contient(3,o7), -carre(o7), -contient(3, o8), -dans(o7, o8), -carre(o8)]). c21([pos(1), -contient(1,o1), -contient(1,o2), -dans(o1, o2), -forme(triangle, o1), -forme(carre, o2)]). c22([pos(2), -contient(2,o3), -forme(carre, o3), -contient(2, o4), -dans(o3, o4), -forme(carre, o4), -contient(2, o5), -forme(triangle, o5), -contient(2, o6), -dans(o5, o6), -forme(cercle, o6)]). c23([pos(3), -contient(3,o7), -forme(carre, o7), -contient(3, o8), -dans(o7, o8), -forme(carre, o8)]). /* Exemples de Plotkin */ ex1([[-occ(un, croix, p1), -occ(deux, rond, p1), gagne(p1)], [-occ(un, croix, p2), -occ(deux, croix, p2), gagne(p2)]]). ex2([[-occ(deux, rond, p1), -occ(un, croix, p1), gagne(p1)], [-occ(un, croix, p2), -occ(deux, croix, p2), gagne(p2)]]). ex3([[-pair(2), -impair(3), -impair(2+3)], [-pair(8), -impair(7), -impair(8+7)]]). ex4([[-pair(2), -impair(3), -impair(2+3)], [-impair(7), -pair(8), -impair(8+7)]]). ex5([[-pair(2), -impair(3), -impair(2+3)], [-impair(7), -pair(8), -impair(7+8)]]). ex6([[-pair(2), -impair(3), -impair(2+3), -eq(2+3, 3+2), -eq(3+2, 2+3)], [-impair(7), -pair(8), -impair(7+8), -eq(7+8, 8+7), -eq(8+7, 7+8)]]). /* Test de subsomption */ test_subsomption(L, C) :- copie(L, LL),copie(C, CC), %print('LL = '), print(LL), print('; CC = '), print(CC),nl, subsume(LL, CC), renomage(C, CC,_). subsume([], _). subsume([L|D], C) :- filtrage(L, C), subsume(D, C). filtrage(L, [P|_]) :- copie(P, PP), filtre(L, P),renomage(P, PP, _). filtrage(L, [_|C]) :- copie(C, CC), filtrage(L, C), renomage(C, CC, _). filtre(L, P) :- var(L),!, unify_with_occurs_check(L, P). %L = P. filtre(_, P) :- var(P), !, fail. filtre(L, P) :- L == P,!. filtre(L, P) :- L =.. [FL|LL], P =.. [PL|PP], FL == PL, \+(FL = '[|]'),!, filtre(LL, PP). filtre([N], [M]) :- !,filtre(N, M). filtre([L|P], [N|M]) :- %copie([N|M],[NC|MC]), filtre(L, N), filtre(P, M),!.%, %renomage([N|M],[NC|MC],_). renomage(L, P, [[L,P]]) :- var(L), var(P),!. renomage(_, P,_) :- var(P), !, fail. renomage(L, _,_) :- var(L), !, fail. renomage(L, P,[]) :- L == P,!. renomage(L, P,In) :- L =.. [FL|LL], P =.. [PL|PP], FL == PL, \+(FL = '[|]'),!, renomage(LL, PP,In). renomage([N], [M],I) :- renomage(N, M,I),!. renomage([L|P], [N|M],Ins) :- renomage(L, N,In1), renomage(P, M,In2),!, compose_(In1, In2, Ins). compose_([],A,A). compose_([[L,P]|LL], Q, [[L,P]|R]) :- compatible([L,P],Q, NQ),!, compose_(LL,NQ,R). compatible([P,V], [[PP, VV]|L],R) :- V == VV, P == PP,!, compatible([P,V],L,R). compatible([P,V], [[PP, VV]|L],[[PP, VV]|R]) :- \+(V == VV), \+(P == PP),!, compatible([P,V],L,R). compatible([P,V], [[PP, VV]|L],[[PP, VV]|R]) :- \+(var(V)), V == VV, \+(P == PP),!, compatible([P,V],L,R). compatible(_, [],[]). copie(C, NC) :- asserta(marqueur(C)),!, retract(marqueur(NC)). /* Réduction d'une clause */ reduction(E,NE) :- reduire(E,ER), simplifier(ER,ES),!, reduction(ES,NE). reduction(E,E):- !. reduire(E, EL) :- copie(E, CE), !, app(_, E, EL), test_subsomption(CE, EL). simplifier([],[]). simplifier([A],[A]). simplifier([A,B|E],ES) :- A==B,!, simplifier([A|E],ES). simplifier([A,B|E],[A|ESS]) :- simplifier([A|E], ES), ES == [A|E],!, simplifier([B|E],ESS). simplifier([A,B|E],ESS) :- simplifier([A|E], ES), simplifier([B|ES],ESS). app(L, [LL|M], M) :- L = LL. app(L, [N|M], [N|P]) :- app(L, M, P). /* construction d'une s�lection */ select([C1, C2], [L1, L2]) :- app(L1, C1, _), app(L2, C2, _), anatomie(L1, Sgn, Pred), anatomie(L2, Sgn, Pred). anatomie(L, -, Pred) :- L =.. [-, Q],!, Q =.. [Pred|_]. anatomie(L, +, Pred) :- L =.. [Pred|_]. selects([C1, C2], L1, L2) :- bagof(L, select([C1,C2], L), K), eclater(K, L1, L2). eclater([], [], []). eclater([[L1, L2]|L], [L1|Q1], [L2|Q2]) :- eclater(L, Q1, Q2). /* Généralisation de deux clauses */ generalisation_cl2(C1, C2, C) :- generalisation_cl2([C1, C2], C). generalisation_cl2([C1, C2], C) :- selects([C1, C2], L1, L2), M1 =.. [p|L1], M2 =.. [p|L2], generalisation(M1, M2, M), M =.. [p|L],%, write(L), reduction(L, C). generalisation_cl(C1, C2, L) :- selects([C1, C2], L1, L2), M1 =.. [p|L1], M2 =.. [p|L2], generalisation(M1, M2, M), M =.. [p|L]. /* Généralisation de termes: algorithme de Plotkin */ generalisation(V1, V2, L) :- generalisation(V1, V2, L, _, _), !. generalisation(V1,V2,V1,[],[]) :- V1==V2, !. generalisation(V1,V2,T,[[L1,X]|Eps1],[[L2,X]|Eps2]) :- ss_termes_diff(V1,V2,L1,L2), remplacer([L1,L2],[V1,V2],X,[NV1,NV2]),!, generalisation(NV1,NV2,T,Eps1,Eps2). ss_termes_diff(V1,V2,L1,L2) :- \+(var(V1)),\+(var(V2)), V1=..[F,G1|A1], V2=..[F,G2|A2],G1==G2, longueur(A1,L), longueur(A2,L),!, /* meme arite */ W1=..[F|A1], W2=..[F|A2], ss_termes_diff(W1,W2,L1,L2). ss_termes_diff(V1,V2,L1,L2) :- \+(var(V1)),\+(var(V2)), V1=..[F,G1|A1], V2=..[F,G2|A2], longueur(A1,L), longueur(A2,L),!, /* meme arite */ ss_termes_diff(G1,G2,L1,L2). ss_termes_diff(V1,V2,V1,V2):-!. remplacer(_,[V1,V2],_,[V1,V2]) :- V1 == V2. remplacer([L1,L2],[T1,T2],X,[[NV1|NQ1],[NV2|NQ2]]):- \+(var(T1)), \+(var(T2)), T1=[V1|Q1],T2=[V2|Q2],!, remplacer([L1,L2],[V1,V2],X,[NV1,NV2]), remplacer([L1,L2],[Q1,Q2],X,[NQ1,NQ2]). remplacer([L1,L2],[V1,V2],X,[NV1,NV2]):- \+(var(V1)), \+(var(V2)), V1=..[F|Q1], V2=..[F|Q2],!, remplacer([L1,L2],[Q1,Q2],X,[NQ1,NQ2]), NV1=..[F|NQ1], NV2=..[F|NQ2]. remplacer([L1,L2],[V1,V2],X,[NV1,NV2]):- remplacer_t(L1,V1,X,NV1), remplacer_t(L2,V2,X,NV2). remplacer_t(L,T,X,X) :- T==L,!. remplacer_t(_,T,_,T) :- var(T). remplacer_t(L,T,X,NT) :- T=..[F|Q], remplacer_l(L,Q,X,NQ), NT=..[F|NQ]. remplacer_l(_,[],_,[]). remplacer_l(L,[T|Q],X,[NT|NQ]) :- remplacer_t(L,T,X,NT), remplacer_l(L,Q,X,NQ). longueur([],0):-!. longueur([_|M],N) :- longueur(M,P), N is P+1. ex_r6([c(a, b),c(c, d), c(a, e), c(e, f), t(e)]). ex_r7([c(aa, bb),c(aa, ee), c(ee, ff), t(ee)]).