POLITECHNIKA WARSZAWSKA
MEL
MEL
WYDZIAA
MECHANICZNY ENERGETYKI I LOTNICTWA
WPROWADZENIE
DO SZTUCZNEJ INTELIGENCJI
NS 586
Dr in\
. Franciszek Dul
© F.A. Dul 2007
8. LOGIKA PIERWSZEGO
RZ
DU
RZ
DU
© F.A. Dul 2007
Logika pierwszego rzędu
Poka\
emy \
e świat w którym działają
agenci logiczni jest bardzo bogaty
 sÄ… w nim obiekty, relacje i zdarzenia.
Obiekty łączą ró\
ne relacje które agent
Obiekty łączą ró\
ne relacje które agent
powinien umieć odnalez
ć i wykorzystać
do realizacji swoich celów.
© F.A. Dul 2007
Plan rozdziału
" Reprezentacje świata.
" Logika pierwszego rzędu.
" Syntaktyka i semantyka logiki pierwszego rzędu.
" U\
ywanie logiki pierwszego rzędu.
" Świat Wumpusa w logice pierwszego rzędu.
" In\
ynieria wiedzy w logice pierwszego rzędu.
© F.A. Dul 2007
Niedostatki logiki boolowskiej...
Agent logiczny jest zdecydowanie  inteligentniejszy
od agenta celowego  dość bezmyślnie
poszukującego właściwego rozwiązania.
Agent logiczny posiada wiedzÄ™ i mo\
e wnioskować
o nieznanych (nieobserwowalnych) własnościach
świata.
Jednak logika której u\
ywał dotychczas do opisu
Jednak logika której u\
ywał dotychczas do opisu
rzeczywistości jest zbyt mało ekspresyjna
 reprezentacja nawet prostych faktów wymaga
