Этот конспект не гарантирует полноту и был записан не со слов Вадима Геннадьевича, а по бумажному конспекту одногруппницы.
По всем вопросам обращаться по адресу: [email protected]

Математическая Логика

Пак Вадим Геннадьевич

Дистанционный курс:

https://dl.spbstu.ru/course/view.php?id=233
Кодовое слово: [email protected]

Коллоквиумы:

Литература

Символы

https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols
https://ru.wikipedia.org/wiki/Список_логических_символов

aˉ\bar{a} \bar{a}
¬\lnot \lnot
\land \land
\lor \lor
\supset \supset
\to \to
    \implies \implies
\equiv \equiv
    \iff \iff
\top \top
\bot \bot
\forall \forall
\exists \exists
\vdash \vdash
\vDash \vDash
\sqsupset \sqsupset

Логика высказываний

Алгебра высказываний

Высказывание — утверждение, о котором можно определенно сказать, истинно оно или ложно.

Высказывания:

1.2 Пропозициональные связки (6)

Простые высказывания сточные a, b, c, a1a_1, b2b_2
Сложные высказывания заглавные AA,

Операции над высказываниями:

  1. Отрициние: aˉ,¬\bar{a}, \lnot
  2. Конъюнкция, логическое умножение: ,&\land, \&
  3. Дизъюнкция, логическое сложение: ,+\lor, +
  4. Импликация: ,,    \supset, \to, \implies
    Антецедент \to консеквент
  5. Эквиваленция: ,    \equiv, \iff

Пропозициональные связки: ¬,,,,\lnot, \land, \lor, \supset, \equiv

1.3 Формулы алгебры высказываний (11)

Высказывания и операции над ними образуют алгебру высказываний.
Алфавит записи:

  1. строчные латинские буквы — пропозициональные буквы
  2. пропозициональные связки
  3. специальные символы (,)

Формулой алгебры высказываний (пропозициональной формой) является называется слово в алфавите алгебры высказываний, построенной по правилам:

  1. Любая буква есть формула
  2. Если A, B есть формулы, то слова (¬A\lnot A), (ABA \land B), (ABA \lor B), (ABA \supset B), (ABA \equiv B) также являются формулами
  3. Слово является формулой в том и только в том случае, если оно построено по правилам 1, 2.

Внешние скобки важны!

Подформулой формулы называется её часть, являющаяся формулой.

1.4 Тавтологии (15)

Тавтология — тождественно истинная формула.

Теорема 1.1:

Если AA, ABA \supset B тавтологии, то BB также тавтология.

Док-во: предположим, что при некотором распределении истинностных значений входящих в AA и BB пропозициональных букв, BB ложно, тогда при этих значениях AA истина, тогда ABA \supset B должна быть ложна, что противоречит тому, что ABA \supset B - тавтология.

Теорема 1.2

Если AA тавтология, содержащая буквы a1,a2,...,ana_1, a_2, ... , a_n, формула BB получена подстановкой в AA формул A1,A2,...,AnA_1, A_2, ... , A_n вместо всех вхождений букв a1,a2,...,ana_1, a_2, ... , a_n. Тогда BB также является тавтологией.

Док-во: аналогично, примем без доказательства.

Теорема 3.1

(теорема дедукции для ИВ)
Если ГГ -- множество формул и ГГ, АBА \vdash B, то ГABГ \vdash A \supset B.

Док-во:
B1,...,Bm\sqsupset B_1, ..., B_m -- вывод формулы BB из мн-ва формул Г{A},Bm=BГ \cup \{A\}, B_m = B
индукции по ii, от 1 до mm докажем, что из ГГ выводится ГABГ \vdash A \supset B.
База индукции: оъi=1i = 1 : B1B_1 либо аксиома, либо гипотеза из ГГ, либо AA
B1,B1(AB1)AB1\frac{B_1, B_1 \supset (A \supset B_1)}{A \supset B_1}

если B1B_1 совпадает с A, то по лемме 3: ГAAГ \vdash A \supset A

Индукционное предположение: ГABk,k<iГ \vdash A \supset B_k, \forall k < i

BiB_i выводится из предыдущих формул Bj,Bm (1<=m,j<=i,j<m)B_j, B_m \ _{(1 <= m,j <=i, j < m)} по modus ponens.

Bm    BjBiB_m \iff B_j \supset B_i

Первые три варианта доказываются так же, как в базе. Четвертый вариант: по индукционному предположению из Г.

ГABj(1)Г \vdash A \supset B_j \quad _{(1)}

ГA(BjBi)(2)Г \vdash A \supset (B_j \supset B_i) \quad _{(2)}

(A(BjBi))((ABi)(ABi))(3, по аксиоме 2)(A \supset (B_j \supset B_i)) \supset ((A \supset B_i) \supset (A \supset B_i)) \quad _\textrm{(3, по аксиоме 2)}

Γ(ABj)(ABi)(4, по modus ponens из 2 и 3)\Gamma \vdash (A \supset B_j) \supset (A \supset B_i) \quad _\textrm{(4, по modus ponens из 2 и 3)}

Γ(ABj)(по modus ponens из 1 и 4)\Gamma \vdash (A \supset B_j) \quad _\textrm{(по modus ponens из 1 и 4)}
Индукционный шаг доказан.
При i=ni = n получаем решение. \Box