Математическая логика и теория алгоритмов [Г. И. Анкудинов] (pdf) читать постранично

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение
высшего профессионального образования
СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Г.И.Анкудинов
И.Г.Анкудинов
О.А.Петухов

МАТЕМАТИЧЕСКАЯ
ЛОГИКА И ТЕОРИЯ
АЛГОРИТМОВ
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
ИЗДАНИЕ ВТОРОЕ

Санкт-Петербург
2003

85

УДК 512
Анкудинов
Г.И.,
Анкудинов
И.Г.,
Петухов
О.А.
Математическая логика и теория алгоритмов: Учеб. пособие.–
2-е изд. − СПб.: СЗТУ, 2003, 104 c.
Учебное пособие соответствует государственному образовательному
стандарту дисциплины “Математическая логика и теория алгоритмов”
направления подготовки дипломированных специалистов 654600 –
“Информатика и вычислительная техника” (Специальность 220100 –
“Вычислительные машины, комплексы, системы и сети”) и направления
подготовки бакалавров 552800 – “Информатика и вычислительная техника”.
В пособии излагаются разделы математической логики и теории
алгоритмов, необходимые для освоения общепрофессиональных и
специальных дисциплин специальности 220100. Достаточно подробно
изложены основы логики высказываний и логики предикатов, включая
приложение логики предикатов к доказательству правильности алгоритмов.
Пособие содержит вводный материал по логическому программированию и
клаузальной логике, а также основные понятия нечеткой и модальной логики.
Приведены основы теории алгоритмов и алгоритмической разрешимости,
доказательство эквивалентности моделей алгоритмов Тьюринга и рекурсивных
схем Клини. Пособие содержит также введение в теорию эффективной
вычислимости, переборных NP-полных и NP-трудных задач.
Во втором издании исправлены опечатки и неточности.
Рецензенты:
кафедра процессов управления и информационных систем СевероЗападного
государственного
заочного
технического
университета
(зав.кафедрой О.И.Золотов, канд.техн.наук, доц., А.Б.Шадрин, д-р техн.наук,
проф.);
В.В.Лохмотко, д-р техн.наук, проф., М.О.Колбанев, канд.техн.наук, доц.
(кафедра
информационных
управляющих
систем
Государственного
университета телекоммуникаций им. проф. М.А.Бонч-Бруевича).

© Северо-Западный государственный заочный технический университет, 2003
© Анкудинов Г.И., Анкудинов И.Г., Петухов О.А., 2003

86

Глава 1
ЛОГИКА ВЫСКАЗЫВАНИЙ
В основе стандартной (классической) логики лежит логика
высказываний (пропозициональная логика) и логика предикатов.
Высказывание это повествовательное предложение, в отношении
которого имеет смысл утверждение об его истинности или
ложности. Пример истинного высказывания: "Земля вращается
вокруг Солнца". Предикат это повествовательное предложение,
содержащее предметные (индивидные переменные), замена которых
на константные значения превращает рассматриваемое предложение
в высказывание – истинное или ложное.

1.1. Логические операции над высказываниями
Высказывание – это повествовательное предложение,
утверждающее что-то о чем-либо, причем высказывание может быть
истинным либо ложным. Высказывания могут быть простыми и
составными. Составные высказывания образуются из простых с
помощью связок НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКОТОГДА.
В алгебре высказываний все высказывания рассматриваются с
точки зрения их логического значения или истинности. Считается,
что каждое высказывание либо истинно (И), либо ложно (Л).
Высказывание не может быть одновременно истинным и ложным.
Будем обозначать высказывания простыми латинскими буквами
A,B,C,.... Составные высказывания образуются из простых с
помощью логических операций над высказываниями. Перечислим
основные логические операции:
• отрицание,
• конъюнкция,
• дизъюнкция,
• импликация,
• эквивалентность.
87

Отрицание высказывания A образуется с помощью операции
отрицания и в данном тексте будет обозначаться ⎯A или ⎤A (читается:
"неверно, что A" или, короче "не A"). Логическую
Таблица 1.1
функцию,
соответствующую
зависимости
логического значения ⎯A от логического
A
⎯A
значения высказывания A, можно представить с
И
Л
помощью таблицы истинности (табл.1.1): если A
Л
И
истинно, то ⎯A ложно и наоборот.
Конъюнкцией двух высказываний A, B называется новое
высказывание, которое обозначается A&B
Таблица 1.2
(читается "A и B"). Конъюнкция A&B истинна
A B
A&B
тогда и только тогда, когда A и B одновременно
Л Л
Л
истинны, а в остальных случаях ложна (табл.1.2).
Л И
Л
Конъюнкцию также иногда именуют логическим
И Л
Л
произведением.
И И
И
Примечание. Кроме символа & в
литературе используются и другие обозначения конъюнкции: A /\ B,
A*B, AB.
Дизъюнкцией высказываний A и B называется новое
высказывание, которое обозначается A \/ B (читается: "A или B").
Дизъюнкция A\/B ложна