Język zdaniowy

Język zdaniowy – w logice matematycznej trójka $\mathcal{L}=\langle\textbf{P},\mathfrak{F},\varsigma\rangle$, gdzie:

$\textbf{P}$ jest zbiorem nieskończonym,

$\mathfrak{F}$ zbiorem rozłącznym z $\textbf{P}$

$\varsigma:\mathfrak{F}\to\Bbb{N}_0$.

Elementy zbioru $\textbf{P}$ są nazywane zmiennymi zdaniowymi, elementy zbioru $\mathfrak{F}$ spójnikami języka $\mathcal{L}$, a $\varsigma$ jego sygnaturą.

Skończone ciągi elementów zbioru $\textbf{P}\cup\mathfrak{F}$ są nazywane napisami języka $\mathcal{L}$.

Najmniejszy (w sensie inkluzji) spośród zbiorów napisów zbiór $Y\,$ spełniający warunki:

$\textbf{P}\subseteq Y$ (jednoelementowe napisy złożone ze zmiennych są w $Y\,$

(1)

$\mathfrak{f}\alpha_1\ldots\alpha_{\varsigma(\mathfrak{f})}\in Y\quad,\qquad \alpha_1,\ldots,\alpha_{\varsigma(\mathfrak{f})}\in Y,\quad \mathfrak{f}\in\mathfrak{F}$

(2)

nazywany jest zbiorem formuł języka $\mathcal{L}$ i oznaczany symbolem $\mathbf{Frm}(\mathcal{L})$.

O zbiorach spełniających warunki (1) i (2) mówi się, że są domknięte na budowę formuł języka $\mathcal{L}$.

Innymi słowy zbiór $\mathbf{Frm}(\mathcal{L})$ jest najmniejszym zbiorem napisów domkniętym na budowę formuł języka $\mathbf{Frm}(\mathcal{L})$.

Przykład

Język klasycznego rachunku zdań)

Niech $\mathcal{L}_\mathbf{CIMV}=\langle\textbf{P},\mathfrak{F},\varsigma_\mathbf{LK}\rangle$, gdzie $\mathbf{P}=\{\mathbf{p},\mathbf{q},\mathbf{r},\mathbf{s},\ldots\}$, $\mathfrak{F}=\{\mathbf{C},\mathbf{A},\mathbf{K},\mathbf{N},\mathbf{E}\}$ i niech

$\varsigma_\mathbf{LK}(\mathbf{C})=2\,,\;\varsigma_\mathbf{LK}(\mathbf{A})=2\,,\;\varsigma_\mathbf{LK}(\mathbf{K})=2\,,\;\varsigma_\mathbf{LK}(\mathbf{E})=2\,,\;\varsigma_\mathbf{LK}(\mathbf{N})=1$

Wówczas $\mathbf{CCNpqApq}$ jest formułą języka $\mathcal{L}_\mathbf{CIMV}$, ale $\mathbf{CCNpqqApq}$ i $\mathbf{CCNpNApq}$ nie są.

Język arytmetyki Peano

Język termów arytmetyki Peano

Niech

$\varsigma_\mathbf{PA}= \left\langle\begin{array}{c|c|c|c}\mathbf{A}&\mathbf{M}&\mathbf{O}&\mathbf{I}\\\hline2&2&0&0\end{array}\right\rangle \qquad\mbox{i niech}\qquad\mathbf{V}=\{\mathbf{v}_0,\mathbf{v}_1,\mathbf{v}_2,\ldots\}$.

Język $\mathcal{L}^t_\mathbf{PA}=\langle\mathbf{V},\{\mathbf{A},\mathbf{M},\mathbf{O},\mathbf{I}\},\varsigma_\mathbf{PA}\rangle$ nazywa się językiem termów arytmetyki Peano. Formuły tego języka nazywa się termami arytmetyki Peano. Zbiór wszyskich termów arytmetyki Peano oznaczany będzie $\mathbf{Trm}_\mathbf{PA}$.

Dla wygody czasem zamiast $\mathbf{v}_0$ pisze się $\mathbf{x}$, zamiast $\mathbf{v}_1$ pisze się $\mathbf{y}$ i zamiast $\mathbf{v}_2$ pisze się $\mathbf{z}$.

