Marcel Słabosz, Łukasz Hayn

?-PROLOG

Spis treści

?-PROLOG........................................................................................ 1
Spis treści........................................................................................ 1
Język Prolog..................................................................................... 1
Czym jest język prolog. ..................................................................... 2
Co to jest obiekt w prologu. ............................................................... 2
Składniki kodu prologu ...................................................................... 2
Klauzula Horna ................................................................................. 2
Komentarze ..................................................................................... 3
Termy ............................................................................................. 3
Stałe ............................................................................................... 3
Zapytania w języku prolog ................................................................. 4
Zmienne .......................................................................................... 4
Łączenie zapytań .............................................................................. 5
Nawracanie ...................................................................................... 6
Reguły............................................................................................. 6
Zasięg zmiennych ............................................................................. 6
Struktury ......................................................................................... 6
Operatory ........................................................................................ 7
Predykat is....................................................................................... 7
Równość i unifikacja.......................................................................... 7
Arytmetyka ...................................................................................... 7

Wybrane predykaty porównania ....................................................... 8
Wybrane predykaty arytmetyczne:................................................... 8
Predykaty obliczania - przykład: ...................................................... 9

Listy................................................................................................ 9

Sprawdzanie przynależności do listy ................................................. 9

Predykaty wbudowane..................................................................... 10
Kompilacja do exe........................................................................... 11
Przykłady....................................................................................... 12

Obliczanie silni: ........................................................................... 12
Zagadka Morderstwo .................................................................... 12
Zagadka „Wyścig” ........................................................................ 14
„Rozkład lotów” ........................................................................... 15
Zagadka Einsteina........................................................................ 16

Słownik ......................................................................................... 19

Język Prolog

Początki języka prolog sięgają 1970 roku. Od tego czasu jest on używany
w wielu bardzo różniących się od siebie dziedzinach:

 Relacyjne bazy danych
 Logika matematyczna
 Rozwiązywanie problemów abstrakcyjnych
 Symboliczne rozwiązywanie równań
 Automatyzacja projektowania.

Czym jest język prolog.

Język prolog można uznać za

język opisowy i deklaratywny

.

Programowanie w prologu nie polega na opisywaniu algorytmu, jak to ma
miejsce

w

klasycznych

językach

programowania.

Zamiast

tego

programiści zajmują się formalnymi relacjami i obiektami związanymi z
danym problemem, badając które relacje są prawdziwe a, które fałszywe
dla szukanego rozwiązania.
Prolog na podstawie danego zbioru faktów wnioskuje nowe, a jedynie w
nielicznych przypadkach działa na podstawie jawnie określonych instrukcji
sterowania. Prolog opiera się o rachunek predykatowy pierwszego
rzędu, jednak ogranicza się tylko do klauzul Horna.

Co to jest obiekt w prologu.

Mówiąc o obiektach w języku prolog nie należy ich mylić z dobrze znanymi
nam obiektami z języków obiektowych takich jak C++ czy Java. W
językach obiektowych określenie to stosujemy do struktur które można
podzielić na pola i metody czyli funkcje składowe tych klas. W języku
prolog natomiast obiektem nazywamy byty które można opisać
termami.

Składniki kodu prologu

Prolog zawiera ujednoliconą strukturę danych, term na bazie której
tworzone są wszystkie dane oraz same programy Prologu.
Program prologowy składa się ze

zbioru klauzul

, a każda klauzula to

jedna z poniższych możliwości:

 Deklaracja faktów dotyczących obiektów i związków między nimi
 Definicja reguł dotyczących obiektów i związków miedzy nimi
 Zapytania o obiekty i związki między nimi.

Klauzula Horna

Klauzula Horna to klauzula, w której co najwyżej jeden element jest
niezanegowany. Przykładem takiej klauzuli jest {p,¬r,¬q}.

Klauzule Horna zapisuje się zwykle w postaci implikacyjnej:
p ← r ∧ q

albo w postaci "Prologowskiej":

p :- r, q.

/* komentarz: ta linijka zostanie objaśniona

później */

Komentarze

W poprzednim dziale w kodzie umieszczono znaczniki:

/* treść komentarza */

Jest to komentarz. Tak jak w innych językach programowania pozwala on
na umieszczanie objaśnień, ale nie jest interpretowany podczas
wykonywania kod.

Termy

Jak już wcześniej wspomniano program Prolog składa się z term czyli
stałych zmiennych bądź struktur. nazwy term mogą składać się z:

 dużych liter (bez znaków z ogonkami, Ą, Ę, Ć, Ż, Ź, Ó, Ł, itd.)
 małych liter (bez znaków z ogonkami)
 cyfr
 znaków specjalnych (symbole): +, -, *, /, \, ~, ^, <, >, :, ., ?, @,

