Дискретная математика для инженеров

 
 
 
 
 
 
 
 
 
Г. С. Филиппов 
 
 
 
ДИСКРЕТНАЯ МАТЕМАТИКА 
для инженеров 
 
 
 
Учебное пособие 
 
Под редакцией профессора А. М. Попова 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва    Вологда 
«Инфра-Инженерия» 
2024 
 
1 

УДК 51 
ББК 22.144 
 
Ф53 
 
 
 
 
Рецензенты: 
доктор технических наук, профессор  
С. М. Мужичек (ГосНИИ АС); 
доктор физико-математических наук, профессор 
С. П. Струнков (НИИ системных исследований РАН) 
 
 
 
 
 
 
 
 
 
 
 
 
Филиппов, Г. С. 
Ф53  
Дискретная математика для инженеров : учебное пособие / Г. С. Филиппов ; под редакцией профессора А. М. Попова. – Москва ; Вологда : 
Инфра-Инженерия, 2024. – 160 с. : ил., табл. 
ISBN 978-5-9729-1956-7 
 
Изложены основные разделы дискретной математики в соответствии с дидактическими блоками Госстандарта. Содержит большое количество примеров, поясняющих 
существо рассматриваемых тем. В конце каждого параграфа приводятся вопросы для 
самоконтроля, а также задачи для самостоятельного решения. 
Для студентов и аспирантов высших учебных заведений, обучающихся по направлениям подготовки 15.03.01, 15.04.01 «Машиностроение»; 15.03.06 «Мехатроника 
и робототехника»; 15.03.03 «Прикладная механика». 
 
УДК 51 
ББК 22.144 
 
 
 
 
ISBN 978-5-9729-1956-7 
© Филиппов Г. С., 2024 
 
© Издательство «Инфра-Инженерия», 2024 
 
© Оформление. Издательство «Инфра-Инженерия», 2024 
 
 
2 

ОГЛАВЛЕНИЕ 
 
Предисловие 
................................................................................................................. 4 
Введение ....................................................................................................................... 5 
Глава 1. Высказывания ........................................................................................... 8 
1.1. Логические операции и их таблицы истинности .............................................. 8 
1.2. Формулы логики высказываний ....................................................................... 10 
1.3. Равносильность формул. Законы логики высказываний ............................... 13 
1.4. Аксиоматический метод. Исчисление высказываний .................................... 17 
1.5. Нормальные формы формул логики высказываний 
....................................... 19 
Глава 2. Булева алгебра ......................................................................................... 26 
2.1. Понятие булевой функции ................................................................................ 26 
2.2. Равенство функций. Основные законы булевой алгебры .............................. 29 
2.3. Нормальные формы ........................................................................................... 32 
Глава 3. Теория графов 
.......................................................................................... 36 
3.1. Основные понятия теории графов 
.................................................................... 36 
3.2. Матрицы графов ................................................................................................. 41 
3.3. Деревья ................................................................................................................ 44 
3.4. Алгоритм Фалкерсона 
........................................................................................ 52 
3.5. Приложения теории графов к решению задач ................................................ 54 
3.5.1. Задача о кратчайшем маршруте на графе 
................................................... 54 
3.5.2. Задача о графе наименьшей длины ............................................................. 59 
Глава 4. Элементы сетевого планирования и управления 
............................. 63 
4.1. Сетевой график и его параметры 
...................................................................... 63 
4.2. Правила построения сетевого графика ............................................................ 65 
4.3. Расчет параметров сетевого графика ............................................................... 68 
4.4. Линейный график и способы его построения ................................................. 72 
4.5. Приложения сетевого планирования к решению задач ................................. 78 
4.5.1. Упорядочение сетевого графика 
.................................................................. 78 
4.5.2. Задача о наибольшем потоке в транспортной сети ................................... 80 
Глава 5. Элементы комбинаторики 
..................................................................... 88 
5.1. Соединения ......................................................................................................... 88 
5.2. Бином Ньютона (полиномиальная формула) .................................................. 92 
Глава 6. Элементы теории нечетких множеств ................................................ 96 
6.1. Нечеткие понятия ............................................................................................... 96 
6.2. Операции над нечеткими множествами .......................................................... 98 
6.3. Матрица инциденций и нечеткие матрицы ................................................... 102 
6.4. Многокритериальный выбор альтернатив принятия решений ................... 105 
6.5. Приложения теории нечетких множеств к решению задач 
......................... 106 
6.6. Метод экспертных оценок 
............................................................................... 114 
Приложения 
............................................................................................................ 120 
Литература 
.............................................................................................................. 163 
 
 
 
