Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Дискретная математика и математическая логика

Покупка
Новинка
Артикул: 885193.01.99
Доступ онлайн
500 ₽
В корзину
В учебнике рассмотрены следующие темы: бинарные отношения, бинарные операции, алгебраические структуры, конечные поля, алгебраические коды, теория графов, логика высказываний. Для успешного освоения представленных материалов в учебник включены также базовые общеалгебраические сведения. В конце каждой главы приведены упражнения для проверки полученных знаний. Издание предназначено для студентов направлений 09.03.01 «Информатика и вычислительная техника», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия» и может быть полезно студентам всех направлений бакалавриата и специалитета ИРИТ—РтФ УрФУ.
Белоусов, И. Н. Дискретная математика и математическая логика : учебник / И. Н. Белоусов, В. И. Белоусова. - 2-е изд., стер. - Москва : ФЛИНТА ; Екатеринбург : Издво Урал. ун-та, 2026. — 180 с. — ISBN 978-5-9765-5905-9 (ФЛИНТА) ; ISBN 978-5-7996-4138-2 (Изд-во Урал. ун-та). - Текст : электронный. - URL: https://znanium.ru/catalog/product/2264841 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования 
Российской Федерации
Уральский федеральный университет
имени первого Президента России Б.Н. Ельцина
И.Н. Белоусов
В.И. Белоусова
Дискретная математика 
и математическая логика
Учебник
2-е издание, стереотипное
Москва
      Екатеринбург
Издательство «ФЛИНТА»       
      Издательство Уральского университета
   2026
      2026


УДК 510.2(075.8)
ББК 22.12я73
          Б43
Р е ц е н з е н т ы:
кафедра шахматного искусства и компьютерной математики 
Уральского государственного экономического университета 
(зав. кафедрой канд. экон. наук, доц. Е.Н. Стариков);
канд. физ.-мат. наук, науч. сотр. Института математики и механики им. 
Н.Н. Красовского УрО РАН Н.А. Минигулов
Н а у ч н ы й р е д а к т о р
канд. физ.-мат. наук, доц. Н.В. Чуксина
Белоусов И.Н.
Б43          Дискретная математика и математическая логика : учебник / И.Н. Белосов, 
В.И. Белоусова. — 2-е изд., стер. — Москва : ФЛИНТА ; Екатеринбург : Издво Урал. ун-та, 2026. — 180 с. — ISBN 978-5-9765-5905-9 (ФЛИНТА) ; ISBN 
978-5-7996-4138-2 (Изд-во Урал. ун-та). — Текст : электронный.
В учебнике рассмотрены следующие темы: бинарные отношения, бинарные 
операции, алгебраические структуры, конечные поля, алгебраические коды, 
теория графов, логика высказываний. Для успешного освоения представленных 
материалов в учебник включены также базовые общеалгебраические сведения. 
В конце каждой главы приведены упражнения для проверки полученных 
знаний.
      Издание предназначено для студентов направлений 09.03.01 «Информатика и 
вычислительная техника», 09.03.03 «Прикладная информатика», 09.03.04 
«Программная инженерия» и может быть полезно студентам всех направлений 
бакалавриата и специалитета ИРИТ—РтФ УрФУ.
УДК 510.2(075.8)
ББК 22.12я73
	
© Уральский федеральный 
     университет, 2026
© Белоусов И.Н., Белоусова В.И.,
2026


Оглавление
Предисловие...............................................................................................5
Глава I. Бинарные отношения....................................................................7
§ 1 Множества. Операции над множествами...........................................7
§ 2 Определение и способы задания бинарного отношения.................10
§ 3 Операции над бинарными отношениями........................................13
§ 4 Основные свойства бинарных отношений.......................................14
§ 5 Классы эквивалентности..................................................................16
§ 6 Частичный порядок...........................................................................18
§ 7 Полурешетки и решетки...................................................................22
§ 8 Рефлексивное, симметричное и транзитивное замыкание 
       бинарного отношения......................................................................24
