В.А. Успенский - Курс лекций по математической логике, страница 2

Это понятие вводится индуктивно.Определение.• Каждая высказывательная переменная есть формула.• Если α — формула, то α — тоже формула.• Если α и β — формулы, то (α&β), (α ∨ β), (α ⇒ β) — тоже формулы.Приведём без доказательства теорему, которая обосновывает законность вычисления значения формулы,построенной таким образом.Теорема 1.2 (О главном знаке). Если α — формула, то обязательно имеет место один из вариантов:••••α — высказывательная переменная.α = β.α = β&γ.α = β ∨ γ.5• α = β ⇒ γ.При этом формулы β и γ определены однозначно.Определение.

Формула называется безымпликативной, если она не содержит знаков импликации.Определение. Формула имеет нормальный вид (нормальную форму), если под каждым знаком отрицаниянаходятся только высказывательные переменные.Теорема 1.3. Каждая формула приводится к нормальному виду. Сначала приводим формулу к безымпликативной форме, заменяя импликацию на её выражение черезотрицание и дизъюнкцию. Затем раскроем все скобки, используя законы Де Моргана. Очевидно, что после этогоформула будет приведена к нормальному виду.

Обозначим через B множество {T, F } = {0, 1}.Определение. Функции вида f : Bn → B называются n-местными логическими функциями.Рассмотрим один пример, который оправдывает вводимые ниже обозначения. Рассмотрим уравнение x2 ++ y 2 = 1. Спросим себя, что задаёт это уравнение? Если переменными в нём являются только x и y, то этоокружность.

Но с тем же успехом можно подумать, что это уравнение цилиндра в R3 , параллельного оси z.Хотелось бы исключить данного рода разночтения. Для этого придуманы специальные λ-обозначения.Правила записи λ-обозначений таковы:λсписок переменныхвыражениеподстановка переменныхПример 1.3. Возьмём выражение y + x2 и рассмотрим его различные λ-записи:Записьλ xy y + x2 (3, 5)λ xy y + x2 (5, 3)λ zyuxv y + x2 (3, 5)λ zyuxv y + x2 (3, 0, 5, 8, 11)λ ztuxv y + x2 (3, 0, 5, 8, 11)Значение3 + 525 + 32не определено0 + 82y + 82Мы видим, что λ-обозначения позволяют определить для каждого выражения некоторую функцию.Определение. Функция, задаваемая λ-обозначением некоторой формулы, называется присоединённой кданной формуле.Определение. Литералом называется высказывательная переменная или её отрицание.Определение.

Формула вида α1 & . . . &αn , где αi — формулы, называется конъюнкцией формул α1 , . . . , αn .Дизъюнкция определяется аналогично с заменой & на ∨.Определение. Пусть A — высказывательная переменная. Положим A1 = A, а A0 = A. Отметим, что Aε —литерал.Утверждение 1.4. Всякая формула языка логики высказываний задаёт некоторую логическую функцию,и наоборот, любая логическая функция может быть записана формулой языка логики высказываний. В одну сторону доказывать нечего, поскольку достаточно рассмотреть подходящее λ-обозначение длязаданной формулы: в качестве списка переменных возьмём все переменные, входящие в формулу.Обратно, пусть задана функция f : Bn → B. Пусть M — множество всех наборов (a1 , .

. . , an ) ∈ Bn , длякоторых f (a1 , . . . , an ) = 1. Заметим, что Aε = 1 тогда и только тогда, когда A = ε, поэтому, если M =6 ∅,рассмотрим формулу_(ae11 & . . . &aenn ) .(1)(e1 ,...,en )∈MПроверим, что эта формула обращается в 1 только при (a1 , . . . , an ) ∈ M. Действительно, ae11 & . . . &aenn = 1 тогдаи только тогда, когда ai = ei для i = 1, . . . , n. Следовательно, если набор (a1 , . . . , an ) не лежит в M, то ни водной из дизъюнкций не будет полного совпадения ai с ei , и каждая из дизъюнкций будет нулевой, поэтомузначение выражения будет ложным. Если же набор (a1 , . . . , an ) присутствует в M, то ровно одна конъюнкциястанет истинной, поэтому значение всего выражения также будет истинным.В случае, когда M пусто, достаточно рассмотреть формулу a1 &a1 , которая тождественно ложна.