3 

ПРЕДИСЛОВИЕ 
 
Учебное пособие предназначено для студентов вузов всех форм обучения. Основной причиной его появления является отсутствие на настоящее время полного и систематического изложения основных разделов дискретной математики по дисциплине «Математика» в соответствии с требованиями Государственного образовательного стандарта.  
Книга написана на основе многолетнего опыта чтения лекций в вузах. В 
соответствии дидактическими блоками Государственного образовательного 
стандарта состоит из шести глав: «Высказывания», «Булева алгебра», «Теория 
графов», «Элементы сетевого планирования и управления», «Элементы комбинаторики» и «Элементы теории нечетких множеств». Пособие содержит большое количество примеров, поясняющих существо рассматриваемых тем. В 
конце каждого параграфа приводятся вопросы для самоконтроля, а также задачи для самостоятельного решения. 
Нумерация формул, рисунков и таблиц произведена отдельно по частям 
книги: первая цифра означает номер параграфа, вторая – номер рисунка или 
таблицы в параграфе. Начало и окончание примера отмечено значком Ź. Авторы пособия стремились в минимальном объеме на доступном уровне изложить 
все разделы дидактических блоков Госстандарта без использования сложных 
формул и трактовок.  
При изложении основного содержания главы 4 были использованы материалы профессора А. И. Буравлева из учебного пособия «Основы теории систем и системного анализа». – М.: ИНЭП, 2005 с соответствующими правками. 
Для углубленного изучения отдельных тем содержания книги приводится 
список литературы. В конце книги оформлен в виде приложений справочный 
материал по математическим формулам. 
Авторы считают приятным долгом поблагодарить рецензентов:  доктора 
технических наук, профессора С. М. Мужичека (ГосНИИ АС), доктора физикоматематических наук, профессора С. П. Стрункова (НИИ системных исследований РАН), взявших на себя нелегкий труд рецензирование рукописи книги, а 
также Л. Н. Марданову (литературное редактирование и корректура), Р. Н. Петренко (верстка) за их внимание и творческую работу по подготовке пособия к 
изданию. 
 
 
 
 
 
 
 
 
 
 
 
4 

ВВЕДЕНИЕ 
 
Математика (в переводе с греческого μανημα – учение, наука, учусь через размышление) – это наука о количественных отношениях и пространственных формах действительного мира. Более просто математику можно охарактеризовать как науку о числах и фигурах. 
С глубокой древности, по мере развития человеческого общества, накапливалось все больше сведений о числах, размерах и формах различных предметов. Появилась необходимость приводить эти сведения в порядок, чтобы их 
легче было передавать от одного поколения к другому. Так постепенно зарождалась математика. 
Зачатки математических знаний обнаруживаются уже примерно за четыре 
тысячи лет до нашего времени. Об этом свидетельствуют дошедшие до нас 
египетские папирусы, клинописные вавилонские таблички, в которых встречаются решения различных арифметических, алгебраических и геометрических 
задач.  
Большого расцвета достигла математика в Древней Греции. Более чем за 
300 лет до нашей эры там появились «Начала» Евклида – сочинение, в котором 
систематически излагалась геометрия примерно в том объеме, в котором она 
ныне изучается в средней школе, а также давались сведения о делимости чисел 
и о решении квадратных уравнений.  
В III веке до н. э. Архимед нашел способ определения площадей, объемов 
и центров тяжести различных простых фигур. В конце III века до н. э. Аполлоний написал книгу о свойствах некоторых замечательных кривых – эллипса, 
гиперболы и параболы. Если к этому добавить, что во II веке до н. э. Птолемей 
изложил основы тригонометрии и дал таблицы синусов, то станет ясным, какой 
вклад в развитие математических знаний внесли древние греки. 
Далее математика развивалась трудами китайских, индийских, арабских 
ученых. Особенно большой вклад был внесен ими в развитие алгебры. В Западной Европе во времена средневековья наступил длительный застой в развитии 
науки, из-за чего европейским ученым пришлось потратить немало усилий, 
чтобы усвоить труды их предшественников. Лишь после этого они смогли двигаться вперед самостоятельно. Расцвет математики в Европе начался с XVII века. В это время зародились новые отрасли математики, которые теперь принято 
относить к высшей математике. 
Основу высшей математики составляют аналитическая геометрия, дифференциальное и интегральное исчисление. Их создание связано с именами великих ученых XVII века Р. Декарта, И. Ньютона, Г. Лейбница, Л. Эйлера, 
Ж. Лагранжа, К. Гаусса, О. Коши и многих других. Это позволило теоретически 
изучать движение, процессы изменения величин и геометрических фигур. Вместе с этим в математику вошли координаты, переменные величины и понятие 
функции.  
Изучение функции приводит к основным понятиям математического анализа: пределу, производной, дифференциалу, интегралу. Возникновение анали5 

