Дискретная математика: прикладные методы теории множеств, подсчета и представления информации и математической логики

ДИСКРЕТНАЯ МАТЕМАТИКА 
ПРИКЛАДНЫЕ МЕТОДЫ ТЕОРИИ МНОЖЕСТВ, 
ПОДСЧЕТА И ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ 
И МАТЕМАТИЧЕСКОЙ ЛОГИКИ

Н.И. ГДАНСКИЙ

Рекомендовано 
Межрегиональным учебно-методическим советом 
профессионального образования в качестве учебного пособия 
для студентов высших учебных заведений, обучающихся 
по укрупненной группе специальностей и направлений подготовки 
09.03.00 «Информатика и вычислительная техника» 
(квалификация (степень) «бакалавр») (протокол № 5 от 11.05.2022)

Москва
ИНФРА-М
2022

УЧЕБНОЕ ПОСОБИЕ

УДК 510(075.8)
ББК 22.176я73
 
Г26

Р е ц е н з е н т ы:
Ю.П. Кораблин, доктор технических наук, профессор, профессор 
кафедры «Прикладная математика и искусственный интеллект» 
Института информационных и вычислительных технологий Национального исследовательского университета «МЭИ»;
И.Г. Благовещенский, доктор технических наук, профессор, заместитель заведующего кафедрой «Теоретическая механика» Московского 
государственного технического университета им. Н.Э. Баумана (национального исследовательского университета)

ISBN 978-5-16-016956-9 (print)
ISBN 978-5-16-109530-0 (online)
© Гданский Н.И., 2022

Гданский Н.И.
Г26 
 
Дискретная математика: прикладные методы теории множеств, подсчета и представления информации и математической логики : учебное пособие / Н.И. Гданский. — Москва : ИНФРА-М, 2022. — 466 с. — 
(Высшее образование: Бакалавриат). — DOI 10.12737/1414881.

ISBN 978-5-16-016956-9 (print)
ISBN 978-5-16-109530-0 (online)
В учебном пособии излагаются в максимально упрощенной форме основные теоретические положения теории множеств, представления чисел, 
комбинаторики и математической логики, а также способы решения практических задач с помощью их методов. Рассмотрено большое число примеров. Также даны вопросы для самостоятельного контроля уровня знаний 
и задачи для самостоятельного решения.
Соответствует требованиям федеральных государственных образовательных стандартов высшего образования последнего поколения.
Для учащихся бакалавриата и магистратуры по направлению подготовки «Информатика и вычислительная техника», а также студентов других 
направлений, изучающих информационные технологии. Также пособие 
может быть использовано молодыми специалистами из IT-сферы в самостоятельной ликвидации пробелов в тех или иных разделах дискретной 
математики.

УДК 510(075.8)
ББК 22.176я73

Введение

Основным предметом дискретной математики является структура цифровых вычислительных устройств и процессы, реализуемые в них, т.е. искусственная среда, специально созданная человеком для преобразования информации. В этом ее принципиальное 
отличие от традиционной непрерывной математики, основной задачей которой было исследование естественных природных объектов и процессов.
Для наиболее полного использования в практических приложениях возможностей современной вычислительной техники 
и про граммного обеспечения каждому инженеру наряду со знанием своей основной предметной области необходимы довольно 
глубокие познания в общей теории информационных технологий. 
Основы ее закладывают информатика и дискретная математика. 
Их методы закладывают основу успешного изучения специальных 
дисциплин в области информационных технологий, формирования 
необходимых знаний, умений и общей компетентности. Их понимание позволяет избежать множества принципиальных ошибок 
при построении информационных структур и алгоритмической организации вычислительных процессов.
В пособии поставлена задача изложения на понятном для инженера и программиста языке основ информатики и дискретной 
математики в объеме, достаточном для понимания и практического использования ее методов в технических приложениях. Оно 
создавалось и перерабатывалось с учетом специфики преподавания 
данных дисциплин в техническом вузе. При этом учитывались 
прак тическая направленность изучаемого курса, более конкретный 
тип мышления, свойственный студентам технических специальностей, особенности учебных планов по данным специальностям 
и другие аспекты.
При минимально возможном числе вводимых теоретических 
понятий акцент сделан на более глубоком объяснении их смысла, 
выявлении связи с практикой, выработке у студентов навыков самостоятельного решения практических задач методами дискретной 
математики. С этой целью в пособии даны многочисленные примеры и задачи.
Также одной из главных целей создания пособия являлась помощь молодым специалистам из IT-сферы в самостоятельной ликвидации пробелов в тех или иных разделах дискретной математики. 

