Sztuczna inteligencja/SI Moduł 2/Semantyka języka logiki

Semantyka języka logiki

Semantyka języka logiki określa sposób, w jaki formułom zapisanym zgodnie z podanymi wyżej regułami składni, można przypisać znaczenie, które z kolei pozwala określić ich wartość logiczną. Aby stało się to możliwe, musi oczywiście zostać określone znaczenie wszystkich symboli wchodzących w skład alfabetu języka logiki, a następnie zasady, zgodnie z którymi określa się znaczenie formuł na podstawie znaczenia symboli w nich występujących. Nie będziemy tu prezentować semantyki języka logiki w sposób w pełni formalny i systematyczny, poprzestając tylko na zwięzłym nieformalnym szkicu.

Dziedzina

Aby interpretować formuły języka predykatów musimy (w ogólnym przypadku) przyjąć pewną ustaloną dziedzinę, do której te formuły się odnoszą. Dziedzina jest zbiorem obiektów (np. przedmiotów, ludzi, sytuacji, zdarzeń itp.), na temat właściwości których lub relacji między którymi wiedzę zamierzamy zapisywać w języku logiki.

Przykład: świat klocków. Będziemy ilustrować definicję semantyki języka logiki posługując się prostym przykładem świata klocków, zilustrowanym na rysunku. Dziedzina jest w tym przypadku zbiorem pięciu klocków $\{A,B,C,D,E\}$,.

\begin{figure}[h] \includegraphics[width=6cm]{rysunki/klocki.eps} \end{figure}

Interpretacja symboli

Mając ustaloną pewną dziedzinę $X$,, symbole alfabetu języka predykatów interpretujemy następująco.

• Symbole stałych: symbol stałej $a$, oznacza pewien obiekt z dziedziny $I(a)\in X$,.
• Symbole funkcyjne: $m$,-argumentowy symbol funkcyjny $f$, oznacza $m$,-argumentowa funkcje $I(f):X^m\mapsto X$,.
• Symbole predykatowe: $m$,-argumentowy symbol predykatowy $P$, oznacza $m$,-argumentowa relacje $I(P)\subset X^m$, (równoważnie, możemy przyjąć, że $P$, oznacza funkcje $I(P):X^m\mapsto \{0,1\}$,).

Przypomnijmy sobie, że relacją $m$, argumentową określoną na zbiorze $X$, jest dowolny podzbior iloczynu kartezjanskiego $X^m$,. Dla krotki złożonej z $m$, elementow zbioru $X$,, która należy do relacji, mówimy także, że relacja jest spełniona.

Operatory logiczne, kwantyfikatory i nawiasy służą do budowania formuł złożonych z formuł atomowych i nie mają samodzielnej interpretacji. Z kolei symbole zmiennych wyłączone są z intepretacji - mając ustaloną interpretację, byłyby identyczne z symbolami stałych. Dopuszcza się jednak przypisywanie zmiennym znaczenia przy intepretowaniu konkretnej formuły za pomocą wartościowania. Wartościowanie jest dowolnym odwzorowaniem symboli zmiennych na elementy dziedziny - dla symbolu zmiennej $x$, wartosciowanie $v$, określa wartosc $v(x)\in X$,.

Przykład: świat klocków. Rozważmy język logiki predykatów, którego alfabet zawiera symbole stałych $\{a,b,c,d,e\}$,. Możemy przyjąć interpretację, w której każdemu symbolowi stałej odpowiada inny klocek z dziedziny, np.:

$I(a)=A$,	(1)
$I(b)=B$,	(2)
$I(c)=C$,	(3)
$I(d)=D$,	(4)
$I(e)=E$,	(5)

Przyjmiemy także, że a alfabecie znajdują się dwa symbole zmiennych $x$, i $y$,, dla których określono wartościowanie następująco:

$v(x)=C$,	(6)
$v(y)=B$,	(7)

Załóżmy dalej, że alfabet zawiera dwa jednoargumentowe symbole funkcyjne $f$, i $g$,. Nasza interpretacja będzie im przypisywać odpowiednio dwuargumentowe funkcje określone na dziedzinie:

$I(f)=\text{<mrow data-mjx-texclass="ORD">gora</mrow>}$,	(8)
$I(g)=\text{<mrow data-mjx-texclass="ORD">dol</mrow>}$,	(9)

Funkcje te określimy następująco:

$\text{<mrow data-mjx-texclass="ORD">gora</mrow>}(A)=B\text{<mrow data-mjx-texclass="ORD">dol</mrow>}(A)=A$,	(10)
$\text{<mrow data-mjx-texclass="ORD">gora</mrow>}(B)=C\text{<mrow data-mjx-texclass="ORD">dol</mrow>}(B)=A$,	(11)
$\text{<mrow data-mjx-texclass="ORD">gora</mrow>}(C)=C\text{<mrow data-mjx-texclass="ORD">dol</mrow>}(C)=B$,	(12)
$\text{<mrow data-mjx-texclass="ORD">gora</mrow>}(D)=E\text{<mrow data-mjx-texclass="ORD">dol</mrow>}(D)=D$,	(13)
$\text{<mrow data-mjx-texclass="ORD">gora</mrow>}(E)=E\text{<mrow data-mjx-texclass="ORD">dol</mrow>}(E)=D$,	(14)

(jak widać, funkcja $\text{<mrow data-mjx-texclass="ORD">gora</mrow>}$, przypisuje każdemu klockowi jego sąsiada z góry, o ile istnieje, albo jego samego; podobnie funkcja $\text{<mrow data-mjx-texclass="ORD">dol</mrow>}$, przypisuje każdemu klockowi jego sąsiada z dołu, o ile istnieje, albo jego samego). Założymy także, że alfabet naszego języka logiki zawiera dwuargumentowe symbole predykatowe $P$,, $Q$, i $R$,, których interpretację ustalimy następująco:

$I(P)=\text{<mrow data-mjx-texclass="ORD">na</mrow>}$,	(15)
$I(Q)=\text{<mrow data-mjx-texclass="ORD">nad</mrow>}$,	(16)
$I(R)=\text{<mrow data-mjx-texclass="ORD">rowne</mrow>}$,	(17)

przy czym:

• $\text{<mrow data-mjx-texclass="ORD">na</mrow>}$, jest relacją dwuargumentową, do której należą wszystkie pary klocków takie, że pierwszy leży na drugim: $⟨B,A⟩$,, $⟨C,B⟩$,, $⟨E,D⟩$,,
• $\text{<mrow data-mjx-texclass="ORD">nad</mrow>}$, jest relacją dwuargumentową, do której należą wszystkie pary klocków takie, że pierwszy leży nad drugim (tj. na nim lub wyżej): $⟨B,A⟩$,, $⟨C,A⟩$,, $⟨C,B⟩$,, $⟨E,D⟩$,,
• $\text{<mrow data-mjx-texclass="ORD">rowne</mrow>}$, jest relacją dwuargumentową, do której należą wszystkie pary złożone z dwóch wystąpień tych samych klocków: $⟨A,A⟩$,, $⟨B,B⟩$,, $⟨C,C⟩$,, $⟨D,D⟩$,, $⟨E,E⟩$,.

Interpretacja termów

Interpretacja wraz z wartościowaniem pozwala ustalić znaczenie dowolnego termu. Dla interpretacji $I$, i wartosciowania $v$, oznaczmy dla wygody przez $I_v$, ich połączenie, rozumiane następująco:

• dla symboli stałych: $I_v(a)=I(a)$,,
• dla symboli zmiennych: $I_v(x)=v(x)$,.

Termy złożone interpretowane są przez zastosowanie intepretacji do wchodzących w ich skład symboli stałych i symboli funkcyjnych oraz zastosowanie wartościowania do wchodzących w ich skład zmiennych. Przy ustalonej dziedzinie, interpretacji $I$, i wartosciowaniu $v$,, może być wyznaczone znaczenie każdego termu postaci $f(t_1,t_2,\dots ,t_m)$, w następujący sposób:

$I_v(f(t_1,t_2,\dots ,t_m))=I(f)(I_v(t_1),I_v(t_2),\dots ,I_v(t_m))$, (18)

Przykład: ślad klocków. Weźmy pod uwagę term $f(b)$,. Poniewaz $I(b)=B$,, $I(f)=\text{<mrow data-mjx-texclass="ORD">gora</mrow>}$, oraz $\text{<mrow data-mjx-texclass="ORD">gora</mrow>}(B)=C$,, wiec oczywiscie $I(f(b))=C$,. Podobnie łatwo można sprawdzić interpretację następujących termów:

$I_v(f(x))=C$,	(19)
$I_v(g(y))=A$,	(20)

Interpretacja formuł