тической геометрии позволило существенно расширить предмет изучения геометрии благодаря переводу ее на язык алгебры и анализа. С другой стороны, 
открылась возможность геометрической интерпретации алгебраических и аналитических фактов. 
С XVII века начинается развитие очень важного раздела математики – 
теории вероятностей. В ее основе лежали труды таких выдающихся математиков, как Б. Паскаль, П. Ферма, Х. Гюйгенс. При этом первые вклады в теорию 
вероятностей были сделаны в связи с изучением азартных игр. Однако уже в 
конце XVII века начали пользоваться теорией вероятностей при страховании 
кораблей от случайностей.  
В XVIII веке для развития теории вероятностей много сделали швейцарец 
Я. Бернулли, французы С. Лаплас и С. Пуассон, «король математиков» немецкий ученый К. Гаусс. В середине XIX века большой сдвиг произвели труды 
знаменитого русского математика П. Чебышева. Он нашел новые методы решения ранее поставленных задач и сумел создать вокруг себя большую группу 
молодых ученых; некоторые из них, например, А. Марков, А. Ляпунов, впоследствии достигли мировой известности. Также нужно отметить большой 
вклад в теорию вероятностей российского ученого А. Колмогорова. 
Невозможно проследить здесь, хотя бы и бегло, успехи математики за последние столетия. Новые теории в ней возникают теперь не только в результате 
запросов других наук, но и вследствие внутренней потребности самой математики. Замечательным примером такой теории является сферическая геометрия, 
созданная российским ученым Н. Лобачевским. 
Таким образом, историю математики кратко (по предложению академика 
Колмогорова А. Н.) можно условно разделить на четыре периода: 
1. Период зарождения (IV в. до н. э.). 
Появление у Вавилонян методов решения квадратных уравнений, теорема 
Пифагора, измерение земельных участков, составление календарей, проектирование строительства и т. д. К сожалению, теоретические разработки этого периода до нашего времени не дошли. 
2. Период элементарной математики (VI в. до н. э. – XVI в. н. э.). 
Математика рассматривается древними греками как средство познания 
природы. Пифагорейцы усматривали сущность вещей и явлений в числах и 
числовых отношениях. Начало дедуктивного и аксиоматического метода. 
Дедуктивная теория Аристотеля (384–322 гг. до н. э.). Первое изложение 
геометрии Евклида (около 300 лет до н. э.). Геометрическая система в виде 
«Начала» свыше ХХ веков до XIX в. являлась образцом логического метода. 
Развитие в работах Паша (1882 г.), Пеано (1889 г.), Пиери (1889 г.). 
3. Период создания математики переменных величин (XVI–XVIII вв.); 
– переменные величины в аналитической геометрии Р. Декарта  
(1596–1650 гг.); 
– дифференциальное и интегральное исчисление в трудах И. Ньютона 
(1642–1727 гг.) и Г. Лейбница (1646–1716 гг.); 
– теория действительных чисел. 
 
6 