Это помогает им ориентироваться в огромном объеме информации, 
четко понять потенциальные возможности методов и алгоритмов 
решения типовых задач, правильно строить свои разработки.
Как показывает опыт автора, специалисты, уже обладающие 
некими практическими навыками, довольно быстро усваивают 
нужные им теоретические знания. В таких случаях для оперативной 
самостоятельной проверки реального уровня усвоения учебного 
материала рекомендуется отвечать на все вопросы для проверки 
знаний, приведенные в конце параграфов и глав пособия. Также 
оценить уровень усвоения знаний помогает решение задач, приводимых после теоретических вопросов и в вариантах контрольных 
работ.
Раздел I является вводным. В нем даны основные понятия и методы, используемые в дискретной математике, основы теории множеств. Особое внимание уделено графическому и формульному 
заданию множеств, дан табличный метод анализа составных множеств. Затем рассмотрена теория бинарных отношений, наиболее 
употребительных в теории и практике информационных технологий.
В Разделе II представлены различные системы представления 
целых и смешанных чисел, используемые в компьютерных технологиях, а также переходы между ними. Отдельно рассмотрены базовые методы подсчета чисел комбинаторных множеств, наиболее 
применимых в теории и практике обработки информации.
Раздел III, посвященный математической логике, занимает 
в учебном пособии центральное место. В первой части этого раздела подробно изложена алгебра логики: анализ и все вопросы, касающиеся ее практического использования в технических и информационных приложениях. Вторая часть раздела представляет собой 
введение в аксиоматическое построение математических теорий, 
которое дает углубленное понимание их структуры и потенциальных возможностей. Третья часть посвящена конечно значной 
логике, в ней упор сделан на методы построения формул. 
В четвертой части достаточно объемно, учитывая востребованность в практических приложениях, изложена теория нечетких 
множеств и начала нечеткой логики. Здесь кратко рассмотрены 
операции с нечеткими множествами, особенности булевой алгебры 
на них, а также изложены основы построения нечетких систем 
управления — рассмотрены нечеткие системы типа Мамдани и Сугено, выполнение логического вывода в них. Пятая и шестая части 
посвящены логике предикатов и теории автоматического вывода.

В учебном пособии рассматривается следующий блок компетенций:
ПК1 — задавать множества, применять операции над ними, анализировать мощность множеств и бинарные отношения на множествах;
ПК2 — определять количество информации, применять методы 
комбинаторики;
ПК3 — использовать позиционные системы счисления с постоянными основаниями, смешанные позиционные системы счисления 
и факториальную систему;
ПК4 — представлять полные и частично определенные булевы 
функции в табличном и формульном виде (нормальные формы 
и полином Жегалкина), минимизировать их, анализировать и синтезировать релейные и функцио нальные схемы;
ПК5 — использовать аксиоматический подход к построению алгебраических и логических теорий;
ПК6 — использовать многозначные логики;
ПК7 — использовать нечеткие множества и нечеткую логику;
ПК8 – использовать логику предикатов;
ПК9 — знать проблему разрешимости и теорию автоматического 
вывода.
В результате изучения материалов учебного пособия студент будет:
знать
 
• способы задания множеств, операции с ними, методы анализа 
формул, методы определения мощности множеств;
 
• способы определения количества информации, основные методы комбинаторики;
 
• способы представления чисел в позиционных системах счисления с постоянными основаниями, смешанных позиционных 
системах счисления и в факториальной системе, способы перехода между системами;
 
• методы представления полных и частично определенных булевых функций в табличном и формульном виде (нормальные 
формы и полином Жегалкина), методы их минимизации, анализа и синтеза релейных и функциональных схем;
 
• способы построения универсальных алгебраических систем, 
универсальных и предметных формальных теорий, аксиоматическое построение исчисления высказываний;
 
• способы представления и анализа функций многозначных логик;
 
• способы представления и анализа нечетких множеств 
и функций нечеткой логики, нечеткие системы типа Мамдани 
и Сугено;

• способы представления формул в логике предикатов, интерпретацию и равносильность формул логики предикатов, исчисление 
предикатов;
 
• способы приведения формул логики предикатов к пренексной 
нормальной форме и скулемовской форме, метод Эрбрана 
и метод резолюций;
уметь
 