Definiujemy indukcyjnie ciąg numerałów:

$\boldsymbol{\Delta}_0:=\mathbf{O}\quad,\quad\boldsymbol{\Delta}_1:=\mathbf{I}\quad,\qquad\boldsymbol{\Delta}_{n+1}:=\mathbf{AI}\boldsymbol{\Delta}_n\qquad,\qquad\quad n=0,1,2,\ldots\,.$

Język formuł arytmetyki PA

Formułami atomowymi arytmetyki Peano nazywamy napisy postaci $\mathbf{Eq}\tau_1\tau_2$ oraz $\mathbf{Le}\tau_1\tau_2$, gdzie $\tau_1,\tau_2\in\mathbf{Trm}_{PA}$.

Zwyczajowo zamiast $\mathbf{Eq}\tau_1\tau_2$, pisze się $(\tau_1\equiv\tau_2)$, zamiast $\mathbf{Le}\tau_1\tau_2$, pisze się $(\tau_1\leqslant\tau_2)$.

Zbiór formuł atomowych języka PA, oznaczymy $\mathbf{Frm}^{(0)}_\mathbf{PA}$.

 ; Przykład:

formułami atomowymi języka PA są

(Zero jest najmniejsze)	$\mathbf{O}\leqslant\mathbf{x}$
(Aksjomaty dla dodawania)	$\mathbf{AxO}\equiv\mathbf{x}$,	$\mathbf{AxAyI}\equiv\mathbf{AAxyI}$
(Aksjomaty dla mnożenia)	$\mathbf{MxO}\equiv\mathbf{O}$,	$\mathbf{MxAyI}\equiv\mathbf{AMxyx}$
(Przemienność dodawania i mnożenia)	$\mathbf{Axy}\equiv\mathbf{Ayx}$,	$\mathbf{Mxy}\equiv\mathbf{Myx}$
(Łączność dodawania i mnożenia)	$\mathbf{AxAyz}\equiv\mathbf{AAxyz}$,	$\mathbf{MxAyz}\equiv\mathbf{MMxyz}$
(2+3=5)	$\mathbf{A}\boldsymbol{\Delta}_2\boldsymbol{\Delta}_3\equiv\boldsymbol{\Delta}_5$
(2*3=6)	$\mathbf{M}\boldsymbol{\Delta}_2\boldsymbol{\Delta}_3\equiv\boldsymbol{\Delta}_6$

Formułami arytmetyki Peano nazywamy formuły języka

$\langle\mathbf{Frm}^{(0)}_\mathbf{PA},\{\mathbf{A},\mathbf{K},\mathbf{N},\mathbf{C},\mathbf{E}\}\cup\mathfrak{Q}^\forall\cup\mathfrak{Q}^\exists, \varsigma_\mathbf{KRK}\rangle$, gdzie $\mathfrak{Q}^\forall=\{(\mathbf{Q}^\forall_n):\,n=0,1,2,\ldots,\,\}\,,\;\mathfrak{Q}^\exists=\{(\mathbf{Q}^\exists_n):\,n=0,1,2,\ldots,\,\}$

oraz gdzie $\varsigma_\mathbf{KRK}$ jest wzbogaceniem sygnatury $\varsigma_\mathbf{LK}$ do zbioru $\{\mathbf{A},\mathbf{K},\mathbf{N},\mathbf{C},\mathbf{E}\}\cup\mathfrak{Q}^\forall\cup\mathfrak{Q}^\exists$, dla którego $\varsigma_\mathbf{LK}(\mathbf{Q}^\forall_n)=\varsigma_\mathbf{LK}(\mathbf{Q}^\exists_n)=1,\,\;n=0,1,2,\ldots$.

Zamiast pisać $(\mathbf{Q}^\forall_n)\alpha$, pisze się zazwyczaj $(\forall\mathbf{v}_n)\alpha$, zamiast zaś pisać $(\mathbf{Q}^\exists_n)\alpha$, pisze się zazwyczaj $(\exists\mathbf{v}_n)\alpha$.

 ; Przykład:

formułami języka PA są

• $\mathbf{E}(\mathbf{x\leqslant y})(\exists\mathbf{z})(\mathbf{Axz\equiv y})$
• $\mathbf{C}(\mathbf{Axz\leqslant Ayz})(\mathbf{x\leqslant y})$
• $\mathbf{CN}(\mathbf{z\equiv O})\mathbf{C}(\mathbf{Mxz\leqslant Myz})(\mathbf{x\leqslant y})$

---

Lemat (o kształcie formuł)

Niech $\mathcal{L}$ będzie językiem zdaniowym.

Wówczas dla każdej formuły $\delta\,$ tego języka zachodzi jeden z warunków

$\delta\in\mathbf{P}$

(3)

$\delta=\mathfrak{f}\alpha_1\ldots\alpha_n$ dla pewnego $\mathfrak{f}\in\mathfrak{F}$ oraz $\alpha_1,\ldots,\alpha_n\in\mathbf{Frm}(\mathcal{L})$

(4)

Dla dowodu tego lematu należy rozważyć zbiór $Y\,$ formuł $\delta\,$ 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)

Niech $\mathcal{L}$ będzie językiem zdaniowym, niech $\alpha_1,\ldots,\alpha_n,\beta_1,\ldots,\beta_m\,$ będą formułami i niech $\mathfrak{f_1}, \mathfrak{f_2}\in\mathfrak{F}\,$ będą takie, że $\mathfrak{f_1}\alpha_1\ldots\alpha_n=\mathfrak{f_2}\beta_1\ldots\beta_m\,$.
Wówczas $\mathfrak{f_1}=\mathfrak{f_2}\,,\,n=m\;\,$ oraz $\alpha_1=\beta_1\,,\,\ldots\,,\,\alpha_n=\beta_m\,$.

Podformuły

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 $\delta\,$ nazywamy zbiór zdefiniowany następująco:

$\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}$

Zmiennymi formuły $\delta\,$ nazywamy elementy zbioru $\mathbf{At}(\delta)=\mathbf{Sbf}(\delta)\cap\mathbf{P}$.

Przykład

$\mathbf{Sbf}(\mathbf{CCNpqApq})=\{\mathbf{p},\mathbf{q},\mathbf{Apq},\mathbf{Np},\mathbf{CNpq},\mathbf{CCNpqApq}\}$

Podstawienie w formule

Podstawieniem w formule $\delta\,$ formuły $\varphi$ w miejsce zmiennej $s\,$ nazywamy formułę:

$(\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}$

Zachodzi $\delta[p/p]=\delta\,$. Jeśli $p\not\in\mathbf{At}(\delta)$, to $\delta[\varphi/p]=\delta$.

Przykład

$(\mathbf{CCNpqApq})[\mathbf{KEpqNp}/\mathbf{q}]=\mathbf{CCNpKEpqNpApKEpqNp}$

Jednoczesne podstawienie kilku formuł

W wielu wypadkach przydaje się umiejętność jednoczesnego podstawienia kilku formuł w miejsce kilku zmiennych:

Podstawieniem w formule $\delta\,$ formuł $\varphi_1,\ldots,\varphi_m$ w miejsce zmiennych $s_1,\ldots,s_m$ nazywamy formułę:

$(\delta)[\varphi_1/s_1,\ldots,\varphi_m/s_m]= \begin{cases} {p} &{\mbox{jeśli }p\in\mathbf{P}\setminus\{s_1,\ldots,s_m\}\,,}\\ {\varphi_j}&{\mbox{jeśli }p=s_j\,,\,j=1,\ldots,m\,, }\\ {\mathfrak{f}(\alpha_1[\varphi_1/s_1,\ldots,\varphi_m/s_m])\ldots(\alpha_n[\varphi_1/s_1,\ldots,\varphi_m/s_m])}& {\mbox{jeśli }\delta=\mathfrak{f}\alpha_1\ldots\alpha_n\;,\;\mathfrak{f}\in\mathfrak{F}\,.} \end{cases}$

