Egyszerű példák DLV-hez

1. A család

Feltételezve, hogy a családi viszonyokban az átlagember különösebb nehézség nélkül tud tájékozódni, vegyünk egy teljesnek nem mondható rokoni "adatbázist" és próbáljuk meg ennek DLV változatát megírni!

A családról ennyit tudunk, a "ki kinek a kije" szöveges elbeszélését mellőzve: 

Nagy János
Kis Zsuzsa
 |
 +--Nagy Róbert
 |
 +--Nagy Gábor
 |
 | Pásztor András
 | Kocsis Piroska
 |  |
 |  +--Pásztor János
 +-----Nagy Réka
        |
        +--Pásztor Edit
           Szabó Elek
            |
            +--Szabó Pál
            |  Varga Zsófia
            |   |
            |   +--Szabó Zsolt
            |   |
            |   +--Szabó Mária
            |
            +--Szabó Péter
               Kovács Anna
                |
                |  Juhász Tamás
                +--Szabó Erika
                    |
                    +--Juhász Orsolya
Kövessük a természetesen adódó logikát és az ismert tényeket "apja" és "anyja" kapcsolatokkal rögzítsük DLV-ben: 
apja( nagy_janos, nagy_robert ).
apja( nagy_janos, nagy_gabor ).
apja( nagy_janos, nagy_reka ).
anyja( kis_zsuzsa, nagy_robert ).
anyja( kis_zsuzsa, nagy_gabor ).
anyja( kis_zsuzsa, nagy_reka ).

apja( szabo_peter, szabo_erika ).
anyja( kovacs_anna, szabo_erika ).

apja( juhasz_tamas, juhasz_orsolya ).
anyja( szabo_erika, juhasz_orsolya ). 

apja( szabo_pal, szabo_zsolt ).
apja( szabo_pal, szabo_maria ).
anyja( varga_zsofia, szabo_zsolt ).
anyja( varga_zsofia, szabo_maria ).

apja( szabo_elek, szabo_pal ).
apja( szabo_elek, szabo_peter ).
anyja( pasztor_edit, szabo_pal ).
anyja( pasztor_edit, szabo_peter ).

apja( pasztor_janos, pasztor_edit ).
anyja( nagy_reka, pasztor_edit ).

apja( pasztor_andras, pasztor_janos ).
anyja( kocsis_piroska, pasztor_janos ).
(Sajnos a nagybetűkről és az ékezetekről most le kellett mondanunk.)

A szokásos példa ezek után a nagyszülők megkeresése lenne, de ennél markoljunk kicsit nagyobbat és vegyük rá a DLV-t rögtön arra, hogy az összes őst feltérképezze!

1.1 Az ősök

Ehhez először is vezessük be a "szülő" predikátumot, ami később megkímél attól, hogy minden esetben apára és anyára külön hivatkozzunk: 
szuloje( A, B ) :- apja( A, B ).
szuloje( A, B ) :- anyja( A, B ).
Ezt nagyjából úgy lehet felolvasni, hogy "B-nek A akkor szülője, ha A B-nek apja, vagy anyja".

Logikus, hogy ha valaki valakinek szülője, akkor őse is: 

ose( A, B ) :- szuloje( A, B ).
Viszont ez még nem elég, mert ennél tovább kell lépnünk, ki kell egészítenünk, hogy a nagyszülőket, dédszülőket, stb. is megtalálja a DLV. Valamiféle iterációra lesz szükségünk, ami a szülőre újra alkalmazza az őse szabályt és mindaddig halad, míg talál valamit.

A két személy, azaz a szülő (ős) és a gyermek (leszármazott) közé belép egy harmadik személy, akiről annyit tudunk, hogy az ősnek gyermeke, de a leszármazottnak őse: 

ose( A, B ) :- ose( A, X ), ose( X, B ).
A többi a DLV dolga, fel is göngyölíti szépen pl. Juhász Orsolya felmenőit, ha feltesszük neki a megfelelő kérdést: 
ose( A, juhasz_orsolya )?

DLV>dlv.mingw.exe -brave family_2.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

nagy_janos
nagy_reka
kis_zsuzsa
szabo_peter
szabo_erika
kovacs_anna
juhasz_tamas
szabo_elek
pasztor_edit
pasztor_janos
pasztor_andras
kocsis_piroska
A teljes program az adatdefiníciós rész nélkül (az fentebb olvasható) a következő volt: 
szuloje( A, B ) :- apja( A, B ).
szuloje( A, B ) :- anyja( A, B ).

