В.Б. Шехтман - Курс лекций по логике и теории алгоритмов (1161807)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетКурс лекций по логикеи теории алгоритмовЛектор — Валентин Борисович ШехтманIV курс, 8 семестр, поток математиковМосква, 2006 г.Оглавление1.2.3.Логика высказываний1.1. Высказывания, формулы и правила вывода . . . . . . . . .
. . . . . . . . . . . .1.1.1. Высказывания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.2. Формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.3. Аксиомы логики высказываний . . . . . . . . . . . . . . . . . . . . . . . .1.1.4. Правило вывода . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .1.2. Корректность и полнота ИВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.1. Теорема корректности . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.2. Отступление об интуиционистской логике . . . . . . . . . . . . . . . . . .1.2.3. Выводимость формулы. Подготовка к доказательству теоремы полноты1.2.4. Путь к теореме полноты . . .
. . . . . . . . . . . . . . . . . . . . . . . . .1.2.5. Семантическая полнота и непротиворечивость теорий . . . . . . . . . . .1.2.6. Доказательство теоремы полноты CL . . . . . . . . . . . . . . . . . . . .1.3. Интуиционистская логика . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .Логика предикатов2.1. Построение языка первого порядка . . . . . . . . . . . . . . . . . . . . .2.1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.2. Определения . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .2.1.3. Интерпретация сигнатуры. Модель. Оценки . . . . . . . . . . .2.1.4. Правила логики предикатов . . . . . . . . . . . . . . . . . . . . .2.1.5. Теорема корректности исчисления предикатов . . . . . . . . . .2.1.6. Теорема корректности и теорема непротиворечивостидля теорий первого порядка . . . .
. . . . . . . . . . . . . . . . .2.1.7. Теории с равенством . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Теории Хенкина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.1. Экзистенциальная полнота . . . . . . . . . . . . . . . . . . . . .2.2.2. Свойство Хенкина . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.3. Вложение непротиворечивых теорий в полные теории Хенкина2.3. Существование модели . . . .
. . . . . . . . . . . . . . . . . . . . . . . .2.3.1. Случай теории без равенства . . . . . . . . . . . . . . . . . . . .2.3.2. Случай теории с равенством . . . . . . . . . . . . . . . . . . . . .2.4. Изоморфизм и элементарная эквивалентность интерпретаций . . . . .2.4.1. Определения и основные свойства . . .
. . . . . . . . . . . . . .2.4.2. Сильная категоричность и счётная категоричность . . . . . . ................................................................................................................................................4445566667881010................................................................................................12121212131517................................................................................................................................................................................................181919191919212122232324Теория алгоритмов3.1.
Введение в системы Поста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1.1. Построение и примеры систем Поста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1.2. Подстановки и правила . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252525262ПредисловиеПорядок изложения материала наиболее соответствует курсу 2006 г.Фактических изменений начиная с 27 мая в тексте не было.БлагодарностиОгромное спасибо . . .За поиск лажи выносится благодарность. . . .Обозначения• A @ B — формулы, связанные любой из логических связок ∨, &, →.• Если имеется k различных величин, обозначаемых, скажем, p1 , . .
. , pk , мы будем иногда использоватьсокращенную запись p, подразумевая всё множество {p1 , . . . , pk }.Последняя компиляция: 31 мая 2006 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.Литература[1] Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Начала теории множеств. М.: МЦНМО, 2000.[2] Н. К. Верещагин, А. Шень.
Лекции по математической логике и теории алгоритмов. Языки и исчисления.М.: МЦНМО, 2000.[3] Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Вычислимые функции.М.: МЦНМО, 2000.[4] В. А. Успенский, Н. К. Верещагин, В. Е. Плиско. Вводный курс математической логики. М.: ФИЗМАТЛИТ,20043Введение: математика и компьютерИз лжи следует истина.Народная мудростьВ 30-е годы XX века была создана аксиоматика теории множеств Цермело – Френкеля (ZF).
Когда сталоясно, что все математические доказательства можно записать с помощью формальных значков, а следствияиз набора аксиом получать с помощью достаточно простых алгоритмических операций (которые легко можнопоручить компьютеру), возник вопрос: а нельзя ли всю математику свести к компьютерным доказательствам?Как выяснилось, на этом пути есть большая проблема. Компьютер способен получить миллионы правильных утверждений, но они будут нам совершенно неинтересны (когда мы сами пытаемся доказать теорему, мыуже знаем, что она нам интересна). А задача отделения полезных утверждений от миллионов правильныхутверждений уже не является алгоритмической.Ну ладно, допустим, что для этой цели компьютер (пока) непригоден. Предположим, однако, что мы хотимдоказать какую-то теорему, но пока не умеем этого делать.
Поручим компьютеру это задание, и он рано илипоздно с этой задачей справится. Однако и здесь есть неприятности: мы получим формальный вывод, но он будетстоль длинен, что мы не усвоим ничего полезного из этого доказательства. Хуже того, если теорема всё-такиневерна, то мы никогда этого не узнаем (ибо не существует алгоритма, который по формуле устанавливает,выводима она в данной аксиоматике или нет).Ну хорошо, в таком случае остаётся надежда только на то, что компьютер можно использовать для проверки доказательств, написанных человеком. Это представляется наиболее реалистичным, однако пока не удалосьнайти разумного способа записывать доказательства на языке, понятном одновременно и человеку, и компьютеру.1. Логика высказыванийМы начнём с маленького фрагмента аксиоматической теории, а именно с исчисления высказываний (ИВ).1.1.
Высказывания, формулы и правила вывода1.1.1. ВысказыванияВысказывание относится к одному из неопределяемых понятий и задаётся аксиоматически: это утверждение,которое может быть либо истинно, либо ложно.Пример 1.1.√• «Число 2 3 является иррациональным.» является истинным высказыванием.• «Число x делится на 2.» не является высказыванием в полном смысле этого слова, потому что содержит свободную переменную x. Про него мы не можем сказать, истинно оно или ложно. Это так называемаявысказывательная форма.• «Верно ли, что сегодня очень холодно?» не является высказыванием.Мы не будем интересоваться смыслом самих высказываний, нам будет важно только их истинностное значение.
Мы будем обозначать высказывания латинскими буквами, например, p1 , p2 , . . .. Это так называемыепропозициональные переменные (от англ. proposition — высказывание).Как и в русском языке, из нескольких высказываний можно образовывать более сложные высказывания.Например, можно объединять их союзами «И», «ИЛИ», «НЕ» и так далее. Так и для высказываний существуютлогические связки.Мы будем использовать символ «1» для обозначения того, что данное высказывание истинно, и символ «0»для обозначения ложных высказываний.Если p — высказывание, то через ¬p будем обозначать отрицание этого высказывания. Зададим его таблицей:¬p10p01Для отрицания ещё используется черта сверху: p = ¬p.Определим теперь значения логических связок «И» (называется конъюнкцией и обозначается & или ∧),«ИЛИ» (называется дизъюнкцией и обозначается ∨).
и «ЕСЛИ, ТО» (обозначается «→» и называется импликацией).4p0011q0101p∨q0111p&q0001p→q11011.1.2. ФормулыКонечно, одних только переменных нам будет мало. Мы будем из высказываний с помощью связок и скобокстроить формулы. Определение даётся индуктивно:Определение.• Все высказывательные переменные являются формулами.• Если P и Q — формулы, то (P & Q), (P ∨ Q), (P → Q) являются формулами.• Если P — формула, то ¬P — тоже формула.Пример 1.2. Выражение (¬(P & Q) → R) является формулой, а P & Q — нет, потому что всякая формула,содержащая хотя бы одну конъюнкцию, содержит хотя бы пару скобок, а в этом выражении скобок нет совсем.Замечание. Мы часто будем опускать внешние скобки.
Кроме того, чтобы не писать лишних скобок, частоиспользуется приоритетность выполнения операций: самой сильной является отрицание, затем следует конъюнкция, затем дизъюнкция и лишь потом — импликация.Замечание. На первый взгляд не совсем понятно, почему импликация имеет такую таблицу истинности.Однако рассмотрим такое утверждение: «если x делится на 4, то x делится на 2». Оно истинно при всех значенияхx. Рассмотрим два высказывания: пусть p обозначает высказывание «x делится на 4», а q обозначает «x делитсяна 2». Тогда наше тождественно истинное утверждение записывается как p → q.Рассмотрим различные значения x.
Возьмём x = 4. Для него истинна и левая, и правая часть, стало быть,получается, что 1 → 1 = 1. Теперь возьмём x, равное 2. Для него истинна только правая часть, значит, 0 → 1 = 1.Теперь рассмотрим x = 1. Для него ложна и правая, и левая часть, значит, 0 → 0 = 1. Тем самым мы поняли,что хоть в каком-то смысле импликация определена «логично» и согласуется с интуитивными представлениями.Для полноты картины рассмотрим ложное высказывание «если x делится на 2, то x делится на 4». Подставляяx = 2, получаем, что 1 → 0 = 0, то есть из истины не следует ложь.Замечание.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