Wynik podstawienia nie zależy od kolejności:

$(\delta)[\varphi_1/s_1,\ldots,\varphi_m/s_m]=(\delta)[\varphi_{\pi(1)}/s_{\pi(1)},\ldots,\varphi_{\pi(m)}/s_{\pi(m)}]$

dla dowolnej permutacji $\pi\,$ zbioru $\{1,2,\ldots,n\}.$

Jeśli $p,q\in\mathbf{At}(\delta)$ i $q\not\in\mathbf{At}(\varphi)$, to:

$(\delta)[\varphi/p,\psi/q]=\big((\delta)[\varphi/p]\big)[\psi/q]\,.$

Przykład

$(\mathbf{CCNpqApq})[\mathbf{KEpqNp}/\mathbf{p},\mathbf{CNpp}/\mathbf{q}]$	=$\mathbf{CCNKEpqNpCNppAKEpqNpCNpp}$
$(\mathbf{CCNpqApq})[\mathbf{KEpqNp}/\mathbf{p}][\mathbf{CNpp}/\mathbf{q}]$	=$(\mathbf{CCNKEpqNpqAKEpqNpq})[\mathbf{CNpp}/\mathbf{q}]$=
	=$\mathbf{CCNKEpCNppNpCNppAKEpCNppNpCNpp}$

Algebra formuł

Język zdaniowy wyznacza dość ważną algebrę sygnatury $\varsigma\,$:

Algebrą formuł języka $\mathcal{L}$ nazywamy algebrę sygnatury tego języka $\mathfrak{A}_\mathcal{L}$, której uniwersum jest $\mathbf{Frm}(\mathcal{L})$ i w której

$\mathfrak{A}_\mathcal{L}(\mathfrak{f})(\alpha_1,\ldots,\alpha_{\varsigma(\mathfrak{f})}){=} \mathfrak{f}\alpha_1\ldots\alpha_{\varsigma(\mathfrak{f})}\quad,\qquad\hbox{dla}\;\;\mathfrak{f}\in\mathfrak{F}\,. \,$

Algebra języka jest algebrą wolną z $\mathbf{P}$ jako zbiorem wolnych generatorów w klasie algebr jej sygnatury:

Dla dowolnej algebry $\mathfrak{C}$ sygnatury języka $\mathcal{L}$ oraz dowolnego odwzorowania $v\colon\mathbf{P}\to|\mathfrak{C}|$ istnieje jedyny homomorfizm $\widehat{\mathfrak{A}_\mathcal{L},v}\colon\mathfrak{A}_\mathcal{L}\to\mathfrak{C}$ rozszerzający $v\,$.

W przypadku, gdy język jest ustalony w danym kontekście homomorfizm ten oznaczamy po prostu symbolem $\widehat{v}$.

Zauważmy, że $(\delta)[\varphi/s]=\widehat{v}(\delta)$, gdzie $v\colon\mathbf{P}\to\mathbf{Frm}(\mathcal{L})$ dane jest wzorem:

$v(p)=\begin{cases}\varphi\,,&p=s\\p\,,&p\in\mathbf{P}\setminus\{s\}\;\;.\end{cases}$

Co więcej, jeśli $\mathbf{At}(\delta)=\{s_1,\ldots,s_n\}$ oraz $v:\mathbf{P}\colon\to\mathbf{Frm}(\mathcal{L})$, to:

$\widehat{v}(\delta)=(\delta)[v(s_1)/s_1,\ldots,v(s_n)/s_n]$.

Niech $X\,$ będzie zbiorem formuł języka $\mathcal{L}$. Wówczas

$\mathbf{Sb}_\mathcal{L}(X)=\Big\{\widehat{v}(\delta):\;\delta\in X\,,\;v\colon\mathbf{P}\to\mathbf{Frm}(\mathcal{L})\Big\}$

Reguła podstawiania

Regułą podstawiania w języku $\mathcal{L}$ jest reguła:

$\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\}$

W przypadku, gdy język jest ustalony, indeks górny jest pomijany.

Bibliografia

• 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.

Zobacz też

• Rachunek zdaniowy
• Matryca logiczna