ose( A, B ) :- szuloje( A, B ).
ose( A, B ) :- ose( A, X ), ose( X, B ).
A program teljes forráskódja.

Keressünk valami nehezebben áttekinthetőbbet (főleg a fentinél bővebb adathalmaznál)!

1.2 Unokatestvérek

Az unokatestvérem a szülőm testvérének gyermeke. Magyarázzuk el ezt valahogy a DLV-nek is!

Először is tudatnunk kell vele, mit értünk testvér alatt. Testvérek azok a gyermekek, akiknek a szülei ugyanazok. (Életszerűbb féltestvér szituációk az olvasóra bízva!) 

testvere( A, B ) :- szuloje( X, A ), szuloje( X, B ), A != B.
A törzs harmadik tagja magyarázatra szorul: elhagyása esetén ugyanis minden gyermek a saját maga testvére is lenne, ami ugyan a gép szempontjából logikus, csak mi nem ilyen választ szeretnénk, ezért ezt az esetet külön ki kell zárnunk azzal, hogy a behelyettesítés során A nem egyezhet meg B-vel.

A DLV a szülő-gyermek kapcsolatot már ismeri, most már tudja, mi a testvér, így megadhatjuk az unokatestvér szabályát: 

unokatestvere( A, B ) :- szuloje( X, A ), testvere( X, Y ), szuloje( Y, B ).
Emberi nyelven kiolvasva körülbelül így szól: "A és B akkor unokatestvérek, ha létezik X és Y testvérek, akik közül X A-nak és Y B-nek szülője". Azt, hogy saját magunk unokatestvére legyünk, a testvér szabály szerencsére már kizárja.

Lássuk, hány unokatestvért talál a DLV! 

unokatestvere( A, B )?

DLV>dlv.mingw.exe -brave family_3.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

szabo_erika, szabo_zsolt
szabo_erika, szabo_maria
szabo_zsolt, szabo_erika
szabo_maria, szabo_erika
A program teljes forráskódja.

Persze így mindenki kétszer szerepel.

Lássunk egy kissé még nehezebb feladatot!

1.3 A sógorok

A sógorom a leánytestvérem férje. Itt már a nemekre is vigyázni kell, de szerencsére az alapadataink apa és anya megkülönböztetése ezt, amennyire most szükséges, biztosítja. Van már testvér szabályunk is, de férj, feleség nincs.

Legyünk az egyszerűség kedvéért bigottak és tételezzük fel, hogy csak azok az igazi párok, melyeknek gyermekük is van, továbbá nincs a rendszerben válás és hasonló zavaró tényezők! :)

Először tehát a "párja" szabály: 

parja( A, B ) :- apja( A, X ), anyja( B, X ).
parja( A, B ) :- anyja( A, X ), apja( B, X ).
A szimmetria biztosítja, hogy a behelyettesítés ne legyen később "féloldalas". "Testvér" szabályunk már van, jöhet a "sógor": 
sogora( A, B ) :- testvere( A, X ), parja( X, B ).
Ellenőrizzük! 
sogora( A, B )?

DLV>dlv.mingw.exe -brave family_4b.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

nagy_robert, pasztor_janos
nagy_gabor, pasztor_janos
szabo_peter, varga_zsofia
szabo_pal, kovacs_anna
A program teljes forráskódja.

Elrontottunk valamit? Igen! :)

Szabó Péternek és Pálnak nem lett volna szabad előbukkanni. Ők ugyanis fiútestvérek és a párjuk nő. :) Sógornőnek persze jó, de mi szigorúbbak akarunk lenni.

A "testvére" szabállyal nem tudunk mit kezdeni, mert nem hordozza a nemet, mint információt, ám a "párja" átalakítható: 

ferje( A, B ) :- apja( A, X ), anyja( B, X ).
felesege( A, B ) :- anyja( A, X ), apja( B, X ).

parja( A, B ) :- ferje( A, B ).
parja( A, B ) :- felesege( A, B ).

sogora( A, B ) :- testvere( A, X ), ferje( B, X ).
sogornoje( A, B ) :- testvere( A, X ), felesege( B, X ).
Futtassuk: 
sogora( A, B )?

DLV>dlv.mingw.exe -brave family_4c.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

nagy_robert, pasztor_janos
nagy_gabor, pasztor_janos
A program teljes forráskódja.

sogornoje( A, B )?

DLV>dlv.mingw.exe -brave family_4d.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

szabo_peter, varga_zsofia
szabo_pal, kovacs_anna
A program teljes forráskódja.

A további rokoni fokokat a kedves olvasó kedvére kidolgozhatja.