#, $, &, _

Stałe

Stałe nazywają konkretne obiekty i konkretne relacje. Istnieją dwa rodzaje
stałych atomy i liczby całkowite.
Stałe typu atom dzielimy na:

 zawierające same litery ewentualnie podkreślenia:

np. kinga, gazeta, rower, rafal, ida_do_kina

 zawierające same symbole:

np. ?- i :-

Stałem zaczynają się od małej litery. Jeśli zaś chcemy nazwę rozpocząć od
dużej litery musimy ją zawrzeć w znaku pojedynczych cudzysłowów.

Zapytania w języku prolog

Zapytanie w języku prolog wygląda tak samo jak fakt jednak na początku
linijki umieszczamy symbol

?-

np.

/* fakty */

posiada(maria, gazeta).

/* maria podziała gazeta */

posiada(maria, rower).

/* maria podziała rower */

/* zapytanie */

?- posiada(maria, gazeta).

/* czy „maria podziała gazeta” ?

*/

Powyższe

zapytanie

spowoduje

przeszukanie

zbioru

wcześniej

zadeklarowanych faktów i jeśli znajdzie odpowiedni zwróci informacje

yes

jeśli zaś nie odszuka faktów wskazujących na to że maria posiada gazetę
to odpowie

no

. Należy zauważyć, że prolog odpowie na pytanie no zawsze

wtedy gdy nie może odnaleźć faktów łączących dane obiekty relacją, ale
również wtedy gdy zadamy pytanie które nie jest zrozumiałe dla Prologu.
Np.:

?- ma(maria, gazeta).

/* czy „maria ma gazeta” ? NIE JEST

RÓWNOZNACZNE z czy „maria podziała gazeta” ?*/

Zmienne

Zmienne w swojej formie przypominają atomy jednak zaczynają się od
dużej litery. Zmienne należy traktować jako zastępstwo obiektu, którego
w danej chwili nie można nazwać.
np. X, Ktos, Cos, Kinga (pisane od dużej litery też oznacza zmienną a
nie osobę o imieniu Kinga).

Jeżeli chcielibyśmy zadać pytanie co posiada maria w powyższy sposób,
musielibyśmy zadawać pytania o każdy obiekt zapisany w bazie.
Wygodniej jednak było by zadać pytanie tak aby Prolog automatyczne
zwrócił nam listę posiadanych obiektów. Do tego celu służą właśnie
zmienne.
Jeśli nie zdefiniujemy co zawiera dana zmienna nazywamy ją zmienna
nieukonkretnioną. Jeśli jednak do zmiennej przypiszemy jakiś obiekt
nazywany ją zmienną ukonkretnioną.
Jak więc zadać pytanie tak aby otrzymać całą listę posiadanych obiektów?

?- posiada(maria, X).

X jest zmienną nieukonkretnioną. Dlatego to zapytanie spowoduje że do
zmiennej X zostanie przypisany efekt poszukiwania. Gdy wykonamy
zapytanie otrzymamy odpowiedź:

X = gazeta;

Prolog ukonkretnił zmienna i teraz czeka na dalsze polecenia. Jeśli wynik
jest dla nas zadowalający to naciskamy

.

i [

enter

] kończąc działanie. Jeśli

zaś chcemy odnaleźć kolejne wyniki naciskamy

;

. Spowoduje to usunięcie

przypisania obiektu gazeta do zmiennej X i dalsze przeszukiwanie faktów:

X = rower

Jest to już ostatni pasujący fakt więc prolog zakończy wykonywanie
zapytania.
Jeżeli zmienna była by wcześniej ukonkretniona to zapytanie było by
potraktowane jako sprawdzenie czy istnieje konkretny fakt.


Zmienne anonimowe to takie, których wartość nas nie interesuje. Zmienną
taką oznacza się pojedynczym podkreśleniem.
np. Czy ktoś ma gazeta?

?- posiada(_, gazeta).
More?

Pytanie wyświetli

More

? jeśli znaleziono zgodne stałe i

no

jeśli nie

znaleziono.

Łączenie zapytań

Załóżmy że w bazie mamy poniższe fakty:

lubi(kinga, kino).
lubi(rafal, rowery).
lubi(kinga, joga).
lubi(rafal, kino).

Jeśli chcielibyśmy zapytać co lubi kinga i rafal możemy dokonać
koniunkcji. Koniunkcje w Prologu oznaczamy znakiem

