Sztuczna inteligencja

Jan Kazimirski

Sztuczna inteligencja

wykład 6

Sztuczna inteligencja

Jan Kazimirski

2

PROLOG

Sztuczna inteligencja

Jan Kazimirski

3

Literatura

●

W. F. Clocksin, C. S. Mellish, „Prolog.
Programowanie”, Helion 2003

●

I. Bratko, „Prolog Programming for Artificial
Intelligence”, Addison-Wesley 1986

●

M. Bramer, „Logic Programming with Prolog”,
Springer 2005

●

L. Sterling, E. Shapiro, „The Art of Prolog”, MIT
1999

Sztuczna inteligencja

Jan Kazimirski

4

Oprogramowanie

●

GNU Prolog

–

Strona domowa:

http://www.gprolog.org/

–

Źródła do pobrania: gprolog-1.3.1.tar.gz

–

Instalacja: po rozpakowaniu: ./configure; make;

make install

●

SWI Prolog

–

Strona domowa:

http://www.swi-prolog.org

–

Instalacja: pakiet RPM (Open SUSE)

Sztuczna inteligencja

Jan Kazimirski

5

Prolog

●

Prolog – „Programowanie w Logice”

●

Alain Colmerauer and Phillipe Roussel – 1972 r

●

Deklaratywny język programowania

●

Dziedziny zastosowań:

–

Analiza języka naturalnego

–

Dowodzenie twierdzeń, obliczenia symboliczne

–

Systemy eksperckie, inteligentne bazy danych

–

Sztuczna inteligencja

Sztuczna inteligencja

Jan Kazimirski

6

Język proceduralny vs. deklaratywny

●

Język proceduralny

–

Programista określa sekwencję instrukcji do

wykonania – algorytm.

●

Język deklaratywny

–

Programista opisuje znane fakty i relacje

dotyczące problemu

–

Programista zadaje pytania prowadzące do

rozwiązania problemu

Sztuczna inteligencja

Jan Kazimirski

7

SWI Prolog

●

Rozwijane od 1987 r.

●

Autor: Jan Wielemaker

●

Platformy: Linux, Windows, MacOS

●

Typ licencji: Open Source

●

Łatwe łączenie z językami proceduralnymi ( m.in.
C, C++, Java)

●

Interfejs graficzny za pośrednictwem XPCE

Sztuczna inteligencja

Jan Kazimirski

8

Uruchomienie programu

Sztuczna inteligencja

Jan Kazimirski

9

Praca z programem

●

Przygotowanie programu

–

Dowolny edytor tekstowy. Treść programu w

zewnętrznym pliku (rozszerzenie .pl)

–

Wczytanie programu - consult(plik). lub [plik].

●

Realizacja zapytań

–

Załadowanie programu

–

Tryb interaktywny - konwersacyjny

Sztuczna inteligencja

Jan Kazimirski

10

Obiekty i relacje

●

Zdanie: „Jan ma książkę”

●

Obiekty: „Jan”, „książka”

●

Relacja „ma”

●

Zdanie określa relację między obiektami.

●

UWAGA! Obiekt ma zupełnie inny sens niż w

językach obiektowych (Java,C++)

Sztuczna inteligencja

Jan Kazimirski

11

Reguły

●

Reguły – służą do zapisu relacji

●

Przykład: „Dwoje ludzi jest siostrami jeżeli są
kobietami i mają tych samych rodziców”

●

Reguły wyjaśniają relację i pozwalają znaleźć
obiekty znajdujące się w tej relacji

Sztuczna inteligencja

Jan Kazimirski

12

Programowanie w PROLOG-u

●

Zdefiniowanie faktów określających obiekty i
związki między nimi

●

Zdefiniowanie reguł dotyczących obiektów i
związków między nimi

●

Zadawanie zapytań o obiekty i związki między
nimi.

Sztuczna inteligencja

Jan Kazimirski

13

Fakty

●

Zdanie: „Jan lubi Marię”

–

Obiekty: Jan, Maria

–

Relacja: lubi

●

Składnia w PROLOG-u:

lubi(jan,maria).

Sztuczna inteligencja

Jan Kazimirski

14

Fakty c.d.

●

Składnia c.d.

–