§ 9 Бинарные отношения из множества в множество...........................27
Упражнения для самостоятельной работы............................................29
Глава II. Элементы общей алгебры..........................................................31
§ 1 Группоиды и полугруппы..................................................................31
§ 2 Алгоритм Лайта.................................................................................34
§ 3 Группы...............................................................................................36
§ 4 Подгруппы. Смежные классы...........................................................39
§ 5 Циклические группы.........................................................................43
§ 6 Группы подстановок..........................................................................46
§ 7 Матричные группы............................................................................51
§ 8 Нормальные подгруппы. Фактор-группы........................................52
§ 9 Изоморфизмы и гомоморфизмы......................................................54
§ 10 Кольца и поля..................................................................................56
§ 11 Линейное пространство над произвольным полем F.....................58
§ 12 Идеалы и гомоморфизмы ассоциативных колец...........................58
Упражнения для самостоятельной работы............................................62
Глава III. Теория чисел............................................................................63
§ 1 Элементарная теория чисел..............................................................63
§ 2 Взаимно простые числа.....................................................................66
§ 3 Теория сравнений..............................................................................67
§ 4 Китайская теорема об остатках.........................................................70
§ 5 Теория сравнений в криптографии..................................................75
Упражнения для самостоятельной работы............................................79


Оглавление
Глава IV. Многочлены над конечными полями........................................80
§ 1 Обзор общей теории многочленов....................................................80
§ 2 Теория сравнений для многочленов и примеры построения 
       полей небольшого составного порядка............................................87
§ 3 Основные теоремы о многочленах над конечными полями............91
Упражнения для самостоятельной работы............................................99
Глава V. Коды, исправляющие ошибки.................................................. 100
§ 1 Блоковые коды................................................................................ 100
§ 2 Примеры блоковых кодов............................................................... 107
§ 3 Линейные коды. Порождающая матрица линейного кода............ 109
§ 4 Проверочная матрица линейного кода........................................... 112
§ 5 Дуальные коды................................................................................. 115
§ 6 Минимальное расстояние линейного кода.................................... 117
§ 7 Декодирование линейных кодов с помощью смежных классов.... 119
§ 8 Декодирование с помощью синдромов.......................................... 121
§ 9 Код Хэмминга и расширенный код Хэмминга.............................. 123
§ 10 Циклические коды......................................................................... 127
§ 11 Нахождение систематической порождающей матрицы 
         циклического кода........................................................................ 132
§ 12 Специальный вид проверочной матрицы циклического кода.... 134
§ 13 Коды, порожденные элементами из расширения 
         основного поля.............................................................................. 134
§ 14 Коды БЧХ....................................................................................... 136
§ 15 Примеры кодов БЧХ...................................................................... 138
§ 16 Декодирование кодов БЧХ............................................................ 139
Упражнения для самостоятельной работы.......................................... 144
Глава VI. Элементы теории графов........................................................ 146
§ 1 Основные понятия теории графов.................................................. 146
§ 2 Алгоритмы на графах....................................................................... 154
Упражнения для самостоятельной работы.......................................... 162
Глава VII. Элементы математической логики........................................ 163
§ 1 Высказывания и операции над ними............................................. 163
§ 2 Формулы логики высказываний..................................................... 165
§ 3 Классификация формул. Равносильные формулы........................ 166
§ 4 Нормальные формы........................................................................ 169
Упражнения для самостоятельной работы.......................................... 172
Ответы к упражнениям для самостоятельной работы............................ 173
Библиографический список.................................................................... 177


Предисловие
Д
искретная математика обеспечивает важную основу практически для каждой области информатики, и ее приложения, 
соответственно, обширны. Освоение дискретной математики позволяет студенту добиться успеха как в магистерской программе, так и в карьере в области разработки программного обеспечения 
или аналогичной технической области. Принципы дискретной математики используются на многих курсах направлений «Информатика 
и вычислительная техника», «Прикладная информатика», «Программная инженерия», включая алгоритмы и анализ сложности, архитектуру 
ЭВМ, компьютерные системы, базы данных, распределенные системы, функциональное программирование, машинное обучение, сети, 
компьютерную безопасность и операционные системы.
Методы решения задач, отточенные в дискретной математике, 
необходимы для написания сложного программного обеспечения. 
Студенты, добившиеся успеха в дискретной математике, смогут делать 
обобщения от одного случая проблемы до целого класса задач, а также выявлять и абстрагировать закономерности из данных.
Наконец, дискретная математика и алгоритмы составляют «лингва франка» для ученых в области компьютерных наук и разработчиков программного обеспечения. Поскольку эти концепции универсальны и важны для данной области, они широко используются для 
общения с коллегами и составляют основной компонент технической 
коммуникации.
Наш учебник адресован в первую очередь студентам укрупненной группы направлений 09.00.00 «Информатика и вычислительная 
техника», но будет полезен студентам всех направлений бакалаври
Предисловие
ата и специалитета ИРИТ-РтФ УрФУ, чья работа связана с дискретной математикой, логикой, информатикой и вычислительной техникой и приложениями.
Надеемся, что задачи для самостоятельного решения, приведенные в конце каждой главы, помогут в освоении и проверке материала. 
Ответы к этим упражнениями вы найдете в конце учебника.
Предполагается, что читатель уже знаком с основными разделами 
общей алгебры университетского курса «Математика». Впрочем, многие необходимые общеалгебраические сведения (определения, некоторые фундаментальные факты) включены в учебник, что делает его 
в большой степени самодостаточным. Предполагается последовательное изучение первых четырех глав («Бинарные отношения», «Элементы общей алгебры», «Теория чисел» и «Многочлены над конечными 
полями»), разделы «Коды, исправляющие ошибки», «Элементы теории графов» и «Элементы математической логики» могут изучаться 
в любом порядке и опираются на материал первых четырех глав.
Основу учебника составляет курс «Дискретная математика и математическая логика», читаемый авторами в ИРИТ-РТФ для студентов направления 09.00.00 «Информатика и вычислительная техника».