Определение. Произвольная дизъюнкция конъюнкций, состоящих из литералов, называется дизъюнктивной нормальной формой (ДНФ). Конъюнкция дизъюнкций, состоящих из литералов, называется конъюнктивной нормальной формой (КНФ). ДНФ (соответственно, КНФ) называются совершенной, если каждая переменная или её отрицание входит в каждую конъюнкцию (соответственно, дизъюнкцию) ровно по одному разу.6Формула (1) приведена к СДНФ. Очевидно, что для данного состава переменных такое представление единственно: если две формулы в СДНФ различаются каким-либо дизъюнктом, то на наборе из показателей, соответствующих этому дизъюнкту, формулы будут иметь разные значения.Отметим, что попутно нами доказана теорема:Теорема 1.5.

Любая функция, не являющаяся тождественно ложной, выражается формулой в СДНФ.Определение. Тождественно истинные высказывания называются тавтологиями и обозначаются |=.Определение. Наряду с импликацией, часто используется логическая связка эквивалентности, определяемая так: A ⇔ B ≡ (A ⇒ B)&(B ⇒ A). Несложно видеть, что она имеет таблицу истинностиA0011A⇔B1001B0101Пример 1.4.1◦ . α ≡ β тогда и только тогда, когда |= (α ⇔ β).2◦ .

|= (A ∨ A).Замечание. Знак равенства между выражениями означает, что это имена одного и того же объекта.Определение. Язык называется разрешимым, если некоторое высказывание отмечено как истинное, и существует алгоритм, который для любого высказывания определяет, истинно оно или ложно.Пример 1.5. Язык логики высказываний разрешим.1.2. Упорядоченные множества1.2.1. Бинарные отношенияОпределение.

Символом 2M мы будем обозначать множество всех подмножеств множества M.Определение. Пусть M — некоторое множество. Говорят, что на M задано бинарное отношение R, есливыделено подмножество R ⊂ M × M. Про элементы x, y ∈ M говорят, что они находятся в отношении R,если (x, y) ∈ R. При этом пишут xRy.Определение.1◦ . R называется рефлексивным, если ∀ x ∈ M имеем xRx.2◦ .

R называется симметричным, если из того, что xRy следует, что и yRx.3◦ . R называется транзитивным, если из того, что xRy и yRz следует, что xRz.Определение. Отношение R, удовлетворяющее свойствам 1◦ , 2◦ и 3◦ , называется отношением эквивалентности.Определение. Будем говорить, что множество M линейно упорядочено, если на нём введено рефлексивноетранзитивное бинарное отношение 4 со следующими свойствами:1◦ . Если x 4 y и y 4 x, то x = y.2◦ . Всегда выполнено x 4 y или y 4 x — связанность.В этом случае отношение 4 называется отношением линейного порядка.Замечание. Это определение сформулировано для случая «нестрогого» порядка.

Для строгого порядканужно подправить свойство связанности: всегда выполнено x 4 y или y 4 x или x = y.Замечание. Если в выражение x 4 y вместо x и y подставить конкретные элементы множества, то получится высказывание, истинное, если верно, что x 4 y, и ложное в противном случае. Таким образом, x 4 y —высказывательная форма.Определение.

Частичное упорядочение отличается от линейного упорядочения отсутствием требованиясвязанности. В этом случае множество называется частично упорядоченным.Определение. Изоморфизм упорядоченных множеств M и N — биекция ϕ : M → N со свойством ϕ(x) 44 ϕ(y) тогда и только тогда, когда x 4 y. Если между множествами существует изоморфизм, то такие множестваназываются изоморфными.Пример 2.1.