Nazwy obiektów muszą zaczynać się od małej

litery. Nie używamy polskich znaków

–

Nazwy obiektów zapisuje się za nazwą relacji w

nawiasach okrągłych i oddziela przecinkami

–

Na końcu zapisu faktu musi znaleźć się kropka

Sztuczna inteligencja

Jan Kazimirski

15

Fakty c.d.

●

Kolejność obiektów

–

Kolejność obiektów jest dowolna, ale istotna, tzn.

musi być stosowana konsekwentnie w

programie

–

Dwa poniższe zapisy

NIE

są równoważne:

lubi(jan,maria).

lubi(maria,jan).

Sztuczna inteligencja

Jan Kazimirski

16

Fakty c.d.

●

Obiekty w zapisie faktu – argumenty

●

Relacja w zapisie faktu – predykat

●

Nazwy obiektów i relacji mogą być dowolne np.
a(b,c).

●

Relacja może mieć dowolną liczbę argumentów.

●

Zbiór faktów – baza danych

Sztuczna inteligencja

Jan Kazimirski

17

Zapytania

●

Po zdefiniowaniu bazy danych można realizować
zapytania, które ich dotyczą

●

Zapytanie zaczyna się od ?-

●

Składnia zapytania jest podobna do składni faktu.

●

Proste zapytanie o fakt pozwala sprawdzić czy

dany fakt znajduje się w bazie danych

Sztuczna inteligencja

Jan Kazimirski

18

Przykład 1

prog1.pl

owoc(jablko).
owoc(gruszka).
owoc(malina).

?- [prog1].
% prog1 compiled 0.00 sec, 680 bytes
true.

?- owoc(malina).
true.

?- owoc(ziemniak).
false.

?- warzywo(malina).
ERROR: toplevel: Undefined procedure: warzywo/1
(DWIM could not correct goal)
?-

Sztuczna inteligencja

Jan Kazimirski

19

Zmienne

●

Zmienne pozwala odpowiadać na pytania o to jaki
obiekt występuje w relacji

●

Zmienne zaczynają się od wielkiej litery

●

Zmienna nieukonkretniona – nie wiadomo

jakiemu obiektowi odpowiada

●

Zmienna ukonkretniona – odpowiada
określonemu obiektowi

Sztuczna inteligencja

Jan Kazimirski

20

Przykład 2

prog1.pl

owoc(jablko).
owoc(gruszka).
owoc(malina).

?- [prog1].
% prog1 compiled 0.00 sec, 400 bytes
true.

?- owoc(X).
X = jablko .

<ENTER>

?- owoc(X).
X = jablko ;

<;>

X = gruszka ;

<;>

X = malina.

?-

Sztuczna inteligencja

Jan Kazimirski

21

Przykład 3

prog2.pl

lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).

?- consult(prog2).
% prog2 compiled 0.00 sec, 424 bytes
true.

?- lubi(X,kwiaty).
X = maria ;

<;>

false.

?- lubi(jan,X).
X = ksiazki ;

<;>

X = maria.

?-

Sztuczna inteligencja

Jan Kazimirski

22

Koniunkcja

●

Koniunkcja pozwala na łączenie celów które
muszą być spełnione aby odpowiedzieć na

pytanie.

●

Przykład:

–

„Czy Jan i Maria lubią się nawzajem”

–

Z użyciem koniunkcji: „Czy Jan lubi Marię i czy

Maria lubi Jana”

●

W PROLOG-u koniunkcję zapisuje się za pomocą
przecinka.

Sztuczna inteligencja

Jan Kazimirski

23

Przykład 4

prog2.pl

lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).

?- consult(prog2).
% prog2 compiled 0.00 sec, 968 bytes
true.

?- lubi(jan,maria),lubi(maria,jan).
false.

?- lubi(jan,ksiazki),lubi(jan,maria).
true ;
false.

?-

Sztuczna inteligencja

Jan Kazimirski

24

Przykład 5

prog3.pl

lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).
lubi(maria,ksiazki).

?- consult(prog3).
% prog3 compiled 0.00 sec, 1,072 bytes
true.

?- lubi(maria,X),lubi(jan,X).
X = ksiazki ;
false.

?-

Sztuczna inteligencja

Jan Kazimirski