§ 1 Множества. Операции над множествами
Элементы теории множеств. Основные определения
П
ервое понятие, с которого мы начнем знакомство с математикой, — множество. Множество является неопределяемым 
понятием. Под множеством можно понимать набор (совокупность) некоторых объектов, объединенных каким-либо признаком или свойством. Примерами множеств служат известные из курса математики числовые множества (натуральных, действительных, 
комплексных чисел), множество функций, непрерывных на отрезке, 
множество многочленов и т. д.
Объекты, составляющие множество, называются его элементами. 
Множества обозначают прописными буквами латинского алфавита 
A, B, C, …, а элементы множества — строчными буквами a, b, c, … Если 
элемент a лежит в множестве A, то кратко записывают a
A
∈, иначе пишут a
A
∉.
Нам понадобится специфическое множество, которое не содержит ни одного элемента. Оно называется пустым и обозначается символом ∅.
Может случиться так, что каждый элемент множества B является 
элементом некоторого множества A. В этом случае говорят, что B — 
подмножество множества A, и обозначают B
A
⊆
.
Теперь мы можем определить равенство множеств. Скажем, что 
A и B называются равными, если B
A
⊆
 и A
B
⊆
, в этом случае пишут 
A
B
=


Если B является подмножеством A и при этом не равно A, то B называется собственным подмножеством A, и этот факт обозначают B
A
⊂
.
Пустое множество ∅ является подмножеством любого множества, 
а любое множество — несобственное подмножество самого себя.
Если A — конечное множество, состоящее из n элементов, то число n называется порядком множества A и обозначается A .
Если в задаче рассматриваются подмножества одного и того же 
множества, то это множество называется универсальным и обозначается через U. Например, числовые промежутки — подмножества множества R, в этом смысле R — универсальное множество.
Множество задают либо перечислением всех его элементов, либо 
указанием свойств элементов множества.
Пример 1
1. Множество A
a b c d


; ; ;
 
  
 — задано перечислением его четырех 
элементов.
2. Множество X
x
Z
x


 

{
:
}
3
7  состоит из целых чисел из интервала (–3; 7), т. е. X = {–2; –1; 0; 1; 2; 3; 4; 5; 6}.
Из заданных множеств можно получать новые множества с помощью операций, рассмотренных ниже.
Операции над множествами
1. Объединением (суммой) множеств A и B (A
B
∪
) называется множество, каждый элемент которого принадлежит множеству А или множеству B, т. е. 


A
B
x x
A
x
B






:
или
.
Пример 2. Если A 

2 4 6 8
;
; ;
 
 
 
 и  B 

1 3 5 7
; ; ;
 
 
 
, то  A
B

1 2 3
;
; ;
 
  

4 5 6 7 8
; ; ; ;
 
 
 
 
.
2. Пересечением (произведением) множеств A и B (A
B
∩
) называется множество, каждый элемент которого принадлежит и множеству A, 
и множеству B, т. е. A
B
x x
A
x
B




{ :
}
 и
.
Пример 3. Если A  


1 3
; 
 и B 

0 4
; 
, то A
B



0 3
;
.
 
3. Разностью множеств A и B (A
B
\
) называется множество всех 
элементов из A, не принадлежащих B, т. е. A
B
\
 




x x
A
x
B
:
 и
.
Пример 4. Если A  

1 4
; 
 и  B = , то  A
B
\
;
;
 