,

. Nasze zapytanie

będzie wyglądało następująco:

?- lubi(kinga, Z) , lubi(rafal, Z).

Aby otrzymać listę wszystkich przedmiotów zastosowaliśmy zmienną Z.
Program prolog najpierw wyszuka fakty pasujące do

lubi(kinga,Z)

i

przypisze je do Z pierwszy pasujący obiekt czyli kino. Następnie sprawdzi
czy istnieje fakt

lubi(rafal,kino)

. Jeśli tak to wyświetli nam

Z = kino

i

będzie oczekiwał na dalsze polecenia. Jeśli ciekawi nas więcej odpowiedzi
naciskamy

;

. Zostanie odnaleziony następny fakt zgodny z

lubi(kinga,Z)

.

czyli

Z = joga

, a następnie prolog sprawdzi czy rafal też lubi joga.

Ponieważ nie ma takiego faktu joga zostaje odrzucona.

Innym łącznikiem faktów i reguł jest alternatywa. W prologu oznacza się
ją jako

;

.

Nawracanie

W poprzednim rozdziale podczas wyszukiwania obiektów pasujących do
złożonych warunków prolog zastosował nawracanie. W momencie gdy
znalazł pierwszy obiekt pasujący do

lubi(kinga, Z)

i przypisał do Z obiekt

kino, również oznaczył miejsce w którym się w tej chwili znajdował
wskaźnikiem. W następnym kroku sprawdził czy

lubi(rafal, kino)

, a gdy

ustalił już wynik sprawdzenia tego warunku powrócił do wcześniej
zaznaczonego miejsca w celu poszukiwania kolejnych obiektów zgodnych z

lubi(kinga, Z)

.

Reguły

W języku prolog reguła składa się z głowy i treści, połączonych ze sobą
znakami

:-

i zakończonych znakiem "

.

". Znak

:-

można traktować jako

łącznik

jeżeli

.

lubi(rafal, kinga) :- lubi(kinga, Z) , lubi(rafal, Z).

Powyższa reguła mówi że rafal lubi kinga jeżeli lubią wspólnie jakiś
obiekt.

Zasięg zmiennych

Podobnie jak w innych językach programowania prolog rozróżnia
parametry wywołania od parametrów formalnych. Posłużmy się
przykładem:

osoba(kinga).
osoba(rafal).
lubi(kinga, kino).
lubi(rafal, kino).
lubi(kinga, X) :- lubi(X, kino).

/* kinga lubi wszystko co

lubi kino. */

ida_do_kina(X,Y) :- lubi(X,Y), osoba(Y).

/* X idzie do kina z

Y, jeżeli X lubi Y i Y jest osobą */

Z kim kinga idzie do kina?:

?- ida_do_kina(kinga, X).
X = kinga;
X = rafal;

Pomimo że zmienna X i Y została wykorzystana wielokrotnie, prolog
zapamiętał poszczególne jej wystąpienia jako inne zmienne.

Struktury

Strukturami nazywamy termy złożone czyli takie obiekty ,w których skład
wchodzą inne obiekty.
Struktury w prologu zapisujemy podając funktor oraz jego składniki.
Nazwa funktora odpowiada typom w innych językach programowania.
Składniki

umieszczamy

w

nawiasach

okrągłych

rozdzielając

je

przecinkami.

posiada(maria,ksiazka(wichrowe_wzgorza,autor(emily,bronte))).

ksiazka to struktura zawierająca w sobie tytuł i kolejną strukturę autor
która zaś składa się z imienia i nazwiska.
Teraz możemy zadać pytanie: Czy maria posiada jakąkolwiek książke
autora o nazwisku bronte? I jaki jest jej tytuł?

?- posiada(maria, ksiazka(X,autor(_,bronte))).

Operatory

Niektóre funktory wygodniej jest zapisać jako operatory np.
x * y + z
Podane wyrażenie można również zapisać jako strukturę term Prologu:
+(*(x, y),z).
Tak jak w innych językach ważną wiedzą podczas używania operatorów
jest to gdzie to umieszczać, jaki jest jego priorytet i łączość.

Predykat is

Należy pamiętać ze struktury zawierające operatory są strukturami takimi
jak wszelkie inne. Aby je wykonać, konieczne jest użycie predykatu is.

Równość i unifikacja

Infiksowi operator

=

zapisany jako

?- X = Y

