Język zdaniowy

Język zdaniowy – 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 \mathbb {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 \alpha _{1},\dots ,\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} ,\dots \},$${\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 Peana

Język termów arytmetyki Peana

Niech

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

Język ${\mathcal {L}}_{\mathbf {PA} }^{t}=\langle \mathbf {V} ,\{\mathbf {A} ,\mathbf {M} ,\mathbf {O} ,\mathbf {I} \},\varsigma _{\mathbf {PA} }\rangle$

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 $\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 {\boldsymbol {\Delta }}_{1}:=\mathbf {I} ,\quad {\boldsymbol {\Delta }}_{n+1}:=\mathbf {AI} {\boldsymbol {\Delta }}_{n},\quad n=0,1,2,\dots$

Język formuł arytmetyki PA

Formułami atomowymi arytmetyki Peana 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} _{\mathbf {PA} }^{(0)}.$

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 Peana nazywamy formuły języka

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

gdzie ${\mathfrak {Q}}^{\forall }=\{(\mathbf {Q} _{n}^{\forall }):n=0,1,2,\dots \},\;{\mathfrak {Q}}^{\exists }=\{(\mathbf {Q} _{n}^{\exists }):n=0,1,2,\dots \}$

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} _{n}^{\forall })=\varsigma _{\mathbf {LK} }(\mathbf {Q} _{n}^{\exists })=1,\;n=0,1,2,\dots$

Zamiast pisać $(\mathbf {Q} _{n}^{\forall })\alpha ,$ pisze się zazwyczaj $(\forall \mathbf {v} _{n})\alpha ,$ zamiast zaś pisać $(\mathbf {Q} _{n}^{\exists })\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},\dots ,\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},\dots ,\alpha _{n},\beta _{1},\dots ,\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},\,\dots ,\,\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\notin \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},\dots ,\varphi _{m}$ w miejsce zmiennych $s_{1},\dots ,s_{m}$ nazywamy formułę:

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

Wynik podstawienia nie zależy od kolejności:

$(\delta )[\varphi _{1}/s_{1},\dots ,\varphi _{m}/s_{m}]=(\delta )[\varphi _{\pi (1)}/s_{\pi (1)},\dots ,\varphi _{\pi (m)}/s_{\pi (m)}]$

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

Jeśli $p,q\in \mathbf {At} (\delta )$ i $q\notin \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},\dots ,\alpha _{\varsigma ({\mathfrak {f}})})={\mathfrak {f}}\alpha _{1}\ldots \alpha _{\varsigma ({\mathfrak {f}})},\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},\dots ,s_{n}\}$ oraz $v:\mathbf {P} \colon \to \mathbf {Frm} ({\mathcal {L}}),$ to:

${\widehat {v}}(\delta )=(\delta )[v(s_{1})/s_{1},\dots ,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.

Zobacz też

• matryca logiczna
• rachunek zdaniowy

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.