В.А. Успенский - Курс лекций по математической логике (1109966)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетКурс лекций поматематической логикеЛектор — Владимир Андреевич Успенский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. Язык логики высказыванийВ предыдущем разделе уже использовались термины «формула», «выражение» и т. п., однако не были даныточные определения. Настало время исправить этот недостаток и строго определить язык логики высказываний.Мы уже договорились, что высказывательныепеременные мы обозначаем латинскими заглавными буквами.Алфавитом языка будет следующий набор: (, ), &, ∨, ⇒, ¬ .Теперь следует определить, что такое формула.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