Prolog będzie się starał dopasować X i Y a jeśli się to uda, cel jest
uzgodniony. O unifikacji można myśleć jak o próbie uczynienia X i Y
równymi.
Poniższy przykład spowoduje ukonkretnienie zmiennej X obiektem rower:

jezdzi(student, rower) = jezdzi(student, X).

Arytmetyka

prolog posiada wbudowane predykaty służące porównywania i obliczania.

Wybrane predykaty porównania

Wśród predykatów służących do porównywania najważniejsze:

X =:= X

/* X i Y są samą liczbą */

X =\= X

/* X i Y są różnymi liczbami */

X < Y

/* X mniejsze od Y */

X > Y
X =< Y

/* X mniejszy bądź równy Y, proszę zwrócić uwagę na

różnice w innych językach stosuje się <= */

X >= Y

Przykład:
Załóżmy ze predykat

włada(X,Y,Z)

jest uzgadniany, jeśli książę o imieniu

X sprawował władzę pomiędzy X a Y rokiem. W bazie zapisujemy poniższe
fakty:

wlada(rhodri, 844, 878).
wlada(anarawd, 878, 916).
wlada(hywel_dda, 916, 950).

Zdefiniujmy teraz predykat:

ksiaze(X,Y) :-
wlada(X,A,B),
Y >= A,
Y =< B.

Zadając teraz pytanie:

?- ksiaze(X,916).

Otrzymam odpowiedź:

X = anarawd;
X = hywel_dda;
yes

Wybrane predykaty arytmetyczne:

X + Y
X – Y
X * Y
X / Y
X // Y

/* dzielenie całkowite */

X mod Y

/* reszta z dzielenia */

Predykaty obliczania - przykład:

droga(krakow_bochnia, 40).

/* pomiędzy Krakowem a Bochnią

jest 40km */

czas(krakow_bochnia, 20).

/* drogę z Krakowa do Bochnii

pokonaliśmy w 20 min */

sredia_predkosc(X, Y) :-

/* średnia prędkość Y na drodze X */

droga(X, D),

czas(X, C),

Y is D / C.

Listy

Lista jest ciągiem uporządkowanych (czyli w określonej kolejności)
elementów. Elementami mogą być dowolnego rodzaju termy: stałe ,
zmienne, struktury.
Listę dzielimy na głowę i ogon czyli. Głową nazywamy pierwszy element
listy natomiast ogonem wszystkie następne. Głowa i ogon są argumentami
funktora

.

(kropka).

Listę pustą zapisuje się za pomocą znacznika

[]

.

Wobec tego pojedynczy element można zapisać jako lista używając
zapisu:

(a.[]).

Ponieważ zapis z kropką jest bardzo niewygodny stosuje się inną notację,
zapisując wszystkie elementy listy w nawiasach kwadratowych:

[a, b, [c, d]]

/* Jest to równoznaczne z (a.[b,c.[d]])*/

Zmienne w liście traktowane są tak samo jak inne zmienne dlatego można
je ukonkretnić w każdej chwili. Staranne wybranie ich położenia pozawala
na wstawienie do listy zmiennych nieukonkretnionych, które mogą być
ukonkretnione podczas działania programu.
Typową operacją jest również dzielenie listy na głowę i ogon dlatego
wprowadzono specjalny zapis z pionową kreską, która ukonkretnia ten
podział:

[X | Y].

Sprawdzanie przynależności do listy

Stwórzmy teraz predykat

member(X,Y)

za pomocą którego będziemy

sprawdzać czy X należy do listy Y.
Na początek należy sprawdzić czy X jest głową tej listy więc definiujemy
predykat:

member(X,[X,_]).

Drugi predykat mówi, że X jest elementem listy, jeśli należy do ogona tej
listy – oznaczonego przez Y.

member(X,[_|Y]) :- member(X,Y)

Do sprawdzenia czy należy do listy wykorzystujemy wcześniejszy predykat
przez co sama operacja ma charakter rekurencyjny.

Predykaty wbudowane

Predykatami budowanymi nazywamy te predykaty które z góry zostały
zdefiniowane w systemie. Najczęściej predykaty te wykonują operacje
których ni da się zaprogramować w czystym prologu.

?- consult(file).

Pozwala on na doładowanie dodatkowych klauzul z pliku już podczas
działania programu. file jest atomem wskazującym na ścieżkę dostępu do
pliku.

?- var(X).

Zwróci

yes

jeśli zmienna jest nieukonkretniona.

?- nonvar(X).

Działa odwrotnie do

var()

zwróci prawdę jeśli zmienna jest już

ukonkretniona.

?- atom(X)

Służy do sprawdzania czy X jest atomem Prologu.