4. Современная математика (XVIII в. – до наших дней): 
– неевклидова геометрия Н. Лобачевского (1792–1856 гг.); 
– развитие аксиоматических методов в работах Д. Гильберта (1862–1943 гг.), 
А. Пуанкаре (1854–1912 гг.) и т. д. 
– комплексные числа, кватернионы У. Гамильтона (1805–1865 гг.), О. Хевисайда (1850–1925 гг.). 
Потребности развития самой математики, «математизация» других областей науки, проникновение математических методов во многие сферы практической деятельности, прогресс вычислительной техники привели к появлению 
новых математических дисциплин, например, исследования операций, теории 
игр и др. 
 
Роль математики в системе фундаментальной подготовки  
современного инженера 
 
Какими качествами и знаниями должен обладать инженер? Прежде всего – способностью к аналитической работе, умением сортировать информацию и классифицировать различные факты. Поэтому ему не обойтись без отличного знания математики. На всех факультетах высших учебных заведений 
изучению этого предмета уделяется особое внимание. «Корпеть» над формулами и задачами студентам вузов приходится вплоть до окончания вуза. 
Техническим наукам нужно учиться, как хорошему инженеру. Прогноз в 
технике немыслим без знаний и умения применять математические модели. В 
свою очередь, модели невозможно успешно освоить без математики – азбуки 
этих моделей. 
Поэтому математическое образование является важнейшей составляющей 
в системе фундаментальной подготовки современного инженера. Математика 
для него является не только мощным средством решения прикладных задач, но 
и элементом общей культуры. 
Профессиональный уровень инженера во многом зависит от того, освоил 
ли он современный математический аппарат и умеет ли использовать его при 
анализе сложных технических процессов и принятии решений. Таким образом, 
в подготовке инженеров изучение математики играет важную роль. 
 
 
 
 
 
 
 
 
 
 
 
 
7 

Глава 1 
 
ВЫСКАЗЫВАНИЯ 
 
1.1. Логические операции и их таблицы истинности 
 
Математическая логика – наука, которая изучает умозаключения с точки 
зрения их формального строения. Базовым понятием здесь является высказывание. 
Высказывание – связное повествовательное предложение, которое истинно или ложно. Высказывание не может быть истинным и ложным одновременно. Не всякое предложение может быть истинным или ложным, т. е. не любое 
предложение может быть высказыванием. 
 
Ź Пример 1.1. 
A. «Число π является иррациональным». 
B. «Неверно, что число π является иррациональным». 
C. «Число π + 1 является иррациональным». 
D. «Если число π является иррациональным, то число π + 1 также является иррациональным». 
E. «Который час?» 
F. «Идите решать задачу к доске». 
G. «Площадь отрезка меньше длины куба». 
Примеры E и F не являются высказываниями, поскольку один из них является вопросительным предложением, другой – повелительным. Повествовательное предложение G не является высказыванием, так как нельзя сказать, истинно оно или ложно, из-за отсутствия в нем смысла. Первые четыре предложения являются высказываниями. Высказывания A, C и D истинны, высказывание B – ложно. Ź 
 
Истинное высказывание имеет логическое значение «истина», а ложное 
высказывание имеет логическое значение «ложь». 
В дальнейшем «истину» будем обозначать цифрой 1, а «ложь» – цифрой 0. 
Проанализируем высказывания A–D в примере с точки зрения их «внутреннего строения». Высказывания А и C можно назвать простыми. Высказывания B и D являются сложными. Действительно, высказывание B получено из 
простого высказывания А с помощью стандартной конструкции русского языка 
«неверно, что…». Высказывание D получено из высказываний A и C с помощью конструкции «если…, то…». Этот простой пример показывает, что в языке 
(русском и любом другом) существуют способы построения одних высказываний из других. Математическая логика изучает способ образования одних высказываний из других с помощью логических операций. 
8 

Логической операцией называется построение из данных высказываний 
нового высказывания. Знаки логических операций называются логическими 
связками.  
Пусть А и В – произвольные высказывания. Рассмотрим пять логических 
операций, сведенных в табл. 1.1, которые являются основными в математической логике. В этих операциях интересует не содержательный смысл высказывания, а только его логическое значение: «истина» или «ложь». Поэтому логические операции рассматриваются как средство вычисления логического значения сложного высказывания по логическим значениям составляющих его простых высказываний. 
 
