1611678155-8e243485e0094ed4164786c6208411db (П.Е. Алаев - Краткий конспект лекций)

П. Е. АЛАЕВЛЕКЦИИ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ, ЧАСТЬ IКРАТКИЙ КОНСПЕКТММФ НГУ, 20121. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ1.1. Слова и операции над нимиАлфавитом называется произвольное множество символов. Слово в алфавите ∆ — произвольная конечная последовательность A = a1 a2 . . . an символов из ∆.Длина слова |A| — количество символов в нём, т. е. число n. Подслово слова A — любая его часть, состоящая из идущих подряд символов, т.

е. слово вида at at+1 . . . as .Начало слова — это подслово вида a1 . . . as , а конец слова — подслово вида at . . . an .Пустое слово — слово длины 0, вообще не содержащее символов.Замечание. На языке теории множеств слово в алфавите ∆ может быть определено как функция f : {1, 2, . . . , n} → ∆.Вхождением подслова в данное слово называется само подслово вместе с указанием того места, в котором оно расположено в слове (вместе с номером символа, скоторого оно начинается). Например, B = ma является словом в алфавите {a, m},является подсловом слова A = mathematics, и при этом существует два вхожденияслова B в слово A.Замена некоторого вхождения подслова B в слово A на слово B 0 производитсятак: пусть A1 — та часть слова A, которая расположена перед вхождением B, аA2 — та часть, которая расположена после него; в этом случае A = A1 BA2 .

Тогдарезультатом замены является слово A1 B 0 A2 .Кроме того, используется и операция подстановки слова B вместо всех вхождений некоторого символа a в слово A. В этом случае все вхождения a одновременнозаменяются на слово B.1.2. Формулы исчисления высказываний (ИВ)Алфавит исчисления высказываний состоит из трёх частей:1) пропозициональные переменные: они, как правило, будут обозначаться буквамиP, P0 , P1 , . . .

, Q, Q0 , Q1 , . . . , R, R0 , R1 , . . .2) логические связки — конъюнкция: &дизъюнкция:∨импликация: →отрицание:¬3) вспомогательные символы — левая скобка:(правая скобка: )Формулы ИВ являются словами в этом алфавите и строятся по правилам:21) Пропозициональная переменная является формулой (такая формула называетсяатомной).2) Если A, B — формулы, то ¬A, (A&B), (A ∨ B), (A → B) — тоже формулы.Для работы с формулами часто будет использоваться индукция. Пусть Φ(n) —некоторое утверждение, которое для каждого натурального числа n может бытьистинным или ложным.Принцип математической индукции.

Если Φ(0) истинно, и для всех n изистинности Φ(n) следует истинность Φ(n + 1), то Φ(n) истинно для всех n.Иногда бывает удобно использовать индукцию в следующей усиленной форме.Возвратная индукция. Пусть для каждого n из того, что Φ(k) истинно прилюбом k < n, следует, что истинно Φ(n). Тогда Φ(n) истинно для всех n.Лемма (о начале формулы). Если A, B — формулы ИВ и слово B являетсяначалом слова A, то A = B.Предложение (о представлении формулы ИВ).

Всякая неатомная формула ИВ единственным образом может быть представлена в одной из форм¬A, (A&B), (A ∨ B), (A → B),где A, B — формулы ИВ.До конца Части 1 формулы ИВ будем называть просто формулами. Назовёмподформулой формулы A её подслово, которое само является формулой.Лемма. Если A, B — формулы и непустой конец слова A совпадает с началомслова B, то этот конец равен B.Предложение (о подформулах формулы ИВ). Пусть A — формула, B —её подформула и A 6= B.1) Если A = (A1 ◦ A2 ), где ◦ ∈ {&, ∨, →}, то любое вхождение B в A являетсявхождением либо в A1 , либо в A2 .2) Если A = ¬A1 , то любое вхождение B в A является вхождением в A1 .Следствие.

Если в формуле A некоторое вхождение подформулы заменить надругую формулу, то результат вновь будет формулой.1.3. Исчисление секвенций (ИС)Алфавит ИС получается из алфавита ИВ добавлением символов ` (“следует”)и запятой. Секвенция — слово одного из следующих видов:A1 , . . . , An ` B (“из A1 , . . . , An следует B”),A1 , . . . , An ` (“набор A1 , . . .

, An противоречив”),` B (“B истинно”),где A1 , . . . , An , B — формулы, n > 1. При этом A1 , . . . , An называются посылкамисеквенции, а B — её заключением.3Исчисление секвенций ИС задаётся аксиомами и правилами вывода. В приведённом ниже списке правил A, B, C обозначают некоторые формулы, Γ, Γ1 , Γ2 —конечные наборы формул (может быть, пустые).Аксиомы ИС: все секвенции вида A ` AΓ ` A; Γ ` B(введение &),Γ ` (A&B)Правила вывода ИС:Γ ` (A&B)Γ ` (A&B)(удаление &),(удаление &),Γ`AΓ`BΓ`AΓ`B(введение ∨),(введение ∨),Γ ` (A ∨ B)Γ ` (A ∨ B)Γ ` (A ∨ B); Γ, A ` C; Γ, B ` C(удаление ∨),Γ`CΓ ` A; Γ ` (A → B)Γ, A ` B(введение →),(удаление →),Γ ` (A → B)Γ`BΓ, A `Γ, ¬A `(введение ¬),(удаление ¬),Γ ` ¬AΓ`AΓ ` (добавление заключения), Γ ` A; Γ ` ¬A (сведение к противоречию),Γ`AΓ`Γ1 , A, B, Γ2 ` CΓ ` A (добавление посылки).(перестановка)Γ1 , B, A, Γ2 ` CΓ, B ` AОпределим теперь понятие дерева вывода в ИС.1) Аксиома одновременно является деревом вывода этой аксиомы.S ; .