25

Poszukiwanie z nawracaniem

●

Poszukiwanie w przypadku koniunkcji:

–

Poszukiwany jest pierwszy cel

–

Po jego znalezieniu zaznaczana jest pozycja w bazie,

zmienna jest ukonkretniana

–

Poszukiwany jest drugi cel – z ukonkretnioną zmienną

–

W przypadku braku rozwiązania – powrót do pozycji

pierwszego celu i dalsze poszukiwanie pierwszego
celu – zmienna jest ponownie nieukonkretniona

Sztuczna inteligencja

Jan Kazimirski

26

Reguły

●

Reguły opisują relacje.

●

Reguła określa, że jakiś fakt zależy od innych
faktów.

●

Przykład: „Jan lubi wszystkich, którzy lubią
książki”

●

Zapis z użyciem zmiennej: „Jan lubi X, jeżeli X
lubi książki”

Sztuczna inteligencja

Jan Kazimirski

27

Reguły c.d.

●

Definicja reguły w prologu składa się z głowy i
treści oddzielonych znakami :-

●

Przykład:

lubi(jan,X) :- lubi(X,ksiazki).

Sztuczna inteligencja

Jan Kazimirski

28

Przykład 6

prog4.pl

lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).
lubi(maria,ksiazki).
lubi(piotr,ksiazki).
lubi(jan,X) :- lubi(X,ksiazki).

?- consult(prog4).
% prog4 compiled 0.00 sec, 1,332 bytes
true.

?- lubi(jan,X).
X = ksiazki ;
X = maria ;
X = jan ;
X = maria ;
X = piotr ;
false.

?-

Sztuczna inteligencja

Jan Kazimirski

29

Reguły c.d.

●

W treści reguły można stosować koniunkcję

●

Zmienne użyte i w głowie i w treści reguły będą
ukonkretniane w całym zakresie reguły

●

Zmienne można również zastosować tylko w
treści reguły.

Sztuczna inteligencja

Jan Kazimirski

30

Przykład 7

prog5.pl

mezczyzna(albert).
mezczyzna(edward).
kobieta(alicja).
kobieta(wiktoria).
rodzice(edward,wiktoria,albert).
rodzice(alicja,wiktoria,albert).
siostra(X,Y) :-
kobieta(X),
rodzice(X,M,O),
rodzice(Y,M,O).

?- consult(prog5).
% prog5 compiled 0.00 sec, 844 bytes
true.

?- siostra(alicja,edward).
true.

?- siostra(edward,alicja).
false.

?- siostra(alicja,albert).
false.

?- siostra(alicja,wiktoria).
false.

?-

Sztuczna inteligencja

Jan Kazimirski

31

PROLOG - składnia

●

Program w PROLOG-u składa się z termów

●

Term – stała, zmienna lub struktura

●

Stała – nazywa konkretny obiekt lub relację

●

Dwa rodzaje stałych: atomy i liczby

●

Atomy mogą składać się z liter i cyfr – zaczynając
się od małej litery np. jan, marta, lubi

●

Atomy mogą składać się z symboli, np. :-

Sztuczna inteligencja

Jan Kazimirski

32

PROLOG – składnia c.d.

●

Atomy o nazwach zawartych w apostrofy mogą
zawierać dowolne znaki.

●

PROLOG rozpoznaje liczby całkowite i
rzeczywiste

●

Zmienne mają postać atomów ale zaczynają się
od wielkiej litery lub znaku podkreślenia

●

Pojedynczy znak podkreślenia - zmienna
anonimowa (jej nazwa nie ma znaczenia)

Sztuczna inteligencja

Jan Kazimirski

33

PROLOG – składnia c.d.

●

Struktury – termy złożone

●

Obiekt złożony z atomów, liczb, zmiennych i
innych termów złożonych.

●

Strukturę zapisuje się jako f(arg1,arg2,...), gdzie f
to funktor (nazwa relacji) a arg1... to składniki.

Sztuczna inteligencja

Jan Kazimirski

34

Przykład 8

prog6.pl

posiada(marcin,auto(fiat,bialy)).
posiada(piotr,auto(ford,czerwony)).
posiada(pawel,auto(opel,bialy)).

