Język zdaniowy - Polski Serwis Naukowy

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:

Algebra – jeden z najstarszych działów matematyki powstały już w starożytności. Zajmuje się on strukturami algebraicznymi i relacjami. Algebra elementarna zajmuje się takimi działaniami jak dodawanie i mnożenie; wprowadza pojęcie zmiennej i wielomianu razem z jego faktoryzacją i znajdowaniem ich pierwiastków, jednakże algebra jest działem bardziej ogólnym (patrz podział algebry).

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ą

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

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

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)