МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
 |
ФГБОУ ВО
“Воронежский государственный УНИВЕРСИТЕТ
ИНЖЕНЕРНЫХ технологиЙ”
Кафедра информационных технологий,
Моделирования и управления
 |
Ю.В. БУГАЕВ, И.Ю. ШУРУПОВА, О.В. АВСЕЕВА
Математическая логика
И теория алгоритмов
ВОРОНЕЖ
УДК 510.6(075.8)
ББК
М-
Научный редактор доцент Л.А. КОРОБОВА
Рекомендуется к размещению
в ЭОС и ЭБ ВГУИТ
Бугаев, Ю.В.
М- Математическая логика и теория алгоритмов [Электронный ресурс]: учеб. пособие / Ю. В. Бугаев, И. Ю. Шурупова, О. В. Авсеева; Воронеж. гос. ун-т инж. технол. – Воронж: ВГУИТ, 2015. – 96 с. – [ЭИ]
ISBN
Учебное пособие разработано в соответствии с требованиями ФГОС ВО подготовки бакалавров направления 09.03.02 – “Информационные системы и технологии”. Излагаются основные разделы математической логики и теории алгоритмов: алгебра высказываний и предикатов, логические исчисления, формальные определения алгоритма, основы теории NP-полноты.
УДК 519.6; 683.1
Без объявл. ББК
ОК2(03) - 2007
ISBN © Бугаев Ю. В., Шурупова И. Ю.,
Авсеева О. В., 2015
© ФГБОУ ВО “Воронеж. гос. ун-т инж. технол.”, 2015
Оригинал-макет данного издания является собственностью Воронежской государственной технологической академии, его репродуцирование (воспроизведение) любым способом без согласия академии запрещается.
ОГЛАВЛЕНИЕ
| Введение | ||
| Глава I. АЛГЕБРА ВЫСКАЗЫВАНИЙ | ||
| Высказывания и операции над ними. Формулы | ||
| Следование, эквивалентность и преобразование формул | ||
| Использование законов логики в доказательстве теорем и построении схем | ||
| Булевы функции | ||
| Нормальные формы | ||
| Полные системы операций и функций. Алгебра Жегалкина | ||
| Выводимость | ||
| Глава II. ЛОГИКА ПРЕДИКАТОВ | ||
| Предикаты. Операции над предикатами | ||
| Модель. Формула алгебры предикатов сигнатуры s | ||
| Формулы алгебры предикатов | ||
| ГЛАВА III. ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ | ||
| Определение формального исчисления | ||
| Исчисление высказываний ИВ | ||
| Отношение эквивалентности в ИВ | ||
| Исчисление секвенций ИС | ||
| Исчисления предикатов ИП (ИПС) | ||
| Прикладные исчисления предикатов | ||
| Автоматическое доказательство теорем | ||
| Метатеория логических исчислений | ||
| ГЛАВА IV. ТЕОРИЯ АЛГОРИТМОВ | ||
| Машины Тьюринга | ||
| Рекурсивные функции | ||
| Временная сложность алгоритма. Классы P и NP | ||
| Полиномиальная сводимость. NP -полные языки и задачи |
Введение
Математическая логика, как и классическая логика, исследует процессы умозаключений и позволяет из истинности одних суждений делать выводы об истинности или ложности других, независимо от их конкретного содержания. Использование в логике математических методов (алгебраизация логики и построение логических исчислений) дало начало развитию новой области математики, называемой «Математической логикой». Основная задача математической логики – формализация знаний и рассуждений. Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, поэтому математическая логика, по существу, – наука о математике.
Математическая логика дала средства для построения логических теорий и вычислительный аппарат для решения задач. Математическая логика и теория алгоритмов нашли широкое применение в различных областях научных исследований и техники (например, в теории автоматов, в лингвистике, в теории релейно-контактных схем, в экономических исследованиях, в вычислительной технике, в информационных системах и др.). Основные понятия математической логики лежат в основе таких ее приложений, как базы данных, экспертные системы, системы логического программирования. Эти же понятия становятся методологической основой описания анализа и моделирования автоматизированных интегрированных производств.
Вопросы, исследуемые математической логикой, могут рассматриваться как средствами семантической (смысловой) теории, в основе которой лежит понятие алгебры, так и формально-аксиоматической (синтаксической) теории, базирующейся на понятии логического исчисления. В данном курсе рассматриваются оба этих подхода, начав с алгебры высказываний, которая затем обобщается алгеброй предикатов, и обе они служат пониманию построения логических исчислений и их частных случаев: исчисления высказываний и исчисления предикатов.
Глава I. АЛГЕБРА ВЫСКАЗЫВАНИЙ
Алгебру высказываний можно рассматривать как переложение на другой (алгебраический) язык результатов, изученных в разделе «Булевы функции», использующем функциональный язык. При функциональном подходе каждой из логических операций и формул сопоставляется определённая двузначная функция. При алгебраическом подходе логические операции интерпретируют как алгебраические, действующие на множестве двух элементов.