często bardzo wielu zdań logicznych.
Zdecydowaną poprawę ekspresyjności reprezentacji
mo\
na uzyskać stosując zamiast rachunku zdań
logikę pierwszego rzędu.
© F.A. Dul 2007
8.1. Reprezentacja świata
Rachunek zdań - zalety i wady
Zalety
" Rachunek zdań jest deklaratywny,
" Rachunek zdań dopuszcza informację, która jest
niepełna, alternatywna, zanegowana
(w przeciwieństwie do większości baz danych)
" Rachunek zdań jest składalny (compositional)
np. znaczenie B1,1 '" P1,2 wynika ze znaczenia B1,1 i P1,2
'"
" Znaczenie w rachunku zdań nie zale\
y od kontekstu
w przeciwieństwie do języka naturalnego, w którym znaczenie
zdań zale\
y od kontekstu.
Wada
" Rachunek zdań ma bardzo ograniczoną ekspresywność
(w przeciwieństwie do języka naturalnego)
Np. nie mo\
na po prostu stwierdzić  dół powoduje wiatr w polach
przyległych - trzeba sformułować takie zdanie dla ka\
dego pola.
© F.A. Dul 2007
8.1. Reprezentacja świata
Logiki - ontologia i epistemologia
Zało\
enia ontologiczne - co istnieje w świecie
" Rachunek zdań: fakty zachodzą lub nie.
" Logika pierwszego rzędu: obiekty i relacje pomiędzy
nimi które zachodzą lub nie.
Zało\
enia epistemologiczne - co agent myśli na temat faktów
Zało\
enia Zało\
enia
Język
Język
ontologiczne epistemologiczne
ontologiczne epistemologiczne
Rachunek zdań Fakty Prawda / fałsz / nieokreślone
Logika pierwszego rzędu Fakty, obiekty, Prawda / fałsz / nieokreślone
relacje
Logika temporalna Fakty, obiekty, Prawda / fałsz / nieokreślone
relacje, czas
Teoria Fakty
Stopień ufności " [0,1]
prawdopodobieństwa
Logika rozmyta Fakty ze stopniem Znane przedziały wartości
prawdziwości " [0,1]
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Rachunek zdań (logika boolowska) zakłada, \
e świat opisany
jest tylko za pomocą faktów:
" Wumpus jest w polu (3,1), nie ma dołu w polu (2,2),
" 2 + 2 = 4, ...
Ontologia rachunku zdań jest ograniczona do faktów.
Logika pierwszego rzędu  First-Order Logic (FOL).
Logika pierwszego rzędu (podobnie jak język naturalny)
Logika pierwszego rzędu (podobnie jak język naturalny)
zakłada, \
e świat składa się z:
" obiektów: ludzi, domów, liczb, kolorów, zawodów,
meczów, podró\
y,...
" relacji: czerwony, okrągły, pierwszy, czyjś brat,
większy ni\
, część czegoś, pomiędzy,...
" funkcji: ojciec kogoś, najlepszy przyjaciel, dodać,
o jeden więcej ni\
, ...
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Przykład modelu w logice pierwszego rzędu
Królowie Ryszard Lwie Serce i Jan bez Ziemi (Anglia, XIII w.).
Obiekty
Relacje
korona
Funkcje
na głowie
brat
osoba
osoba
król
król
brat
lewa lewa
noga noga
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Syntaktyka logiki pierwszego rzędu
Podstawowe elementy syntaktyczne logiki pierwszego rzędu
" Stałe KrólJan, 2, MEiL,...
" Predykaty Brat, >, <, ...
" Funkcje Sqrt, LewaNoga, ...
" Zmienne x, y, a, b,...
" Operatory logiczne Ź , Ò! , '" , (" , Ô!
" Operatory logiczne Ź , Ò! , '" , (" , Ô!
" Równość =
" Kwantyfikatory ", "
Uwagi:
" Predykat jest innÄ… nazwÄ… funkcji zdaniowej.
" Predykat mo\
na uwa\
ać za szczególny rodzaj funkcji, która zwraca
wartość logiczną: prawdę lub fałsz.
" Predykaty mogą mieć jeden, dwa lub większą liczbę argumentów.
" Funkcja mo\
e zwracać obiekty ró\
nych typów.
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Zdania proste (atomowe) w logice pierwszego rzędu
Zdanie proste zbudowane jest z symboli predykatów
i opisuje fakt dotyczący obiektów i relacji między nimi.
Term = stała
lub zmienna
lub funkcja (term1,...,termn)
Zdanie proste = predykat (term1,...,termn)
lub term1 = term2
Zdanie P( x ,y ) czytamy:  x jest P y(greka) ( x is a P of y )
Zdanie P( x ,y ) czytamy:  x jest P y(greka) ( x is a P of y )
Przykłady:
 Jan jest królem.
Król(Jan)
 Król Jan jest bratem Ryszarda.
Brat( KrólJan , Ryszard )
 Ojciec Ryszarda i matka króla Jana są mał\
eństwem.
Mał\
eństwo( Ojciec(Ryszard) , Matka( KrólJan ) )
 Lewa noga Ryszarda jest dłu\
sza ni\
lewa noga króla Jana.
>( Długość( LewaNoga(Ryszard)) , Długość( LewaNoga( KrólJan )))
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Zdania zło\
one w logice pierwszego rzędu
Zdania zło\
one zbudowane są ze zdań prostych za pomocą
operatorów logicznych,
ŹS, S1 '" S2, S1 (" S2, S1 Ò! S2 , S1 Ô! S2,
Przykłady:
 Je\
eli król Jan jest bratem Ryszarda to Ryszard jest bratem
króla Jana.
Brat( KrólJan , Ryszard ) Ò! Brat( Ryszard , KrólJan )
Brat( KrólJan , Ryszard ) Ò! Brat( Ryszard , KrólJan )
 Król Jan ma koronę na głowie i Król Jan i Ryszard są rodzeństwem.
NaGłowie( Korona , KrólJan ) '" Rodzeństwo( Ryszard , KrólJan )
 a jest większe ni\
b lub a jest mniejsze ni\
b.
>(a,b) (" <(a,b)
Konkretyzacja (instantiations) P(C) zdania P(x) polega
na zastąpieniu zmiennej x dowolną stałą C, np.
Brat(x,Ryszard) x/KrólJan Brat( KrólJan , Ryszard )
Brat(x,Ryszard) x/Korona Brat( Korona , Ryszard ) (!)
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Prawdziwość zdań w logice pierwszego rzędu
Prawdziwość zdań w logice pierwszego rzędu rozpatruje się
względem modelu oraz interpretacji.
Modele zawierajÄ… obiekty (elementy z dziedziny) oraz relacje
zachodzące między nimi.
Interpretacje określają odniesienia pomiędzy:
" symbolami stałych a obiektami
" symbolami predykatów a relacjami pomiędzy obiektami
" symbolami funkcji a zale\
nościami funkcyjnymi
" symbolami funkcji a zale\
nościami funkcyjnymi
Przykład
KrólJan Król Jan
ale mo\
liwe sÄ… tak\
e interpretacje  dziwne , np.:
Ryszard korona (!)
Prawdziwość zdań FOL
Zdanie proste predykat(term1,...,termn) jest prawdziwe
wtedy i tylko wtedy gdy obiekty term1,...,termn spełniają
relacjÄ™ predykat( ... ).
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Kwantyfikatory w logice pierwszego rzędu
Kwantyfikatory sÄ… elementami syntaktycznymi logiki
pierwszego rzędu które nie występują w rachunku zdań.
Kwantyfikatory pozwalają opisywać zwięz
le własności zbioru
obiektów (nawet nieskończonego).
Istnieją dwa rodzaje kwantyfikatorów:
" " kwantyfikator ogólny ( dla wszystkich )
"
"
"
" " kwantyfikator szczegółowy ( istnieje ).
" " kwantyfikator szczegółowy ( istnieje ).
"
"
"
"
"
"
U\
ycie kwantyfikatorów eliminuje konieczność wyliczania
obiektów poprzez podanie ich nazw.
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Kwantyfikator ogólny
Składnia kwantyfikatora ogólnego
"
Przykład:  Na MEiL-u wszyscy są sympatyczni
"x Na(x,MEiL) Ò! Sympatyczny(x)
Zdanie "x P(x) jest prawdziwe dla modelu m wtedy i tylko
wtedy gdy P jest prawdziwe dla ka\
dego x będącego
wtedy gdy P jest prawdziwe dla ka\
dego x będącego
obiektem modelu.
U\
ycie kwantyfikatora ogólnego jest równowa\
ne koniunkcji
konkretyzacji zdania P,
Na( KrólJan , MEiL ) Ò! Sympatyczny( KrólJan ) '"
Na( JamesBond , MEiL ) Ò! Sympatyczny( JamesBond ) '"
Na( MEiL , MEiL ) Ò! Sympatyczny( MEiL ) '" ...
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Kwantyfikator szczegółowy
Składnia kwantyfikatora ogólnego
"
Przykład:  Ktoś na MEiL-u jest sympatyczny
" x Na(x,MEiL) '" Sympatyczny(x)
Zdanie "x P(x) jest prawdziwe dla modelu m wtedy i tylko
wtedy gdy P jest prawdziwe dla pewnego x będącego
wtedy gdy P jest prawdziwe dla pewnego x będącego
obiektem modelu.
U\
ycie kwantyfikatora ogólnego jest równowa\
ne alternatywom
konkretyzacji zdania P,
Na( KrólJan , MEiL ) '" Sympatyczny( KrólJan ) ("
Na( JamesBond , MEiL ) '" Sympatyczny( JamesBond ) ("
Na( MEiL , MEiL ) '" Sympatyczny( MEiL ) (" ...
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Kwantyfikatory - typowe błędy
Zazwyczaj z kwantyfikatorem ogólnym " łączy się operator
wynikania Ò!
Typowy błąd polega na łączeniu z kwantyfikatorem ogólnym
" operatora koniunkcji '" , np.
"x Na(x, MEiL) '" Sympatyczny(x)
co znaczy:  Ka\
dy jest na MEiL-u i ka\
dy jest sympatyczny
Z kwantyfikatorem szczegółowym " łączy się z kolei operator
koniunkcji '"
Typowy błąd polega na łączeniu z kwantyfikatorem
szczegółowym " operatora implikacji Ò! , np. zdanie
" x Na(x, MEiL) Ò! Sympatyczny(x)
jest prawdziwe nawet wtedy, gdy na MEiL-u nie ma nikogo.
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Własności kwantyfikatorów
" "x "y a" "x,y
" "x "y a" " x, y
" "x "y a" "y "x
" "x "y a" "y "x
" "x "y nie jest równowa\
ne "y "x:
 Everybody loves somebody
"y "x Loves(x,y)  Ka\
dy (y) jest kochany przez kogoÅ› (x)
"x "y Loves(x,y)  Ktoś (x) która kocha ka\
dego (y)
"x "y Loves(x,y)  Ktoś (x) która kocha ka\
dego (y)
" Dualizm kwantyfikatorów:
jeden mo\
e być wyra\
ony za pomocÄ… drugiego, np.
"x Lubi( x , Lody ) Ź"x ŹLubi( x , Lody )
"x Lubi( x , Mozart ) Ź"x ŹLubi( x , Mozart )
" Prawa De Morgana dla kwantyfikatorów:
Ź"x P(x) a" "x ŹP(x)
"x ŹP(x) a" Ź"x P(x)
"x P(x) a" Ź"x ŹP(x)
"x P(x) a" Ź"x P(x)
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Równość logiczna
Symbol równości = słu\
y do budowania zdań logicznych.
Równość term1 = term2 jest prawdą w danej interpretacji
wtedy i tylko wtedy gdy term1 i term2 odnoszÄ… siÄ™ do tego
samego obiektu.
Przykłady:
Określenie osoby będącej ojcem Jana
Ojciec( Jan ) = Henryk
Ojciec( Jan ) = Henryk
Definicja Rodzeństwa wyra\
ona za pomocą pojęcia Rodzica:
"x,y Rodzeństwo(x,y)
Ô! [Ź(x = y) '" " m,f Ź (m = f ) '"
Rodzic(m,x) '" Rodzic(f,x) '" Rodzic(m,y) '" Rodzic(f,y) ]
Ź(x = y) wyra\
a ró\
ność osób będących rodzeństwem,
Ź(m = f) wyra\
a ró\
ność rodziców.
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Podstawienie logiczne
Podstawienie (substitution) słu\
y do otrzymywania ze zdań
ogólnych zdań dotyczących konkretnych obiektów.
Podstawienie ą ma postać
Ä… = { zmienna / obiekt , ... }
" Dane jest zdanie S oraz podstawienie Ä…,
" SÄ… oznacza wynik wstawienia Ä… do zdania S;
Przykład
S = Sprytniejszy(x,y)
Ä… = { x/Ewa , y/Adam }
SÄ… = Sprytniejszy( Ewa , Adam )
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Logika pierwszego rzędu ma następujące cechy:
" Mo\
e wyra\
ać fakty dotyczące dowolnych obiektów
w świecie.
" Pozwala reprezentować ogólne zasady rządzące
światem.
" Nie mo\
na w niej dowieść fałszywego twierdzenia
(soundness).
" Wszystkie prawdziwe twierdzenia mają dowód
" Wszystkie prawdziwe twierdzenia mają dowód
(completeness)
(completeness)
" Nie pozwala jednak reprezentować kategorii, czasu
lub zdarzeń.
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Matematyka
Definicja rekurencyjna liczb naturalnych w języku logiki
pierwszego rzędu.
" Funkcja następnika S
S(0) = 1, S(S(0)) = 2, ...
" Aksjomaty Peano
NatNum(0)
"n NatNum(n) Ò! NatNum( S(n) )
"n NatNum(n) Ò! NatNum( S(n) )
" Aksjomaty następnika
"n 0 `" S(n)
"m, n m `" n Ò! S(m) `" S(n)
" Definicja dodawania za pomocą następnika
"m NatNum(m) Ò! +(0,m) = m
"m, n NatNum(m) ) '" NatNum(n) Ò! +(S(m),n) = S(+(m,n))
" Notacja wewnętrzna -  cukier syntaktyczny ; S(n) = n+1
"m, n NatNum(m) ) '" NatNum(n) Ò! (m+1)+n = (m+n)+1
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Socjologia
Wyra\
enie relacji pokrewieństwa w języku logiki pierwszego
rzędu.
" Bracia są rodzeństwem
"x,y Brat(x,y) Ô! RodzeÅ„stwo(x,y)
" CzyjaÅ› matka jest czyjÄ…Å› \
eńską rodzicielką
"m,c Matka(c) = m Ô! (Å›eÅ„ski(m) '" Rodzić(m,c))
"  Rodzeństwo jest relacją symetryczną
"x,y RodzeÅ„stwo(x,y) Ô! RodzeÅ„stwo(y,x)
" Kuzyn jest dzieckiem rodzeństwa rodzica
"x,y Kuzyn(x,y) Ô!
"p,q Rodzic(p,x) '" Rodzeństwo(q,p) '" Rodzic(q,y)
" itd.
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Logika pierwszego rzędu w bazach wiedzy
Baza wiedzy zapisanej w logice pierwszego rzędu - operacje
komunikacji TELL i ASK.
Baza wiedzy FOL  asercje (stwierdzenia prawdy):
TELL( KB , Król(Jan) )
TELL( KB , Osoba(Ryszard) )
TELL( KB , "x Król(x) Ò! Osoba(x) )
Baza wiedzy FOL  zapytania (kwerendy):
Baza wiedzy FOL  zapytania (kwerendy):
ASK( KB , Król(Jan) ) True
ASK( KB , Osoba(Jan) ) True
Zapytanie kwantyfikowane - odpowiedz
trywialna
ASK( KB , "x Osoba(x) ) True
Odpowiedz
na zapytanie kwantyfikowane w postaci
podstawienia lub listy podstawień
ASK( KB , "x Osoba(x) ) {x/Jan} , {x/Ryszard}.
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Baza wiedzy FOL dla świata Wumpusa
Reprezentacja obserwacji i działań w języku FOL.
Wiedza w bazie KB świata Wumpusa musi obejmować
obserwacje oraz czasy w których zostały wykonane.
" Typowa obserwacja, np. w chwili t = 5:
Obserwacja( [Odór,Wiatr,Blask,Nic,Nic] , 5 )
" Zapis działań agenta w języku FOL:
Skręć(WPrawo), Skręć(WLewo), WPrzód,
Skręć(WPrawo), Skręć(WLewo), WPrzód,
Strzał, Chwyć, Puść, WspinajSię
" Aby wyznaczyć najlepsze działanie agent tworzy zapytanie:
" a NajlepszeDziałanie(a,5)
" ASK wyznacza odpowiedz
i zwraca podstawienie, np.
ASK( KB , "a NajlepszeDziałanie(a,5) ) {a/Chwyć}
" Jednocześnie baza jest informowana za pomocą TELL
o podjętym działaniu,
TELL( KB , NajlepszeDziałanie( {a/Chwyć}, 5 ))
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Baza wiedzy FOL dla świata Wumpusa
" Obserwacje w rodzaju
"t,s,g,m,c Obserwacja( [s,Wiatr,g,m,c],t ) Ò! Wietrzne(t)
"t,s,b,m,c Obserwacja( [s,b,Blask,m,c],t ) Ò! BÅ‚yszczy(t)
stanowiÄ… rodzaj wnioskowania zwany percepcjÄ….
" Działania agenta refleksowego mogą być opisane
zdaniami kwantyfikowanymi, np.
"t BÅ‚yszczy(t) Ò! NajlepszeDziaÅ‚anie( Chwyć , t )
"t BÅ‚yszczy(t) Ò! NajlepszeDziaÅ‚anie( Chwyć , t )
" Agent refleksowy ze stanem wewnętrznym
"t Błyszczy(t) '" ŹTrzyma(Agent,Złoto,t)
Ź
Ź
Ź
Ò! NajlepszeDziaÅ‚anie( Chwyć,t )
Ale uwaga! Predykat Trzyma(Agent,ZÅ‚oto,t) nie jest obserwowany.
Mo\
na tylko śledzić zmiany poło\
enia ZÅ‚ota.
Wszystkie zdania sÄ… synchroniczne - nie obejmujÄ… historii
obserwacji i działań.
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Baza wiedzy FOL dla świata Wumpusa
Reprezentacja środowiska i obiektów w języku FOL.
" Nazwy obiektów w języku FOL:
Agent, Wumpus, Dół, Pole[i,j]
" Sąsiedztwo pól mo\
na zapisać następująco:
"x,y,a,b SÄ…siednie( [x,y] , [a,b] )
Ô! [a,b]"{ [x-1,y], [x+1,y], [x,y-1], [x,y+1] }
" Połe w którym jest Wumpus definiuje funkcja
" Połe w którym jest Wumpus definiuje funkcja
Dom(Wumpus)
" Poło\
enie agenta zmienia siÄ™ z czasem,
JestWPolu( Agent, s, t )
" Agent mo\
e wnioskować o własnościach pola w którym
przebywa, np.
"s,t JestWPolu( Agent, s, t ) '" Wiatr(t) Ò! Wietrzne(s)
Mając informację o własnościach środowiska agent mo\
e
wnioskować o poło\
eniu dołów i Wumpusa.
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Odkrywanie ukrytych własności środowiska
IstniejÄ… dwa rodzaje wnioskowania dedukcyjnego:
" Wnioskowanie diagnostyczne  wnioskowanie o ukrytych
przyczynach na podstawie poczynionych obserwacji.
Na przykład obserwacja
"s Wietrzne(s) Ò! " r SÄ…siednie(r,s) '" Dół(r)
prowadzi do wniosku, \
e w pewnym polu sÄ…siednim
jest dół, zaś obserwacja
"s ŹWietrzne(s) Ò! Ź" r SÄ…siednie(r,s) '" Dół(r)
"s ŹWietrzne(s) Ò! Ź" r SÄ…siednie(r,s) '" Dół(r)
oznacza, \
e w \
adnym polu sąsiednim nie ma dołu.
Połączenie tych obserwacji daje regułę ogólną dla
poło\
enia dołów
"s Wietrzne(s) Ô! " r SÄ…siednie(r,s) '" Dół(r)
Wnioskowanie diagnostyczne stosowane jest wówczas, gdy
nie istnieje adekwatny model świata.
Wnioskowanie diagnostyczne jest stosowane powszechnie
w medycynie.
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Odkrywanie ukrytych własności środowiska
" Wnioskowanie przyczynowe  wnioskowanie na podstawie
znanego modelu świata.
Ukryte przyczyny powodujÄ… obserwowane efekty.
Na przykład model powstania wiatru w polach
"r Dół(r) Ò! [ "s SÄ…siednie(r,s) Ò! Wietrzne(s) ]
oraz obserwacja, \
e w polach przyległych nie ma dołów
prowadzÄ… do wniosku, \
e w polu nie ma wiatru
"s [ "r SÄ…siednie(r,s) Ò! ŹDół(r) ] Ò! ŹWietrzne(s)
"s [ "r SÄ…siednie(r,s) Ò! ŹDół(r) ] Ò! ŹWietrzne(s)
Mo\
na wykazać, \
e powy\
sze zdania są równowa\
ne
regułę
"s Wietrzne(s) Ô! " r SÄ…siednie(r,s) '" Dół(r)
Wnioskowanie diagnostyczne i przyczynowe prowadzÄ…
zatem do tych samych konkluzji przy zało\
eniu, \
e
model świata jest poprawny.
Wnioskowanie przyczynowe stosowane jest wtedy, gdy
istnieje adekwatny model świata.
© F.A. Dul 2007
8.3. Zastosowanie logiki pierwszego rzędu
Odkrywanie ukrytych własności środowiska
Rozró\
nienie pomiędzy wnioskowanie przyczynowym
i diagnostycznym jest istotne w wielu obszarach sztucznej
inteligencji.
Systemy ekspertowe bazujÄ… na obu rodzajach wnioskowania,
lecz np. w medycynie przewa\
a wnioskowanie diagnostyczne.
Wraz z opracowaniem modeli zjawisk wnioskowanie
przyczynowe wypiera wnioskowanie diagnostyczne.
Je\
eli niezale\
nie od reprezentacji aksjomaty opisują świat
oraz obserwacje w sposób poprawny i zupełny, to ka\
de
zupełne wnioskowanie logiczne prowadzi do najlepszego
mo\
liwego opisu stanu świata przy danych obserwacjach.
Wynika stÄ…d, \
e projektujÄ…c systemy wykorzystujÄ…ce bazy
wiedzy i wnioskowanie, nale\
y skupić się na gromadzeniu
mo\
liwie obszernej i poprawnej wiedzy, a nie na samym
procesie wnioskowania.
© F.A. Dul 2007
8.4. In\
ynieria wiedzy w logice pierwszego rzędu
Proces budowania bazy wiedzy nazywany jest in\
ynieriÄ…
wiedzy.
Etapy budowy bazy wiedzy:
" Sformułowanie zadania.
" Zgromadzenie wiedzy istotnej dla zadania.
" Wybór odpowiedniego słownika dla predykatów,
funkcji oraz stałych.
funkcji oraz stałych.
" Zapisanie w języku FOL ogólnej wiedzy na temat
dziedziny.
" Zapisanie w języku FOL specyficznych cech zadania.
" Formułowanie zapytań dla procedury wnioskowania
i odbieranie odpowiedzi.
" Usuwanie błędów z bazy wiedzy.
© F.A. Dul 2007
8.4. In\
ynieria wiedzy w logice pierwszego rzędu
Przykład z dziedziny obwodów elektrycznych
Jednobitowy układ sumujący.
Bit 1
Bit sumy
Bit 2
Bit
przeniesienia
Bit
przeniesienia
Układ oblicza sumę logiczną bitów Bit 1 i Bit 2.
Układ jest zbudowany z przewodów i bramek AND, OR, XOR
Nale\
y zbudować bazę wiedzy w języku FOL.
Przykłady pytań do bazy wiedzy:
- Czy układ potrafi poprawnie dodawać?
- Tabela stanów wyjściowych dla wszystkich stanów wejściowych.
- Czy w układzie występują pętle sprzę\
eń zwrotnych?
© F.A. Dul 2007
8.4. In\
ynieria wiedzy w logice pierwszego rzędu
" Sformułowanie zadania
 Zbudować bazę wiedzy
opisującą działanie układu
w logice pierwszego rzędu.
" Zgromadzenie wiedzy
istotnej dla zadania
 Układ jest zbudowany z przewodów i bramek;
Typy bramek: AND, OR, XOR.
 Cechy nieistotne: rozmiar, kształt, kolor, koszt bramek
" Wybór odpowiedniego słownika
 Alternatywne sposoby opisu:
Typ( X1 ) = XOR
Typ( X1, XOR )
XOR( X1 )
© F.A. Dul 2007
8.4. In\
ynieria wiedzy w logice pierwszego rzędu
" Zapisanie w języku FOL ogólnej
wiedzy o układzie
Definicje mo\
liwych sygnałów:
"t Sygnał(t) = 1 (" Sygnał(t) = 0
1 `" 0
Definicje działania bramek:
"t1,t2 PoÅ‚Ä…czony(t1, t2) Ò! PoÅ‚Ä…czony(t2, t1)
"t ,t PoÅ‚Ä…czony(t , t2) Ò! SygnaÅ‚(t ) = SygnaÅ‚(t2)
"t1,t2 PoÅ‚Ä…czony(t1, t ) Ò! SygnaÅ‚(t1) = SygnaÅ‚(t )
Definicje działania bramek:
"g Typ(g)=OR Ò! SygnaÅ‚(Wyj(1,g)) = 1 Ô! "n SygnaÅ‚(Wej(n,g)) = 1
"g Typ(g)=AND Ò! SygnaÅ‚(Wyj(1,g)) = 0 Ô! "n SygnaÅ‚(Wej(n,g)) = 0
"g Typ(g)=XOR Ò! SygnaÅ‚(Wej(1,g)) = 1 Ô!
Ô! SygnaÅ‚(Wej(1,g)) `" SygnaÅ‚(Wej(2,g))
"g Typ(g)=NOT Ò! SygnaÅ‚(Wyj(1,g)) `" SygnaÅ‚(Wej(1,g))
© F.A. Dul 2007
8.4. In\
ynieria wiedzy w logice pierwszego rzędu
" Zapisanie w języku FOL
specyficznych cech zadania
Definicje typów bramek:
Typ(X1) = XOR
Typ(X2) = XOR
Typ(A1) = AND
Typ(A2) = AND
Typ(O1) = OR
Definicje połączeń:
Połączony(Wyj(1,X1), Wej(1,X2)) Połączony(Wej(1,C1), Wej(1,X1))
Połączony(Wyj(1,X1), Wej(2,A2)) Połączony(Wej(1,C1), Wej(1,A1))
Połączony(Wyj(1,A2), Wej(1,O1)) Połączony(Wej(2,C1), Wej(2,X1))
Połączony(Wyj(1,A1), Wej(2,O1)) Połączony(Wej(2,C1), Wej(2,A1))
Połączony(Wyj(1,X2), Wyj(1,C1)) Połączony(Wej(3,C1), Wej(2,X2))
Połączony(Wyj(1,O1), Wyj(2,C1)) Połączony(Wej(3,C1), Wej(1,A2))
© F.A. Dul 2007
8.4. In\
ynieria wiedzy w logice pierwszego rzędu
" Formułowanie zapytań
dla procedury wnioskowania
i odbieranie odpowiedzi:
Jakie kombinacje sygnałów
wejściowych dają wartości
wyjściowe o1 = 0, o2 =1?
" i1,i2,i3 Sygnał(Wej(1,C1)) = i1 '" Sygnał(Wej(2,C1)) = i2 '"
Sygnał(Wej(3,C1)) = i3 '" Sygnał(Wyj(1,C1)) = 0 '" Sygnał(Wyj(2,C1)) = 1
Odpowiedz
: podstawienia:
Odpowiedz
: podstawienia: {i1/1 i2 /1,i3 /0 } , {i1/1 i2 /0,i3 /1 } , {i1/0 i2 /1,i3 /1 }.
1 2 3 1 2 3 1 2 3
Jaki jest zbiór mo\
liwych wartości dla wszystkich końcówek
układu sumującego?
" i1,i2,i3,o1,o2 Sygnał(Wej(1,C1)) = i1 '" Sygnał(Wej(2,C1)) = i2 '"
Sygnał(Wej(3,C1)) = i3 '" Sygnał(Wyj(1,C1)) = o1 '" Sygnał(Wyj(2,C1)) = o2
Odpowiedz
: Tabela wartości wejścia-wyjścia
Weryfikacja obwodu: Czy układ potrafi poprawnie dodawać?
" Usunięcie błędów z bazy wiedzy
Np. pominięcie asercji 1 `" 0 prowadzi do błędnych odpowiedzi
dotyczących działania układu.
© F.A. Dul 2007
8.2. Logika pierwszego rzędu
Ekspresja systemów logicznych
Ekspresja logiki pierwszego rzędu nie jest wystarczająco
silna, aby opisać ka\
de stwierdzenie.
W logice pierwszego rzędu nie mo\
na np. zapisać
stwierdzenia:
 Wszystkie predykaty majÄ… jeden argument .
Takie zdanie wymaga logiki wy\
szego rzędu w której mo\
na
wypowiadać się na temat predykatów a nie tylko zmiennych.
wypowiadać się na temat predykatów a nie tylko zmiennych.
Większe mo\
liwości ekspresji mają logiki wy\
szego rzędu
(Higher-Order Logic, HOL).
Przykłady:
 Piłka jest czerwona - logika pierwszego rzędu,
 Czerwień to kolor - logika drugiego rzędu,
 Kolor to atrybut - logika trzeciego rzędu.
Logiki wy\
szego rzędu są jednak trudne w implementacji,
co praktycznie wyklucza ich stosowanie.
© F.A. Dul 2007
Podsumowanie
" Język reprezentacji wiedzy musi być: deklaratywny, składal-
ny, ekspresyjny, niezale\
ny od kontekstu i jednoznaczny.
" Rachunek zdań opisuje tylko fakty; logika pierwszego rzędu
(FOL) opisuje tak\
e obiekty i relacje pomiędzy nimi.
" Logika pierwszego rzędu ma du\
o większą ekspresywność
ni\
rachunek zdań.
" Modele FOL zawierajÄ… obiekty, relacje i funkcje.
" Składnia logiki pierwszego rzędu obejmuje: stałe, predykaty,
funkcje i kwantyfikatory.
funkcje i kwantyfikatory.
" Kwantyfikatory pozwalają budować ogólne zdania zło\
one.
" Stałe oznaczają obiekty, predykaty opisują relacje między
obiektami, funkcje opisujÄ… zale\
ności funkcyjne.
" Interpretacja odwzorowuje symbole na elementy modelu.
" Budowa bazy wiedzy wymaga analizy zadania, wyboru
słownika oraz sformułowania właściwych aksjomatów.
" Logiki rzędów wy\
szych mają jeszcze większe mo\
liwości
ekspresji, ale ich implementacja jest du\
o bardziej zło\
ona.
© F.A. Dul 2007