Język zdaniowy

Język zdaniowy – trójka $ℒ=⟨\mathbf{\text{P}},𝔉,\varsigma ⟩,$ gdzie:

$\mathbf{\text{P}}$ jest zbiorem nieskończonym,

$𝔉$ zbiorem rozłącznym z $\mathbf{\text{P}}$

$\varsigma :𝔉\to {\mathbb{N}}_0.$

Elementy zbioru $\mathbf{\text{P}}$ są nazywane zmiennymi zdaniowymi, elementy zbioru $𝔉$ spójnikami języka $ℒ,$ a $\varsigma$ jego sygnaturą.

Skończone ciągi elementów zbioru $\mathbf{\text{P}}\cup 𝔉$ są nazywane napisami języka $ℒ.$

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

Szablon:Wzór

Szablon:Wzór

nazywany jest zbiorem formuł języka $ℒ$ i oznaczany symbolem $𝐅𝐫𝐦(ℒ).$

O zbiorach spełniających warunki Szablon:LinkWzór i Szablon:LinkWzór 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 $𝐅𝐫𝐦(ℒ).$

Przykład

Język klasycznego rachunku zdań

Niech ${ℒ}_{𝐂𝐈𝐌𝐕}=⟨\mathbf{\text{P}},𝔉,{\varsigma }_{𝐋𝐊}⟩,$

gdzie $𝐏=\{𝐩,𝐪,𝐫,𝐬,\dots \},$$𝔉=\{𝐂,𝐀,𝐊,𝐍,𝐄\}$

i niech ${\varsigma }_{𝐋𝐊}(𝐂)=2,{\varsigma }_{𝐋𝐊}(𝐀)=2,{\varsigma }_{𝐋𝐊}(𝐊)=2,{\varsigma }_{𝐋𝐊}(𝐄)=2,{\varsigma }_{𝐋𝐊}(𝐍)=1.$

Wówczas $𝐂𝐂𝐍𝐩𝐪𝐀𝐩𝐪$ jest formułą języka ${ℒ}_{𝐂𝐈𝐌𝐕},$ ale $𝐂𝐂𝐍𝐩𝐪𝐪𝐀𝐩𝐪$ i $𝐂𝐂𝐍𝐩𝐍𝐀𝐩𝐪$ nie są.

Język arytmetyki Peana

Język termów arytmetyki Peana

Niech

${\varsigma }_{𝐏𝐀}=⟨\begin{array}{cccc}𝐀& 𝐌& 𝐎& 𝐈\\ 2& 2& 0& 0\end{array}⟩\text{i niech}𝐕=\{{𝐯}_0,{𝐯}_1,{𝐯}_2,\dots \}.$

Język ${ℒ}_{𝐏𝐀}^t=⟨𝐕,\{𝐀,𝐌,𝐎,𝐈\},{\varsigma }_{𝐏𝐀}⟩$

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 ${𝐯}_0$ pisze się $𝐱,$ zamiast ${𝐯}_1$ pisze się $𝐲$ i zamiast ${𝐯}_2$ pisze się $𝐳.$

Definiujemy indukcyjnie ciąg numerałów:

${\mathrm{\Delta }}_0:=𝐎,{\mathrm{\Delta }}_1:=𝐈,{\mathrm{\Delta }}_{n+1}:=𝐀𝐈{\mathrm{\Delta }}_n,n=0,1,2,\dots$

Język formuł arytmetyki PA

Formułami atomowymi arytmetyki Peana nazywamy napisy postaci $𝐄𝐪{\tau }_1{\tau }_2$ oraz $𝐋𝐞{\tau }_1{\tau }_2,$ gdzie ${\tau }_1,{\tau }_2\in {𝐓𝐫𝐦}_{PA}.$

Zwyczajowo zamiast $𝐄𝐪{\tau }_1{\tau }_2,$ pisze się $({\tau }_1\equiv {\tau }_2),$ zamiast $𝐋𝐞{\tau }_1{\tau }_2,$ pisze się $({\tau }_1⩽{\tau }_2).$

Zbiór formuł atomowych języka PA, oznaczymy ${𝐅𝐫𝐦}_{𝐏𝐀}^{(0)}.$

Przykład:

formułami atomowymi języka PA są

(Zero jest najmniejsze)	$𝐎⩽𝐱$
(Aksjomaty dla dodawania)	$𝐀𝐱𝐎\equiv 𝐱,$	$𝐀𝐱𝐀𝐲𝐈\equiv 𝐀𝐀𝐱𝐲𝐈$
(Aksjomaty dla mnożenia)	$𝐌𝐱𝐎\equiv 𝐎,$	$𝐌𝐱𝐀𝐲𝐈\equiv 𝐀𝐌𝐱𝐲𝐱$
(Przemienność dodawania i mnożenia)	$𝐀𝐱𝐲\equiv 𝐀𝐲𝐱,$	$𝐌𝐱𝐲\equiv 𝐌𝐲𝐱$
(Łączność dodawania i mnożenia)	$𝐀𝐱𝐀𝐲𝐳\equiv 𝐀𝐀𝐱𝐲𝐳,$	$𝐌𝐱𝐀𝐲𝐳\equiv 𝐌𝐌𝐱𝐲𝐳$
(2+3=5)	$𝐀{\mathrm{\Delta }}_2{\mathrm{\Delta }}_3\equiv {\mathrm{\Delta }}_5$
(2*3=6)	$𝐌{\mathrm{\Delta }}_2{\mathrm{\Delta }}_3\equiv {\mathrm{\Delta }}_6$

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

