Przeskocz do treści

Delta mi!

Na ścieżce rezolucji

Aleksy Schubert

o artykule ...

  • Publikacja w Delcie: kwiecień 2017
  • Publikacja elektroniczna: 30 marca 2017
  • Wersja do druku [application/pdf]: (67 KB)

Naszą wiedzę o zjawiskach lub przedmiotach wygodnie jest zapisywać w postaci koniunkcji wyrażanej za pomocą spójnika "i" (np. w ten sposób można powiedzieć, że kaczki mają skrzydła i latają). Niestety, taki format nie sprawdza się dobrze...

obrazek

Dzieje się tak dlatego, że nasz słownik do opisu rzeczywistości jest niepełny, a własności zmieniają się w zależności od obserwacji (np. jeśli nie mamy w słowniku możliwości mówienia o młodych kaczkach, a widzimy, że takie nie latają, to pozostaje nam opisać tę rzeczywistość stwierdzeniem korzystającym z alternatywy wyrażanej za pomocą spójnika "lub": kaczka lata lub nie lata i ma skrzydła). Ujmując to symbolicznie, możemy przyjąć, że wiedzę wygodnie się zapisuje się w formacie koniunkcji alternatyw

 1 1 n n (φ1∨ ⋯ ∨ φi1)∧ ⋯ ∧ (φ1 ∨⋯ ∨φ in)

gdzie każde z φ i j jest literałem, czyli albo zdaniem atomowym (inaczej zwanym faktem), albo zaprzeczeniem zdania atomowego. Taką postać zdania logicznego nazywamy koniunkcyjną postacią normalną. Tego rodzaju wyrażenia można też zapisać w postaci

{φ1,...,φ1},...,{φ n,...,φ n} 1 i1 1 in

zwanej klauzulową postacią formuły, przy czym wyrażenia |{φ j,...,φ j} 1 ij nazywa się
briclink[2]klauzulami.

Wiadomo, że zapis klauzulowy ma charakter pełny - wszystkie zdania klasycznego rachunku zdań dają się równoważnie zapisać w koniunkcyjnej postaci normalnej, a więc w postaci klauzulowej.

obrazek

Zbudujmy teraz małą bazę faktów (którą można też nazywać bazą danych) ujętych w postaci klauzul. Ta nasza baza będzie opisywała widoczny tu obok graf złożony z czterech wierzchołków p,q,r,s oraz trzech krawędzi |(p,q),(r,q),(s,q). Będziemy starali się w tym grafie wypatrzeć ścieżkę Hamiltona (której tam zresztą nie ma). Dla tych, którzy nie wiedzą, albo nie pamiętają: ścieżka Hamiltona to ciąg wszystkich wierzchołków grafu, w którym (1) każde kolejne wierzchołki są połączone krawędzią, (2) nie mogą występować powtórzenia. Baza będzie operowała faktami postaci |p ,q ,r ,s, i i i i które oznaczają, że odpowiedni wierzchołek znajduje się na |i -tym miejscu hipotetycznej ścieżki Hamiltona. Oto jak wygląda zawartość bazy:

(1)
{p ,p ,p ,p }, 1 2 3 4 {q ,q ,q ,q }, 1 2 3 4 |{r,r ,r ,r }, 1 2 3 4 {s,s ,s ,s } 1 2 3 4
(każdy wierzchołek musi się pojawić na ścieżce),
(2)
{¬ p1,¬p2} {¬ p1,¬ p3},... , {¬ p3,¬p4},... , {¬s3,¬s4}
(żaden wierzchołek nie pojawia się na ścieżce dwa razy),
(3)
{p1,q1,r1,s1}, |{p2,q2,r2,s2}, |{p3,q3,r3,s3}, |{p4,q4,r4,s4},
(każda pozycja na ścieżce musi być zajęta),
(4)
{¬ p1,¬q1},...,{¬r1,¬s1},...,{¬ r4,¬ s4}
(żadne dwa różne wierzchołki nie zajmują tego samego miejsca w ciągu),
(5)
{¬ p1,¬r2},{¬p1,¬s2}, {¬p2,¬ r3},{¬p2,¬s3}, {¬ p3,¬r4},{¬p3,¬ s4},...,
{¬ s3,¬ r4}
(wierzchołki niepołączone krawędzią nie mogą sąsiadować na ścieżce).

Możemy teraz pobawić się jej zawartością. Do tego wykorzystamy regułę rezolucji, która ma następującą postać:

{-φ1,...,φ-k−1,¬p,-φk+1...,φn},{ψ1,...,ψl−1,p,-ψl+1,...,ψm-} {φ1,...,φk−1,φ k+1,...φn,ψ 1,...,ψl−1,ψ l+1,...,ψm }

