Kolejne kroki tej metody to



Pobieranie 269,69 Kb.
Strona1/3
Data28.10.2017
Rozmiar269,69 Kb.
  1   2   3

Refutacja:

Metoda dowodzenia, że jakies Q jest logiczną konsekwencją pewngo zbioru S. Opiera się na równoważności, że:

S|=Q ⇔S ∪ {~Q} jest niespełnialny.

Reguła dowodzenia w przód zaczyna od pewnych klauzul i wytwarza nowe klauzule uzyskane przez powtarzanie rezolucji. W praktyce jest to trudne osiągnąć odpowiedź na nasze pytanie bo nie wiemy od początku które dwie klauzule połączyć, żeby szybko uzyksac odpowiedź. Wtedy własnie z pomocą przychodzi metoda refutacji i to w niej rezolucjajest najczęściej stosowana

Kolejne kroki tej metody to:


  1. Tworzymy zbiór S1=S∪{~Q}

  2. Wszystkie wyrażenia w S1 zapisujemy w formie klauzul czyli ~Q≡←Q

  3. Stosujemy rezolucję na S1 dotąd aż uzyskamy klauzulę pustą czyli zmienna wystepująca w obu klauzulach (z tylko tą zmienną), sie uprości.

Formuła jest prawdziwa (“valid”) kiedy jest prawdziwa dla wszystkich możliwych podstawień argumentów w danej interpretacji języka.


Język pierwszego rzędu:

Język pierwszego rzedu jest zbiorem formuł utworzonych przy pomocy alfabetu symboli odnoszących się do specyficznych reguł.


Definicja: Alfabet składa się z symboli przypisanych do następujących klas


  1. symbole zmiennych – X,Y,Z,A,B....

  2. symbole stałych – x,y,z,a,b....

  3. symbole funkcji np f/2,g/1,h/2....

  4. symbole predykatów – np: <, >, =, p/2,q/2, r/2

  5. połaczeń logicznych: ~, ˄, ˅, → i ⇔

  6. kwantyfikatorów: ∀ i ∃

  7. nawiasów i kropki

Interpretacja języka L:


Niech będzie dany niepusty zbiór D okreslany dziedziną. Interpretacja języka pierwszego rzędu określają nastepujące własności:

  1. dla każdej stałej a przypisany zostaje element a’ należacy do D

  2. dla każdej funkcji f zostaje przypisana funkcja f’: Dn→D

  3. dla każdego predykatu p przypisany jest predykat p’: Dn→{T,F}

Interpretacja nadaje jakieś znaczenie symbolom języka L. Pod jakąś określoną interpretacją sstałe odwołują się do określonych elementów zbioru D, funkcje odwołują się do funkcji określonych na zbiorze D, każdy z predykatów reprezentuje określoną relację o obiektach ze zbioru D.


Po okresleniu interpretacji określamy prawdziwość danej formuły w danym, konkretnym języku.
Formuła zamknięta (closed formula) – jest wtedy, gdy każda zmienna wyrażenia poprzedzonego kwantyfikatorem wystepuje także w kwantyfikatorze np.

∀x∀yp(x,y) jest formułą zamkniętą

∀x∃y p(x,y) jest formułą zamkniętą

∀x p(x,y,z) nie jest formułą zamkniętą, gdyż zmienne y i z z predykatu nie mają kwantyfikatorów (nie są bound).


Definicja zbioru spełnialnego i nie oraz zbioru zawsze prawdziwego (valid)

Niech S będzie zbiorem zamknietych formuł języka pierwszego rzędu. S jest określony jako spełnialny jeśli jest jakaś interpretacja, która jest modelem dla S. i niespełnialny jesli nie ma żadnej interpretacji, która jest modelem dla S. Jeśli każda interpretacja jest modelem dla S, wtedy S jest określany „valid” (prawdziwy)


Arytmetyka w „pure” Prologu

Poniższe przykłady są dobrym sposobem na opanowanie tego jak „myśli” Prolog.


Liczby naturalne w Prologu definiujemy tak jak w ich aksjomacie czyli mamy liczbę zero a reszta jest tworzona przez dodanie 1 z zastosowaniem funkcji nastepnika s(x)=x+1.
zero, s(zero), s(s(zero)) to kolejno 0, 1, 2....
Teraz potrzebujemy zabezpieczyć się, że to, co dodajemy, odejmujemy, mnożymy etc jest w ogóle liczbą, bo dodamy 0+coś i Prolog odpowie, że coś.
Predykat czyliczba jest predykatem, którego potrzebujemy.
Wszystkie predykaty, które tu omówimy potrzebują mieć warunek graniczny, fakt, od którego zaczynamy definiowanie operacji dodawania, mnożenie, dzielenia....np. ze zwykłej arytmetyki wiemy, że dodając 0 do jakiejkolwiek liczby dostaniemy tą liczbę i to może być fakt w Prologu.
Wróćmy do predykatu czyliczba. Faktem jest, że liczbą jest zero:

czyliczba(X):-zero.

Teraz potrzebujemy zależności rekurencyjnej, aby zapytać o inne liczby: np pytamy czy jest liczbą s(X)=X+1 i kiedy jest liczba?

Odp. S(X) jest liczbą kiedy X jest liczbą

czyliczba(s(X)):-czyliczba(X).
Zobaczmy teraz predykat dodawanie dod(X,Y,Z) prawdziwy gdy X+Y=Z. Wspominaliśmy wcześniej, że w dodawaniu zachodzi fakt: 0+X=X o ile X jest liczbą.

(a) dod(zero,X,X):-czyliczba(X).

Teraz rekurencyjna zależność wymaga od nas wyrażenia dla X czyli (1) X+Y=Z i dla kolejnego X czyli X+1 (s(X)). Wyrażenie nr 1 opisane jest faktem dod(X,Y,Z), a w szczególnym przypadku faktem (a). Wyrażenie dla s(X) wygląda tak: (2) X+1+Y=Z+1 ⇔ S(X)+Y=s(Z)

Lewa strona reguły będzie miała zapis jak niżej a prawą stronę otrzymamy podstawiając do (2) wyrażenie nr (1):

dod(s(X),Y,s(Z)):-dod(X,Y,Z).
Inna formą predykatu może być:

dod(X,zero,X):-czyliczba(X).

dod(X,S(Y),s(Z)):-dod(X,Y,Z).
Predykat mnożenia: (1) mnoz(X,Y,Z) jest prawdziwy, gdy X*Y=Z, a szczególny przypadek to warunek początkowy to: X*0=0

mnoz(X,zero,zero):-czyliczba(X).

Teraz szukamy rekurencji – korzystamy z następnego X czyli s(X)=X+1.



(X+1)*Y=(2) X*Y+X=Z+X. Miejsce podkreślone jest odwołaniem do predykatu (1). Z innej strony (3) (X+1)*Y=Z1, a więc (4) Z+X =Z1.

Zapisując regułę mamy z prawej strony wyrażenia (2) i (4):

(3) mnoz(s(X),Y,Z1):-(2) mnoz(X,Y,Z), (4) dod(Z,X,Z1).

Rekurencja w Prologu:

Poniżej przedstawiam przykład zastępowania ciągu reguł przez rekurencję w Prologu. Warto przeanalizować te rysunki.

*Źródło rysunków – niestety nieznane, ale i nie moje.




  1   2   3


©operacji.org 2019
wyślij wiadomość

    Strona główna