Microsoft Word - Klauzule.docx

Rachunek predykatów, k

Programowanie w prologu polega na zapisywaniu stwierdzeń uŜywając predykatów

pierwszego rzędu. Wyniki powstają jako rezultat (automatycznego wnioskowania).

Rachunek predykatów pierwszego rzędu:

•

Term to funktor (symbol stanowiący nazwę relacji) z listą parametrów atomowych, np.
lubi(jan, maria).

•

ZauwaŜmy, Ŝe stała jest szczególnym przypadkiem termu (bezparametrowym).

•

Stwierdzenie to jeden lub więcej termów połączonych spójnikami (negacja
alternatywa , koniunkcja

•

W stwierdzeniach mogą pojawiać się
(uniwersalny , egzystencjalny

Klauzule

•

W Prologu nie uŜywa się kwantyfikatorów; w zamian za to stwierdzenia zapisuje się
w postaci klauzul.

•

Ogólna postać klauzuli jest następująca:

gdzie

są termami.

to poprzednik klauzuli, zaś

KaŜde stwierdzenie moŜna zapisać w formie klauzuli. Istnieje algorytm, który to robi.

W Prologu uŜywa się postaci jeszcze
w następniku mają zero lub jeden term (

Klauzula Horna to klauzula, w której co najwyŜej jeden element jest
Przykładem takiej klauzuli jest {p,¬r,¬q
w postaci implikacyjnej: p

Klauzule z termem w następniku („z głową”) wyraŜają zaleŜności (dla
fakty (dla

= 0).

Klauzule z pustym następnikiem („bez
czyli tego, co ma zostać udowodnione.

Rezolucja

•

Jest to metoda wnioskowania, którą moŜna stosować do opisanych tu stwierdzeń.

•

Podstawowa reguła jest następująca: wiedząc Ŝe P

S, o ile tylko Q i R dają się zunifikować.

•

Z technicznego punktu widzenia, osiąga się to przez wyliczenie Q
i usunięcie termów, które występują po obydwu stronach T.

Rachunek predykatów, klauzule

Programowanie w prologu polega na zapisywaniu stwierdzeń uŜywając predykatów

pierwszego rzędu. Wyniki powstają jako rezultat (automatycznego wnioskowania).

Rachunek predykatów pierwszego rzędu:

to funktor (symbol stanowiący nazwę relacji) z listą parametrów atomowych, np.

ZauwaŜmy, Ŝe stała jest szczególnym przypadkiem termu (bezparametrowym).

to jeden lub więcej termów połączonych spójnikami (negacja

, koniunkcja , równowaŜność

, implikacja

W stwierdzeniach mogą pojawiać się zmienne związane kwantyfikatorami

, egzystencjalny ).

W Prologu nie uŜywa się kwantyfikatorów; w zamian za to stwierdzenia zapisuje się

Ogólna postać klauzuli jest następująca:

to poprzednik klauzuli, zaś

KaŜde stwierdzenie moŜna zapisać w formie klauzuli. Istnieje algorytm, który to robi.
W Prologu uŜywa się postaci jeszcze prostszej — klauzul Horna, czyli klauzul, które
w następniku mają zero lub jeden term (  = 0 lub  = 1).
Klauzula Horna to klauzula, w której co najwyŜej jeden element jest
Przykładem  takiej  klauzuli  jest  {p,¬r,¬q}.  Klauzule  Horna  zapisuje  się  zwykle
w postaci implikacyjnej:  p ← r

∧ q, a w prolog wygląda to następująco

Klauzule z termem w następniku („z głową”) wyraŜają zaleŜności (dla

Klauzule z pustym następnikiem („bez głowy”) są uŜywane do wyraŜenia celu
czyli tego, co ma zostać udowodnione.

Jest to metoda wnioskowania, którą moŜna stosować do opisanych tu stwierdzeń.
Podstawowa reguła jest następująca: wiedząc Ŝe P

Q oraz R

S, wnioskujemy Ŝe P

le tylko Q i R dają się zunifikować.

Z technicznego punktu widzenia, osiąga się to przez wyliczenie Q
i usunięcie termów, które występują po obydwu stronach T.

Programowanie w prologu polega na zapisywaniu stwierdzeń uŜywając predykatów

pierwszego rzędu. Wyniki powstają jako rezultat (automatycznego wnioskowania).

to funktor (symbol stanowiący nazwę relacji) z listą parametrów atomowych, np.

ZauwaŜmy, Ŝe stała jest szczególnym przypadkiem termu (bezparametrowym).

to jeden lub więcej termów połączonych spójnikami (negacja

związane kwantyfikatorami

W Prologu nie uŜywa się kwantyfikatorów; w zamian za to stwierdzenia zapisuje się

— następnik.

KaŜde stwierdzenie moŜna zapisać w formie klauzuli. Istnieje algorytm, który to robi.

klauzul Horna, czyli klauzul, które

Klauzula Horna to klauzula, w której co najwyŜej jeden element jest niezanegowany.

}. Klauzule Horna zapisuje się zwykle

q, a w prolog wygląda to następująco

: p :- r, q.

Klauzule z termem w następniku („z głową”) wyraŜają zaleŜności (dla

> 0) lub

głowy”) są uŜywane do wyraŜenia celu —

Jest to metoda wnioskowania, którą moŜna stosować do opisanych tu stwierdzeń.

S, wnioskujemy Ŝe P

Z technicznego punktu widzenia, osiąga się to przez wyliczenie Q S oraz P R

•

Występowanie  zmiennych  w  stwierdzeniach  powoduje,  Ŝe  w  trakcie  rezolucji  trzeba
znaleźć  takie  wartości  dla  tych  zmiennych,  które  pozwolą  na  odpowiednie
dopasowanie.

•

Unifikacja to proces znajdowania wartości dla zmiennych, dzięki którym uzyskamy Q
= R.

•

Podstawianie pod zmienne tymczasowych wartości pozwalających na unifikację
zwane jest instancjonowaniem. Mówimy teŜ o utoŜsamieniu zmiennej z wartością.

•

Unifikacja często wymaga nawrotów: Zmienna jest instancjonowana, lecz
dopasowanie nie udaje się. Zmienną instancjonuje się wówczas inną wartością itd.

Program w PROLOG-u jest zbiorem klauzul Horna:

^ . . . ^ L

n−1

→ L

Gdzie L

Ln−1

to poprzedniki klauzuli natomiast L

to następnik klauzuli, klauzule mogą być

z  poprzednikami  lub  bez.  Klauzule  z  poprzednikami  reprezentują  zaleŜności,  klauzule  bez
poprzedników reprezentują fakty (prawda jest, ze L).

Klauzule  bez  następnika  nie  występują  bezpośrednio  w  programie,  natomiast  moŜna  je
wykorzystywać w konwersacji (po kompilacji programu) jako cel wnioskowania.

Proces wnioskowania w języku Prolog opiera sie na specyficznym rodzaju rezolucji:

Podstawowa reguła jest następująca:

wiedząc ze z P wynika Q oraz z R wynika S, wnioskujemy ze z P wynika S, tylko wtedy, gdy Q i R
dadzą się zunifikować.

Jeśli  w  wyraŜeniach  występują  zmienne  to  w  trakcie  wnioskowania  znajduje  sie  takie  wartości
zmiennych dla których Q=R. Taki proces nazywa sie właśnie unifikacja. Poszukiwanie takich wartości
zmiennych, dla których Q=R polega na ukonkretnianiu wartości kolejnych zmiennych stałymi. Proces
unifikacji  zazwyczaj  wiąŜe  sie  z  wieloma  próbami  podstawiania  (nawrotami),  gdy  ukonkretnianie
zmiennych pewnymi stałymi nie udaje się. Wnioskowanie w języku PROLOG polega na dowodzeniu
twierdzeń (hipotez). Hipotezy dowodzi sie korzystając z rezolucji, czyli przekształcania klauzul aŜ do
doprowadzenia do powstania sprzeczności.

Przykłady zadań wraz z rozwiązaniami

Mamy zadanie logiczne o następującej treści:

•  Przy ulicy stoją trzy domy:
•  kaŜdy z nich ma inny kolor:
•  jeden jest czerwony, drugi zielony a trzeci niebieski.
•  W kaŜdym z tych domów mieszka osoba innej narodowości:

w jednym Anglik, w drugim Hiszpan a w trzecim Japończyk.

• KaŜdy z nich hoduje jakieś zwierzę: jedna osoba ma ślimaka, druga jaguara a trzecia zebrę.

• Wiadomo jeszcze, ze Anglik mieszka w czerwonym domu, Hiszpan ma jaguara, Japończyk

mieszka na prawo od właściciela ślimaka, a właściciel ślimaka mieszka na lewo od
niebieskiego domu.

Pytanie brzmi: Kto hoduje zebrę?

Koncepcja rozwiązania zadania

Rozwiązanie tej zagadki w duŜej mierze opiera sie na znalezieniu odpowiedniej struktury

danych,  która  pozwoliłaby  nie  tylko  wyrazić  to,  kto  w  którym  domu  mieszka  ale  takŜe  relacje  „na
prawo  od”  i  „na  lewo  od”.  Implementacja  rozwiązania  w  klasycznym  proceduralnym  języku
programowania  jest  dość  pracochłonna  i  wymaga  dodatkowo  implementacji  algorytmu,  który
przeszukałby  przestrzeń  układów  mieszkańców  i  kolorów  tych  domów.  Najprostszy  jest  oczywiście
w  takiej  sytuacji przegląd zupełny,  który  sprawdza  wszystkie  moŜliwe  stany.  Niestety jak to  zwykle
bywa  algorytm  najprostszy  jest  najmniej  efektywny:  Dla  tak  prostego  zadania  jest  216  moŜliwych
stanów do sprawdzenia, gdzie dla pełnej wersji tej zagadki (5 domów i pięć cech do spełniania) jest
ich aŜ 24883200000. Zrozumiałe jest, Ŝe do takiego zadania lepiej jest wykorzystać algorytm bardziej
skomplikowany ale pozwalający na znaczną redukcję stanów do sprawdzenia. Próbując rozwiązać to
zadanie  wykorzystując  język  PROLOG  nie  ma  konieczności  implementacji  algorytmu,  bo  z  tym
poradzi  sobie  kompilator  natomiast  waŜne  jest  by  w  sposób  właściwy  opisać  obiekty  i  zaleŜności
w zagadce.
Zadanie  to  moŜna  zrealizować  na  kilka  sposobów,  poniŜej  zostanie  zaprezentowany  jeden  z  nich.
Pierwszym  krokiem  powinno  być  zdefiniowanie  sposobu  zakodowania  istniejących  zaleŜności.  Na
pierwszy  rzut  oka  wydaje  sie,  ze  naleŜałoby  zdefiniować  predykaty  opisujące  relacje  miedzy
obiektami  ale  moŜna  to  zadanie  rozwiązać  w  inny  sposób.  Opiera  sie  on  na  spostrzeŜeniu,  Ŝe
w zagadce relacje moŜna uprościć do takiej postaci: „występują razem”, „na lewo”, „na prawo”, czyli
jeśli  człowiek  mieszka  w  którymś  domu  to  człowiek  i  dom  występują  razem,  jeśli  człowiek  hoduje
któreś zwierze, to teŜ występują razem, jeśli człowiek mieszka na prawo od hodowcy ślimaka tzn. Ŝe
miedzy ślimakiem a tym człowiekiem jest relacja „na prawo”. Kolejne spostrzeŜenie wiąŜe się z tym,
Ŝe  skoro  w  zagadce  są  relacje  na  lewo  i  na  prawo  to  znaczy,  ze  domy  są  ustawione  w  jednej  linii,
w związku z czym moŜna je, na uŜytek rozwiązania, ponumerować i oznaczyć tak, ze dom na prawo
ma  numer  większy  od  numeru  na  lewo.  Skoro  domy  zostały  ponumerowane,  to  numery  te  moŜna
równieŜ podstawić pod ich mieszkańców, czyli jeśli dom o takim a nie innym kolorze ma numer jeden
to mieszkańcom tego domu (człowiekowi i zwierzęciu) moŜna teŜ ten numer przypisać. Mając takie
załoŜenia moŜna znów zredukować liczbę relacji i zauwaŜyć w takim razie, ze nie są konieczne relacje
„występują  razem”,  „na  lewo”,  i  „na  prawo”  poniewaŜ  wystarczy  porównać  numery  domów
przypisane  kaŜdemu  obiektowi.  W  związku  z  tym  zamiast  definiować  stałe  odpowiadające
poszczególnym  obiektom  moŜna  załoŜyć,  Ŝe  kaŜdy  z  obiektów  będzie  opisany  przez  jedna  zmienną
(Anglik,  Hiszpan,  Japonczyk,  Czerwony,  Zielony,  Niebieski,  Zebra,  Slimak,  Jaguar)  a  wartością
kaŜdej  zmiennej  będzie  numer  domu.  Wystarczy,  wobec  tego,  zdefiniować  zakres  wartości  jaki  te
zmienne mogą przyjmować (predykat „dom(numer domu)” ) i moŜna definiować zaleŜności:

Przykładowy program rozwiązujący zadanie:

dom(1).

dom(2).

dom(3).

zebra(Zebra,Jaguar,Slimak,Czerwony,Niebieski,Zielony,Anglik,Japonczyk,Hiszpan):-

dom(Zebra),

dom(Jaguar),

dom(Slimak),

dom(Czerwony),

dom(Niebieski),

dom(Zielony),

dom(Anglik),

dom(Japonczyk),

dom(Hiszpan),

Zebra =\= Jaguar,

Zebra =\= Slimak,

Jaguar =\= Slimak,

Czerwony =\= Niebieski,

Czerwony =\= Zielony,

Zielony =\= Niebieski,

Anglik =\= Japonczyk,

Anglik =\= Hiszpan,

Japonczyk =\= Hiszpan,

Czerwony = Anglik,

Jaguar = Hiszpan,

Japonczyk > Slimak,

Slimak < Niebieski .

Jak działa powyŜszy program?
Pierwsze trzy definicje deklarują, ze jednoargumentowy predykat „dom” spełniony będzie dla trzech
wartości  argumentu  (1,2,3).  Określa  się  w  ten  sposób  zakres  wartości  jaki  moŜe  mieć  numer  domu.
Dziewięcioargumentowy  predykat  „zebra”  jest  właściwym  opisem  problemu.  Dziewięć  zmiennych
oznacza  tu  wszystkie  obiekty  jakie  występują  w  zagadce  tzn.:  Anglika,  Hiszpana,  Japończyka,
czerwony  dom,  niebieski  dom,  zielony  dom  oraz  jaguara,  ślimaka  i  zebrę.  Wartość  z  jaką  ukonkret-
nione  będą  te  zmienne  będzie  oznaczało  numer  domu,  który  dany  obiekt  ma  lub  w  nim  mieszka.
Pierwsze  dziewięć  warunków  określa  zakres  wartości  wszystkich  zmiennych.  Kolejne  trzy  warunki
zastrzegają,  Ŝe  kaŜde  zwierzę  mieszka  w  innym  domu  (numery  domów  przypisane  pod  zmienne
muszą być róŜne), kolejne trzy zastrzegają, ze dom o kaŜdym  kolorze ma inny numer a kolejne trzy
warunki zastrzegają, Ŝe kaŜda osoba mieszka w innym domu.

W warunku:
Czerwony = Anglik,

zastrzega  się,  ze  w  czerwonym  domu  mieszka  Anglik  (wartość  podstawiona  pod  kolor  domu,  czyli
jego numer jest równy wartości podstawionej pod zmienną Anglik).

W warunku:

Jaguar = Hiszpan,

zastrzega  sie,  ze  Hiszpan  ma  jaguara,  natomiast  ostatnie  dwa  warunki  informują,  ze  Japończyk
mieszka  na  prawo  od  ślimaka  (numer  domu  Japończyka  jest  większy  od  numeru  domu,  w  którym
mieszka ślimak) i ślimak mieszka na lewo od niebieskiego domu.
Taka definicja zagadki jest wystarczająca i opisuje wszystkie zaleŜności jakie w zagadce występują.

Po zadaniu zapytania:

?- zebra(Zebra, Jaguar, Slimak, Czerwony, Zielony, Niebieski,

Anglik, Japonczyk, Hiszpan).

Otrzymamy rozwiązanie zagadki.

Problem n-hetmanów

W roku 1850 wybitny matematyk Carl Friedrich Gauss sformułował następujące

zadanie:  Ustawić  na  szachownicy  osiem  hetmanów  tak  aby  Ŝaden  z  nich  nie  bił
któregokolwiek  z  pozostałych.  Na  Rysunku  1  przedstawiono  jedno  z  jego  92  rozwiązań.
Zadanie  o  hetmanach  moŜna  uogólnić  na  szachownice  dowolnych  rozmiarów.  Dalej
będziemy  zajmować  się  takim  uogólnionym  zadaniem,  czyli  będziemy  szukać  ustawienia
n hetmanów na szachownicy o n wierszach i n kolumnach. Uogólnione zadanie o hetmanach
naleŜy  do  klasy  problemów  NP-trudnych.  Trudność  (dokładniej  wysoka  czasochłonność)
znalezienia  rozwiązania  problemu  n-hetmanów,  przy  jednoczesnej  prostocie  jego
sformułowania,  przyczyniła  się  do  tego,  Ŝe  stał  się  on  jednym  z  najczęściej  uŜywanych
problemów  do  testowania  ogólnych  metod  poszukiwania  rozwiązania  trudnych  problemów.

Rys.1 Przykładowe rozwiązanie – problem ośmiu hetmanów

Przykładowy program rozwiązujący problem ośmiu hetmanów:

queens([]). % dodanie do pustej listy – jest rozwiązanie

queens([ Row/Col | Rest]) :- % w przeciwnym razie, dla każdego wiersza

queens(Rest), % połóż hetmana na najwyżej numerowanych wierszach

member(Col, [1,2,3,4,5,6,7,8]), % wybierz jedną możliwą kolumnę

safe( Row/Col, Rest). % i sprawdź, czy jest bezpieczna,

% jeśli nie, powróć i sprawdź inną kolumnę, dopóki

% nie sprawdzisz wszystkich kolumn, jeśli błąd to powróć do poprzedniego wiersza

safe(Anything, []). % pusta szachownica jest zawsze bezpieczna

safe(Row/Col, [Row1/Col1 | Rest]) :- % sprawdź, czy atakujesz hetmana w następnym wierszu poniżej

Col =\= Col1, % ta sama kolumna ?

Col1 - Col =\= Row1 - Row, % sprawdź przekątną

Col1 - Col =\= Row - Row1,

safe(Row/Col, Rest). % nie atakuje w następnym wierszu, sprawdź resztę szachownicy

%member(X, [X | Tail]). % czytaj kolejne wartości kolumn

%member(X, [Head | Tail]) :-

% member(X, Tail).

board([1/C1, 2/C2, 3/C3, 4/C4, 5/C5, 6/C6, 7/C7, 8/C8]). % prototyp szachownicy

Różniczkowanie symboliczne

W matematyce przez różniczkowanie symboliczne rozumiemy przekształcenie jednego

wyrażenia algebraicznego na inne, nazywane pierwszą pochodną funkcji. Załóżmy, że U oznacza

wyrażenie algebraiczne ze zmienną x. Pochodną U względem x zapisujemy jako:

Pochodną wyznaczamy stosując rekurencyjne pewne zasady przekształcania wyrażeń do wyrażenia

U. Warunki graniczne są określone następująco:

c – stała.

Wybrane pochodne funkcji (U,V – wyrażenia):

•

PowyŜsze zestawy reguł łatwo przekształcić w klauzule Prologu, gdyŜ wyraŜenia algebraiczne
moŜemy zapisać jako struktury, a operatorów uŜyć jako funktorów. MoŜemy teŜ korzystać
z dopasowania wzorców, dopasowując cele do głów reguł.

Cel d(E,X,F) nie zawiedzie, jeśli pochodną wyraŜenia E względem zmiennej X jest wyraŜenie F.
Wprawdzie operatory +,-,*,/ są juŜ wbudowane, ale musimy zadeklarować operator ^, taki, Ŝe
X^Y oznaczać będzie x

. Deklaracje operatorów ułatwią na odczytywanie wyraŜeń.

Przykładowy program obliczający pochodne:

:-op(300,yfx,^).

d(X,X,1):-!.

d(C,_,0):-atomic(C).

d(-U,X,-A):-d(U,X,A).

d(U+V,X,A+B):-d(U,X,A),d(V,X,B).

d(U-V,X,A-B):-d(U,X,A),d(V,X,B).

d(C*U,X,C*A):-atomic(C),\+C=X,d(U,X,A),!.

d(U*V,X,B*U+A*V):-d(U,X,A),d(V,X,B).

d(U/V,X,A):-d((U*V)^(-1),X,A).

d(U^C,X,C*U^(C-1)*W):-atomic(C),\+C=X,d(U,X,W).

d(log(U),X,A*U^(-1)):-d(U,X,A).

Jak obliczyć pochodną funkcji ?

?- d(x+1,x,X).

Zadania:

1. Oblicz pochodne kilku wybranych funkcji, dokonaj interpretacji uzyskanych

wyników,

2. Zastanów się, jak moŜna usprawnić sposób wypisywania wyników róŜniczkowania,
3. Utwórz zestaw predykatów, który pozwoli na wykonywania operacji +,-,/,* na

ułamkach prostych, zapisanych w postaci

!" #

$ %"&" #

. Wynik powinien zostać

przedstawiona w najprostszej postaci, naleŜy równieŜ uwzględnić sytuacje
wyjątkowe.

4. Utwórz zestaw predykatów, który pozwoli na wykonywania operacji +,-,/,* na

liczbach zespolonych.