Formuły atomowe intepretowane są podobnie jak termy złożone: przez zastosowanie intepretacji i wartościowania do każdego występującego w nich symbolu. Dla formuły postaci $P(t_1,t_2,\dots ,t_m)$, otrzymujemy w ten sposób relację $I(P)$, oraz krotke $m$, obiektów z dziedziny $⟨I_v(t_1),I_v(t_2),\dots ,I_v(t_m)⟩\in X^m$,. Znaczeniem formuły będzie jej wartość logiczna określona na podstawie tego, czy krotka obiektów należy do relacji:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{cases}”): {\displaystyle I_v(P(t_1,t_2,\dots,t_m)) = \begin{cases} 1 & \textit{jesli <math>\langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\in I(P)} ,}

0 & \textit{jesli $⟨I_v(t_1),I_v(t_2),\dots ,I_v(t_m)⟩\in ̸I(P)$,.} \end{cases} </math>, (21)

Intepretacja formuł złożonych polega na przypisaniu wartości logicznej formułom uzyskanym przez zastosowanie operatorów logicznych, kwantyfikatorów i nawiasów, na podstawie wartości logicznej wchodzących w ich skład formuł atomowych. Skrupulatne definiowanie wszystkich przypadków operatorów logicznych byłoby żmudne i mało pouczające, więc ograniczymy się do przykładu dla operatora implikacji $\to$,:

\begin{center}

$I_v(\alpha )$,	$I_v(\beta )$,	$I_v(\alpha \to \beta )$,
$0$,	$0$,	$1$,
$0$,	$1$,	$1$,
$1$,	$0$,	$0$,
$1$,	$1$,	$1$,

\end{center}

Jak widać, definicja "znaczenia implikacji" sprowadza się do podania tzw. tabeli prawdy.

Na uważniejsze potraktowanie zasługuje kwestia znaczenia formuł zbudowanych z wykorzystaniem kwantyfikatorów. Przyjmując dziedzinę $X$,, interpretacje $I$, i wartosciowanie $v$,, rozważmy interpretację formuły postaci $(\mathrm{\forall }x)\alpha$,. Aby uniknąć wikłania się w dyskusje o zasięgu kwantyfikatorów założymy, że w formule $\alpha$, nie występuje żaden inny kwantyfikator dla zmiennej $x$, (czyli że wszystkie wystąpienia zmiennej $x$, w formule $\alpha$, są wolne). Wartość logiczną formuły $(\mathrm{\forall }x)\alpha$, przy interpretacji $I$, i wartosciowaniu $v$, ustalamy w następujący sposób:

1. $I_v((\mathrm{\forall }x)\alpha )=1$, wtedy i tylko wtedy gdy dla wszystkich wartościowań $v_x$, rozniacych sie od $v$, co najwyżej wartością przypisywaną zmiennej $x$, (a wiec takze dla $v_x$, identycznego z $v$,) uzyskujemy $I_{v_x}(\alpha )=1$,,
2. $I_v((\mathrm{\forall }x)\alpha )=0$, w przeciwnym przypadku.

Analogicznie dla formuły $(\mathrm{\exists }x)\alpha$,:

1. $I_v((\mathrm{\exists }x)\alpha )=1$, wtedy i tylko wtedy gdy istnieje wartościowanie $v_x$, rozniace sie od $v$, co najwyżej wartością przypisywaną zmiennej $x$, (moze to byc w szczegolnosci $v_x$, identyczne z $v$,) uzyskujemy $I_{v_x}(\alpha )=1$,,
2. $I_v((\mathrm{\exists }x)\alpha )=0$, w przeciwnym przypadku.

Istotą przytoczonych definicji znaczenia formuł z kwantyfikatorem jest wyłączenie zmiennej objętej kwantyfikatorem z wartościowania. Dla określenia wartości logicznej takiej formuły jest obojętne, jaką wartość $v(x)$, wartosciowanie $v$, przypisuje zmiennej $x$, objętej kwantyfikatorem. Ważne jest tylko, aby przy niezmienionych wartościach przypisywanych wszystkim pozostałym zmiennym można było stwierdzić, że $I_v(\alpha )=1$, dla wszystkich mozliwych wartosci zmiennej $x$, (w przypadku kwantyfikatora ogólnego) albo dla przynajmniej jednej wartości zmiennej $x$, (w przypadku kwantyfikatora szczegółowego) z dziedziny $X$,.

Przykład: świat klocków. Weźmy pod uwagę formułę $P(x,y)\to Q(x,y)$,. Przy ustalonej w poprzednich przykładach intepretacji i wartościowaniu dostajemy:

$I_v(P(x,y))=1$,	(22)
$I_v(Q(x,y))=1$,	(23)