?- number(X)

Zwraca

yes

dla X będącego liczbą.

?- select(X,Y,Z).

Wybiera elementy z listy. Zapisze do X obiekty znajdujące się w Y, a nie
znajdujące się w Z.

?- X , Y

Koniunkcja zwróci prawdę gdy zarówno X jak i Y są prawdziwe.

?- X ; Y

Alternatywa. Zwróci prawdę gdy chociaż jedna ze zmiennych jest
prawdziwa.

?- call(X)

Zakładamy że X jest ukonkretniony termem. Wywołanie to sprawdzi czy
ukonkretnienie X zawodzi czy nie.

?- \+ X

Działa dokładnie jak operator logiczny

not

czyli zaprzeczenie. Zwróci

prawdę gdy zmienna nie będzie mogła być uzgodniona i fałsz gdy
uzgodnienie będzie możliwe. Działa dokładnie odwrotnie do

call()

.

?- X == Y

Działa podobnie jak

X = Y

jednak traktuje zmienne dokładniej. Predykat

ten traktuje zmienne nieukonkretnione jedynie jako zmienne z nią
związane.

Kompilacja do exe.

Program prolog potrafi kompilować swój kod do plików wykonywalnych.
Załóżmy, że prolog został zainstalowany w katalogu:

C:\pl\bin\

W tym też katalogu znajduje się plik lubi.pl o zawartości:

lubi(jarek, jablko).
lubi(jarek, gruszka).
lubi(kasia, piwo).
lubi(kasia, hamburger).

pisz_co_lubi(Imie2):-
lubi(Imie2, X),
write(X),
nl,
fail.

pytanie:-
write('podaj imie: '),
nl,
read(Imie),
nl,nl,
write('Podales: '),
write(Imie),
nl,nl,
write(Imie),
write('lubi:'),
nl,
not(pisz_co_lubi(Imie)),
nl,nl,
write('KONIEC'),
get0(_),
halt.

Wpisując w linii poleceń:

"C:\pl\bin\plcon.exe" --goal=pytanie --stand_alone=true -o
pytanko.exe -c lubi.pl

Otrzymamy skompilowany program .exe.

Przykłady

Obliczanie silni:

silnia(0,1).

/* silnia 0 jest równa 1*/

silnia(N,F) :-

/* silnie N zapisujemy do F */

N>0,

/* dla N większego od 0 */

N1 is N-1,

/* wyznacz N1 mniejsze o 1 */

silnia(N1,F1),

/* wywołaj silnie dla N1 i zapisz wynik do

F1*/

F is N * F1.

/* wynik F1 przemnóż przez N */

/* W przeciwnym wypadku użyj pierwszego faktu. */

Zagadka Morderstwo

Pani Katarzyna została zabita przez jedną z czterech sąsiadek, inna
sąsiadka z tej uroczej czwórki była pomagierką. Oto ich zeznania:

 Alicja: jeżeli Beata jest winna czegoś, Celina musi być niewinna.
 Beata: jeżeli Alicja jest niewinna, Celina musi być winna.
 Celina: jeżeli Beata była zabójcą, Dorota nie ma nic wspólnego z

morderstwem.

 Dorota: ja jestem niewinna.

Pamiętajcie że winne zawsze kłamią a niewinne mówią prawdę. Kto zabił
p. Katarzynę i z czyją pomocą.

Rozwiązanie:

rozwiazanie([Morderca, Pomocnik]) :-

L0 = [alicja, celina, beata, dorota],

/* powołanie listy (

[…] ) o elementach: alicja, celina, beata, Dorota */

select(Morderca, L0, L1),
select(Pomocnik, L1, Niewinne),

zeznanieA([Morderca, Pomocnik], Niewinne),
zeznanieB([Morderca, Pomocnik], Niewinne),
zeznanieC([Morderca, Pomocnik], Niewinne).

/* zeznanie Doroty nic nie wnosi, więc brane są pod uwagę

tylko trzy pozostałe zeznania */

/* Alicja: jeżeli Beata jest winna czegoś, Celina musi być
niewinna. */
/* Lub równoważnie: Celina lub Beata są niewinne */

zeznanieA(W, N) :-
(

/*jeśli alicja jest niewinna to mówi prawdę */

member(alicja, N),

(member(celina, N) ; member(beata, N))

/* Celina lub beata

są niewinne */

) ;
(

/*jeśli alicja jest winna to prawdziwa jest negacja (\+) jej
zeznań */

member(alicja, W),
\+ (member(celina, N) ; member(beata, N))
).