Покажем, что между (Z, 6) и (Q, 6) не существует изоморфизма. Здесь 6 — обычное нестрогоенеравенство, очевидно, являющееся отношением порядка. Действительно, допустим, что ϕ : N → Q — изоморфизм, тогда рассмотрим a := ϕ(3) и b := ϕ(4). Число a+b2 должно иметь прообраз в N, но его «некуда запихнуть»,потому что между 3 и 4 нет натуральных чисел.7Пример 2.2. Для класса всех множеств M можно ввести отношение частичного порядка следующим образом: A 4 B тогда и только тогда, когда A ⊂ B.Задача 1.5. Доказать, что каждое частично упорядоченное множество изоморфно некоторому классумножеств.Задача 1.6. Изоморфны ли R и R r Q?Для изоморфных частично упорядоченных множеств любое утверждение, сформулированное только в терминах отношения порядка, автоматически переносится с одного множества на другое.TODO: Определения минимальных и наименьших элементов!Определение.

Бинарное отношение называется квазипорядком (или предпорядком), если оно рефлексивнои транзитивно.Задача 1.7. Пусть 4 — квазипорядок на множестве M. Скажем, что a ∼ b, если a 4 b и b 4 a. Доказать,что ∼ задаёт отношение эквивалентности.Задача 1.8. Пусть (M, 4, ∼) — множество, квазипорядок и отношениеэквивалентности из задачи 1.7.Рассмотрим фактормножество классов эквивалентности F = M ∼ .

Пусть [a], [b] ∈ F. Рассмотрим условия:1◦ . ∃ x ∈ [a], ∃ y ∈ [b] такие, что x 4 y.2◦ . ∀ x ∈ [a], ∀ y ∈ [b] имеем x 4 y.Доказать, что 1◦ равносильно 2◦ . Скажем, что [a] 4 [b], если выполнено любое из условий 1◦ или 2◦ . Доказать,что введённое таким образом отношение задаёт упорядочение на F .Задача 1.9. Введём на формулах математической логики отношение: α 4 β тогда и только тогда, когда|= (α ⇒ β). Доказать, что 4 является квазипорядком.Если решить задачу 1.9, то мы докажем существование алгебры Линденбаума — множества A классов эквивалентных формул.

Впрочем, поскольку в нашем случае получаемое отношение эквивалентности есть просто ≡,предыдущие задачи можно и не решать. Действительно, по определению, оно может быть записано как α ∼ βтогда и только тогда, когда |= (α ⇒ β) и |= (β ⇒ α), но это и означает, что α ≡ β. На элементах алгебры Линденбаума можно ввести логические операции: [α]&[β] := [α&β]. Ясно, что такое определение корректно ввидусовпадения ∼ c ≡.Определение. Говорят, что A и B образуют разбиение множества M, если A ∪ B = M, при этом A, B 6= ∅и A ∩ B = ∅. Мы1 будем обозначать разбиения так: M = (A; B).Пусть (M, 4) — линейно упорядоченное множество.Определение. Разбиение (A; B) множества M называется сечением, если ∀ x ∈ A, ∀ y ∈ B имеем x 4 y.В этом случае A называется левым (нижним) смежным классом (ЛСК), a B — правым (верхним) смежнымклассом (ПСК). Обозначение: M = (A|B).Пусть (A|B) = M, а ϕ : M → N — изоморфизм.

Очевидно, что ϕ(A)|ϕ(B) — сечение N . Иными словами,при изоморфизмах сечение переходит в сечение.Название сеченияСкачокДедекиндово сечениеДедекиндово сечениеЩель∃ наибольший элемент в ЛСКДаНетДаНет∃ наименьший элемент в ПСКДаДаНетНетЗадача 1.10. Доказать, что изоморфизм сохраняет скачки, щели и дедекиндовы сечения.1.2.2. Язык описания упорядоченных множествАлфавитом нашего языка будет следующий набор символов: ∨, &, ¬, ⇒, ), (, =, 4, ≺, ∃ , ∀ . Индивидныепеременные: x, y, .