. . ; Sk2) Если 1— правило вывода ИС, D1 , . . . , Dk — деревья выводов секвенцийSD ; . . . ; DkS1 , . . . , Sk , соответственно, то 1— дерево вывода секвенции S.SСеквенция S выводима (доказуема) в ИС, если существует дерево вывода этойсеквенции.1.4. Семантика исчисления высказыванийЛогические связки можно рассматривать как операции на логических величинах и (“истина”) и л (“ложь”), которые определяются так:A B (A&B) (A ∨ B) (A → B)и ииииA ¬Aи ллилилл илиилил лллиПусть M — некоторое множество пропозициональных переменных.

Назовём означиванием пропозициональных переменных из M соответствие γ, которое каждойпеременной P ∈ M сопоставляет значение γ(P ) из множества {и, л}.4Если A — формула и γ — означивание, при котором каждая переменная из Aполучает некоторое значение, то значение формулы A при означивании γ, A[γ],может быть определено индукцией по длине формулы:1.

Если A — переменная P , то A[γ] = γ(P ).2. Если A = (A1 ◦ A2 ), где ◦ ∈ {&, ∨, →}, то A[γ] = A1 [γ] ◦ A2 [γ] (см. таблицу выше).3. Если A = ¬A1 , то A[γ] = ¬A1 [γ].Замечание. Значение формулы A при означивании γ зависит от значенийтолько тех переменных, которые входят в A.Ясно, что если не все переменные формулы A получают значения при означивании γ, говорить о A[γ], вообще говоря, бессмысленно. Договоримся, что всякийраз, когда речь идёт о значении формулы при означивании γ, неявно подразумевается условие, что γ сопоставляет значения всем переменным, входящим в этуформулу.Формула называется тождественно истинной (тождественно ложной), еслиона принимает значение и (л) при любом означивании переменных.Пусть фиксировано некоторое означивание. Секвенция вида A1 , .

. . , An ` Bистинна при этом означивании, если B истинна или хотя бы одна из Ai ложна.Секвенция вида A1 , . . . , An `истинна, если хотя бы одна из Ai ложна. Секвенция` B истинна, если формула B истинна.Секвенция называется тождественно истинной, если она истинна при любомозначивании переменных.Теорема о корректности ИС. Любая выводимая в ИС секвенция тождественно истинна.1.5.

Допустимые правила выводаS1 ; . . . ; Skназывается допустимым в ИС, если из выводимости секвенSций S1 , . . . , Sk следует выводимость S.ПравилоДерево вывода с допустимыми правилами определяется точно так же, какобычное дерево вывода в ИС, с дополнительным условием, что вместе с исходными правилами ИС могут использовать и любые допустимые.Предложение (о выводе с допустимыми правилами).

Если у секвенцииесть дерево вывода с допустимыми правилами, то она выводима в ИС.5Предложение (о допустимых в ИС правилах). Следующие правила допустимы в ИС:Γ ` A; Γ, A ` B(сечение),Γ`BΓ, A ` C; Γ, B ` C(разбор случаев),Γ, (A ∨ B) ` CΓ, (A&B) ` CΓ, A, B ` C(соединение посылок),(разделение посылок),Γ, (A&B) ` CΓ, A, B ` CΓ, A ` BΓ, ¬A ` ¬BΓ, A ` ¬BΓ, ¬A ` B(контрапозиция),Γ, ¬B ` ¬AΓ, B ` AΓ, ¬B ` AΓ, B ` ¬AA1 , . . . , An ` BA1 , . . .