/* Beata: jeżeli Alicja jest niewinna, Celina musi być
winna.*/
/* Lub równoważnie: Alicja lub Celina są zamieszane w
morderstwo */

zeznanieB(W, N) :-
(
member(beata, N),
( member(alicja,W) ; member(celina,W) )
) ;
(
member(beata, W),
\+ ( member(alicja,W) ; member(celina,W) )
).

/* Celina: jeżeli Beata była zabójcą, Dorota jest niewinna.*/
/* Lub równoważnie: Beata nie jest zabójcą lub Dorota jest
niewinna */

zeznanieC([M,P],N) :-
(
member(celina, N),
( M \= beata ; member(dorota, N) )
) ;
(
member(celina, [M,P]),
\+ ( M \= beata ; member(dorota, N) )
).

/*
rozwiazanie zagadki:
*/

rozwiazanie([Morderca, Pomocnik]).

Zagadka „Wyścig”

Pięcioro przyjaciół rywalizowało na bieżni. Wincenty ze smutkiem
opowiedział, że nie udało mu się zająć pierwszego miejsca. Grzegorz
przybiegł na metę jako trzeci i został wyprzedzony przez Dymitra.
Wincenty zauważył na marginesie, że Dymitr nie zajął drugiego miejsca, a
Andrzej nie był ani pierwszy ani ostatni. Borys powiedział, ze przybiegł na
metę zaraz po Wincentym.
Kto zajął jakie miejsce?

Rozwiązanie:

/* w poniższej liście W oznacza miejsce zajęte przez
Wincenta, D - Dymitra, A - Andrzeja, B - Borysa, G -
Grzegorza. */

/* poniższy kod nadaje się do bezpośredniego zapisania w
pliku z rozszerzeniem .pl i wykorzystania */

miejsce([wincenty,W,dymitr,D,andrzej,A,borys,B,grzegorz,G])
:-
L0 = [1,2,3,4,5],
select(W, L0, L1), W \= 1,

/* Wincenty nie zajął pierwszego

miejsca, więc nie równa się 1 */

select(D, L1, L2), D \= 2,

/* Dymitr nie zajął drugiego,

ani tego co Wincenty */

select(A, L2, L3), A \= 1, A \= 5,

/* Andrzej nie zajął

pierwszego ani piątego miejsca, ani tego co Wincenty lub
Dymitr */

select(B, L3, [G]),

/* pozostałe miejsca zajęli Borys i

Grzegorz */

B is W+1,

/* Borys przybiegł zaraz za Wincentym */

G = 3,

/* Grzegorz zajął trzecie miejsc, wiadomo to od

początku */

G > D.

/* Dymitr był na mecie wcześniej niż Grzegorz */

/*
oto rozwiązanie zagadki:
*/

miejsce(X).

„Rozkład lotów”

W poniższym programie zdefiniowano dwa predykaty:



rejsy(skad, dokad, odlot, przylot)



polaczenie(skad, dokad, odlot, przylot)

Pierwszy z nich wyraża dostępne loty między miastami USA, natomiast
drugi pozwala znajdować połączenia bezpośrednie i pośrednie, przy czym
na każdą ewentualną przesiadkę wymagana jest co najmniej 100 minut
między przylotem a odlotem.

rejsy( sf, den, 930, 1230).
rejsy( sf, dal, 900, 1430).
rejsy( den, chi, 1500, 1800).
rejsy( den, dal, 1400, 1700).
rejsy( dal, chi, 1530, 1730).
rejsy( chi, ny, 1500, 1930).
rejsy( chi, ny, 1900, 2200).
rejsy( chi, ny, 1830, 2130).

polaczenie(X, Y, O, P) :-

rejsy(X, Y, O, P).

polaczenie(X, Y, O, P) :-

rejsy(X, Z, O, T1),

polaczenie(Z, Y, T2, P),

T2 >= T1+100.

W celu znalezienia połączeń z San Francisco do Chicago zadajemy
następujące pytanie:

polaczenie(sf, chi, Odlot, Przylot).

Którego wynikiem będzie :

Odlot = 930,
Przylot = 1800 ? ;
Odlot = 900,
Przylot = 1730 ? ;

Jeśli chcemy wylecieć z San Francisco do Nowego Yorku po godzinie 9:00,
to możemy znaleźć odpowiednie połączenia zadając pytanie:

?- polaczenie(sf, ny, Odlot, Przylot), Odlot > 900.

Wynik:

Odlot = 930,
Przylot = 2200 ? ;

Zagadka Einsteina