$⟨{𝐅𝐫𝐦}_{𝐏𝐀}^{(0)},\{𝐀,𝐊,𝐍,𝐂,𝐄\}\cup {𝔔}^{\mathrm{\forall }}\cup {𝔔}^{\mathrm{\exists }},{\varsigma }_{𝐊𝐑𝐊}⟩,$

gdzie ${𝔔}^{\mathrm{\forall }}=\{({𝐐}_n^{\mathrm{\forall }}):n=0,1,2,\dots \},{𝔔}^{\mathrm{\exists }}=\{({𝐐}_n^{\mathrm{\exists }}):n=0,1,2,\dots \}$

oraz gdzie ${\varsigma }_{𝐊𝐑𝐊}$ jest wzbogaceniem sygnatury ${\varsigma }_{𝐋𝐊}$ do zbioru $\{𝐀,𝐊,𝐍,𝐂,𝐄\}\cup {𝔔}^{\mathrm{\forall }}\cup {𝔔}^{\mathrm{\exists }},$ dla którego ${\varsigma }_{𝐋𝐊}({𝐐}_n^{\mathrm{\forall }})={\varsigma }_{𝐋𝐊}({𝐐}_n^{\mathrm{\exists }})=1,n=0,1,2,\dots$

Zamiast pisać $({𝐐}_n^{\mathrm{\forall }})\alpha ,$ pisze się zazwyczaj $(\mathrm{\forall }{𝐯}_n)\alpha ,$ zamiast zaś pisać $({𝐐}_n^{\mathrm{\exists }})\alpha ,$ pisze się zazwyczaj $(\mathrm{\exists }{𝐯}_n)\alpha .$

Przykład:

formułami języka PA są

• $𝐄(𝐱\mathbf{⩽}𝐲)(\mathrm{\exists }𝐳)(𝐀𝐱𝐳\mathbf{\equiv }𝐲)$
• $𝐂(𝐀𝐱𝐳\mathbf{⩽}𝐀𝐲𝐳)(𝐱\mathbf{⩽}𝐲)$
• $𝐂𝐍(𝐳\mathbf{\equiv }𝐎)𝐂(𝐌𝐱𝐳\mathbf{⩽}𝐌𝐲𝐳)(𝐱\mathbf{⩽}𝐲)$

Lemat (o kształcie formuł)

Niech $ℒ$ będzie językiem zdaniowym.

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

Szablon:Wzór

Szablon:Wzór

Dla dowodu tego lematu należy rozważyć zbiór $Y$ formuł $\delta$ spełniających warunki Szablon:LinkWzór i Szablon:LinkWzór powyżej, a następnie pokazać, że jest on domknięty na budowę formuł.

Lemat (o jednoznaczności budowy)

Niech $ℒ$ będzie językiem zdaniowym, niech ${\alpha }_1,\dots ,{\alpha }_n,{\beta }_1,\dots ,{\beta }_m$ będą formułami i niech ${𝔣}_1,{𝔣}_2\in 𝔉$ będą takie, że ${𝔣}_1{\alpha }_1\dots {\alpha }_n={𝔣}_2{\beta }_1\dots {\beta }_m.$

Wówczas ${𝔣}_1={𝔣}_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:

$𝐒𝐛𝐟(\delta )=\{\begin{array}{cc}\delta ,& \text{jeśli }\delta \in 𝐏\\ 𝐒𝐛𝐟({\alpha }_1)\cup \dots \cup 𝐒𝐛𝐟({\alpha }_n)\cup \{\delta \}& \text{jeśli }\delta =𝔣{\alpha }_1\dots {\alpha }_n,𝔣\in 𝔉.\end{array}$

Zmiennymi formuły $\delta$ nazywamy elementy zbioru $𝐀𝐭(\delta )=𝐒𝐛𝐟(\delta )\cap 𝐏.$

Przykład

$𝐒𝐛𝐟(𝐂𝐂𝐍𝐩𝐪𝐀𝐩𝐪)=\{𝐩,𝐪,𝐀𝐩𝐪,𝐍𝐩,𝐂𝐍𝐩𝐪,𝐂𝐂𝐍𝐩𝐪𝐀𝐩𝐪\}$

Podstawienie w formule

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

$(\delta )[\phi /s]=\{\begin{array}{cc}p,& \text{jeśli }p\in 𝐏\setminus \{s\}\\ \phi & \text{jeśli }p=s\\ 𝔣({\alpha }_1[\phi /s])\dots ({\alpha }_n[\phi /s])& \text{jeśli }\delta =𝔣{\alpha }_1\dots {\alpha }_n,𝔣\in 𝔉.\end{array}$

Zachodzi $\delta [p/p]=\delta .$ Jeśli $p\notin 𝐀𝐭(\delta ),$ to $\delta [\phi /p]=\delta .$

Przykład

$(𝐂𝐂𝐍𝐩𝐪𝐀𝐩𝐪)[𝐊𝐄𝐩𝐪𝐍𝐩/𝐪]=𝐂𝐂𝐍𝐩𝐊𝐄𝐩𝐪𝐍𝐩𝐀𝐩𝐊𝐄𝐩𝐪𝐍𝐩$

Jednoczesne podstawienie kilku formuł

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

Podstawieniem w formule $\delta$ formuł ${\phi }_1,\dots ,{\phi }_m$ w miejsce zmiennych $s_1,\dots ,s_m$ nazywamy formułę:

$(\delta )[{\phi }_1/s_1,\dots ,{\phi }_m/s_m]=\{\begin{array}{cc}p& \text{jeśli }p\in 𝐏\setminus \{s_1,\dots ,s_m\},\\ {\phi }_j& \text{jeśli }p=s_j,j=1,\dots ,m,\\ 𝔣({\alpha }_1[{\phi }_1/s_1,\dots ,{\phi }_m/s_m])\dots ({\alpha }_n[{\phi }_1/s_1,\dots ,{\phi }_m/s_m])& \text{jeśli }\delta =𝔣{\alpha }_1\dots {\alpha }_n,𝔣\in 𝔉.\end{array}$

Wynik podstawienia nie zależy od kolejności:

$(\delta )[{\phi }_1/s_1,\dots ,{\phi }_m/s_m]=(\delta )[{\phi }_{\pi (1)}/s_{\pi (1)},\dots ,{\phi }_{\pi (m)}/s_{\pi (m)}]$

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

Jeśli $p,q\in 𝐀𝐭(\delta )$ i $q\notin 𝐀𝐭(\phi ),$ to:

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

Przykład

$(𝐂𝐂𝐍𝐩𝐪𝐀𝐩𝐪)[𝐊𝐄𝐩𝐪𝐍𝐩/𝐩,𝐂𝐍𝐩𝐩/𝐪]$	$=𝐂𝐂𝐍𝐊𝐄𝐩𝐪𝐍𝐩𝐂𝐍𝐩𝐩𝐀𝐊𝐄𝐩𝐪𝐍𝐩𝐂𝐍𝐩𝐩$
$(𝐂𝐂𝐍𝐩𝐪𝐀𝐩𝐪)[𝐊𝐄𝐩𝐪𝐍𝐩/𝐩][𝐂𝐍𝐩𝐩/𝐪]$	$=(𝐂𝐂𝐍𝐊𝐄𝐩𝐪𝐍𝐩𝐪𝐀𝐊𝐄𝐩𝐪𝐍𝐩𝐪)[𝐂𝐍𝐩𝐩/𝐪]=$
	$=𝐂𝐂𝐍𝐊𝐄𝐩𝐂𝐍𝐩𝐩𝐍𝐩𝐂𝐍𝐩𝐩𝐀𝐊𝐄𝐩𝐂𝐍𝐩𝐩𝐍𝐩𝐂𝐍𝐩𝐩$

Algebra formuł

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

Algebrą formuł języka $ℒ$ nazywamy algebrę sygnatury tego języka ${𝔄}_{ℒ},$ której uniwersum jest $𝐅𝐫𝐦(ℒ)$ i w której

${𝔄}_{ℒ}(𝔣)({\alpha }_1,\dots ,{\alpha }_{\varsigma (𝔣)})=𝔣{\alpha }_1\dots {\alpha }_{\varsigma (𝔣)},\text{dla}𝔣\in 𝔉.$

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 $v:𝐏\to |ℭ|$ istnieje jedyny homomorfizm $\widehat{{𝔄}_{ℒ},v}:{𝔄}_{ℒ}\to ℭ$ rozszerzający $v.$

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

Zauważmy, że $(\delta )[\phi /s]=\hat{v}(\delta ),$ gdzie $v:𝐏\to 𝐅𝐫𝐦(ℒ)$ dane jest wzorem:

$v(p)=\{\begin{array}{cc}\phi ,& p=s\\ p,& p\in 𝐏\setminus \{s\}.\end{array}$

Co więcej, jeśli $𝐀𝐭(\delta )=\{s_1,\dots ,s_n\}$ oraz $v:𝐏:\to 𝐅𝐫𝐦(ℒ),$ to:

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

Niech $X$ będzie zbiorem formuł języka $ℒ.$ Wówczas

${𝐒𝐛}_{ℒ}(X)=\{\hat{v}(\delta ):\delta \in X,v:𝐏\to 𝐅𝐫𝐦(ℒ)\}$

Reguła podstawiania

Regułą podstawiania w języku $ℒ$ jest reguła:

${𝐫}_{\star }^{ℒ}=\{⟨\{\delta \},\hat{v}(\delta )⟩:\delta \in X,v:𝐏\to 𝐅𝐫𝐦(ℒ)\}$

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.