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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетКурс лекций поматематической логикеЛектор — Владимир Андреевич УспенскийI курс, 2 семестр, поток математиковМосква, 2003 г.Оглавление1.Языки и исчисления1.1. Логика высказываний . . . . . . . . . .

. . . . . . . . . . . . .1.1.1. Основные понятия . . . . . . . . . . . . . . . . . . . .1.1.2. Язык логики высказываний . . . . . . . . . . . . . . .1.2. Упорядоченные множества . . . . . . . . . . . . . . . . . . . .1.2.1. Бинарные отношения . . . . . . . . . . . . . . . .

. . .TODO: Определения минимальных и наименьших элементов1.2.2. Язык описания упорядоченных множеств . . . . . . .1.2.3. Связанные и свободные вхождения переменных . . .1.2.4. Приведение формулы к предварённой форме . . . . .1.2.5. Теорема о свободной подстановке . . . . . . .

. . . . .1.2.6. Теорема об элиминации кванторов . . . . . . . . . . .1.3. Неэлементарные языки первого порядка . . . . . . . . . . . .1.3.1. Предикаты . . . . . . . . . . . . . . . . . . . . . . . . .1.3.2. Общее определение языка первого порядка . . . . . .1.4. Структуры и сигнатуры, интерпретации и модели . . .

. . .1.4.1. Математические модели . . . . . . . . . . . . . . . . .2................................................................................................................................................................................................................................................................................................................................................................4445778891010101111121313ВведениеПредисловиеНастоящее издание представляет собой записи лекций В.

А. Успенского. Убедительная просьба ко всем читателям: в случае обнаружения ошибок немедленно сообщайте автору на dmvn@mccme.ru или загляните наhttp://dmvn.mexmat.net и посмотрите, где можно достать в настоящее время самого автора. Все пожелания ипредложения по поводу оформления и содержания документа будут обязательно приняты к сведению.

Последнее обновление: 27 января 2006 года.Слова благодарностиДля начала хотелось бы поблагодарить того, кто изначально набирал эти лекции. К сожалению, Историяне сохранила ни TEX-овских исходников его лекций, ни имени. Так что данный материал — улучшенная версиястарого документа.Принятые в тексте соглашения и используемые сокращения1◦ Множество натуральных чисел в математической логике принято начинать с нуля: N = {0, 1, 2, 3, .

. . }.Литература[1] Конспекты лекций В.А. Успенского по математической логике. МГУ, 2003.[2] Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Начала теории множеств. М.: МЦНМО, 2000.[3] Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов.

Языки и исчисления.М.: МЦНМО, 2000.[4] Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Вычислимые функции.М.: МЦНМО, 2000.3Математическая логика может быть условно разделена на три части:• Математическая логика (в более узком смысле)• Теория алгоритмов• Основание математики1. Языки и исчисления1.1. Логика высказываний1.1.1. Основные понятияДля начала введём несколько понятий, которые постоянно будут использоваться в нашем курсе.Определение. Алфавит — произвольный конечный непустой набор символов. Можно считать, что алфавит — произвольное непустое конечное множество.Определение. Текст — любая конечная последовательность символов некоторого алфавита.Определение. Слово — любая конечная последовательность символов некоторого алфавита.

Итак, с точкизрения логики, слово и текст — это одно и то же. Пустое слово обозначается буквой Λ.Замечание. Иногда возникает потребность в рассмотрении счётных алфавитов, но в нашем курсе этого небудет.Следствие 1.1. Множество слов в конечном алфавите счётно.Определение. Алгоритм — одно из неопределяемых понятий в математике. Разговор о том, что это такое,у нас ещё впереди, однако одним из требований является то, что алгоритм — это текст, записанный в некоторомалфавите.Следствие 1.2.

Множество алгоритмов счётно.Задача 1.1. Доказать, что множество функций f : N → N несчётно.Следствие 1.3. Существуют функции f : N → N, для которых нельзя построить алгоритм A, принимающий на вход x ∈ N и выдающий на выходе f (x), т. е. вычисляющий функцию f .Определение. Высказывание является неопределяемым понятием. Вместо определения скажем, что высказывание — это утверждение, которое может быть либо истинным, либо ложным. Высказывания обычнообозначаются буквами A, B, . . . , Z, A1 , B1 , . . . , Z1 , . . ..Если высказывание истинно, то говорят, что его истинностное значение — «истина», в противном случае —«ложь».