a więc $I_v(P(x,y)\to Q(x,y))=1$,. Nietrudno się przekonać, że także dla formuły $(\mathrm{\forall }x)(\mathrm{\forall }y)(P(x,y)\to Q(x,y))$, uzyskamy wartość logiczną $1$,, sprawdzajac, ze $I_v(P(x,y)\to Q(x,y))$, niezaleznie od wartosci przypisanych zmiennym $x$, i $y$,.

Mając określoną składnię i semantykę języka logiki, możemy zapisywać w nim stwierdzenia na temat dziedziny wyrażone w języku naturalnym:

• Jeśli jakiś klocek leży na innym klocku, to jest jego górnym sąsiadem:

$(\mathrm{\forall }x)(\mathrm{\forall }y)P(x,y)\to R(x,f(y))$, (24)

• Dla dowolnych dwóch klocków nie jest możliwe, żeby pierwszy z nich leżał nad drugim i jednocześnie drugi nad pierwszym.

$(\mathrm{\forall }x)(\mathrm{\forall }y)\mathrm{\neg }(P(x,y)\wedge P(y,x))$, (25)

• Każdy klocek, który nie ma górnego sąsiada, jest dolnym sąsiadem jakiegoś innego klocka.

$(\mathrm{\forall }x)R(x,f(x))\to (\mathrm{\exists }y)R(x,g(y))$, (26)

Spełnialność i prawdziwość

Formułę, która dla ustalonej interpretacji i wartościowania ma wartość logiczną $1$,, nazywa się formułą spełnioną przy tej interpretacji i wartościowaniu. Formuła, dla której istnieje intepretacja i wartościowanie, przy których jest ona spełniona, nazywana jest formułą spełnialną. Z kolei formuła spełniona przy dowolnej intepretacji i wartościowaniu jest formułą prawdziwą.

Dla formuły, która nie jest prawdziwa, istnieje interpretacja i wartościowanie, przy których jej wartość logiczna wynosi $0$,. Taką formułę nazywa się formułą falsyfikowalną. Z kolei formuła, która nie jest spełnialna, ma wartość logiczną $0$, przy dowolnej interpretacji i wartościowaniu. O takiej formule mówi się, że jest fałszywa.

Weryfikacja spełnienie formuły przy konkretnej intepretacji i wartościowaniu jest trywialna. Dalej będziemy się interesować tylko znacznie bardziej złożonym zagadnieniem rozstrzygania o prawdziwości bądź fałszywości formuł. Z wyjątkiem trywialnie małych dziedzin, nie można takiej weryfikacji przeprowadzić bezpośrednio opierając się na powyższych definicjach. Z tego wynika potrzeba stosowania wnioskowania.

Przykład: świat klocków. Łatwo sprawdzić, że następujące formuły są spełnione przy intepretacji i wartościowaniu określonych w poprzednich przykładach:

$\mathrm{\neg }P(y,x)$,	(27)
$\mathrm{\neg }P(b,a)\vee Q(e,d)$,	(28)
$P(f(x),b)$,	(29)
$Q(f(x),y)$,	(30)
$P(x,y)\wedge Q(x,a)$,	(31)
$P(x,y)\to P(e,d)$,	(32)
$P(x,y)\to Q(x,y)$,	(33)
$(\mathrm{\forall }x)(P(f(x),x)\vee R(f(x),x)$,	(34)
$(\mathrm{\forall }x)(\mathrm{\forall }y)(P(x,y)\to Q(x,y)$,	(35)
$(\mathrm{\forall }x)(\mathrm{\forall }y)(P(x,y)\to \mathrm{\neg }R(x,a))$,	(36)
$(\mathrm{\forall }x)R(g(x),x)\to (\mathrm{\exists }y)P(y,x)$,	(37)

Następujące formuły są także prawdziwe:

$P(x,y)\to (P(x,y)\to Q(x,y))$,	(38)
$P(a,e)\vee \mathrm{\neg }P(a,e)$,	(39)

Konsekwencja semantyczna

W praktycznych zadaniach wnioskowania najczęściej rozważanym pytaniem jest w gruncie rzeczy nie tyle pytanie o prawdziwość pojedynczych formuł, co raczej o "wynikanie" pewnych formuł z innych formuł. Opisuje to relacja konsekwencji semantycznej, którą definiuje się bezpośrednio odwołując się do prawdziwości. Będziemy mówić, że formuła $\beta$, jest konsekwencją semantyczną zbioru formuł $\mathrm{\Gamma }=\{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\}$,, jeśli formuła ${\alpha }_1\wedge {\alpha }_2\wedge \dots \wedge {\alpha }_n\to \beta$, jest prawdziwa. Będziemy wówczas pisać $\mathrm{\Gamma }\models \beta$,.