Курс лекций по логике и теории алгоритмов, Шехтман В.Б., 2006

Курс лекций по логике и теории алгоритмов, Шехтман В.Б., 2006.
 
  В 30-е годы XX века была создана аксиоматика теории множеств Цермело - Френкеля (ZF). Когда стало ясно, что все математические доказательства можно записать с помощью формальных значков, а следствия из набора аксиом получать с помощью достаточно простых алгоритмических операций (которые легко можно поручить компьютеру), возник вопрос: а нельзя ли всю математику свести к компьютерным доказательствам?
Как выяснилось, на этом пути есть большая проблема. Компьютер способен получить миллионы правильных утверждений, но они будут нам совершенно неинтересны (когда мы сами пытаемся доказать теорему, мы уже знаем, что она нам интересна). А задача отделения полезных утверждений от миллионов правильных утверждений уже не является алгоритмической.




Высказывания, формулы и правила вывода.
Высказывания
Высказывание относится к одному из неопределяемых понятий и задаётся аксиоматически: это утверждение, которое может быть либо истинно, либо ложно.

Пример 1.1.
• «Число 2/3 является иррациональным.» является истинным высказыванием.
• «Число х делится на 2.» не является высказыванием в полном смысле этого слова, потому что содержит свободную переменную х. Про него мы не можем сказать, истинно оно или ложно. Это так называемая высказывательная форма.
• «Верно ли, что сегодня очень холодно?» не является высказыванием.

Мы не будем интересоваться смыслом самих высказываний, нам будет важно только их истинностное значение. Мы будем обозначать высказывания латинскими буквами, например, p1, p2, ... . Это так называемые пропозициональные переменные (от англ, proposition — высказывание).

Как и в русском языке, из нескольких высказываний можно образовывать более сложные высказывания. Например, можно объединять их союзами «И», «ИЛИ», «НЕ» и так далее. Так и для высказываний существуют логические связки.
Мы будем использовать символ «1» для обозначения того, что данное высказывание истинно, и символ «0» для обозначения ложных высказываний.

Оглавление
1. Логика высказываний
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. Логика предикатов
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. Сильная категоричность и счётная категоричность
3. Теория алгоритмов
3.1. Введение в системы Поста
3.1.1. Построение и примеры систем Поста
3.1.2. Подстановки и правила.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Курс лекций по логике и теории алгоритмов, Шехтман В.Б., 2006 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск. 




Теги: учебник по математике :: математика :: Шехтман