1 0
0 1
 
 
 
;
;
;




1 2
2 3
3 4
 
 
 


§ 1 Множества. Операции над множествами
4. Симметрической разностью множеств A и B (A
B
∆
) называется 
множество всех элементов, лежащих только в одном из этих множеств, 
т. е. A
B
A
B
B
A

 


\
\
 или A
B
A
B
A
B








\
.
5. Дополнением множества A до универсального множества U называется разность U
A
A
\
=
, т. е. A
x x
U
x
A





:
и
.
6. Пусть A и B — некоторые множества. Декартовым (прямым) произведением множеств A и B (A
B
× ) называется множество упорядоченных пар a b
, 

, где a
A
∈, b
B
∈, т. е. A
B
a b
a
A b
B




{( ,
) |
,
}
 
 
.
7. Пусть A
A
An
1
2
,
,
,
 
 
 

 — некоторые множества. Под прямым произведением множеств A
i
n
i (
{ ,
,
})
∈1  
 

 понимается множество упорядоченных n-ок ( ,
,
,
),
a
a
an
1
2
 
 
 

 где a
A
i
n
i
i
∈
∈
(
{ ,
,
})
1  
 

, обозначается через 
A
A
An
1
2
×
×
×

.
8. Пусть A — некоторое множество. Тогда декартово произведение 
A
A
×  называется декартовым квадратом множества A и обозначается 
через A2. Кратко A
A
a
a
a
a
A



{( ,
)|
,
}
1
2
1
2
 
 
.
9. Множество A
A
A
k
×
×
×
…





раз
 называется k-й степенью множества A 
и обозначается через Ak.
10. Разбиением множества A называется семейство его непустых 
подмножеств A
i
I
i,  ∈, таких, что:
1)
;
 A
Ai
i I


2)
,
,



 
i j
I A
A
i
j
 


 при i
j
≠.
Свойства операций над множествами
1. Коммутативность: A
B
B
A
A
B
B
A






;   
 .
2. Ассоциативность: A
B
C
A
B
C







;
A
B
C
A
B
C









.
3. Дистрибутивность: A
B
C
A
C
B
C









;
A
B
C
A
C
B
C









.
4. Идемпотентность: A
A
A
A
A
A




;  
.
5. A
A
A
 
  
;   
.
6. Законы де Моргана: A
B
A
B
A
B
A
B








 

;


§ 2 Определение и способы задания  
бинарного отношения
При работе с множествами часто нужно знать связи между их элементами. Для формального описания этих связей используют понятие отношения на множестве.
Определение 1. Назовем n-арным отношением на множестве X любое подмножество ρ n-ой степени множества Х (  X n). При n = 2 операция называется бинарной, при n = 3 — тернарной.
В дальнейшем будем рассматривать в основном бинарные отношения.
Самыми простыми примерами бинарных отношений являются:
•  X
X
X

   — универсальное отношение на X;
•  ∅ — пустое бинарное отношение;
•  X
x x
x
X
 




,
,
 
 
 — диагональ X
X
×
.
Если X — конечное множество, то бинарное отношение на X можно задать полным списком упорядоченных пар, содержащихся в этом 
отношении.
Например, на множестве X
a b c


, ,
 
 
 можно задать следующие бинарные отношения: 1  
 
 



a b
b b
c a
,
,
,
,
,
 
 
 
 
 
, 2  



c b
, 
, …
Для бинарного отношения ρ на множестве X вместо x
x
1
2
, 

 будем писать x x
1
2
ρ
. Такой способ записи называется инфиксным.
Пример 1. Пусть  — множество всех целых чисел. Запишем m|n, 
если m — делитель числа n. Тогда 2|14, 14|28, 5|10.
Пример 2. Пусть  — множество всех вещественных чисел, бинарное отношение ≤ (не больше). Оно состоит из всех точек плоскости, 
лежащих не выше прямой y = x.
Пример 3. Пусть A — подмножество действительных чисел, f x
( ) — 
функция, определенная на A (отображение, ставящее в соответствие 
каждому элементу множества A некоторый элемент того же множества). 
Тогда с f можно связать бинарное отношение  f
a f a
a
A
   




,
( )
 
. Отношение  f  — это не что иное, как график функции f x
( ).
Определение 2. Пусть A
a
an




1,
,
 
 
 и ρ — бинарное отношение 
на A. Матрицей отношения ρ называется n
n
× -матрица из нулей и еди
Доступ онлайн
500 ₽
В корзину