Этот конспект не гарантирует полноту и был записан не со слов Вадима Геннадьевича, а по бумажному конспекту одногруппницы.
По всем вопросам обращаться по адресу: [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 Определений теорий исчислениея высказываний (25)

Аксиомы теории:

Аксиома 1

ABAA ⊃ B ⊃ A

Аксиома 2

AB𝐶ABA𝐶A ⊃ B ⊃ 𝐶 ⊃ A ⊃ B ⊃ A ⊃ 𝐶

Аксиома 3

¬B¬A¬BAB¬B ⊃ ¬A ⊃ ¬B ⊃ A ⊃ B

Единственное правило вывода: B – непосредственное
следствие формул A,ABA, A ⊃ B, или
A,ABB\frac{A, A ⊃ B}{B}
Это правило называется modus ponens\text{modus ponens} (MP). Его
правомерность обосновывается теоремой 1.1.

Теорема 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 = 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

сл 32. лемму 3.10 доказать самостоятельно !

II. Логика предикатов первого порядка

1. Кванторы и формулы логики предикатов

<!!!!????>

Полнота и непоротиворечивость теорий первого порядка

Свойство 1.

Если в даннной интерпретации истинны AA и ABA \supset B, то истинна и BB.

Свойство 2.

Всякий частный случай тавтологии истенен во всякой интерпретации. Поэтому любые подстановки в аксиомы A1-A3 логически общезначимы. Тогда в силу свойства 1 правило modus ponens\text{modus ponens}, применённое к аксиомам A1-A3 сохраняет логическую общезначимость.

Если на произвольной последовательности элементов из DD выполнена формула для всех xA(x)\forall{x} A(x), то на ней выполнена и формула A(t)A(t), где tt - терм, свободный на области интерпретации, следовательно формула xA(x)A(t)\forall{x} A(x) \supset A(t) истинна при любом высказывании. Следовательно, аксиома A4 логически общезначима.