Курс лекций по логике и теории алгоритмов, Шехтман В.Б., 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. Подстановки и правила.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12812 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Книга Белова Елена - 11 книг
Название: Белова Елена - 11 книг Автор: Елена Петровна Белова Формат: FB2 Размер: 14 mb Качество: Отличное Язык: Русский Жанр: Юмористическое фэнтези, Попаданцы Год издания: 2015 Белова Елена Петровна . . .
-
Лысак Сергей - Собрание сочинений (7 книг)
Лысак Сергей Васильевич современный писатель-фантаст родился 20 февраля 1959 года в Ростове На-Дону .Работает моряком торгового флота . Cвои первые книги начал писать находясь в очередном рейде. Первы . . .
-
Рай на заказ (сборник)
Название: Рай на заказ (сборник) Автор: Бернар Вербер Издательство: РИПОЛ Классик Год: 2008 Страниц: 440 Формат: fb2 epub Размер: 1,3 mb ISBN: 978-5-386-01751-4 Впервые на русском языке! Сборник расск . . .
-
Книга Смертельные инвестиции
Название: Смертельные инвестиции Автор: Хьелль Ола Даль Формат: EPUB Размер: 1.09 Mb Качество: Отличное Язык: Русский Жанр: Зарубежные детективы, Зарубежная литература Год издания: 2015 Зверски убита . . .
-
Книга Убийцы Мидаса
Название: Убийцы Мидаса Автор: Питер Аспе Формат: EPUB Размер: 1,15 Mb Качество: Отличное Язык: Русский Жанр: Зарубежные детективы, Зарубежная литература Год издания: 2014 Морозным утром на одной из ц . . .
-
Поднебесная
Название: Поднебесная Автор: Кей Гай Гэвриел Издательство: АСТ Год: 2013 Страниц: 608 Формат: rtf, fb2 Размер: 15,22 мб Качество: хорошее Язык: русский Двадцать лет назад закончилась очередная война м . . .
-
Burda special E576. Мода для невысоких
Название: Burda special. Мода для невысокихИздательство: Aenne Burda Gmbh & Co.Выпуск / Номер / Год: E576 / 2 / 2000Страниц: 49 + выкройкиФормат: PDFРазмер файла: 61,59 MbЯзык: русскийЖурнал для тех, . . .
-
Макс Фрай - Тубурская Игра (Аудиокнига)
Из этой книжки читатель узнает так много тайн и секретов, что даже непонятно, как справится с этим бедная его голова. Но определенно можно сказать одно: это не те знания, от которых бывает много печал . . .
-
Книга "Хроника "Беркута" - 8 книг
Название: "Хроника "Беркута" - 8 книг Автор: Сушинский Богдан Иванович Формат: FB2, RTF Размер: 30 mb Качество: Отличное Язык: Русский Жанр: Военные приключения Год издания: 2015 В Цикле книг писателя . . .
-
Новый солдат 67 - Гранада, 1492 г. Изгнание мавров из Испании
Название: Новый солдат 67 - Гранада, 1492 г. Изгнание мавров из ИспанииАвтор: не указанИздательство: Артемовск: Военно-исторический клуб 'Ветеран'Страниц: 48Формат: pdfРазмер: 47,1 mbКачество: выше . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Курс лекций по логике и теории алгоритмов, Шехтман В.Б., 2006. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.