, An `(структурные), где A1 , . . . , An — поднабор в C1 , . . . , Cm .C1 , . . . , Cm ` BC 1 , . . . , Cm `1.6. Теорема о заменеФормулы A и B синтаксически эквивалентны (A ≡ B), если выводимы секвенции A ` B и B ` A.Лемма. Отношение ≡ обладает следующими свойствами:a) A ≡ A;b) A ≡ B ⇒ B ≡ A;c) A ≡ B, B ≡ C ⇒ A ≡ C;d) A ≡ A0 ⇒ ¬A ≡ ¬A0 ;e) A ≡ A0 , B ≡ B 0 ⇒ (A ◦ B) ≡ (A0 ◦ B 0 ), где ◦ ∈ {&, ∨, →}.Теорема (о замене). Если в формуле A некоторую подформулу заменитьна синтаксический эквивалентную ей формулу, то результат будет синтаксическиэквивалентен A.1.7.

Нормальные формыДокажем теперь, что любая формула ИВ может быть приведена через цепочку эквивалентностей к некоторому простому виду. Договоримся, что при записиформул две внешние скобки (в начале и конце формулы) могут быть опущены.Лемма (основные эквивалентности ИВ-1). Пусть A, B, C — произвольныеформулы. Тогда верно, чтоa) A&B ≡ B&A и A ∨ B ≡ B ∨ A (коммутативность);b) A&(B&C) ≡ (A&B)&C и A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C (ассоциативность);c) A&(B ∨ C) ≡ (A&B) ∨ (A&C) иd) A ∨ (B&C) ≡ (A ∨ B)&(A ∨ C) (дистрибутивность).6Лемма (основные эквивалентности ИВ-2). Пусть A, B — произвольныеформулы.

Тогда верно, чтоa) A → B ≡ ¬A ∨ B;b) ¬¬A ≡ A;c) ¬(A&B) ≡ ¬A ∨ ¬B;d) ¬(A ∨ B) ≡ ¬A&¬B;e) A ≡ A ∨ A и A ≡ A&A.Обозначим через (A1 ∨ A2 ∨ . . . ∨ An ) формулу (. . . ((A1 ∨ A2 ) ∨ A3 ) . . . ∨ An ),а через (A1 &A2 & . . . &An ) — формулу (. . .

((A1 &A2 )&A3 ) . . . &An ). Иногда будемnn_^кратко обозначать их какAi иAi .i=1i=1Лемма. Пусть Ai , Bj , C — произвольные формулы. Тогдаa) (A1 ∨ . . . ∨ An ) ∨ (B1 ∨ . . . ∨ Bk ) ≡ (A1 ∨ . . . ∨ An ∨ B1 ∨ . . . ∨ Bk );b) C&(A1 ∨ . . . ∨ An ) ≡ ((C&A1 ) ∨ . . . ∨ (C&An ));c) пункты (a) и (b) останутся верными при замене & на ∨, а ∨ на &.Элементарная конъюнкция — это формула вида (A1 & . . . &An ), n > 1, где каждая Ai — переменная или отрицание переменной.Дизъюнктивная нормальная форма (д.н.ф.) — формула вида (B1 ∨ . . . ∨ Bk ),k > 1, где каждая Bi — элементарная конъюнкция.Элементарная дизъюнкция — формула вида (A1 ∨ . . .

∨ An ), n > 1, где каждаяAi — переменная или отрицание переменной.Конъюнктивная нормальная форма (к.н.ф.) — формула вида (B1 & . . . &Bk ), k >1, где каждая Bi — элементарная дизъюнкция.Теорема (о приведении к д.н.ф. и к.н.ф.). Любая формула синтаксическиэквивалентна некоторой к.н.ф. и некоторой д.н.ф., содержащим тот же набор переменных, что и она сама.1.8. Теорема о полноте ИСПредложение (о тождественно истинных к.н.ф.). К.н.ф. A тождественноистинна тогда и только тогда, когда каждая её элементарная дизъюнкция содержит P и ¬P для некоторой переменной P .Обратным утверждением к теореме о корректности ИС являетсяТеорема о полноте ИС.

Любая тождественно истинная секвенция выводима вИС.7Напомним, что запись A ≡ B обозначает синтаксическую эквивалентность.Говорим, что A и B семантически эквивалентны (A ∼ B), если при любом означивании переменных значения A и B совпадают.Следствие. A ≡ B тогда и только тогда, когда A ∼ B.1.9. Совершенные нормальные формыСовершенная д.н.ф. (с.д.н.ф.) — это такая д.н.ф., что1) любая входящая в неё переменная входит в каждую элементарную конъюнкциюровно 1 раз, с отрицанием или без;2) любые две элементарные конъюнкции существенно различаются, т.е.

существует такая переменная P , что в одну из них входит P , а в другую ¬P .Совершенная к.н.ф. (с.к.н.ф.) — определяется аналогично, с заменой ∨ на & инаоборот — это такая к.н.ф., что1) любая входящая в неё переменная входит в каждую элементарную дизъюнкциюровно 1 раз, с отрицанием или без;2) любые две элементарные дизъюнкции существенно различаются.Теорема (о совершенных нормальных формах).a) Любая не тождественно ложная формула эквивалентна некоторой с.д.н.ф., содержащей тот же набор переменных, что и она сама;b) Любая не тождественно истинная формула эквивалентна некоторой с.к.н.ф.,содержащей тот же набор переменных, что и она сама;c) Нормальная форма в (a) и (b) единственна с точностью до перестановки элементарных конъюнкций (дизъюнкций) и их компонент.Замечание.