Таблица 1.1 
Основные логические операции 
Обозначение 
операции 
Название  
операции 
Прочтение  
полученного высказывания 
А 
Отрицание 
«не А» или «неверно, что А» 
A
B
∧
 
Конъюнкция 
«A и B» 
A
B
∨
 
Дизъюнкция 
«A или B» 
A ≡ B 
Эквивалентность 
«A тогда и только тогда, когда B», 
«A эквивалентно B», «A равносильно B» 
A → B 
Импликация 
«если A, то B», «A влечет B» 
 
Табл. 1.2 показывает, какие логические значения принимают высказывания, полученные с помощью пяти основных логических операций, на всевозможных наборах A и B значений 1 или 0. Такая таблица называется таблицей 
истинности.  
Таблица 1.2 
Таблица истинности для основных логических операций 
A 
B 
А 
A
B
∧
 
A
B
∨
 
A ≡ B 
A → B 
0 
0 
1 
0 
0 
1 
1 
0 
1 
1 
0 
1 
0 
1 
1 
0 
0 
0 
1 
0 
0 
1 
1 
0 
1 
1 
1 
1 
 
Прокомментируем смысл введенных логических операций, их обозначения и таблицы истинности. 
Отрицание – это логическая операция, применяемая к сложному или 
простому высказыванию. Высказывание А истинно, когда ложно А, и ложно, 
когда истинно А. Отрицание может также обозначатся 
А
¬
. 
9 

Четыре других логических операции являются бинарными, т. е. применяются к двум высказываниям. 
Конъюнкция, или логическое умножение, соответствует союзу «и» в русском языке. Высказывание A
B
∧
 истинно, когда оба высказывания A и B в логической операции истинны, и ложно во всех остальных случаях. Конъюнкция 
может обозначаться также A & B или просто AB. 
Дизъюнкция, или логическое сложение, соответствует союзу «или». Высказывание A
B
∨
 истинно, когда хотя бы одно из высказываний истинно; ложно, когда ложны оба высказывания A, B. Дизъюнкция может обозначаться также A + B. 
Эквивалентность, или равносильность высказываний, истинна тогда и 
только тогда, когда образующие ее высказывания A, B имеют одинаковые логические значения, т. е. оба истинны или оба ложны. Кроме A ≡ B, для обозначения эквивалентности используются также символы A ↔ B, A ∼ B, A ⇔ B. 
Импликация соответствует конструкциям «если…, то…», «из… следует…». Высказывания, образующие импликацию A → B, имеют специальные 
названия: A – посылка, B – заключение. Импликация ложна тогда и только тогда, когда ее посылка A истинна, а ее заключение B ложно. Это свойство импликации часто формулируют в виде принципа «из истины не может следовать 
ложь». Строки табл. 1.2 позволяют сформулировать в виде принципов еще два 
свойства импликации: «из ложного утверждения может следовать все что угодно» (см. первую и вторую строки), «истинное утверждение может следовать из 
чего угодно» (см. вторую и четвертую строки). 
С импликацией A → B связывают еще три импликации: В → А, А
В
→
, 
В
А
→
. Первую из них называют обратной к импликации A → B, вторую – противоположной, а третью – обратно-противоположной. 
Заметим, что в обычном языке в предложении вида «Если A, то B» высказывания A и B связаны друг с другом по контексту. В определении импликации 
это совершенно необязательно. Может существовать импликация вида «Если 
сегодня четверг, то дважды два равно пяти», которая (поскольку ее заключение 
ложно) будет истинна во все дни, кроме четверга, а в четверг – ложна. 
Как будет показано ниже, перечисленные выше операции могут быть 
применимы к произвольному количеству высказываний. 
 
1.2. Формулы логики высказываний 
 
Для изучения высказываний математическими средствами используется 
понятие формулы логики высказываний. Дадим соответствующие определения. 
Логическими константами будем называть символ истины 1 и символ 
лжи 0. 
Логическими переменными будем называть буквы с индексами и без них. 
Логическим значением логических переменных может быть как истина, так и 
ложь. 
Например, логическими переменными могут быть А, В, Y, Z, xk, En, ui и т. п. 
Логические переменные – символы, которые обозначают высказывания. 
10