Математическа логика - основни понятия

Основни понятия

Увод

В курса ще разглеждаме тъй наречената Класическа математическа логика. Класическа е, защото има и некласическа :-). Математическа е, защото има и философска, която за нас е, да си го кажем честно, безсмислена :-)

Във този предмет ще разсъждаваме и доказваме разни твърдения свързани с математическата логика. За да правим разсъжденията ще използваме както логика, така и математика. Ще ги наричаме мета-логика и мета-математика. Не може да се тръгне от 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$ е дефинирано.
  • индукционна стъпка:
(1)
\begin{align} \Phi_{n+1} = \Phi_n \cup \{ \lnot \circ A | A \in \Phi_n \} \cup \{ (A \star B ) | A, B \in \Phi_n \And \star \in \{\land, \lor, \Rightarrow, \iff \} \} \end{align}

Идеята е, че по-сложни формули се получават като сложите $\lnot$ пред някоя формула, или обедините 2 формули със някой оператор (различен от отрицание) и заградите във скоби (за да не става двусмислено). За да е записано изрядно трябва да има $\circ$ между всеки 2 символа в последното множество (между скоба и А, A и звездата итн).
Всъщност във формулите със сложност $n$ влизат и всички по-прости формули (т.е тези с по-малка сложност).

Накрая дефинираме

(2)
\begin{align} \Phi = \bigcup_{n = 0}^{\infty} \Phi_n \end{align}

Нека $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)
\begin{align} \lnot p \land q \Rightarrow r \iff p \longleftrightarrow (((\lnot p \land q) \Rightarrow r) \iff p) \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License