Математическа логика - тема 1

Език на съждителното смятне, думи, формули, теорема за еднозначен синтактичен анализ.

++Азбука на езика на съждителното смятане++

Азбуката на езика на съждителното смятане е обединението на следните три множества:
- изброимо множество от съждителни променливи: Var. Обикновено ще използваме буквите $p, q, p_1, q_1, \dots$ за да означаваме променливи.
- множество на логическите съюзи: $\{\lnot, \land, \lor, \Rightarrow, \Leftrightarrow\}$.
— отрицание (не): $\lnot$
— конюнкция (и): $\land$
— дизюнкция (или): $\lor$
— импликация (ако …, то …): $\Rightarrow$
— еквиваленция (тогава и само тогава): $\Leftrightarrow$
- лява и дясна скоба: $\{(, )\}$

Въведените три множества са непресичащи се (тоест множеството на променливите Var не може да съдържа елементи от другите 2).

Дефиниция(дума): Всяка крайна редица от знаци от азбуката наричаме дума. Дума е също празната дума (дума без символи), която ще означаваме с $\varnothing$.

Примери за думи: $\lnot \lnot \lnot, \lnot p, ppp, (p \land q ), )()()(pp \Leftrightarrow )) \lnot$
Обикновено ще използваме малки гръцки букви за означаване на думи.
Казваме, че две думи са равни, ако са една и съща редица от знаци. Означаваме по обичайния начин$\alpha = \beta$.

Конкатенация на думи:
Конкатенацията на думите $\alpha$ и $\beta$ записваме $\alpha \beta$ (или $\alpha . \beta$). Това е думата, получена като непосредствено след $\alpha$ е написана думата $\beta$.
Свойства:
1)Единичен елемент: $\varnothing . \alpha = \alpha . \varnothing = \alpha$
2)Асоциативност: $[ \alpha . \beta ] . \gamma = \alpha . [ \beta . \gamma ]$ (тук квадратни скоби са използвани за означение на реда на операциите, те не са част от езика)
3)В общия случай няма комутативност: $\alpha . \beta \neq \beta . \alpha$
4a)Съкращаване отдясно: Ако $\alpha . \gamma = \beta . \gamma$, то $\alpha = \beta$.
4b)Съкращаване отляво: Ако $\gamma . \alpha = \gamma . \beta$, то $\alpha = \beta$.
Множеството на думите образува полугрупа с единичен елемент с операцията конкатенация.

Дефиниция(начало): Казваме, че $\alpha$ е начало на $\beta$, ако съществува дума $\gamma$, такава че $\alpha . \gamma = \beta$. Означаваме $\alpha \prec \beta$
Свойства:
1) $\varnothing \prec \alpha$ за всяка дума $\alpha$
2) Транзитивност: ако $\alpha \prec \beta$ и $\beta \prec \gamma$, то $\alpha \prec \gamma$
3) Рефлексивност: за всяка дума $\alpha$ е в сила $\alpha \prec \alpha$.
4) Антисиметричност: Ако $\alpha \prec \beta$ и $\beta \prec \alpha$, то $\alpha = \beta$
Така релацията 'начало' е чатична наредба.
5) Ако $\alpha . \beta \prec \alpha . \gamma$, то $\beta \prec \gamma$

Дефиниция: Ако $\alpha$ е непразна дума и е начало на $\beta$ казваме, че $\alpha$ е същинско начало на $\beta$.

++Формули на съждителното смятане++

На някои думи от езика ще придадем специален смисъл и ще ги наричаме формули.

Дефиниция: Ще означаваме с $\Phi$ множеството на всички формули. Дефинираме $\Phi \leftrightharpoons \cup_{n=1}^{\infty} Phi_n$, където множествата $\Phi_n$ са дефинирани индуктивно така:
$\Phi_1 \leftrightharpoons Var$
Ако $\Phi_n$ е вече дефинирано, дефинираме $\Phi_{n+1} \leftrightharpoons \Phi_n \cup \{\lnot \alpha | \alpha \in \Phi_n\} \cup \{ (\alpha \circ \beta) | \alpha, \beta \in \Phi_n, \circ \in \{\land, \lor, \Rightarrow, \Leftrightarrow\}\}$.

По-късно ще дадем еквивалентна дефиниция, която е по-лесна за разбиране.

Дефиниция: Сложност на думата $\alpha$ наричаме естествено число $n$, за което $\alpha \in \Phi_n$.
Една дума има много различни сложности, затова дефинираме минимална сложност на $\alpha$ най-малкото естествено числа $n$, което е сложност на $\alpha$.

Теорема: Ако $\alpha$ е формула, то броят на левите скоби на $\alpha$ е равен на броя на десните скоби.
Доказателство:

Примери:
Думата $\alpha = (p \land q)$ (където $p, q \in \mathrm{Var}$) е формула.
$p, q \in \Phi_1$, следоватлно $(p \land q) \in \Phi_2$.
Думата $\beta = \lnot (p \land q)$ съще е формула (този път от $\Phi_3$.
Думата $\gamma = p \land q$ не е формула (скобите са задължителни).

Лема: Ако $\alpha \in \Phi_n$ за някое естествено число $n$ и $\alpha \notin \Phi_1$, то първият символ на $\alpha$ е или $\lnot$ или $($. Ако първият символ е (, то последният е ).
Доказателството е по дефиницията на $\Phi_n$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License