• задавать множества, применять к ним операции, сравнивать составные множества, определять мощность множеств и анализировать бинарные отношения на множествах;
 
• рассчитывать количество информации, практически применять 
основные методы комбинаторики;
 
• представлять числа в позиционных системах счисления с постоянными основаниями, смешанных позиционных системах счисления и в факториальной системе, выполнять переходы между 
ними;
 
• представлять полные и частично определенные булевы функции 
в табличном и формульном виде (нормальные формы и полином 
Жегалкина), минимизировать их, анализировать и синтезировать релейные и функциональные схемы;
 
• применять способы построения универсальных алгебраических 
систем, универсальных и предметных формальных теорий, использовать аксиоматическое построение исчисления высказываний;
 
• представлять и анализировать функции многозначных логик;
 
• представлять и анализировать нечеткие множества и функции 
нечеткой логики, нечеткие системы типа Мамдани и Сугено;
 
• представлять и анализировать формулы в логике предикатов, 
интерпретировать и проверять равносильность формул логики 
предикатов, использовать методы исчисления предикатов;
 
• приводить формулы логики предикатов к пренексной нормальной форме и скулемовской форме, применять метод Эрбрана и метод резолюций;
владеть
 
• операциями с множествами, методами их сравнения и анализа, 
методами анализа мощности множеств, а также бинарных отношений на них;
 
• способами определения количества информации, основными 
методами комбинаторики;
 
• способами представления чисел в позиционных системах счисления с постоянными основаниями, смешанных позиционных 

системах счисления и в факториальной системе, способами перехода между системами;
 
• методами представления полных и частично определенных булевых функций в табличном и формульном виде (нормальные 
формы и полином Жегалкина), методами их минимизации, анализа и синтеза релейных и функциональных схем;
 
• способами построения универсальных алгебраических систем, 
универсальных и предметных формальных теорий, аксиоматическим построением исчисления высказываний;
 
• способами представления и анализа функций многозначных 
логик;
 
• способами представления и анализа нечетких множеств 
и функций нечеткой логики, нечеткими системами типа 
Мамдани и Сугено;
 
• способами представления и анализа формул в логике предикатов, методами построения интерпретаций, проверки равносильности формул логики предикатов, методами исчисления 
предикатов;
 
• способами приведения формул логики предикатов к пренексной 
нормальной форме и скулемовской форме, методами Эрбрана 
и резолюций.
Изложение материала в учебном пособии по возможности 
максимально упрощено и построено в расчете на базовые знания 
студентов по курсу средней школы, математическому анализу, линейной алгебре и теории вероятностей.
В конце каждой темы приведены вопросы для проверки знаний, 
помогающие самостоятельно выяснить уровень подготовки, а также 
задачи для самостоятельного решения. Содержание задач, с одной 
стороны, максимально приближено к прикладным приложениям 
теоретических разделов, с другой — помогает усвоению учебного 
материала. Решение их составляет основу семинарских занятий. 
Также даны варианты контрольных заданий по основным темам 
курса.
Учебное пособие рассчитано на бакалавров и магистров направлений подготовки информационного профиля. Также оно может 
быть использовано для углубленного изучения математики и информатики в средней школе.

Раздел I. 
ОСНОВЫ ТЕОРИИ МНОЖЕСТВ

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

Глава 1. 
МНОЖЕСТВА. АЛГЕБРА МНОЖЕСТВ

1.1. ЭЛЕМЕНТЫ И МНОЖЕСТВА. ОСНОВНЫЕ ПОНЯТИЯ

Поскольку понятия множества и его элемента первичны, их невозможно сформулировать с помощью понятий других дисциплин.
Определение. Под множеством понимают некоторый набор (конечный или бесконечный) объектов, называемых его элементами, 
которые обладают некоторыми существенными для исследования 
общими свойствами.
На вид элемен тов, составляющих множества, нет никаких принципиальных ограничений — они могут моделировать объекты реального мира и быть виртуальными, в качестве них могут выступать числа, символы, строки символов, геометрические фигуры, 
предметы окружающей среды, люди и др.
В формулах множества обыч но обозначают с помощью заглавных латинских букв — как без индексов, так и с индексами (А, 
В, С, А1, Сi). Элемен ты множеств обозначают прописными буквами 
(также без индексов и с индексами). При этом вхождение элемента a1 в множество А обозначают как a1 ∈ А.
В зависимости от числа элемен тов в множествах их делят на конечные (у которых число элемен тов ограничено) и бесконечные 
(с неограниченным, бесконечным числом элемен тов).