Powyższe wzory mają następujące znaczenie: Jeśli w bazie faktów mamy dwie klauzule, z których jedna zawiera fakt, a druga jego negację, to można te klauzule połączyć, pozbywając się przy tym owego faktu i jego negacji. Nowo powstała klauzula jest dokładana do bazy. Istotę działania tej reguły łatwiej zrozumieć, jeśli uświadomimy sobie, że w logice klasycznej formuła ¬ p∨ RESZTA jest równoważna implikacji "jeśli |p, to RESZTA ". Taką właśnie postać ma pierwsza przedstawiona jawnie klauzula w regule rezolucji. Skoro zatem w drugiej klauzuli mamy w alternatywie p,| to zastąpienie tegoż przez coś, co z |p wynika, powinno dać wniosek spójny z dotychczasową wiedzą.Spójne z naszym rozumieniem powyższej bazy faktów byłoby dojście do sprzeczności, która w formalizmie klauzulowym jest reprezentowana jako pusta klauzula |{}. Można zatem teraz postawić konkretne zadanie: jak za pomocą rezolucji dojść do bazy danych, w której będziemy mieli taką pustą klauzulę?

Gdybyśmy mieli przeprowadzić rozumowanie udowadniające brak ścieżki Hamiltonowskiej, zapewne postąpilibyśmy jakoś tak. Gdyby ścieżka zaczynała się od p, wiodłaby do |q, a potem do r lub |s. W pierwszym przypadku nie moglibyśmy dojść do |s, w drugim nie moglibyśmy dojść do |r. Zatem ścieżka Hamiltonowska nie mogłaby się zaczynać od |p. Ze względu na symetrię grafu analogiczny argument zadziała dla r i s. Gdyby ścieżka zaczynała się od |q, to prowadziłaby po pierwszym kroku do |p,r lub |s. W każdym z tych przypadków nie mogłaby dojść do innych wierzchołków, w szczególności odpowiednio do r,s i p. Skoro rozważyliśmy wszystkie możliwe początki i dla żadnego z nich ścieżki nie było, to taka ścieżka nie istnieje.

Tego rodzaju rozumowania nie da się uprościć (zmniejszyć liczby analizowanych przypadków) za pomocą reguły rezolucji, bo nie pozwala ona na uwzględnienie symetrii. Zatem dowód z niej korzystający będzie musiał rozważyć bezpośrednio wszystkie przypadki. Jest ich dużo, spróbujmy jednak je sobie przynajmniej w części wyobrazić.

W powyższym szkicu istotne znaczenie ma sytuacja, gdy stwierdzamy, że nie może być ścieżki postaci p,q, r,s. Wiedza ta jest opisywana klauzulą |{¬p ,¬q ,¬ r, 1 2 3 |¬s }. 4 Spróbujmy zobaczyć, jak ją uzyskać. Możemy wyjść z klauzuli |{p2,q2,r2,s2} z grupy (3) i użyć rezolucji z klauzulą |{¬p1,¬r2} z grupy (5). Uzyskamy w ten sposób {¬p1,p2,q2,s2}. Następne dwa kroki polegające na połączeniu klauzul |{¬p1,¬s2},{¬p1,¬ p2} z kolejnymi klauzulami wynikowymi doprowadzają nas do |{¬p ,q }. 1 2 Nieco inną drogą z |{p2,q2,r2,s2} dostajemy {q2,¬ r3}, zaś z {p3, q3,r3,s3}, klauzulę |{¬s4,q3}. Tak uzyskane trzy klauzule połączone przez rezolucję z |{¬q2,¬q3} z grupy (2) dadzą oczekiwane {¬p1,¬ q2,¬r3,¬s4} (tu trzeba zwrócić uwagę, że klauzule są zbiorami, więc możemy skorzystać z trzech kopii |¬q2 w klauzuli {¬q2,¬ q3} ).

Jak widać, za pomocą małych kroczków rezolucji da się wykonywać większe kroki rozumowania. Jest to żmudne i wymaga nieco pomysłowości (chwilę trzeba pomyśleć, aby zgadnąć, od której klauzuli zacząć; a tak przy okazji: ciekawą łamigłówką jest pytanie, jak dojść do klauzuli mówiących, że niemożliwe są ścieżki startujące od q ; jeszcze ciekawszą - jak wykonać za pomocą przedstawionych tutaj klauzul mówiących o braku ścieżek, ostatni krok, dochodzący do sprzeczności). To wada, ale zaletą jest prostota metody - łatwo to zaprogramować. Ze żmudnością komputery jakoś sobie radzą. Stąd metoda rezolucji jest jedną z podstawowych technik w automatycznym dowodzeniu twierdzeń.