Для обозначения истинностных значений используются следующие значки:ИстинныеИTtrue⊤1ЛожныеЛFfalse⊥1Истинностное значение высказывания A обозначается через |A|.Пример 1.1. «14 июля 2004 года — среда» — истинное высказывание. «14 июля 2004 года — вторник» —ложное высказывание. «Среда ли 14 июля 2004 года?» — не высказывание.Ещё один замечательный пример утверждения, не являющегося высказыванием, таков:Всё, что написано в этой рамке, есть ложьДействительно, попытка определить истинностное значение этого «высказывания» приводит к противоречию:если то, что написано, истинно, то это противоречит смыслу слов в рамке.

То же противоречие возникает, еслипредположить, что оно ложно.Определение. Высказывания с одинаковыми истинностными значениями называются равносильными, илиэквивалентными. Обозначение: A ≡ B.Высказывания можно объединять, используя логические связки: отрицание («НЕ», ¬), конъюнкцию («И»,&), дизъюнкцию («ИЛИ», ∨) и импликацию («ЕСЛИ. . . ТО», ⇒). Их определения приведены в следующихтаблицах истинности:4A01¬A10A0011B0101A&B0001A∨B0111A⇒B1101Определение. Закон логики — такое высказывание, которое истинно вне зависимости от высказываний,входящих в него.Вообще говоря, в логических выражениях нужно везде писать скобки. Однако часто скобки не пишут, пользуясь правилами приоритета логических связок. Так, отрицание имеет наивысший приоритет, затем следуетконъюнкция и лишь потом — дизъюнкция. Что касается импликации, то она имеет низший приоритет.

Крометого, необходимо помнить, что ∨ и & ассоциативны, а ⇒ — нет.Задача 1.2. Проверьте справедливость утверждений относительно ассоциативности. Указание: доказательство ассоциативности провести для трёх высказываний, а затем по индукции обобщить на произвольноеколичество.Пример 1.2. A ∨ B&C ⇒ D ≡ A ∨ (B&C) ⇒ D , а выражение A ⇒ B ⇒ C не имеет смысла. Правильнаязапись — (A ⇒ B) ⇒ C или A ⇒ (B ⇒ C) , причём это неэквивалентные формулы.Замечание.

Иногда для обозначения конъюнкции используют знак ∧, а для обозначения отрицания — чертусверху. Так, A ∧ B ≡ A&B, а ¬A ≡ A.Утверждение 1.1. Справедливы следующие законы логики:••••A ≡ A — закон снятия двойного отрицания.A&B ≡ A ∨ B, A ∨ B ≡ A&B — законы Де Моргана.A&B ≡ A ∨ B, A ∨ B ≡ A&B — выражения для конъюнкции и дизъюнкции.A ⇒ B ≡ A ∨ B — выражение для импликации.

Чтобы доказать любую из этих формул, достаточно проверить её для всех возможных истинностныхзначений высказываний, входящих в неё. Например, докажем, что A ≡ A. Если A истинно, то A ложно, ипотому A истинно. Если же A ложно, то A истинно, поэтому A ложно. Аналогично доказываются все остальныеформулы. Из соотношений, полученных выше, мы видим, что на самом деле можно обойтись всего двумя логическимисвязками, например, конъюнкцией и отрицанием, а остальные — дизъюнкцию и импликацию — можно выразитьчерез первые две.Задача 1.3. Выразить ∨ и & через ¬ и ⇒.Задача 1.4.

Доказать, что нельзя полностью избавиться от отрицания в логических выражениях, невводя других логических связок и не используя импликацию.1.1.2. Язык логики высказыванийВ предыдущем разделе уже использовались термины «формула», «выражение» и т. п., однако не были даныточные определения. Настало время исправить этот недостаток и строго определить язык логики высказываний.Мы уже договорились, что высказывательныепеременные мы обозначаем латинскими заглавными буквами.Алфавитом языка будет следующий набор: (, ), &, ∨, ⇒, ¬ .Теперь следует определить, что такое формула.