Математическая логика и теория алгоритмов

Купить бумажную книгу и читать

Название: Математическая логика и теория алгоритмов

Автор: Судоплатов С.В., Овчинникова Б.В.

Издательство: М.: Инфра-М; Новосибирск: Изд-во НГТУ

Год: 2004

Страниц: 224

ISBN: 5-16-001975-8, 5-7782-0458-2

Формат: PDF

Размер: 20.4 Мб

Язык: русский

В книге излагаются основные исчисления математической логики: исчисления высказываний и исчисления предикатов; основы теории моделей и теории алгоритмов, а также элементы неклассических логик.

Для студентов младших курсов технических вузов, изучающих математическую логику и теорию алгоритмов.

Оглавление

Предисловие

Введение

Исчисление высказываний

Определение формальногo исчисления

Исчисление высказываний генценовскоro типа

Эквивалентность формул

Нормальные формы

Семантика исчислении секвенций

Исчисление высказываний гильбертовского типа

Алгоритмы проверки общезначимости и противоречивости в ИB

Логические задачи

Задачи и упражнения

Логика и исчисления предикатов

Формулы сигнатуры ?. Истинность формулы на aлгебраической системе

Секвенциальное исчисление предикатов

Эквивалентность формул в ИПС?

Нормальные формы

Теорема о существовании модели

Исчисление предикатов гильбертовского типа

Скулемизация алгебраических систем

Meтoд резолюций в исчислении предикатов

Логические программы

Задачи и упражнении

Элементы теории моделей

Элементарная эквивалентность. Teopeмы Лёвенгейма-Скулема

Элементарные теории

Типы. Основные классы моделей

Категоричность. Спектры моделей полных теорий

Система аксиом арифметики Пеано

Нестандартные модели арифметики

Задачи и упражнения

Элементы теории алгоритмов

Машины Тьюринга

Рекурсивные функции и отношении

Эквивалентность моделей алгоритмов

Универсальныe частично рекурсивные фyнкции. Теорема Райса

Рекурсивно пepeчислимые отношения

Неразрешимость исчисления предикатов. Теорема Гёделя о неполноте. Разрешимые и неразрешимые теории.

Xapaктepистики сложности aлгoритмов

Переборные задачи

Aлгоpитмы сортировки

Конечные автоматы

Задачи и упражнения

Нeклaccичecкие логики

Пропозициональные логики

Предикатные лoгики

Предикатные временные логики и их приложение к программированию

Aлгоpитмичecкиe логики

Список литeратуры

Предметный указатель