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

 

 

Министерство образования и науки Российской Федерации 

 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ 

И РАДИОЭЛЕКТРОНИКИ (ТУСУР) 

 

ФАКУЛЬТЕТ ДИСТАНЦИОННОГО ОБУЧЕНИЯ (ФДО) 

 
 
 

Т. О. Перемитина 

 
 

 

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

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

 

 
 
 
 
 

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

 
 
 
 
 
 
 
 

Томск 
2016

 

 

УДК
510.6 + 510.51

ББК
22.12я73
П 270
 

Рецензенты: 

Т. А. Ципилева,  канд. техн. наук, доцент кафедры автоматизации  

обработки информации ТУСУР; 

О. С. Токарева, канд. техн. наук, доцент кафедры вычислительной  

техники Института кибернетики Томского политехнического университета 

 

Перемитина Т. О. 

П 270
Математическая логика и теория алгоритмов : учебное пособие / 
Т. О. Перемитина. – Томск : ФДО, ТУСУР, 2016. –132 с.

 

В учебном пособии представлены разделы, традиционно изучаемые 

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

 

 
 
 
 
 

 
 
 
 

© Перемитина Т. О., 2016 
© Оформление. 

ФДО, ТУСУР, 2016 

ОГЛАВЛЕНИЕ 

Введение ................................................................................................................ 4 
1 Алгебра высказываний ................................................................................... 6 

1.1 Аксиоматический метод в математике ..................................................... 6 
1.2 Краткие сведения из истории ..................................................................... 7 
1.3 Высказывания и логические операции ................................................... 10 
1.4 Формулы алгебры высказываний ............................................................ 18 
1.5 Логическая равносильность формул ....................................................... 22 
1.6 Нормальные формы записи формул алгебры высказываний ............... 26 
1.7 Логическое следование формул .............................................................. 33 

2 Булевы функции ............................................................................................. 46 

2.1 Введение в булеву алгебру ....................................................................... 46 
2.2 Способы задания булевых функций ....................................................... 47 
2.3 Реализация булевых функций формулами ............................................. 51 
2.4 Минимизация булевых функций ............................................................. 55 
2.5 Представление булевых функций полиномами Жегалкина ................. 62 
2.6 Функциональная полнота системы булевых функций .......................... 65 
2.7 Практическое применение булевых функций ........................................ 74 

3 Логика предикатов ........................................................................................ 81 

3.1 Основные понятия логики предикатов ................................................... 81 
3.2 Логические операции над предикатами .................................................. 85 
3.3 Кванторные операции ............................................................................... 88 
3.4 Формулы логики предикатов ................................................................... 92 
3.5 Равносильные формулы логики предикатов .......................................... 97 
3.6 Нормальная форма записи формул логики предикатов ........................ 99 

4 Теория алгоритмов ...................................................................................... 106 

4.1 Характерные черты алгоритма .............................................................. 106 
4.2 Машины Тьюринга ................................................................................. 108 
4.3 Рекурсивные функции ............................................................................ 116 
4.4 Нормальные алгоритмы Маркова.......................................................... 121 
4.5 Классы сложности ................................................................................... 124 

Заключение ....................................................................................................... 129 
Литература........................................................................................................ 130 
Глоссарий .......................................................................................................... 131 

 
 

Введение 

 
В научном познании, практической деятельности и повседневной жизни 

нам постоянно приходится убеждать своих собеседников и оппонентов в правильности и обоснованности своих утверждений, гипотез и мнений. Хотя 
на убеждение людей могут влиять также их эмоции, настроения, склонности 
и даже предубеждения, все же наибольшей убедительностью обладают доводы, 
опирающиеся на разум и факты [4].  

Логике принадлежит центральная роль в обосновании правильности 

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

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

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

 

 ································ ·····························   

Эта пиктограмма означает определение или новое понятие. 

 ································ ·····························   

································ ·····························   

Эта пиктограмма означает «Внимание». Здесь выделена важ
ная информация, требующая акцента на ней. Автор может поделиться с читателем опытом, чтобы помочь избежать некоторых 
ошибок. 
 ································ ·····························   
 ································ ·····························   

