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

Московский 
государственный 
горный 
университет 

РЕДАКЦИОННЫЙ 

С
О
В
Е
Т 

Пр ед сед am 
ель 

Л.А. 
ПУЧКОВ 
ректор 
МГГУ, 
чл.-корр. 
РАН 

Зам. 
председателя 

Л.Х. 
ГИТИС 
директор 
Издательства 
МГГУ 

Члены 
редсовета 

И. В. 
ДЕМЕНТЬЕВ 
академик 
РАЕН 

А.П. 
ДМИТРИЕВ 
академик 
РАЕН 

Б.А. 
КАРТОЗИЯ 
академик 
РАЕН 

М.В. 
КУРЛЕНЯ 
академик 
РАН 

В. И. 
ОСИПОВ 
академик 
РАН 

Э.М. 
СОКОЛОВ 
академик 
МАН 
ВШ 

КН. 
ТРУБЕЦКОЙ 
академик 
РАН 

В.В. 
ХРОНИН 
профессор 

В.А. 
ЧАНТУРИЯ 
академик 
РАН 

Е.И. 
ШЕМЯКИН 
академик 
РАН 

Л.М. Гурова 
Е.В. Зайцева 

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

Допущено Учебно-методическим объединением вузов 
по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных 
заведений, обучающихся по направлениям 552800, 654600 
«Информатика и вычислительная техника», специальности 220200 «Автоматизированные системы обработки информации и управления» 

Высшее 

горное 
образование 

А 

МОСКВА 
ИЗДАТЕЛЬСТВО МОСКОВСКОГО 
ГОСУДАРСТВЕННОГО 
ГОРНОГО УНИВЕРСИТЕТА 
2006 

УДК 519.768.681.3 
ББК 22.12 
Г 95 

Книга соответствует «Гигиеническим требованиям к изданиям книжным для 
взрослых. СанПиН 1.2.1253 — 03», утвержденным Главным государственным 
санитарным врачом России 30 марта 2003 г. 

Экспертиза проведена Учебно-методическим 
объединением вузов по университетскому 
и политехническому 
образованию 
(письмо № 16-07/191 от 
15.07.2005 г.) 

Рецензенты: 

• 
академик Международной академии наук информации, информационных 
процессов и технологий, д-р техн. наук А.А. Садердинов 
(ФГУП «Главный 
информационно-вычислительный центр металлургии»); 
• 
кафедра «Автоматизированные системы обработки информации и управления » Московской государственной академии приборостроения и информатики (зав. кафедрой проф., д-р техн. наук ОМ. Петров) 

Гурова Л.М., Зайцева Е.В. 

Г 95 
Математическая логика и теория алгоритмов: Учебное пособие. — 
М.: Издательство Московского государственного горного университета, 2006. —262 с : ил. 

ISBN 5-7418-0451 -9 (918-5-7418-0451 -3) 

Изложен материал основного курса «Математическая логика и теория алгоритмов», читаемого на факультете «Автоматизации и информатики (АИ)» МГГУ: 
основные понятия, относящиеся к семантике формализованных логико-математических языков; математическая логика, исчисление высказываний и предикатов, элементы теории множеств, основы теории моделей и алгоритмов. Показано практическое 
использование алгебры к задачам математической логики. 

Для студентов вузов, обучающихся по направлениям 552800, 654600 «Информатика и вычислительная техника», специальности 220200 «Автоматизированные системы обработки информации и управления». 

УДК 519.768.681.3 
ББК 22.12 

ISBN 5-7418-0451-9 (918-5-7418-0451-3) 
© Л.М. Гурова, 

Е.В. Зайцева, 2006 
© Издательство МГГУ, 2006 
© Дизайн книги. 

Издательство МГГУ, 2006 

ВВЕДЕНИЕ 

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

Предмет современной математической логики разнообразен. 
Это и исследование различных логических исчислений, из которых основным является классическое исчисление высказываний 
и предикатов, и изучение взаимосвязанных синтаксических (информационных) и семантических (реальных) объектов, и разработки в области теории алгоритмов. 

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

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

Теория алгоритмов — раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие 
к образованию понятия «алгоритм», прослеживаются в математике в течение всего времени ее существования. Однако само 

5 

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

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

ФОРМАЛЬНАЯ 
АКСИОМАТИЧЕСКАЯ 
ТЕОРИЯ 

1.1 
— 

ФОРМАЛИЗАЦИЯ МАТЕМАТИЧЕСКИХ 
ТЕОРИЙ 

Формализация 
математических теорий состоит в формализации мыслительных процессов и процессов построения умозаключений, т.е. слияния математической теории и математической логики. 

Понятия формальной аксиоматической теории возникли на 
рубеже XVII — XVIII веков и принадлежат великому математику Готфриду Вильгельму Лейбницу, пожелавшему заменить идеи 
конкретными 
вычислениями 
с использованием специальных символов или знаков. Это была эпоха расцвета аксиоматической 
теории древних греков, идущая от Аристотеля и Евклида, с методологической схемой аксиома — доказательство 
— 
теорема 

— определение 
— доказательство 
— теорема 
— в ы х о д я щей за рамки геометрии и математики и оказавшей влияние на 
новые области философии и естествознания. 

Немецкому философу и математику Г. Лейбницу принадлежит мысль сформулировать правила математического доказательства, чтобы избежать рассуждения о содержательном смысле математических выражений, т.е. создать calculus 
ratiocinator 

— исчисление, в котором естественные содержательные доказательства заменены формальными вычислениями с использованием символики, где представлены аксиомы, теоремы и определения математики. Такая символика была целью лейбницевского языка формул, знаменитой characteristica 
universalis. 

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

9 

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

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

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

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

Вопросы формализации аксиоматических теорий подтверждают работы Дедекинда, Кантора, Буля, Пеано, Пирса, Шредера и других ученых. Высокой степени точности формализация математического языка в рамках современных логических исчислений достигла в работах математиков XX века: Рассела, Гильберта, 
Гёделя, Чёрча, А.А. Маркова, А.И. Мальцева и др. Это было время 

10 

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

Кроме того, XX век — это период начала глубокого проникновения идей и методов математической логики в технику, 
процесс конструирования и создания ЭВМ, программирование, 
кибернетику, вычислительную математику, структурную лингвистику. 

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

1.2. ПОНЯТИЕ ФОРМАЛЬНОЙ 
АКСИОМАТИЧЕСКОЙ ТЕОРИИ 

Определение 1.1. Классические 
формальные 
системы 
математических теорий — это математическая модель, задающая 
множество дискретных объектов путем описания исходных объектов и правил построения новых за счет усовершенствования 
уже построенных ранее. 

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

Любая формальная система, как и философская, основана на 
некоторых постулатах (аксиомах), которых обычно не менее двух. 

11