Sztuczna inteligencja/SI Moduł 5 - Wnioskowanie jako metoda przeszukiwania

Wprowadzenie

Jak mieliśmy okazję przekonać się w lekcji trzeciej, PROLOG jest językiem deklaratywnym, opisującym sposób sterowania algorytmem wnioskowania. Sama zasada wnioskowania polega na zastępowaniu stwierdzeń, których prawdziwość jest poddawana weryfikacji, przez inne stwierdzenia, zgodnie z zapisanymi definicjami predykatów. Proces ten kończy się wtedy, gdy algorytm wnioskowania dojdzie do stwierdzenia prawdziwego (gdyż zapisanego jako prawdziwe), bądź wtedy, gdy nie da się dopasować żadnej reguły wnioskowania.

Spróbujmy sobie wyobrazić graficznie schemat zależności między stwierdzeniami, poddawanymi weryfikacji, regułami i faktami. Dla przykładu rozważmy najpierw predykaty kr_ko, m_ko, m_kr, m_s, opisujące relacje: kraj położony na kontynencie, miasto położone na kontynencie, miasto położone w kraju oraz miasto będące stolicą kraju.

m_ko(Berlin, Europa).
m_ko(Warszawa, Europa).
m_ko(Kraków, Europa)
m_ko(Irkuck, Azja)
m_ko(Moskwa, Europa)

m_kr(„Kraków”, „Polska”).
m_kr(Irkuck, Rosja).

m_s(Warszawa, Polska).
m_s(Moskwa, Rosja).

m_kr(Miasto, Kraj):-
  m_s(Miasto, Kraj).
kr_ko(Kraj, Kont):-
  m_kr(Miasto, Kraj),
  m_ko(Miasto, Kont).

Skonstruujmy graf skierowany w następujący sposób (patrz rysunek poniżej). Istnieją dwa wyróżnione węzły: „prawda” i „porażka”. Węzeł „prawda” jest połączony krawędziami z każdym z podanych faktów (ujętymi w pola prostokątne). Węzeł „porażka” jest połączony krawędziami z każdym stwierdzeniem, którego zmiennych nie da podstawić na wartości zgodne z żadnym faktem ani z konkluzją żadnej z reguł. Każda definicja predykatu, będąca regułą, jest połączona krawędziami ze stwierdzeniami (ujętymi w zaoblone prostokąty), które są wynikiem podstawień zmiennych z części przesłankowej reguły. W przypadku reguł, w których część przesłankowa jest koniunkcją warunków logicznych, wprowadzamy pomocniczy węzeł koniunkcyjny (ujęty w owal), w którym zapisujemy podstawienia wszystkich zmiennych pomocniczych (tj. nie występujących jako elementy konkluzji reguły). W naszym przykładzie dotyczy to definicji predykatu kr_ko, której argumentami są Kraj i Kont, zaś zmienną pomocniczą jest Miasto.

Śledzenie ścieżek prowadzących do węzłów „prawda” i „porażka” jest istotą wnioskowania. Jako prawdziwe uznaje się:

• Fakty (prostokąty), połączone bezpośrednio z węzłem prawda (jak np. w przypadku faktu m_kr(„Kraków”, „Polska”).
• Pomocnicze węzły koniunkcyjne (owale), połączone wyłącznie z prawdziwymi węzłami,
• Stwierdzenia (zaoblone prostokąty) połączone z co najmniej jednym węzłem prawdziwym.