Эта пиктограмма означает теорему.  

 ································ ·····························   
 ································ ·····························   

Эта пиктограмма означает лемму.  

 ································ ·····························   

 ························   
 Пример  ··························   

Эта пиктограмма означает пример. В данном блоке автор может привести 

практический пример для пояснения и разбора основных моментов, отраженных в теоретическом материале. 
 ································ ································ ·······  

 ·························································  

Контрольные вопросы по главе  

 ·························································  

 

 
 

1 Алгебра высказываний  

 
1.1 Аксиоматический метод в математике 

 ································ ·····························   

Аксиома – основное положение рассматриваемой теории, 

принимаемое без доказательств. 
 ································ ·····························   

Аксиома является истинным исходным положением теории. Такой способ 

построения научной теории в виде системы аксиом (постулатов) и правил вывода (аксиоматики) позволяет путем дедукции, т. е. по правилам логики, получать утверждения данной теории.  

Аксиоматический метод не является достижением двадцатого столетия 

[5]. В начале XX в. благодаря главным образом работам немецкого математика 
Д. Гильберта (1862–1943) окончательно сформировались принципиальные положения данного метода и было осознано его значение для математики. Первые 
идеи, связанные с этим методом, восходят к титанам античной мысли Платону 
и Аристотелю (IV в. до н. э.). Внутри математической науки взгляд на аксиомы 
претерпевал самые решительные изменения. Процесс шел постепенно, но качественный скачок в нем произошел после того, как в 20–30-е гг. XIX в. великим 
русским математиком Н. И. Лобачевским (1792–1856) и независимо от него молодым венгром Яношем Бояи (1802–1860), а также великим немецким ученым 
К. Ф. Гауссом (1777–1855) были внесены изменения в представления о природе 
пространства, т. е. возникаkf неевклидова геометрия. Суть открытия состояла в 
том, что вместо пятого постулата Евклида о параллельных в систему аксиом 
было включено утверждение, являющееся его отрицанием, и затем на базе полученной системы аксиом была построена непротиворечивая геометрическая 
теория, названная Н. И. Лобачевским «воображаемой геометрией».  

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

Такое развитие взглядов на природу аксиом и аксиоматический метод 

привело к следующей концепции аксиоматической теории. Выбирается ряд 

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

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

распространение аксиоматического метода в построении различных математических теорий, в первую очередь геометрии, а затем арифметики, теории групп 
и т. д. [15].  

 ································ ·····························   

Аксиоматическая система – совокупность основных и про
изводных понятий, аксиом и теорем. 
 ································ ·····························   

 К системе аксиом предъявляется одно главное требование – она должна 

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

 

1.2 Краткие сведения из истории 

Возникновение логики как науки имело две предпосылки. Во-первых, это 

зарождение и первоначальное развитие наук. Этот процесс получает развитие 
в Древней Греции с VI в. до н. э. Зарождение науки требовало исследования 
природы мышления как средства познания. Во-вторых, возникновение логики 
было связано с развитием ораторского искусства. Логика должна была объяснить, как должна строиться речь и какими свойствами она должна обладать. 
Поэтому неслучайно, что именно Греция стала родиной такой науки, как логика. Основателем логики принято считать древнегреческого философа Аристотеля, который изложил свои идеи в работе «Органон». Согласно Аристотелю, 
«мышление – это не конструирование или создание умом некой новой сущно

сти, но, скорее, уподобление в акте мышления чему-то, находящемуся 
вовне» [5]. 

Классическая логика Аристотеля – суждение истинное, если соответству
ет действительности (фактам). Логика как наука в трудах Аристотеля связана 
с судебной и политической практикой. 

В Средние века (VI–XIV вв.) логика была в значительной мере подчинена 

богословию. В этот период теоретический поиск в логике развернулся вокруг 
проблемы объяснения общих понятий – универсалий. При этом на всем протяжении Средних веков систематическая разработка формальной логики почти 
не выходила за пределы силлогистики. Основателем арабо язычной логики считается сирийский математик Аль-Фараби. Его логика направлена на анализ 
научного мышления. Аль-Фараби выделял в логике две ступени: одна охватывала представления и понятия, другая – теорию суждений, выводов и доказательств. В эпоху Возрождения логика переживала настоящий кризис. Она расценивалась в качестве логики «искусственного мышления», основанного 
на вере, которому противопоставлялось естественное мышление, базирующееся 
на интуиции и воображении.  