5 ludzi różnych narodowości zamieszkuje 5 domów w 5 różnych kolorach.
Wszyscy palą papierosy 5 różnych marek i piją 5 różnych napojów. Hodują
zwierzęta 5 różnych gatunków. Który z nich hoduje rybki?

1. Norweg zamieszkuje pierwszy dom
2. Anglik mieszka w czerwonym domu.
3. Zielony dom znajduje się bezpośrednio po lewej stronie domu

białego.

4. Duńczyk pije herbatkę.
5. Palacz Rothmansów mieszka obok hodowcy kotów.
6. Mieszkaniec żółtego domu pali Dunhille.
7. Niemiec pali Marlboro.
8. Mieszkaniec środkowego domu pija mleko.
9. Palacz Rothmansów ma sąsiada, który pija wodę.
10.

Palacz Pall Malli hoduje ptaki.

11.

Szwed hoduje psy.

12.

Norweg mieszka obok niebieskiego domu.

13.

Hodowca koni mieszka obok żółtego domu.

14.

Palacz Philip Morris pija piwo.

15.

W zielonym domu pija się kawę.

Zakłada się, że domy ustawione są w jednej linii (1-2-3-4-5), a określenie
"po lewej stronie" w punkcie 3. dotyczy lewej strony z perspektywy
naprzeciw tych domów (tj. dom o numerze n jest bezpośrednio po lewej
stronie domu n+1)

Rozwiązanie:

rozwiazanie([norweg, Norweg, anglik, Anglik, dunczyk,
Dunczyk, niemiec, Niemiec, szwed, Szwed],[zielony_dom,
Zielony_dom, bialy_dom, Bialy_dom, czerwony_dom,
Czerwony_dom, zolty_dom, Zolty_dom, niebieski_dom,
Niebieski_dom],[rothmans, Rothmans, dunhill, Dunhill,
marlboro, Marlboro, pallmall, Pallmall, philipmoris,
Philipmoris],[herbata, Herbata, mleko, Mleko, woda, Woda,
piwo, Piwo, kawa, Kawa],[kot, Kot, ptaki, Ptaki, pies, Pies,
konie, Konie, rybki, Rybki]) :-

P = [1, 2, 3, 4, 5],

/* Możliwe pozycje */

select(Norweg, P, N1),

select(Anglik, N1, N2),

select(Dunczyk, N2, N3),

select(Niemiec, N3, [Szwed]),

Norweg = 1,

/* (1) */

Anglik = Czerwony_dom,

/* (2) */

Dunczyk = Herbata,

/* (4) */

Niemiec = Marlboro,

/* (7) */

Szwed = Pies,

/* (11) */

select(Niebieski_dom, P, D1),

select(Bialy_dom, D1, D2),

select(Zielony_dom, D2, D3),

select(Czerwony_dom, D3, [Zolty_dom]),

Zielony_dom is Bialy_dom - 1,

/* (3) */

Zolty_dom = Dunhill,

/* (6) */

(Niebieski_dom is Norweg-1 ; Niebieski_dom is Norweg+1),

/* (12) */

(Konie is Zolty_dom+1 ; Konie is Zolty_dom-1),

/* (13) */

Zielony_dom = Kawa,

/* (15) */

select(Dunhill, P, T1),

select(Philipmoris, T1, T2),

select(Marlboro, T2, T3),

select(Pallmall, T3, [Rothmans]),

(Kot is Rothmans-1 ; Kot is Rothmans+1),

/* (5) */

Philipmoris = Piwo,

/* (14) */

Pallmall = Ptaki,

/* (10) */

select(Mleko, P, P1),

select(Kawa, P1, P2),

select(Herbata, P2, P3),

select(Piwo, P3, [Woda]),

Mleko = 3,

/* (8) */

(Rothmans is Woda-1 ; Rothmans is Woda+1),

/* (9) */

select(Konie, P, Z1),

select(Ptaki, Z1, Z2),

select(Pies, Z2, Z3),

select(Kot, Z3, [Rybki]).

Aby uzyskać wynik zadajemy pytanie:

?- rozwiazanie([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10],[S1,
S2, S3, S4, S5, S6, S7, S8, S9, S10],[R1, R2, R3, R4, R5, R6,
R7, R8, R9, R10],[W1, W2, W3, W4, W5, W6, W7, W8, W9,
W10],[J1, J2, J3, J4, J5, J6, J7, J8, J9, J10]).

Można również zapisać tą regułę za pomocą innego kodu:

rozwiazanie([norweg, Norweg, anglik, Anglik, dunczyk,
Dunczyk, niemiec, Niemiec, szwed, Szwed],[zielony_dom,
Zielony_dom, bialy_dom, Bialy_dom, czerwony_dom,
Czerwony_dom, zolty_dom, Zolty_dom, niebieski_dom,
Niebieski_dom],[rothmans, Rothmans, dunhill, Dunhill,
marlboro, Marlboro, pallmall, Pallmall, philipmoris,
Philipmoris],[herbata, Herbata, mleko, Mleko, woda, Woda,
piwo, Piwo, kawa, Kawa],[kot, Kot, ptaki, Ptaki, pies, Pies,
konie, Konie, rybki, Rybki]) :-

P = [1, 2, 3, 4, 5],

/* Możliwe pozycjie */

Norweg = 1,

/* (1) */

select(Norweg, P, N1),

(Niebieski_dom is Norweg-1 ; Niebieski_dom is Norweg+1),

/* (12) */

select(Niebieski_dom, P, D1),

Mleko = 3,

/* (8) */

select(Mleko, P, P1),

select(Bialy_dom, D1, D2),

Zielony_dom is Bialy_dom - 1,

/* (3) */

select(Zielony_dom, D2, D3),

Zielony_dom = Kawa,

/* (15) */

select(Kawa, P1, P2),

select(Anglik, N1, N2),

Anglik = Czerwony_dom,

/* (2) */

select(Czerwony_dom, D3, [Zolty_dom]),

Zolty_dom = Dunhill,

/* (6) */

select(Dunhill, P, T1),

(Konie is Zolty_dom+1 ; Konie is Zolty_dom-1),

/* (13) */

select(Konie, P, Z1),

select(Dunczyk, N2, N3),

Dunczyk = Herbata,

/* (4) */

select(Herbata, P2, P3),

select(Philipmoris, T1, T2),

Philipmoris = Piwo,

/* (14) */

select(Piwo, P3, [Woda]),

(Rothmans is Woda-1 ; Rothmans is Woda+1),

/* (9) */

select(Niemiec, N3, [Szwed]),

Niemiec = Marlboro,

/* (7) */

select(Marlboro, T2, T3),

select(Pallmall, T3, [Rothmans]),

Pallmall = Ptaki,

/* (10) */

select(Ptaki, Z1, Z2),

Szwed = Pies,

/* (11) */

select(Pies, Z2, Z3),

(Kot is Rothmans-1 ; Kot is Rothmans+1),

/* (5) */

select(Kot, Z3, [Rybki]).

Słownik

relacja - dowolny podzbiór iloczynu kartezjańskiego zbiorów. Intuicyjnie,

oznacza pewien związek pomiędzy elementami tych zbiorów.

predykat - może oznaczać funktor zdaniotwórczy od (co najmniej

jednego) argumentu nazwowego. Predykatem nazwiemy zatem
takie wyrażenie, które z terminem jednostkowym da nam
zdanie. Np. w zdaniu "Jugosławia rozpadła się" wyrażenie
"rozpadła

się"

jest

predykatem

jednoargumentowym

(funktorem

zdaniotwórczym

od

jednego

argumentu

nazwowego), w zdaniu "Tomek lubi Basię" wyrażenie "lubi" jest
predykatem dwuargumentowym (funktorem zdaniotwórczym od
dwóch argumentów nazwowych), w zdaniu "Arystoteles
umiłował prawdę bardziej niż Sokratesa" wyrażenie "umiłował...
bardziej niż" jest predykatem trójargumentowym (funktorem
zdaniotwórczym od trzech argumentów nazwowych).

funktor - wyrażenie, które wraz z innymi wyrażeniami, nazywanymi

argumentami funktora, tworzy zdanie lub funkcję zdaniową.

terma - wyrażenie składające się ze zmiennych oraz symboli funkcyjnych

o dowolnej argumentowości (w tym o argumentowości 0, czyli
stałych) z pewnego ustalonego zbioru.
W wielu dziedzinach matematyki używa się określenia term na
oznaczenie napisów (wyrażeń) formalnych które mogą być
traktowane jako nazwy na obiekty matematyczne.

klauzula - to zbiór literałów, który jest prawdziwy wtedy i tylko wtedy,

gdy ich alternatywa jest prawdziwa. Klauzula pusta jest zawsze
fałszywa.

reguła - właściwa dla danego systemu dedukcyjnego reguła pozwalająca

uznawać zdania o określonej strukturze na podstawie zdań już

uprzednio uznanych. Stanowi strukturalną regułę wnioskowania
dedukcyjnego.