Пример 1.1
Примеры множеств с общепринятыми обозначениями:
1) множество студентов в группе (конечное, его элемент — студент);
2) множество арабских цифр (состоит из 10 элементов — цифр 
от 0 до 9);
3) множество N всех натуральных чисел (бесконечное, его элементы — числа 1, 2, …);
4) N = {0, 1, 2, 3, …} — бесконечное расширенное множество натуральных чисел;
5) Z = {…, –3, –2, –1, 0, 1, 2, 3, …} — бесконечное множество всех 
целых чисел на всей числовой оси;
6) Еk = {0, 1, …, k – 1} — конечное множество целых чисел по модулю k (k ∈ N);
7) Р = {2, 3, 5, 7, 11, …} — бесконечное множество положительных 
целых простых чисел (тех, которые делятся без остатка только 
на себя и на единицу);
8) Q = {±m / n, где m ∈ N, n ∈ N} — бесконечное множество всех 
рациональных чисел на всей числовой оси;
9) R — множество вещественных чисел на всей числовой оси 
(бесконечное, его элементы — вещественные числа от –∞ до +∞);
10) R2 = {(х, у), где х ∈ R, у ∈ R} — бесконечное множество всех 
точек на декартовой плоскости с вещественными координатами;
11) R+ = (0, +∞) — бесконечное множество всех положительных 
вещественных чисел;
12) R– = (–∞, 0) — бесконечное множество всех отрицательных 
вещественных чисел;
13) C = {x + i y, где x ∈ R, y ∈ R, 
1
i =
− } — бесконечное множество всех комплексных чисел.
Среди всех возможных множеств в теории множеств особо выделяют пустое и универсальное множества.

Определение. Пустым называют множество, в котором нет 
элемен тов. Обозначают его символом ∅.
Обыч но в каждой конкретной задаче все исследуемые частные 
наборы элемен тов (множества) выбирают из некоторой более широкой исходной их совокупности, которая описывает исследуемую 
предметную область.
Определение. Универсальным называют множество U, содержащее полный набор объектов, моделирующих некоторую изучаемую предметную область, из которого выбирают все конкретные 
множества.

Для каждого конкретного множества А универсальное множество U, как правило, можно выбрать не единственным способом.

Пример 1.2
Для множества N всех натуральных чисел в качестве универсального теоретически может быть принято любое из множеств⎯N, 
Z, Q, R, R+, С.

Пример 1.3
Примем в качестве универсального множество Сr всех окружностей на декартовой плоскости Оху. На нем в качестве частных множеств можно рассмотреть, например, множества Сr(а, b) окружностей с общим центром в точке с координатами (х = а, y = b). Каждое 
из данных множеств бесконечно. Это следует из того, что 
их элемен ты однозначно задаются радиусами r, а множество 
{r} = R+ — бесконечно.

Пример 1.4
Для множества студентов в некоторой группе первого курса факультета ФИТ института Х в качестве универсального могут быть 
приняты следующие расширенные множества: 1) U1 = {множество 
всех студентов первого курса факультета ФИТ института Х}; 
2) U2 = {множество всех студентов факультета ФИТ института Х}; 
3) U3 = {множество всех студентов института Х}. При этом U1 ⊂ 
⊂ U2 ⊂ U3.
Одной из основных операций, применяемых для порождения 
новых множеств более сложной структуры из более простых исходных, является декартово произведение.

Определение. Декартовым произведением множеств А и В называют новое производное от них множество, которое состоит из всех 
возможных пар (а, b), где а ∈ А, b ∈ В. Оно обозначается как А × В. 
Степенью n множества А называют такое декартово произведение А × 
× А × … × А, в которое А входит ровно n раз. Оно обозначается 
как Аn.

Пример 1.5
А = {V, &}, B = {!, ?}.
А × В = {(V, !); (V, ?); (&, !); (&, ?)}; А2 = {(V, V); (V, &); (&, V); 
(&, &)};
В × А = {(!, V); (!, &); (?, V); (?, &)}; B2 = {(!, !); (!, ?); (?, !); (?, ?)}.
Пример 1.5 показывает, что в общем случае декартово произведение не является коммутативным — в нем нельзя менять местами 
различающиеся сомножители.