Język zdaniowy – trójka
gdzie:
jest zbiorem nieskończonym,
zbiorem rozłącznym z ![{\displaystyle {\textbf {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03e1597aa2c271e29ec518b80ba8ce00b22e0599)
![{\displaystyle \varsigma :{\mathfrak {F}}\to \mathbb {N} _{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6b2a25683073876ee623965ddfca164ca0b08d1)
Elementy zbioru
są nazywane zmiennymi zdaniowymi, elementy zbioru
spójnikami języka
a
jego sygnaturą.
Skończone ciągi elementów zbioru
są nazywane napisami języka
Najmniejszy (w sensie inkluzji) spośród zbiorów napisów zbiór
spełniający warunki:
| | (jednoelementowe napisy złożone ze zmiennych są w |
|
(1) |
| | ![{\displaystyle {\mathfrak {f}}\alpha _{1}\ldots \alpha _{\varsigma ({\mathfrak {f}})}\in Y,\quad \alpha _{1},\dots ,\alpha _{\varsigma ({\mathfrak {f}})}\in Y,\quad {\mathfrak {f}}\in {\mathfrak {F}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e3a1031a9de3d0e9d3be78f7d9805f85898081c) |
|
(2) |
nazywany jest zbiorem formuł języka
i oznaczany symbolem
O zbiorach spełniających warunki (1) i (2) mówi się, że są domknięte na budowę formuł języka
.
Innymi słowy zbiór
jest najmniejszym zbiorem napisów domkniętym na budowę formuł języka
Niech
gdzie ![{\displaystyle \mathbf {P} =\{\mathbf {p} ,\mathbf {q} ,\mathbf {r} ,\mathbf {s} ,\dots \},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b6a409520b6dff8715c3fb0905cf0be27296d2d)
i niech
Wówczas
jest formułą języka
ale
i
nie są.
Język termów arytmetyki Peana[edytuj | edytuj kod]
Niech
![{\displaystyle \varsigma _{\mathbf {PA} }=\left\langle {\begin{array}{c|c|c|c}\mathbf {A} &\mathbf {M} &\mathbf {O} &\mathbf {I} \\\hline 2&2&0&0\end{array}}\right\rangle \qquad {\mbox{i niech}}\qquad \mathbf {V} =\{\mathbf {v} _{0},\mathbf {v} _{1},\mathbf {v} _{2},\dots \}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9a98128dd97ee6d1b00a8cd176813b5bbc59aa4)
Język
nazywa się językiem termów arytmetyki Peana. Formuły tego języka nazywa się termami arytmetyki Peana. Zbiór wszystkich termów arytmetyki Peana oznaczany będzie
Dla wygody czasem zamiast
pisze się
zamiast
pisze się
i zamiast
pisze się
Definiujemy indukcyjnie ciąg numerałów:
![{\displaystyle {\boldsymbol {\Delta }}_{0}:=\mathbf {O} ,\quad {\boldsymbol {\Delta }}_{1}:=\mathbf {I} ,\quad {\boldsymbol {\Delta }}_{n+1}:=\mathbf {AI} {\boldsymbol {\Delta }}_{n},\quad n=0,1,2,\dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e6bb160d94ca8b329009f6775311c25b847d54e)
Formułami atomowymi arytmetyki Peana nazywamy napisy postaci
oraz
gdzie
Zwyczajowo zamiast
pisze się
zamiast
pisze się
Zbiór formuł atomowych języka PA, oznaczymy
- Przykład:
- formułami atomowymi języka PA są
(Zero jest najmniejsze)
|
|
(Aksjomaty dla dodawania)
|
|
|
(Aksjomaty dla mnożenia)
|
|
|
(Przemienność dodawania i mnożenia)
|
|
|
(Łączność dodawania i mnożenia)
|
|
|
(2+3=5)
|
|
(2*3=6)
|
|
Formułami arytmetyki Peana nazywamy formuły języka
![{\displaystyle \langle \mathbf {Frm} _{\mathbf {PA} }^{(0)},\{\mathbf {A} ,\mathbf {K} ,\mathbf {N} ,\mathbf {C} ,\mathbf {E} \}\cup {\mathfrak {Q}}^{\forall }\cup {\mathfrak {Q}}^{\exists },\varsigma _{\mathbf {KRK} }\rangle ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43bd4730d0d21d813b3e63bbd55118dd52c38fed)
gdzie
oraz gdzie
jest wzbogaceniem sygnatury
do zbioru
dla którego
Zamiast pisać
pisze się zazwyczaj
zamiast zaś pisać
pisze się zazwyczaj
- Przykład:
- formułami języka PA są
![{\displaystyle \mathbf {E} (\mathbf {x\leqslant y} )(\exists \mathbf {z} )(\mathbf {Axz\equiv y} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67327746d19cd7dff859dd6f27265502b656dfb4)
![{\displaystyle \mathbf {C} (\mathbf {Axz\leqslant Ayz} )(\mathbf {x\leqslant y} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d76dba7965df36a1d88c5aa468dc9f8fb23f755f)
![{\displaystyle \mathbf {CN} (\mathbf {z\equiv O} )\mathbf {C} (\mathbf {Mxz\leqslant Myz} )(\mathbf {x\leqslant y} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/592461bffa08c0c82a573c751de85a56e988e24a)
Niech
będzie językiem zdaniowym.
Wówczas dla każdej formuły
tego języka zachodzi jeden z warunków
| | ![{\displaystyle \delta \in \mathbf {P} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/96cea04f1c6bb7b211e8a9f6c8e5923fad05ce0f) |
|
(3) |
| | dla pewnego oraz ![{\displaystyle \alpha _{1},\dots ,\alpha _{n}\in \mathbf {Frm} ({\mathcal {L}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41f4cfc4084d5e4a3ed1fb21de3e2c0c89071ad4) |
|
(4) |
Dla dowodu tego lematu należy rozważyć zbiór
formuł
spełniających warunki (3) i (4) powyżej, a następnie pokazać, że jest on domknięty na budowę formuł.
Lemat (o jednoznaczności budowy)[edytuj | edytuj kod]
Niech
będzie językiem zdaniowym, niech
będą formułami i niech
będą takie, że
Wówczas
oraz
Lematy o kształcie formuł i jednoznaczności budowy pozwalają na indukcyjne zdefiniowanie pojęcia podformuły danej formuły oraz podstawienia w formule innej formuły w miejsce zmiennej:
Zbiorem podformuł formuły
nazywamy zbiór zdefiniowany następująco:
![{\displaystyle \mathbf {Sbf} (\delta )={\begin{cases}\delta ,&{\mbox{jeśli }}\delta \in \mathbf {P} \\\mathbf {Sbf} (\alpha _{1})\cup \ldots \cup \mathbf {Sbf} (\alpha _{n})\cup \{\delta \}&{\mbox{jeśli }}\delta ={\mathfrak {f}}\alpha _{1}\ldots \alpha _{n},\;{\mathfrak {f}}\in {\mathfrak {F}}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49f0e049b5a9a687c5f13b686470af5497584ec7)
Zmiennymi formuły
nazywamy elementy zbioru
![{\displaystyle \mathbf {Sbf} (\mathbf {CCNpqApq} )=\{\mathbf {p} ,\mathbf {q} ,\mathbf {Apq} ,\mathbf {Np} ,\mathbf {CNpq} ,\mathbf {CCNpqApq} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cdf5e9cde34561a8fcddf4931a8d472aad3cb46)
Podstawieniem w formule
formuły
w miejsce zmiennej
nazywamy formułę:
![{\displaystyle (\delta )[\varphi /s]={\begin{cases}p,&{\mbox{jeśli }}p\in \mathbf {P} \setminus \{s\}\\\varphi &{\mbox{jeśli }}p=s\\{\mathfrak {f}}(\alpha _{1}[\varphi /s])\ldots (\alpha _{n}[\varphi /s])&{\mbox{jeśli }}\delta ={\mathfrak {f}}\alpha _{1}\ldots \alpha _{n},\;{\mathfrak {f}}\in {\mathfrak {F}}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d62b3162c39965e4adb25a60eda987a80b9e182b)
Zachodzi
Jeśli
to
![{\displaystyle (\mathbf {CCNpqApq} )[\mathbf {KEpqNp} /\mathbf {q} ]=\mathbf {CCNpKEpqNpApKEpqNp} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/14d0b45ba8090f0da1d08b39e927256b2a1ff26d)
Jednoczesne podstawienie kilku formuł[edytuj | edytuj kod]
W wielu wypadkach przydaje się umiejętność jednoczesnego podstawienia kilku formuł w miejsce kilku zmiennych:
Podstawieniem w formule
formuł
w miejsce zmiennych
nazywamy formułę:
![{\displaystyle (\delta )[\varphi _{1}/s_{1},\dots ,\varphi _{m}/s_{m}]={\begin{cases}{p}&{{\mbox{jeśli }}p\in \mathbf {P} \setminus \{s_{1},\dots ,s_{m}\},}\\{\varphi _{j}}&{{\mbox{jeśli }}p=s_{j},\,j=1,\dots ,m,}\\{{\mathfrak {f}}(\alpha _{1}[\varphi _{1}/s_{1},\dots ,\varphi _{m}/s_{m}])\ldots (\alpha _{n}[\varphi _{1}/s_{1},\dots ,\varphi _{m}/s_{m}])}&{{\mbox{jeśli }}\delta ={\mathfrak {f}}\alpha _{1}\ldots \alpha _{n},\;{\mathfrak {f}}\in {\mathfrak {F}}.}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f3febf13e4c4c8a5d80f368b8b3a5f640d4f6d3)
Wynik podstawienia nie zależy od kolejności:
![{\displaystyle (\delta )[\varphi _{1}/s_{1},\dots ,\varphi _{m}/s_{m}]=(\delta )[\varphi _{\pi (1)}/s_{\pi (1)},\dots ,\varphi _{\pi (m)}/s_{\pi (m)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61970bea9b46838415d6ef3438a50617a8d31c33)
dla dowolnej permutacji
zbioru
Jeśli
i
to:
![{\displaystyle (\delta )[\varphi /p,\psi /q]={\big (}(\delta )[\varphi /p]{\big )}[\psi /q].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f94c69245b57949952ce8a30c95d9a8c61ff8d4b)
|
|
|
|
|
|
|
Język zdaniowy wyznacza dość ważną algebrę sygnatury
Algebrą formuł języka
nazywamy algebrę sygnatury tego języka
której uniwersum jest
i w której
![{\displaystyle {\mathfrak {A}}_{\mathcal {L}}({\mathfrak {f}})(\alpha _{1},\dots ,\alpha _{\varsigma ({\mathfrak {f}})})={\mathfrak {f}}\alpha _{1}\ldots \alpha _{\varsigma ({\mathfrak {f}})},\qquad {\hbox{dla}}\;\;{\mathfrak {f}}\in {\mathfrak {F}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe241e655347b959a8d9fba32cebb397c2ae1b13)
Algebra języka jest algebrą wolną z
jako zbiorem wolnych generatorów w klasie algebr jej sygnatury:
- Dla dowolnej algebry
sygnatury języka
oraz dowolnego odwzorowania
istnieje jedyny homomorfizm
rozszerzający ![{\displaystyle v.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb7b87f7afb1452b9d0e287f8ef746a9912c8333)
- W przypadku, gdy język jest ustalony w danym kontekście homomorfizm ten oznaczamy po prostu symbolem
![{\displaystyle {\widehat {v}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53704e6fb11bc312e70fec31dfe8bf424759c39c)
Zauważmy, że
gdzie
dane jest wzorem:
![{\displaystyle v(p)={\begin{cases}\varphi ,&p=s\\p,&p\in \mathbf {P} \setminus \{s\}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbd59258d0d546e45a491bf8c2ad0e8fd093cb28)
Co więcej, jeśli
oraz
to:
![{\displaystyle {\widehat {v}}(\delta )=(\delta )[v(s_{1})/s_{1},\dots ,v(s_{n})/s_{n}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eef610bd88aac3f09149e92949cbf8aa6410be1)
Niech
będzie zbiorem formuł języka
Wówczas
![{\displaystyle \mathbf {Sb} _{\mathcal {L}}(X)={\Big \{}{\widehat {v}}(\delta ):\delta \in X,\;v\colon \mathbf {P} \to \mathbf {Frm} ({\mathcal {L}}){\Big \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ff929c2fd5d304a10e0fb5fe17e460eb1113fb1)
Regułą podstawiania w języku
jest reguła:
![{\displaystyle \mathbf {r} _{\star }^{\mathcal {L}}={\Big \{}{\big \langle }\{\delta \},{\widehat {v}}(\delta ){\big \rangle }:\delta \in X,\;v\colon \mathbf {P} \to \mathbf {Frm} ({\mathcal {L}}){\Big \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ccb3160094b8aeceabc25c39a70676932572c06d)
W przypadku, gdy język jest ustalony, indeks górny jest pomijany.
- Pogorzelski Witold, Elementarny słownik logiki formalnej, wyd. Filii UW, Białystok 1992.
- Pogorzelski Witold, Klasyczny rachunek zdań, Warszawa 1975.
- Hunter Geoffrey, Metalogika, Warszawa, PWN 1982.
- Shoenfield Joseph R., Mathematical Logic, Addison-Wesley, 1967.