Министерство Российской Федерации по связи и информатизации

Поволжская государственная академия телекоммуникаций и информатики

И.М.Сергиевская

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

Учебное пособие

Рекомендовано УМО по образованию в области

телекоммуникаций в качестве учебного пособия

для студентов, обучающихся по направлению

подготовки дипломированных специалистов –

654400 (210400) Телекоммуникации

2004

Содержание.

Введение.

Глава 1. Высказывания, формулы, тавтологии.

Отношения логической эквивалентности и логического следствия.

Задачи.

Глава 2. Формальные теории.

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

Построение вывода в логике высказываний.

Задачи.

Глава 4. Метод резолюций в логике высказываний.

Задачи.

Глава 5. Предикаты.

Задачи.

Глава 6. Исчисление предикатов.

Теория равенства.

Формальная арифметика.

Теория частично упорядоченных множеств.

Задачи.

Глава 7. Алгоритмы.

Глава 8. Рекурсивные функции.

Задачи.

Глава 9. Машины Тьюринга.

Операции с машинами Тьюринга.

Принцип двойственности.

Способы композиции машин Тьюринга.

Задачи.

Ответы и указания.

Литература.

Введение.

Логикой называют науку о законах и формах мышления. Формальная логика изучает формы правильных рассуждений. Математическая логика – часть формальной логики – изучает формы рассуждений, принятые в математике.

В настоящее время значение математической логики в инженерном образовании возрастает в связи с необходимостью развития математического мышления, а также изучения дискретной или компьютерной математики. Математическая логика и теория алгоритмов являются основой курса дискретной математики, что нашло отражение в данном учебном пособии.

Учебное пособие адресовано студентам, обучающимся по направлениям 210300 – радиотехника, 230000 – информатика и вычислительная техника, и по специальностям: 210401 – физика и техника оптической связи, 210402 – средства связи с подвижными объектами, 210403 – защищенные системы связи, 210404 – многоканальные телекоммуникационные системы, 210405 – радиосвязь, радиовещание и телевидение, 210406 – сети связи и системы коммутации, и полностью соответствует действующему Государственному образовательному стандарту высшего профессионального образования и требованиям квалификационной характеристики выпускника. Теоретическая часть пособия основана на лекциях, читанных автором в Поволжской государственной академии телекоммуникаций и информатики.

Сейчас издается достаточно большое количество учебной литературы по дискретной математике. В этой литературе (в особенности, [3], [12], [14]) уделяется внимание и математической логике, и теории алгоритмов. Тем не менее, и указанные пособия, и задачники, в частности, [2] и [6], ориентированы все же на математиков, а не на студентов инженерных специальностей (исключениями являются, пожалуй, только [1], [8], [13], на идеях которых основывался автор). Поэтому в настоящем пособии приведено достаточно много задач, причем решения многих задач подробно разобраны.

Предполагается, что студент, начинающий работу с данным учебным пособием, знаком с основными понятиями теории множеств и отношений, а также с аппаратом булевых функций.

Автор выражает благодарность рецензентам – доктору технических наук, профессору В.К.Трофимову и доктору физико-математических наук, профессору В.Е.Воскресенскому, а также доцентам Самарского государственного университета Е.Я.Гореловой, И.С.Фролову и И.А.Шведовой за содержательные консультации и внимание к работе.

В Содержание.