Новый, более высокий этап в развитии логики начинается с XVII в. 

Его начало было связано с появлением работы Ф. Бэкона «Новый Органон». 
В этом труде автор стремился разработать приемы исследования самой природы. Он положил начало созданию механизмов установления причинноследственных связей в объективной реальности. Таким образом, Ф. Бэкон стал 
родоначальником индуктивной логики, в которой нашли отражение процессы 
получения новых общих знаний на основе данных, полученных путем эмпирических исследований. 

Растущие успехи в развитии математики выдвинули две фундаменталь
ные проблемы: применение логики для разработки математических теорий. Попытку решения этих проблем впервые предпринял Готфрид Лейбниц. В 1666 г., 
применив аппарат алгебры, он придал новый импульс логическим исследованиям. 

В XIX в. была создана символическая логика. Символическая логика изу
чает символические абстракции, которые фиксируют формальную структуру 
логического вывода. В алгебраическом духе прогресс периодически возобновлялся, достигнув кульминационных точек в 1847–1877 гг. в работах Дж. Буля, 
О. де Моргана, Ч. С. Пирса и Э. Шредера.  

Дж. Буль предложил логику рассуждений безотносительно к содержанию 

определить символическим языком формальной логики, утверждениям присвоить абстрактные значения True (истина) или False (ложь). Причем следует отметить, что при изучении проблемы взаимодействия логики и алгебры приоритет 
всегда отдавался алгебре. Более того, указанные ученые стремились скорее не 
синтезировать эти науки, а полностью подчинить логику математике.  

И только Г. Фреге в 1879 г. отказался от алгебраических аналогий и раз
работал оригинальный символический и понятийный аппарат, пригодный для 
использования в универсальной и эффективной логической теории. Только 
отойдя от полного подражания алгебре, Г. Фреге выяснил истинную природу 
центрального понятия алгебры и логики – переменной. Обнаружилось родство 
между переменной и неопределенным местоимением.  

Продолжением развития символической логики занимались Б. Рассел 

и А. Н. Уайтхед. Новая логика позволила с большой точностью описать формы 
суждений и отношения между ними. На целый ряд философских вопросов, 
в частности касавшихся природы математики, были сразу даны новые и четкие 
ответы, и стало казаться, что с помощью формальной логики можно будет 
найти окончательное решение философских проблем. В современной науке 
значение символической логики очень велико. Она находит приложение в кибернетике, нейрофизиологии, лингвистике. Символическая логика является современным этапом в развитии формальной логики. Она изучает процессы рассуждения и доказательства посредством его отображения в логических 
системах (исчислениях). Таким образом, по своему предмету эта наука является 
логикой, а по методу – математикой [5] . 

Непосредственным результатом революции, произошедшей в логике 

в конце XIX – начале XX в., было возникновение логической теории, получившей название математическая логика.  

 ································ ·····························   

Математическая логика – естественнонаучная дисциплина, 

изучающая математические доказательства и вопросы оснований 
математики. 
 ································ ·····························   

Характерным для этой дисциплины является использование формальных 

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

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

 

1.3 Высказывания и логические операции 

 ································ ·····························   

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

Основным (неопределяемым) понятием математической логики является 

понятие «высказывание». 

 ································ ·····························   

Высказывание – повествовательное предложение, для кото
рого имеет смысл говорить о его истинности или ложности.  
 ································ ·····························   

Логическими значениями высказываний являются «истина» и «ложь».  
Для формализации работы с высказываниями их обозначают символами 

алфавита, например: А, В, С…, P, Q, R…, X, Y, Z…, и называют логическими переменными. 

 ································ ·····························   

Логическая переменная – это переменная, обозначающая 

любое высказывание, которая может принимать логические значения «истина» или «ложь».  
 ································ ·····························   

Истинные высказывания обозначают символом 1 (Истина, True), а лож
ные – 0 (Ложь, False).