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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \{A,B,C,D,E\} \} ,.
\begin{figure}[h] \includegraphics[width=6cm]{rysunki/klocki.eps} \end{figure}
Interpretacja symboli
Mając ustaloną pewną dziedzinę Parser nie mógł rozpoznać (błąd składni): {\displaystyle X \} ,, symbole alfabetu języka predykatów interpretujemy następująco.
- Symbole stałych: symbol stałej Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , oznacza pewien obiekt z dziedziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(a)\in X \} ,.
- Symbole funkcyjne: Parser nie mógł rozpoznać (błąd składni): {\displaystyle m \} ,-argumentowy symbol funkcyjny Parser nie mógł rozpoznać (błąd składni): {\displaystyle f \} , oznacza Parser nie mógł rozpoznać (błąd składni): {\displaystyle m \} ,-argumentowa funkcje Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(f): X^m\mapsto X \} ,.
- Symbole predykatowe: Parser nie mógł rozpoznać (błąd składni): {\displaystyle m \} ,-argumentowy symbol predykatowy Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , oznacza Parser nie mógł rozpoznać (błąd składni): {\displaystyle m \} ,-argumentowa relacje Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(P)\subset X^m \} , (równoważnie, możemy przyjąć, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , oznacza funkcje Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(P): X^m\mapsto\{0,1\} \} ,).
Przypomnijmy sobie, że relacją Parser nie mógł rozpoznać (błąd składni): {\displaystyle m \} , argumentową określoną na zbiorze Parser nie mógł rozpoznać (błąd składni): {\displaystyle X \} , jest dowolny podzbior iloczynu kartezjanskiego Parser nie mógł rozpoznać (błąd składni): {\displaystyle X^m \} ,. Dla krotki złożonej z Parser nie mógł rozpoznać (błąd składni): {\displaystyle m \} , elementow zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , wartosciowanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} , określa wartosc Parser nie mógł rozpoznać (błąd składni): {\displaystyle v(x)\in X \} ,.
Przykład: świat klocków. Rozważmy język logiki predykatów, którego alfabet zawiera symbole stałych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \{a,b,c,d,e\} \} ,. Możemy przyjąć interpretację, w której każdemu symbolowi stałej odpowiada inny klocek z dziedziny, np.:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(a) = A \} , (1) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(b) = B \} , (2) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(c) = C \} , (3) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(d) = D \} , (4) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(e) = E \} , (5)
Przyjmiemy także, że a alfabecie znajdują się dwa symbole zmiennych Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle y \} ,, dla których określono wartościowanie następująco:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle v(x) = C \} , (6) Parser nie mógł rozpoznać (błąd składni): {\displaystyle v(y) = B \} , (7)
Załóżmy dalej, że alfabet zawiera dwa jednoargumentowe symbole funkcyjne Parser nie mógł rozpoznać (błąd składni): {\displaystyle f \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle g \} ,. Nasza interpretacja będzie im przypisywać odpowiednio dwuargumentowe funkcje określone na dziedzinie:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(f) = \textit{gora} \} , (8) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(g) = \textit{dol} \} , (9)
Funkcje te określimy następująco:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{gora}(A) = \; B \; \textit{dol}(A)= \; A \} , (10) Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{gora}(B) = \; C \; \textit{dol}(B)= \; A \} , (11) Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{gora}(C) = \; C \; \textit{dol}(C)= \; B \} , (12) Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{gora}(D) = \; E \; \textit{dol}(D)= \; D \} , (13) Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{gora}(E) = \; E \; \textit{dol}(E)= \; D \} , (14)
(jak widać, funkcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{gora} \} , przypisuje każdemu klockowi jego sąsiada z góry, o ile istnieje, albo jego samego; podobnie funkcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{dol} \} , 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle R \} ,, których interpretację ustalimy następująco:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(P) = \textit{na} \} , (15) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(Q) = \textit{nad} \} , (16) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(R) = \textit{rowne} \} , (17)
przy czym:
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{na} \} , jest relacją dwuargumentową, do której należą wszystkie pary klocków takie, że pierwszy leży na drugim: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle B,A\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle C, B\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle E,D\rangle \} ,,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{nad} \} , jest relacją dwuargumentową, do której należą wszystkie pary klocków takie, że pierwszy leży nad drugim (tj. na nim lub wyżej): Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle B,A\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle C, A\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle C,B\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle E,D\rangle \} ,,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{rowne} \} , jest relacją dwuargumentową, do której należą wszystkie pary złożone z dwóch wystąpień tych samych klocków: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle A,A\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle B,B\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle C,C\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle D,D\rangle \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle E,E\rangle \} ,.
Interpretacja termów
Interpretacja wraz z wartościowaniem pozwala ustalić znaczenie dowolnego termu. Dla interpretacji Parser nie mógł rozpoznać (błąd składni): {\displaystyle I \} , i wartosciowania Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} , oznaczmy dla wygody przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v \} , ich połączenie, rozumiane następująco:
- dla symboli stałych: Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(a)=I(a) \} ,,
- dla symboli zmiennych: Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle I \} , i wartosciowaniu Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} ,, może być wyznaczone znaczenie każdego termu postaci Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(t_1,t_2,\dots,t_m) \} , w następujący sposób:
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(b) \}
,. Poniewaz Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(b)=B \}
,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(f)=\textit{gora} \}
,
oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{gora}(B)=C \}
,, wiec oczywiscie Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(f(b))=C \}
,. Podobnie łatwo
można sprawdzić interpretację następujących termów:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(f(x)) = C \} , (19) Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(t_1,t_2,\dots,t_m) \} , otrzymujemy w ten sposób relację Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(P) \} , oraz krotke Parser nie mógł rozpoznać (błąd składni): {\displaystyle m \} , obiektów z dziedziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\not\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
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \}
,:
\begin{center}
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(\alpha) \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(\beta) \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(\alpha\rightarrow\beta) \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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ę Parser nie mógł rozpoznać (błąd składni): {\displaystyle X \} ,, interpretacje Parser nie mógł rozpoznać (błąd składni): {\displaystyle I \} , i wartosciowanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} ,, rozważmy interpretację formuły postaci Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x)\alpha \} ,. Aby uniknąć wikłania się w dyskusje o zasięgu kwantyfikatorów założymy, że w formule Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha \} , nie występuje żaden inny kwantyfikator dla zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , (czyli że wszystkie wystąpienia zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , w formule Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha \} , są wolne). Wartość logiczną formuły Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x)\alpha \} , przy interpretacji Parser nie mógł rozpoznać (błąd składni): {\displaystyle I \} , i wartosciowaniu Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} , ustalamy w następujący sposób:
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v((\forall x)\alpha)=1 \} , wtedy i tylko wtedy gdy dla wszystkich wartościowań Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_x \} , rozniacych sie od Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} , co najwyżej wartością przypisywaną zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , (a wiec takze dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_x \} , identycznego z Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} ,) uzyskujemy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_{v_x}(\alpha)=1 \} ,,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v((\forall x)\alpha)=0 \} , w przeciwnym przypadku.
Analogicznie dla formuły Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\exists x)\alpha \} ,:
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v((\exists x)\alpha)=1 \} , wtedy i tylko wtedy gdy istnieje wartościowanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_x \} , rozniace sie od Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} , co najwyżej wartością przypisywaną zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , (moze to byc w szczegolnosci Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_x \} , identyczne z Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} ,) uzyskujemy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_{v_x}(\alpha)=1 \} ,,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v((\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ść Parser nie mógł rozpoznać (błąd składni): {\displaystyle v(x) \} , wartosciowanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} , przypisuje zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , objętej kwantyfikatorem. Ważne jest tylko, aby przy niezmienionych wartościach przypisywanych wszystkim pozostałym zmiennym można było stwierdzić, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(\alpha)=1 \} , dla wszystkich mozliwych wartosci zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , (w przypadku kwantyfikatora ogólnego) albo dla przynajmniej jednej wartości zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , (w przypadku kwantyfikatora szczegółowego) z dziedziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle X \} ,.
Przykład: świat klocków. Weźmy pod uwagę formułę Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(x,y)\rightarrow Q(x,y) \} ,. Przy ustalonej w poprzednich przykładach intepretacji i wartościowaniu dostajemy:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(P(x,y)) = 1 \} , (22) Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(Q(x,y)) = 1 \} , (23)
a więc Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(P(x,y)\rightarrow Q(x,y))=1 \} ,. Nietrudno się przekonać, że także dla formuły Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x)(\forall y)(P(x,y)\rightarrow Q(x,y)) \} , uzyskamy wartość logiczną Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} ,, sprawdzajac, ze Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_v(P(x,y)\rightarrow Q(x,y)) \} , niezaleznie od wartosci przypisanych zmiennym Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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:
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x)(\forall y) P(x,y)\rightarrow 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.
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x)(\forall y)\neg(P(x,y)\land P(y,x)) \} , (25)
- Każdy klocek, który nie ma górnego sąsiada, jest dolnym sąsiadem jakiegoś innego klocka.
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x) R(x,f(x)) \rightarrow (\exists y) R(x,g(y)) \} , (26)
Spełnialność i prawdziwość
Formułę, która dla ustalonej interpretacji i wartościowania ma wartość logiczną Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} ,. Taką formułę nazywa się formułą falsyfikowalną. Z kolei formuła, która nie jest spełnialna, ma wartość logiczną Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \neg P(y,x) \} , (27) Parser nie mógł rozpoznać (błąd składni): {\displaystyle \neg P(b,a)\lor Q(e,d) \} , (28) Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(f(x),b) \} , (29) Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(f(x),y) \} , (30) Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(x,y)\land Q(x,a) \} , (31) Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(x,y) \rightarrow P(e,d) \} , (32) Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(x,y)\rightarrow Q(x,y) \} , (33) Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x) (P(f(x),x)\lor R(f(x),x) \} , (34) Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x)(\forall y) (P(x,y)\rightarrow Q(x,y) \} , (35) Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x)(\forall y) (P(x,y)\rightarrow \neg R(x,a)) \} , (36) Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall x) R(g(x),x)\rightarrow (\exists y) P(y,x) \} , (37)
Następujące formuły są także prawdziwe:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(x,y)\rightarrow (P(x,y)\rightarrow Q(x,y)) \} , (38) Parser nie mógł rozpoznać (błąd składni): {\displaystyle P(a,e)\lor\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \beta \} , jest konsekwencją semantyczną zbioru formuł Parser nie mógł rozpoznać (błąd składni): {\displaystyle \Gamma=\{\alpha_1,\alpha_2,\dots,\alpha_n\} \} ,, jeśli formuła Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha_1\land\alpha_2\land\dots\land\alpha_n\rightarrow\beta \} , jest prawdziwa. Będziemy wówczas pisać Parser nie mógł rozpoznać (błąd składni): {\displaystyle \Gamma\models\beta \} ,.