?- consult(prog6).
% prog6 compiled 0.00 sec, 496 bytes
true.

?- posiada(pawel,auto(_,_)).
true.

?- posiada(X,auto(fiat,_)).
X = marcin ;
false.

?-

Wykorzystanie zmiennej
anonimowej oraz struktury.

! Poszczególne wystąpienia
zmiennej anonimowej nie
muszą być ukonkretnione do tej
samej wartości

Sztuczna inteligencja

Jan Kazimirski

35

Operatory

●

Niektóre operacje wygodniej zapisywać za
pomocą operatorów, np. działania matematyczne

●

Zapis a+b to inna forma zapisu termu w postaci
+(a,b)

●

Charakterystyka operatorów:

–

Operatory infiksowe, prefiksowe, postfiksowe

–

Priorytet operatora

–

Łączność operatorów – lewo-, prawostronna

Sztuczna inteligencja

Jan Kazimirski

36

Predykat równości

●

Wbudowany predykat infiksowy zapisywany jako
X = Y

●

Celem jest próba dopasowania X z Y.

●

Przykłady:

–

jan = pawel. /* zawodzi */

–

jan = jan. /* OK */

–

auto(fiat,bialy) = auto(X,Y). /* OK, ukonkretnienie */

Sztuczna inteligencja

Jan Kazimirski

37

Arytmetyka

●

Wbudowane predykaty porównania

–

X =:= Y - X i Y są tą samą liczbą

–

X =/= Y – X i Y są różnymi liczbami

–

X > Y – X jest większe niż Y

–

X < Y – X jest mniejsze niż Y

–

X =< Y – X jest mniejsze lub równe Y

–

X >= Y – X jest większe lub równe Y

Sztuczna inteligencja

Jan Kazimirski

38

Arytmetyka c.d.

●

Obliczenia

–

Do obliczeń wykorzystuje się operatora

infiksowego is

–

Operator is wylicza term występujący po prawej

stronie a następnie próbuje dopasować go do

termu po lewej stronie

–

Wbudowane operatory arytmetyczne obejmują:

dodawanie(+), odejmowanie(-), mnożenie(*),

