Основни понятия
Увод
В курса ще разглеждаме тъй наречената Класическа математическа логика. Класическа е, защото има и некласическа :-). Математическа е, защото има и философска, която за нас е, да си го кажем честно, безсмислена :-)
Във този предмет ще разсъждаваме и доказваме разни твърдения свързани с математическата логика. За да правим разсъжденията ще използваме както логика, така и математика. Ще ги наричаме мета-логика и мета-математика. Не може да се тръгне от 0лата на чисто, защото за да изкажем някоя дефиниция или аксиома трябва да стъпим все на нещо. Е тази най-най основна математика/логика която ще използваме се нарича мета-математика/логика и не подлежи на доказателство. Нейната истинност е очевидна.
Разглеждането на математическата логика позволява да се правят заключения за самите съждения в дадена наука. Интересен е въпросът за съществуване на алгоритъм за разрешаване на даедн 'език' (при дадени аксиоми и твърдение за дадена теория, дали е истина или не).
Видове логика
Съждителна логика
Основни понятия:
- Съждение - "Тебиширът е бял", "12 се дели на 5". Съжденията могат да са както вярни (истина), така и невярни (лъжа/неистина).
- Използват се следните съюзи
- не
- и
- или
- Ако .. то ..
- // .. тогава и само тогава .. //
наименование | означение |
---|---|
съждение | латински букви $A, B$ |
не | $\lnot$ |
и | $\land$ |
или | $\lor$ |
ако .. то .. | $\Rightarrow$ |
тогава и само тогава | $\iff$ |
В съждителната логика се използват понятията съждения (твърдения). Пример за твърдение: "Тебиширът е бял". Още едно твърдение: "Обиколихме 4те ъгъла на кръглата стая".
Семантика:
Основни понятия в логиката са истината и лъжата. По принцип се отбелязват по различни начини със (и/л, t/f, T/F), но за нашите цели най-удобно е да се използва 1/0. Значението на операторите е дадено в следните 2 таблици.
$x$ | $\lnot x$ |
0 | 1 |
1 | 0 |
$x$ | $y$ | $x \land y$ | $x \lor y$ | $x \Rightarrow y$ | $x \iff y$ |
0 | 0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
Някой твърдения са вярни независимо от избора на променливите. Такива твърдения се наричат закони
- $p \lor \lnot p$ - закон за изключеното 3то
- $\lnot ( p \land \lnot p)$ - закон за непротиворечието
- $(\lnot p \land (\lnot p \Rightarrow (q \land \lnot q))) \Rightarrow p$ - доказателство с допускане на противното използва този закон.
Предикатна логика
Тази логика включва в себе си съждителната логика, но за разлика от нея обръща повече внимание на простите твърдения (т.е тези, за който в съждителната логика се използват малки/главни латински букви). Предикатната логика обръща внимание точно на тези прости твърдения. Въвеждат се кванторите за общност и за съществуване:
- $\forall n((6 / n) \iff (2 / n) \land (3 / n))$
- $\exists n(17 / n \land 31 / n)$
Ще ги разгледаме по-подробно по-нататък във курса
Съждителна логика
Съждителната логика е още известна като "Съждително смятане".
Ще разгледаме основните елементи
Език на съждителната логика
- изборимо множество от съждителни променливи - $\mathrm{Var}$
- $p, q, r, p_1, q_1, r_1 \quad x \in \mathrm{Var}$ - така ще отбелязваме че нещо е съждителна променлива
- логически връзки (съюзи)
$\lnot$ | не | отрицание | $\bar x, \sim$ |
$\land$ | и | конюнкция | $\And$ |
$\lor$ | или | дизюнкция | |
$\Rightarrow$ | ако .. то | импликация | $\rightarrow \supset$ |
$\iff$ | тг.ст. | еквиваленция | $\leftrightarrow$ |
$\{ \lnot, \land, \lor, \Rightarrow, \iff \}$ - множество на логическите съюзи
- скоби $\{ ( \ ) \}$ - множество на помощните символи (фигурните скоби са за множество - само кръглите скоби влизат във спец. символи).
3те множества са чужди (непресичащи се)
2. Думи в езика на съждителното смятане (с.с)
Всяка крайна редица от символи на езика на с.с се нарича дума. Празната дума ще бележим с $\varnothing$.
За сега ще бележим думите със гръцки букви - $\alpha, \beta, \cdots$.
- релацията равенство. Записваме $\alpha = \beta$, когато 2те редици от символи от който са образувани $\alpha$ и $\beta$ са еднакви. Т.е едни и същи символи подредени по един и същи начин
- релацията различно. Записваме $\alpha \ne \beta$. Това е просто отрицанието на релацията равно. Т.е $\alpha \ne \beta \iff \lnot (\alpha = \beta)$.
- операцията конкатанация (на български - слепване). Бележим $\alpha \circ \beta$ или просто $\alpha\beta$. Смисълът е да напишем $\beta$ след $\alpha$.
Сега ще разгледаме няколко свойства на операцията конкатанация:
Заб: Ще използваме квадратни скоби $[, ]$ вместо кръгли и единична стрелка $\longrightarrow$ вместо двойна ($\Longrightarrow$), за да не съвпадат символите с който разсъждаваме със символите от формалния език.
$\alpha \circ [ \beta \circ \gamma ] = [ \alpha \circ \beta ] \circ \gamma$ | асоциативност |
$\alpha \circ \beta \ne \beta \circ \alpha$ | няма комутативност в общия случай |
$\varnothing \circ \alpha = \alpha = \alpha \circ \varnothing$ | $\varnothing$ е единица на полугрупата1 на думите |
$\alpha \circ \beta = \alpha \circ \gamma \longrightarrow \beta = \gamma$ | съкращаване отляво |
$\beta \circ \alpha = \gamma \circ \alpha \longrightarrow \beta = \gamma$ | съкращаване отдясно |
$\alpha \circ \beta = \varnothing \longrightarrow \alpha = \beta = \varnothing$ |
- Ще въведем още една релация - начало. Бележим $\alpha \prec \beta$. Има значението че $\beta$ започва с $\alpha$. Това е просто съкратен запис: $\alpha \prec \beta \longleftrightarrow \exists \gamma : \beta = \alpha \circ \gamma$.
Сега разбира се малко свойства на тази релация:
$\alpha \prec \alpha$ | рефлексивност |
$\alpha \prec \beta,\ \beta \prec \gamma \longrightarrow \alpha \prec \gamma$ | транзитивност |
$\alpha \prec \beta,\ \beta \prec \alpha \longrightarrow \alpha = \beta$ | антисиметричност |
от тези 3 следва че $\prec$ е релация на частична наредба | |
---|---|
$\gamma \circ \alpha \prec \gamma \circ \beta \longrightarrow \alpha \prec \beta$ | съкращаване на неравенство отляво (няма отдясно) |
- Брой символи в дума бележим с $| \alpha |$. Това е естествено число. Продължаваме със свойства на дължина, начало и конкатанация:
$\alpha \prec \beta \longrightarrow | \alpha | \le | \beta |$ |
$| \varnothing | = 0$ |
$\alpha \in \mathrm{Var} \longrightarrow | \alpha | = 1$ |
$\alpha \in \mathrm{Var} \longrightarrow | \alpha \circ \beta | = | \beta | + 1 = | \beta \circ \alpha |$ |
$| \alpha \circ \beta | = | \alpha | + | \beta |$ |
$\alpha \circ \gamma = \beta \circ \delta \And | \alpha | \le | \beta | \longrightarrow \alpha \prec \beta$ |
$\alpha \circ \gamma = \beta \circ \delta \longrightarrow \alpha \prec \beta \Or \beta \prec \alpha$ |
3. Формули в езика на c.c.
Ще дефинираме следните понятия
- $\Phi$ - множеството на всички формули
- $\Phi_n$ - множеството на всички формули със сложност $n$.
$\Phi_n$ дефинираме с индукция по $n$.
- базис: $\Phi_0 = \mathrm{Var}$ - множеството на съждителните променливи са най-простите формули (сложност 0)
- индукционно предположение: нека $\Phi_n$ е дефинирано.
- индукционна стъпка:
Идеята е, че по-сложни формули се получават като сложите $\lnot$ пред някоя формула, или обедините 2 формули със някой оператор (различен от отрицание) и заградите във скоби (за да не става двусмислено). За да е записано изрядно трябва да има $\circ$ между всеки 2 символа в последното множество (между скоба и А, A и звездата итн).
Всъщност във формулите със сложност $n$ влизат и всички по-прости формули (т.е тези с по-малка сложност).
Накрая дефинираме
(2)Нека $p, q, r \in \mathrm{Var}$
Примери за валидни формули: $p, \ \lnot p, \ \lnot\lnot p, \ (\lnot p \land q), \ \lnot(p \land q), \ ((\lnot (p \land q) \lor r) \Rightarrow p)$
Примери за невалидни формули: $\lnot, \ \lnot p \land q,\ (),\ (\lnot p)$
Никой2 не обича твърде много скоби - израза става по-неясен. Ще приемем следните правила, при който е правилно да изпуснем скобите - т.е да ги подразбираме:
- изпускаме външните скоби (ако има такива) - т.е няма смисъл целия израз да е заграден. Обърнете внимание, че по правилата ако последната операция е била обединение на 2 формули със операция, то скоби трябва да има.
- дефинираме следния приоритет на операциите: $\lnot, \land, \lor, \Rightarrow, \iff$. Това е същото като приоритета на + * итн. Ако скобите го припокриват (т.е не го променят) няма смисъл да ги пишем.
- нямаме право да махаме скоби при последователност от $\Rightarrow$. Израза $p \Rightarrow q \Rightarrow r$ не е добре дефиниран (макар да можем да приемем една от посоките в който да се смята по подразбиране - е, не го правим).
Ето една напълно коректна формула със изпуснати знаци:
(3)