Sztuczna inteligencja/SI Moduł 2/Semantyka języka logiki: Różnice pomiędzy wersjami
Nowa zawartość |
m Zastępowanie tekstu – „,</math>” na „</math>,” |
||
| Linia 22: | Linia 22: | ||
Będziemy ilustrować definicję semantyki języka logiki posługując się | Będziemy ilustrować definicję semantyki języka logiki posługując się | ||
prostym przykładem świata klocków, zilustrowanym na rysunku. Dziedzina | prostym przykładem świata klocków, zilustrowanym na rysunku. Dziedzina | ||
jest w tym przypadku zbiorem pięciu klocków <math>\{A,B,C,D,E\} \ | jest w tym przypadku zbiorem pięciu klocków <math>\{A,B,C,D,E\} \</math>,. | ||
\begin{figure}[h] | \begin{figure}[h] | ||
| Linia 30: | Linia 30: | ||
=== Interpretacja symboli === | === Interpretacja symboli === | ||
Mając ustaloną pewną dziedzinę <math>X \ | Mając ustaloną pewną dziedzinę <math>X \</math>,, symbole alfabetu języka predykatów | ||
interpretujemy następująco. | interpretujemy następująco. | ||
* '''Symbole stałych:''' symbol stałej <math>a \ | * '''Symbole stałych:''' symbol stałej <math>a \</math>, oznacza pewien obiekt z dziedziny <math>I(a)\in X \</math>,. | ||
* '''Symbole funkcyjne:''' <math>m \ | * '''Symbole funkcyjne:''' <math>m \</math>,-argumentowy symbol funkcyjny <math>f \</math>, oznacza <math>m \</math>,-argumentowa funkcje <math>I(f): X^m\mapsto X \</math>,. | ||
* '''Symbole predykatowe:''' <math>m \ | * '''Symbole predykatowe:''' <math>m \</math>,-argumentowy symbol predykatowy <math>P \</math>, oznacza <math>m \</math>,-argumentowa relacje <math>I(P)\subset X^m \</math>, (równoważnie, możemy przyjąć, że <math>P \</math>, oznacza funkcje <math>I(P): X^m\mapsto\{0,1\} \</math>,). | ||
Przypomnijmy sobie, że relacją <math>m \ | Przypomnijmy sobie, że relacją <math>m \</math>, argumentową określoną na zbiorze | ||
<math>X \ | <math>X \</math>, jest dowolny podzbior iloczynu kartezjanskiego <math>X^m \</math>,. Dla krotki | ||
złożonej z <math>m \ | złożonej z <math>m \</math>, elementow zbioru <math>X \</math>,, która należy do relacji, mówimy | ||
także, że relacja jest spełniona. | także, że relacja jest spełniona. | ||
| Linia 50: | Linia 50: | ||
formuły za pomocą ''wartościowania''. Wartościowanie jest dowolnym | formuły za pomocą ''wartościowania''. Wartościowanie jest dowolnym | ||
odwzorowaniem symboli zmiennych na elementy dziedziny - dla symbolu | odwzorowaniem symboli zmiennych na elementy dziedziny - dla symbolu | ||
zmiennej <math>x \ | zmiennej <math>x \</math>, wartosciowanie <math>v \</math>, określa wartosc <math>v(x)\in X \</math>,. | ||
'''Przykład: świat klocków.''' | '''Przykład: świat klocków.''' | ||
Rozważmy język logiki predykatów, którego alfabet zawiera symbole | Rozważmy język logiki predykatów, którego alfabet zawiera symbole | ||
stałych <math>\{a,b,c,d,e\} \ | stałych <math>\{a,b,c,d,e\} \</math>,. Możemy przyjąć interpretację, w której | ||
każdemu symbolowi stałej odpowiada inny klocek z dziedziny, np.: | każdemu symbolowi stałej odpowiada inny klocek z dziedziny, np.: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 1 --><math>I(a) = A \ | |<!-- equation 1 --><math>I(a) = A \</math>, || ''(1)'' | ||
|- | |- | ||
|<!-- equation 2 --><math>I(b) = B \ | |<!-- equation 2 --><math>I(b) = B \</math>, || ''(2)'' | ||
|- | |- | ||
|<!-- equation 3 --><math>I(c) = C \ | |<!-- equation 3 --><math>I(c) = C \</math>, || ''(3)'' | ||
|- | |- | ||
|<!-- equation 4 --><math>I(d) = D \ | |<!-- equation 4 --><math>I(d) = D \</math>, || ''(4)'' | ||
|- | |- | ||
|<!-- equation 5 --><math>I(e) = E \ | |<!-- equation 5 --><math>I(e) = E \</math>, || ''(5)'' | ||
|- | |- | ||
| Linia 74: | Linia 74: | ||
Przyjmiemy także, że a alfabecie znajdują się dwa symbole zmiennych | Przyjmiemy także, że a alfabecie znajdują się dwa symbole zmiennych | ||
<math>x \ | <math>x \</math>, i <math>y \</math>,, dla których określono wartościowanie następująco: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 6 --><math>v(x) = C \ | |<!-- equation 6 --><math>v(x) = C \</math>, || ''(6)'' | ||
|- | |- | ||
|<!-- equation 7 --><math>v(y) = B \ | |<!-- equation 7 --><math>v(y) = B \</math>, || ''(7)'' | ||
|- | |- | ||
| Linia 87: | Linia 87: | ||
Załóżmy dalej, że alfabet zawiera dwa jednoargumentowe symbole | Załóżmy dalej, że alfabet zawiera dwa jednoargumentowe symbole | ||
funkcyjne <math>f \ | funkcyjne <math>f \</math>, i <math>g \</math>,. Nasza interpretacja będzie im przypisywać | ||
odpowiednio dwuargumentowe funkcje określone na dziedzinie: | odpowiednio dwuargumentowe funkcje określone na dziedzinie: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 8 --><math>I(f) = \textit{gora} \ | |<!-- equation 8 --><math>I(f) = \textit{gora} \</math>, || ''(8)'' | ||
|- | |- | ||
|<!-- equation 9 --><math>I(g) = \textit{dol} \ | |<!-- equation 9 --><math>I(g) = \textit{dol} \</math>, || ''(9)'' | ||
|- | |- | ||
| Linia 104: | Linia 104: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 10 --><math>\textit{gora}(A) = \; B \; \textit{dol}(A)= \; A \ | |<!-- equation 10 --><math>\textit{gora}(A) = \; B \; \textit{dol}(A)= \; A \</math>, || ''(10)'' | ||
|- | |- | ||
|<!-- equation 11 --><math>\textit{gora}(B) = \; C \; \textit{dol}(B)= \; A \ | |<!-- equation 11 --><math>\textit{gora}(B) = \; C \; \textit{dol}(B)= \; A \</math>, || ''(11)'' | ||
|- | |- | ||
|<!-- equation 12 --><math>\textit{gora}(C) = \; C \; \textit{dol}(C)= \; B \ | |<!-- equation 12 --><math>\textit{gora}(C) = \; C \; \textit{dol}(C)= \; B \</math>, || ''(12)'' | ||
|- | |- | ||
|<!-- equation 13 --><math>\textit{gora}(D) = \; E \; \textit{dol}(D)= \; D \ | |<!-- equation 13 --><math>\textit{gora}(D) = \; E \; \textit{dol}(D)= \; D \</math>, || ''(13)'' | ||
|- | |- | ||
|<!-- equation 14 --><math>\textit{gora}(E) = \; E \; \textit{dol}(E)= \; D \ | |<!-- equation 14 --><math>\textit{gora}(E) = \; E \; \textit{dol}(E)= \; D \</math>, || ''(14)'' | ||
|- | |- | ||
| Linia 118: | Linia 118: | ||
<!-- end{align} --> | <!-- end{align} --> | ||
(jak widać, funkcja <math>\textit{gora} \ | (jak widać, funkcja <math>\textit{gora} \</math>, przypisuje każdemu klockowi jego | ||
sąsiada z góry, o ile istnieje, albo jego samego; podobnie funkcja | sąsiada z góry, o ile istnieje, albo jego samego; podobnie funkcja | ||
<math>\textit{dol} \ | <math>\textit{dol} \</math>, 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 | istnieje, albo jego samego). Założymy także, że alfabet naszego języka | ||
logiki zawiera dwuargumentowe symbole predykatowe <math>P \ | logiki zawiera dwuargumentowe symbole predykatowe <math>P \</math>,, <math>Q \</math>, i <math>R \</math>,, | ||
których interpretację ustalimy następująco: | których interpretację ustalimy następująco: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 15 --><math>I(P) = \textit{na} \ | |<!-- equation 15 --><math>I(P) = \textit{na} \</math>, || ''(15)'' | ||
|- | |- | ||
|<!-- equation 16 --><math>I(Q) = \textit{nad} \ | |<!-- equation 16 --><math>I(Q) = \textit{nad} \</math>, || ''(16)'' | ||
|- | |- | ||
|<!-- equation 17 --><math>I(R) = \textit{rowne} \ | |<!-- equation 17 --><math>I(R) = \textit{rowne} \</math>, || ''(17)'' | ||
|- | |- | ||
| Linia 139: | Linia 139: | ||
przy czym: | przy czym: | ||
* <math>\textit{na} \ | * <math>\textit{na} \</math>, jest relacją dwuargumentową, do której należą wszystkie pary klocków takie, że pierwszy leży na drugim: <math>\langle B,A\rangle \</math>,, <math>\langle C, B\rangle \</math>,, <math>\langle E,D\rangle \</math>,, | ||
* <math>\textit{nad} \ | * <math>\textit{nad} \</math>, jest relacją dwuargumentową, do której należą wszystkie pary klocków takie, że pierwszy leży nad drugim (tj. na nim lub wyżej): <math>\langle B,A\rangle \</math>,, <math>\langle C, A\rangle \</math>,, <math>\langle C,B\rangle \</math>,, <math>\langle E,D\rangle \</math>,, | ||
* <math>\textit{rowne} \ | * <math>\textit{rowne} \</math>, jest relacją dwuargumentową, do której należą wszystkie pary złożone z dwóch wystąpień tych samych klocków: <math>\langle A,A\rangle \</math>,, <math>\langle B,B\rangle \</math>,, <math>\langle C,C\rangle \</math>,, <math>\langle D,D\rangle \</math>,, <math>\langle E,E\rangle \</math>,. | ||
=== Interpretacja termów === | === Interpretacja termów === | ||
Interpretacja wraz z wartościowaniem pozwala ustalić znaczenie | Interpretacja wraz z wartościowaniem pozwala ustalić znaczenie | ||
dowolnego termu. Dla interpretacji <math>I \ | dowolnego termu. Dla interpretacji <math>I \</math>, i wartosciowania <math>v \</math>, oznaczmy | ||
dla wygody przez <math>I_v \ | dla wygody przez <math>I_v \</math>, ich połączenie, rozumiane następująco: | ||
* '''dla symboli stałych:''' <math>I_v(a)=I(a) \ | * '''dla symboli stałych:''' <math>I_v(a)=I(a) \</math>,, | ||
* '''dla symboli zmiennych:''' <math>I_v(x)=v(x) \ | * '''dla symboli zmiennych:''' <math>I_v(x)=v(x) \</math>,. | ||
Termy złożone interpretowane są przez zastosowanie intepretacji do | Termy złożone interpretowane są przez zastosowanie intepretacji do | ||
wchodzących w ich skład symboli stałych i symboli funkcyjnych oraz | 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 | zastosowanie wartościowania do wchodzących w ich skład zmiennych. Przy | ||
ustalonej dziedzinie, interpretacji <math>I \ | ustalonej dziedzinie, interpretacji <math>I \</math>, i wartosciowaniu <math>v \</math>,, może być | ||
wyznaczone znaczenie każdego termu postaci <math>f(t_1,t_2,\dots,t_m) \ | wyznaczone znaczenie każdego termu postaci <math>f(t_1,t_2,\dots,t_m) \</math>, w | ||
następujący sposób: | następujący sposób: | ||
| Linia 162: | Linia 162: | ||
:<math> | :<math> | ||
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)). | 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)). | ||
\ | \</math>, ''(18)'' | ||
'''Przykład: ślad klocków.''' | '''Przykład: ślad klocków.''' | ||
Weźmy pod uwagę term <math>f(b) \ | Weźmy pod uwagę term <math>f(b) \</math>,. Poniewaz <math>I(b)=B \</math>,, <math>I(f)=\textit{gora} \</math>, | ||
oraz <math>\textit{gora}(B)=C \ | oraz <math>\textit{gora}(B)=C \</math>,, wiec oczywiscie <math>I(f(b))=C \</math>,. Podobnie łatwo | ||
można sprawdzić interpretację następujących termów: | można sprawdzić interpretację następujących termów: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 19 --><math>I_v(f(x)) = C \ | |<!-- equation 19 --><math>I_v(f(x)) = C \</math>, || ''(19)'' | ||
|- | |- | ||
|<!-- equation 20 --><math>I_v(g(y)) = A \ | |<!-- equation 20 --><math>I_v(g(y)) = A \</math>, || ''(20)'' | ||
|- | |- | ||
| Linia 185: | Linia 185: | ||
Formuły atomowe intepretowane są podobnie jak termy złożone: przez | Formuły atomowe intepretowane są podobnie jak termy złożone: przez | ||
zastosowanie intepretacji i wartościowania do każdego występującego w | zastosowanie intepretacji i wartościowania do każdego występującego w | ||
nich symbolu. Dla formuły postaci <math>P(t_1,t_2,\dots,t_m) \ | nich symbolu. Dla formuły postaci <math>P(t_1,t_2,\dots,t_m) \</math>, otrzymujemy w | ||
ten sposób relację <math>I(P) \ | ten sposób relację <math>I(P) \</math>, oraz krotke <math>m \</math>, obiektów z dziedziny | ||
<math>\langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\in X^m \ | <math>\langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\in X^m \</math>,. Znaczeniem | ||
formuły będzie jej wartość logiczna określona na podstawie tego, czy | formuły będzie jej wartość logiczna określona na podstawie tego, czy | ||
krotka obiektów należy do relacji: | krotka obiektów należy do relacji: | ||
| Linia 196: | Linia 196: | ||
\begin{cases} | \begin{cases} | ||
1 & | 1 & | ||
\textit{jesli <math>\langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\in I(P) \ | \textit{jesli <math>\langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\in I(P) \</math>,} | ||
0 & | 0 & | ||
\textit{jesli <math>\langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\not\in I(P) \ | \textit{jesli <math>\langle I_v(t_1),I_v(t_2),\dots,I_v(t_m)\rangle\not\in I(P) \</math>,.} | ||
\end{cases} | \end{cases} | ||
\ | \</math>, ''(21)'' | ||
| Linia 209: | Linia 209: | ||
wszystkich przypadków operatorów logicznych byłoby żmudne i mało | wszystkich przypadków operatorów logicznych byłoby żmudne i mało | ||
pouczające, więc ograniczymy się do przykładu dla operatora implikacji | pouczające, więc ograniczymy się do przykładu dla operatora implikacji | ||
<math>\rightarrow \ | <math>\rightarrow \</math>,: | ||
\begin{center} | \begin{center} | ||
| Linia 215: | Linia 215: | ||
<!-- \begin{tabular}{c|c||c} --> | <!-- \begin{tabular}{c|c||c} --> | ||
:{| width="400" border="1" | :{| width="400" border="1" | ||
|<math>I_v(\alpha) \ | |<math>I_v(\alpha) \</math>, || <math>I_v(\beta) \</math>, || <math>I_v(\alpha\rightarrow\beta) \</math>, | ||
|- | |- | ||
|<math>0 \ | |<math>0 \</math>, || <math>0 \</math>, || <math>1 \</math>, | ||
|- | |- | ||
|<math>0 \ | |<math>0 \</math>, || <math>1 \</math>, || <math>1 \</math>, | ||
|- | |- | ||
|<math>1 \ | |<math>1 \</math>, || <math>0 \</math>, || <math>0 \</math>, | ||
|- | |- | ||
|<math>1 \ | |<math>1 \</math>, || <math>1 \</math>, || <math>1 \</math>, | ||
|- | |- | ||
| Linia 236: | Linia 236: | ||
Na uważniejsze potraktowanie zasługuje kwestia znaczenia formuł | Na uważniejsze potraktowanie zasługuje kwestia znaczenia formuł | ||
zbudowanych z wykorzystaniem kwantyfikatorów. Przyjmując dziedzinę | zbudowanych z wykorzystaniem kwantyfikatorów. Przyjmując dziedzinę | ||
<math>X \ | <math>X \</math>,, interpretacje <math>I \</math>, i wartosciowanie <math>v \</math>,, rozważmy interpretację | ||
formuły postaci <math>(\forall x)\alpha \ | formuły postaci <math>(\forall x)\alpha \</math>,. Aby uniknąć wikłania się w | ||
dyskusje o zasięgu kwantyfikatorów założymy, że w formule <math>\alpha \ | dyskusje o zasięgu kwantyfikatorów założymy, że w formule <math>\alpha \</math>, nie | ||
występuje żaden inny kwantyfikator dla zmiennej <math>x \ | występuje żaden inny kwantyfikator dla zmiennej <math>x \</math>, (czyli że | ||
wszystkie wystąpienia zmiennej <math>x \ | wszystkie wystąpienia zmiennej <math>x \</math>, w formule <math>\alpha \</math>, są | ||
''wolne''). Wartość logiczną formuły <math>(\forall x)\alpha \ | ''wolne''). Wartość logiczną formuły <math>(\forall x)\alpha \</math>, przy | ||
interpretacji <math>I \ | interpretacji <math>I \</math>, i wartosciowaniu <math>v \</math>, ustalamy w następujący sposób: | ||
# <math>I_v((\forall x)\alpha)=1 \ | # <math>I_v((\forall x)\alpha)=1 \</math>, wtedy i tylko wtedy gdy dla wszystkich wartościowań <math>v_x \</math>, rozniacych sie od <math>v \</math>, co najwyżej wartością przypisywaną zmiennej <math>x \</math>, (a wiec takze dla <math>v_x \</math>, identycznego z <math>v \</math>,) uzyskujemy <math>I_{v_x}(\alpha)=1 \</math>,, | ||
# <math>I_v((\forall x)\alpha)=0 \ | # <math>I_v((\forall x)\alpha)=0 \</math>, w przeciwnym przypadku. | ||
Analogicznie dla formuły <math>(\exists x)\alpha \ | Analogicznie dla formuły <math>(\exists x)\alpha \</math>,: | ||
# <math>I_v((\exists x)\alpha)=1 \ | # <math>I_v((\exists x)\alpha)=1 \</math>, wtedy i tylko wtedy gdy istnieje wartościowanie <math>v_x \</math>, rozniace sie od <math>v \</math>, co najwyżej wartością przypisywaną zmiennej <math>x \</math>, (moze to byc w szczegolnosci <math>v_x \</math>, identyczne z <math>v \</math>,) uzyskujemy <math>I_{v_x}(\alpha)=1 \</math>,, | ||
# <math>I_v((\exists x)\alpha)=0 \ | # <math>I_v((\exists x)\alpha)=0 \</math>, w przeciwnym przypadku. | ||
Istotą przytoczonych definicji znaczenia formuł z kwantyfikatorem jest | Istotą przytoczonych definicji znaczenia formuł z kwantyfikatorem jest | ||
wyłączenie zmiennej objętej kwantyfikatorem z wartościowania. Dla | wyłączenie zmiennej objętej kwantyfikatorem z wartościowania. Dla | ||
określenia wartości logicznej takiej formuły jest obojętne, jaką | określenia wartości logicznej takiej formuły jest obojętne, jaką | ||
wartość <math>v(x) \ | wartość <math>v(x) \</math>, wartosciowanie <math>v \</math>, przypisuje zmiennej <math>x \</math>, objętej | ||
kwantyfikatorem. Ważne jest tylko, aby przy niezmienionych wartościach | kwantyfikatorem. Ważne jest tylko, aby przy niezmienionych wartościach | ||
przypisywanych wszystkim pozostałym zmiennym można było stwierdzić, że | przypisywanych wszystkim pozostałym zmiennym można było stwierdzić, że | ||
<math>I_v(\alpha)=1 \ | <math>I_v(\alpha)=1 \</math>, dla wszystkich mozliwych wartosci zmiennej <math>x \</math>, (w | ||
przypadku kwantyfikatora ogólnego) albo dla przynajmniej jednej | przypadku kwantyfikatora ogólnego) albo dla przynajmniej jednej | ||
wartości zmiennej <math>x \ | wartości zmiennej <math>x \</math>, (w przypadku kwantyfikatora szczegółowego) z | ||
dziedziny <math>X \ | dziedziny <math>X \</math>,. | ||
'''Przykład: świat klocków.''' | '''Przykład: świat klocków.''' | ||
Weźmy pod uwagę formułę <math>P(x,y)\rightarrow Q(x,y) \ | Weźmy pod uwagę formułę <math>P(x,y)\rightarrow Q(x,y) \</math>,. Przy ustalonej w | ||
poprzednich przykładach intepretacji i wartościowaniu dostajemy: | poprzednich przykładach intepretacji i wartościowaniu dostajemy: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 22 --><math>I_v(P(x,y)) = 1 \ | |<!-- equation 22 --><math>I_v(P(x,y)) = 1 \</math>, || ''(22)'' | ||
|- | |- | ||
|<!-- equation 23 --><math>I_v(Q(x,y)) = 1 \ | |<!-- equation 23 --><math>I_v(Q(x,y)) = 1 \</math>, || ''(23)'' | ||
|- | |- | ||
| Linia 276: | Linia 276: | ||
<!-- end{align} --> | <!-- end{align} --> | ||
a więc <math>I_v(P(x,y)\rightarrow Q(x,y))=1 \ | a więc <math>I_v(P(x,y)\rightarrow Q(x,y))=1 \</math>,. Nietrudno się przekonać, że | ||
także dla formuły <math>(\forall x)(\forall y)(P(x,y)\rightarrow Q(x,y)) \ | także dla formuły <math>(\forall x)(\forall y)(P(x,y)\rightarrow Q(x,y)) \</math>, | ||
uzyskamy wartość logiczną <math>1 \ | uzyskamy wartość logiczną <math>1 \</math>,, sprawdzajac, ze <math>I_v(P(x,y)\rightarrow Q(x,y)) \</math>, niezaleznie od wartosci przypisanych zmiennym <math>x \</math>, i <math>y \</math>,. | ||
Mając określoną składnię i semantykę języka logiki, możemy zapisywać w | Mając określoną składnię i semantykę języka logiki, możemy zapisywać w | ||
| Linia 287: | Linia 287: | ||
:<math> | :<math> | ||
(\forall x)(\forall y) P(x,y)\rightarrow R(x,f(y)) | (\forall x)(\forall y) P(x,y)\rightarrow R(x,f(y)) | ||
\ | \</math>, ''(24)'' | ||
| Linia 294: | Linia 294: | ||
:<math> | :<math> | ||
(\forall x)(\forall y)\neg(P(x,y)\land P(y,x)) | (\forall x)(\forall y)\neg(P(x,y)\land P(y,x)) | ||
\ | \</math>, ''(25)'' | ||
| Linia 301: | Linia 301: | ||
:<math> | :<math> | ||
(\forall x) R(x,f(x)) \rightarrow (\exists y) R(x,g(y)) | (\forall x) R(x,f(x)) \rightarrow (\exists y) R(x,g(y)) | ||
\ | \</math>, ''(26)'' | ||
| Linia 308: | Linia 308: | ||
Formułę, która dla ustalonej interpretacji i wartościowania ma wartość | Formułę, która dla ustalonej interpretacji i wartościowania ma wartość | ||
logiczną <math>1 \ | logiczną <math>1 \</math>,, nazywa się formułą ''spełnioną'' przy tej | ||
interpretacji i wartościowaniu. Formuła, dla której istnieje | interpretacji i wartościowaniu. Formuła, dla której istnieje | ||
intepretacja i wartościowanie, przy których jest ona spełniona, | intepretacja i wartościowanie, przy których jest ona spełniona, | ||
| Linia 316: | Linia 316: | ||
Dla formuły, która nie jest prawdziwa, istnieje interpretacja i | Dla formuły, która nie jest prawdziwa, istnieje interpretacja i | ||
wartościowanie, przy których jej wartość logiczna wynosi <math>0 \ | wartościowanie, przy których jej wartość logiczna wynosi <math>0 \</math>,. Taką | ||
formułę nazywa się formułą ''falsyfikowalną''. Z kolei formuła, | formułę nazywa się formułą ''falsyfikowalną''. Z kolei formuła, | ||
która nie jest spełnialna, ma wartość logiczną <math>0 \ | która nie jest spełnialna, ma wartość logiczną <math>0 \</math>, przy dowolnej | ||
interpretacji i wartościowaniu. O takiej formule mówi się, że jest | interpretacji i wartościowaniu. O takiej formule mówi się, że jest | ||
''fałszywa''. | ''fałszywa''. | ||
| Linia 337: | Linia 337: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 27 --><math> \neg P(y,x) \ | |<!-- equation 27 --><math> \neg P(y,x) \</math>, || ''(27)'' | ||
|- | |- | ||
|<!-- equation 28 --><math> \neg P(b,a)\lor Q(e,d) \ | |<!-- equation 28 --><math> \neg P(b,a)\lor Q(e,d) \</math>, || ''(28)'' | ||
|- | |- | ||
|<!-- equation 29 --><math> P(f(x),b) \ | |<!-- equation 29 --><math> P(f(x),b) \</math>, || ''(29)'' | ||
|- | |- | ||
|<!-- equation 30 --><math> Q(f(x),y) \ | |<!-- equation 30 --><math> Q(f(x),y) \</math>, || ''(30)'' | ||
|- | |- | ||
|<!-- equation 31 --><math> P(x,y)\land Q(x,a) \ | |<!-- equation 31 --><math> P(x,y)\land Q(x,a) \</math>, || ''(31)'' | ||
|- | |- | ||
|<!-- equation 32 --><math> P(x,y) \rightarrow P(e,d) \ | |<!-- equation 32 --><math> P(x,y) \rightarrow P(e,d) \</math>, || ''(32)'' | ||
|- | |- | ||
|<!-- equation 33 --><math> P(x,y)\rightarrow Q(x,y) \ | |<!-- equation 33 --><math> P(x,y)\rightarrow Q(x,y) \</math>, || ''(33)'' | ||
|- | |- | ||
|<!-- equation 34 --><math> (\forall x) (P(f(x),x)\lor R(f(x),x) \ | |<!-- equation 34 --><math> (\forall x) (P(f(x),x)\lor R(f(x),x) \</math>, || ''(34)'' | ||
|- | |- | ||
|<!-- equation 35 --><math> (\forall x)(\forall y) (P(x,y)\rightarrow Q(x,y) \ | |<!-- equation 35 --><math> (\forall x)(\forall y) (P(x,y)\rightarrow Q(x,y) \</math>, || ''(35)'' | ||
|- | |- | ||
|<!-- equation 36 --><math> (\forall x)(\forall y) (P(x,y)\rightarrow \neg R(x,a)) \ | |<!-- equation 36 --><math> (\forall x)(\forall y) (P(x,y)\rightarrow \neg R(x,a)) \</math>, || ''(36)'' | ||
|- | |- | ||
|<!-- equation 37 --><math> (\forall x) R(g(x),x)\rightarrow (\exists y) P(y,x) \ | |<!-- equation 37 --><math> (\forall x) R(g(x),x)\rightarrow (\exists y) P(y,x) \</math>, || ''(37)'' | ||
|- | |- | ||
| Linia 367: | Linia 367: | ||
<!-- begin{align} TODO: kolumny--> | <!-- begin{align} TODO: kolumny--> | ||
:{| width="400" | :{| width="400" | ||
|<!-- equation 38 --><math>P(x,y)\rightarrow (P(x,y)\rightarrow Q(x,y)) \ | |<!-- equation 38 --><math>P(x,y)\rightarrow (P(x,y)\rightarrow Q(x,y)) \</math>, || ''(38)'' | ||
|- | |- | ||
|<!-- equation 39 --><math>P(a,e)\lor\neg P(a,e) \ | |<!-- equation 39 --><math>P(a,e)\lor\neg P(a,e) \</math>, || ''(39)'' | ||
|- | |- | ||
| Linia 383: | Linia 383: | ||
Opisuje to relacja konsekwencji semantycznej, którą definiuje się | 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 | bezpośrednio odwołując się do prawdziwości. Będziemy mówić, że formuła | ||
<math>\beta \ | <math>\beta \</math>, jest konsekwencją semantyczną zbioru formuł | ||
<math>\Gamma=\{\alpha_1,\alpha_2,\dots,\alpha_n\} \ | <math>\Gamma=\{\alpha_1,\alpha_2,\dots,\alpha_n\} \</math>,, jeśli formuła | ||
<math>\alpha_1\land\alpha_2\land\dots\land\alpha_n\rightarrow\beta \ | <math>\alpha_1\land\alpha_2\land\dots\land\alpha_n\rightarrow\beta \</math>, jest | ||
prawdziwa. Będziemy wówczas pisać <math>\Gamma\models\beta \ | prawdziwa. Będziemy wówczas pisać <math>\Gamma\models\beta \</math>,. | ||
Wersja z 09:30, 5 wrz 2023
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 \} ,.