dzielenie(/), dzielenie całkowite (//), dzielenie

modulo (mod)

Sztuczna inteligencja

Jan Kazimirski

39

Przykład 9

?- 2 < 3.
true.

?- 2 > 3.
false.

?- X is 2*3.
X = 6.

?- X is 8 mod 3.
X = 2.

?-

Sztuczna inteligencja

Jan Kazimirski

40

Przykład 10

prog7.pl

cena(fiat,5).
cena(ford,10).
cena(bmw,80).
cena(audi,40).
tanszy(X,Y) :-
cena(X,A),
cena(Y,B),
A<B.
drozszy(X,Y) :-
cena(X,A),
cena(Y,B),
A>B.

?- tanszy(fiat,ford).
true.

?- tanszy(bmw,ford).
false.

?- tanszy(X,ford).
X = fiat ;
false.

?- tanszy(X,bmw).
X = fiat ;
X = ford ;
X = audi.

Sztuczna inteligencja

Jan Kazimirski

41

Przykład 11

prog8.pl

/* populacja - mln mieszk.*/
populacja(usa,203).
populacja(indie,548).
populacja(chiny,800).
/* obszar - mln mil kw. */
obszar(usa,3).
obszar(indie,1).
obszar(chiny,4).
/* gstosc zaludnienia */
gestosc(X,Y) :-
populacja(X,P),
obszar(X,O),
Y is P/O.

?- consult(prog8).
% prog8 compiled 0.00 sec, 888 bytes
true.

?- gestosc(chiny,X).
X = 200.

?- gestosc(usa,X).
X = 67.6667.

?- gestosc(polska,X).
false.

?-

Sztuczna inteligencja

Jan Kazimirski

42

Struktury a drzewa

●

Struktury mogą być reprezentowane w postaci
drzew.

●

Przykład: a+b*c – tzn. +(a,*(b,c))

+

a

*

b

c

Sztuczna inteligencja

Jan Kazimirski

43

Lista

●

Ciąg uporządkowanych elementów

●

Lista może być dowolnej długości

●

Elementami listy mogą być dowolne termy: stałe,

zmienne, struktury, a także inne listy

●

Z listy można korzystać jeżeli nie wiadomo z góry

ile będzie elementów

Sztuczna inteligencja

Jan Kazimirski

44

Lista c.d.

●

Szczególny rodzaj listy nie zawierającej
elementów – lista pusta – zapisywana jako [].

●

Lista składa się z głowy i ogona.

●

Koniec listy zwyczajowo zapisywany jest jako
lista pusta.

●

Wewnętrzna reprezentacja listy opiera się o
funktor dwuargumentowy - kropkę

Sztuczna inteligencja

Jan Kazimirski

45

Lista c.d.

●

Lista zawierająca 1 element (a)

.(a.[])

●

Lista zawierająca 3 elementy (a,b,c)

.(a,.(b,.(c,[])))

●

Notacja alternatywna – elementy listy zapisane w
nawiasach kwadratowych np. [a,b,c]

Sztuczna inteligencja

Jan Kazimirski

46

Lista a drzewo

●

Listę można
zapisać w

postaci
drzewa, np.
Lista [a,b,c]

będzie miała
postać:

a

.

b

.

.

c

[]

Sztuczna inteligencja

Jan Kazimirski

47

Głowa i ogon listy

●

Podział na głowę i ogon listy wykorzystuje się do
jej przetwarzania.

●

Do dzielenia listy na głowę i ogon służy symbol
pionowej kreski (|).

●

Wzorzec H|T ukonkretnia H głową listy a T jej
ogonem.

Sztuczna inteligencja

Jan Kazimirski

48

Przykład 12

?- [] = [H|T].
false.

?- [a] = [H|T].
H = a,
T = [].

?- [a,b,c] = [H|T].
H = a,
T = [b, c].

?- [[a,b],c] = [H|T].
H = [a, b],
T = [c].

?- [a,[b,c]] = [H|T].
H = a,
T = [[b, c]].

?- [a,b,c] = [H1,H2|T].
H1 = a,
H2 = b,
T = [c].

?- [[1,2,3],4] = [[H1|T1]|T2].
H1 = 1,
T1 = [2, 3],
T2 = [4].

Sztuczna inteligencja

Jan Kazimirski

49

Listy i rekurencja

●

Listy są praktycznie głównym elementem
PROLOG-u (w sensie wykorzystania)

●

Efektywne korzystanie z list wymaga specjalnego
podejścia do ich przetwarzania – rekurencji.

●

Połączenie list i rekurencji pozwala na efektywne
i eleganckie rozwiązywanie w PROLOG-u bardzo

złożonych problemów

Sztuczna inteligencja

Jan Kazimirski

50

Listy i rekurencja – przykład 1

●

Problem: Chcemy stworzyć predykat isList(X)
sprawdzający czy dany term jest listą

●

Rozwiązanie:

–

Lista pusta jest listą. A więc:

isList([]).

–

Każda inna lista da się rozłożyć na głowę i ogon

będący listą.

isList([H|T]) :- isList(T).

Sztuczna inteligencja

Jan Kazimirski

51

Listy i rekurencja – przykład 2

●

Problem: Predykat isMember(X,Y) sprawdzający
czy X jest elementem listy Y.

●

Rozwiązanie:

–

X należy do listy jeżeli jest jej głową

isMember(X,[X|_]).

–

Jeżeli X nie jest głową listy to może należeć do jej

ogona

isMember(X,[_,Y]) :- isMember(X,Y).

Sztuczna inteligencja

Jan Kazimirski

52

Odcięcie

●

Szukając rozwiązań PROLOG stosuje
nawracanie

●

Aby uniknąć nawracania można użyć w regule
tzw. odcięcia

●

Odcięcie oznacza się symbolem !

Sztuczna inteligencja

Jan Kazimirski

53

Odcięcie c.d.

●

Przykład reguły z odcięciem:

a(X) :- b(X),

!

, c(X).

b(d).
b(e).
b(f).
c(e).

●

Zapytanie

?- a(X).

da odpowiedź

false

●

Bez odcięcia rezultatem byłoby

X = e

Sztuczna inteligencja

Jan Kazimirski

54

Wejście/wyjście

●

Wbudowane predykaty PROLOG-u pozwalają na
bardziej rozbudowaną komunikację z

użytkownikiem.

●

Predykat wbudowany

read

pozwala na

wczytywanie termów ze standardowego wejścia

●

Predykat wbudowany

write

– wypisywanie

termów na standardowe wyjście

Sztuczna inteligencja

Jan Kazimirski

55

Czytanie termów

●

Do czytania termów można użyć predykatu read

●

Wpisywany term należy zakończyć znakiem

kropki

●

Predykat read uzgadnia zmienną tylko raz.

●

Nawracania w przypadku read można wymusić
predykatem repeat.

Sztuczna inteligencja

Jan Kazimirski

56

Przykład 12

prog9.pl

a(1,b).
a(1,c).
a(2,d).
a(2,e).
e(X) :- read(Y),a(Y,X).

?- consult(prog9).
% prog9 compiled 0.00 sec, 1,236 bytes
true.

?- e(X).
|:

1.

X = b ;
X = c.

?-

Sztuczna inteligencja

Jan Kazimirski

57

Przykład 13

prog10.pl

a(1,b).
a(1,c).
a(2,d).
a(2,e).
e(X) :- repeat,read(Y),a(Y,X).

?- consult(prog10).
% prog10 compiled 0.00 sec, 1,316 bytes
true.

?- e(X).
|:

1.

X = b ;
X = c ;
|:

2.

X = d ;
X = e ;
|: |

Sztuczna inteligencja

Jan Kazimirski

58

Pisanie termów

●

Do pisania termów służy predykat write

●

W predykacie write zmienna uzgadniana jest
tylko raz

●

Predykat nl służy do wypisywania znaku nowej
linii

Sztuczna inteligencja

Jan Kazimirski

59

Przykład 14

prog11.pl

kwadrat :- read(X), licz(X).
licz(stop) :- !.
licz(X) :- C is X * X,
write(C),kwadrat.

?- consult(prog11).
% prog11 compiled 0.00 sec, 492 bytes
true.

?- kwadrat.
|:

3.

9
|:

5.

25
|:

stop.

true.

?-

Sztuczna inteligencja

Jan Kazimirski

60

Reguły bez głowy

●

Reguła bez głowy pozwala na definiowanie
obiektu na etapie kompilacji

●

Przykład:

:- write('Witaj!').

●

Rezultat kompilacji:

?- consult(prog12).
Witaj!
% prog12 compiled 0.00 sec, 404 bytes
true.

?-

Sztuczna inteligencja

Jan Kazimirski

61

Przykład 15 - silnia

prog13.pl

silnia(0,F) :- F is 1.
silnia(N1,F1) :- N1>0,
N2 is N1-1,
silnia(N2,F2),
F1 is N1*F2.

?- consult(prog13).
% prog13 compiled 0.00 sec, 832 bytes
true.

?- silnia(5,X).
X = 120 ;
false.

?- silnia(10,X).
X = 3628800 ;
false.

?- silnia(3,X).
X = 6 ;
false.

Sztuczna inteligencja

Jan Kazimirski

62

Przykład 16 - Fibonacci

prog14.pl

fib(0,F) :- F is 1.
fib(1,F) :- F is 1.
fib(N,F):- N>1,
N1 is N-1,
N2 is N-2,
fib(N1,F1),
fib(N2,F2),
F is (F1 + F2).

?- consult(prog14).
% prog14 compiled 0.00 sec, 968 bytes
true.

?- fib(2,X).
X = 2

?- fib(3,X).
X = 3 .

?- fib(4,X).
X = 5 .

?- fib(5,X).
X = 8 .

Sztuczna inteligencja

Jan Kazimirski

63

Przykład 17 – Bubble sort

prog15.pl

bSort(List,Sorted) :-
swap(List,List1),
!,
bSort(List1,Sorted).
bSort(Sorted,Sorted).
swap([X,Y|Rest],[Y,X|Rest]) :-
X > Y.
swap([Z|Rest],[Z|Rest1]) :-
swap(Rest,Rest1).

?- consult(prog15).
% prog15 compiled 0.00 sec, 1,072 bytes
true.

?- bSort([1,8,4,7,2,3],Sorted).
Sorted = [1, 2, 3, 4, 7, 8].

?-