Дискретная математика

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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

  
 
 
 
Н.Д. БЕКАРЕВА 
 
 
 
 
 
ДИСКРЕТНАЯ МАТЕМАТИКА 
 
 
 
Утверждено  
Редакционно-издательским советом университета 
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2019 

УДК 519.1(075.8) 
   Б42 
 
 
Рецензенты: 
д-р физ.-мат. наук, доцент С.В. Судоплатов 
канд. техн. наук, доцент М.А. Семенова 
 
 
Работа подготовлена на кафедре теоретической  
и прикладной информатики для студентов I курса, обучающихся  
по направлению «Математическое обеспечение и администрирование 
информационных систем» (02.03.03) 
 
 
 
Бекарева Н.Д.  
Б42  
Дискретная математика: учебное пособие / Н.Д. Бекарева. – 
Новосибирск: Изд-во НГТУ, 2019. – 80 с. 

ISBN 978-5-7782-3952-4 

Работа включает разделы: операции теории множеств, математическую логику в составе булевой алгебры, исчисления высказываний и 
исчисления предикатов. При изложении материала использован конструктивный подход – наиболее современная и эффективная форма подачи материала. Каждый раздел сопровождается задачами, приводятся 
решения типовых задач. Работа окажется полезной при подготовке бакалавров по всем направлениям факультета прикладной математики и 
информатики. 
 
 
 УДК 519.1(075.8) 
  
 
 
 
ISBN 978-5-7782-3952-4 
 Бекарева Н.Д., 2019 
 
 Новосибирский государственный 
 
    технический университет, 2019 

 
 
 
 
 
 
ОГЛАВЛЕНИЕ 
 

1. Множества ........................................................................................................... 4 

1.1. Основные определения ............................................................................... 4 
1.2. Операции над множествами ....................................................................... 7 
1.3. Свойства операций .................................................................................... 11 
1.4. Бинарные отношения ................................................................................ 13 
Упражнения ............................................................................................................ 18 

2. Математическая логика ................................................................................. 20 

2.1. Операции логики Буля .............................................................................. 21 
2.2. Основные законы алгебры Буля ............................................................... 28 
2.3. Совершенные формы представления  логических функций ................. 30 
2.4. Базовые наборы логических функций ..................................................... 39 
Упражнения ............................................................................................................ 46 

3. Введение в логику высказываний ................................................................ 51 

3.1. Высказывания и операции над ними ....................................................... 51 
3.2. Построение доказательств  в логике высказываний .............................. 53 
3.2.1. Аксиоматика в логике высказываний ............................................ 54 
3.2.2. Табличный метод доказательства .................................................. 56 
3.2.3. Метод резолюций ............................................................................ 57 
Упражнения ............................................................................................................ 59 

4. Введение в логику предикатов ...................................................................... 63 

4.1. Конкретизация предикатов ....................................................................... 65 
4.2. Кванторы в предикатах ............................................................................. 66 
4.3. Построение доказательств  в логике предикатов ................................... 71 
Упражнения ............................................................................................................ 74 

Библиографический список .................................................................................. 79 

 
 

1. МНОЖЕСТВА 

1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ 

В этой теме первичными (неопределяемыми) являются понятия 
множества, элемента и принадлежности элемента множеству. Создатель теории множества Георг Кантор (1845- 1918) дал следующее толкование множества: «множество или совокупность – это собрание 
определенных и различных объектов нашей интуиции или интеллекта, 
мыслимое в качестве целого».  
Обычно множества обозначают прописными буквами латинского 
алфавита: A, B, C, D, …, X, Y, Z, элементы множества – строчными 
буквами того же алфавита: a, b, c, d, …, x, y, z. Если элемент a является 
элементом множества A, то пишут: 
,

a
A  (читают «элемент a принадлежит множеству A» или, что то же самое, «множество A содержит 
элемент a». Если элемент a не принадлежит множеству A, то это записывают с помощью символа 
:
  a
A

. 
Отметим, что необязательно элементы множества A определять 
строчными буквами этой же буквы, т. е. вполне понятны и возможны 
записи: 
,
.
x
A
a
B


 
Как можно задать (описать) множество? 
1. Множество может быть задано перечислением его элементов, заключенных в фигурные скобки, например, A = {1, 3, 5, 7, 11, 13, 17, 19), 
B = {1, 2, 3, 5, 8, 13}, 
{ , , ...,
}
C
a b
d

. Некоторые множества можно 
интерпретировать, т. е. определять смысл его элементов, так например, 
множество A содержит простые числа из первых двух десятков, множество B содержит числа Фибоначчи того же промежутка. Множество C 
можно воспринимать как математическую модель некоторого класса 
множеств, имеющих одинаковое число элементов.  

Множество называется конечным, если оно содержит конечное 
число элементов, иначе оно называется бесконечным.  
2. Множество может быть задано характеристическим свойством его 
элементов. Записывают это так: 


| характеристическое свойство
A
x

, 
слева от черты в фигурных скобках задается вид элементов множества – число, пара чисел, последовательность каких-либо символов 
и т. д.; справа от черты записывают свойства элементов множе- 
ства, выделяющих его из множеств, ему подобных. Например, 

{ |
– четное натуральное число}
A
x x

 или 


( ,
) |
,
,
B
x y
x
R y
R



 

где R – множество действительных чисел, 

R  – множество неотрицательных действительных чисел. Множество A можно определить и подругому: 
{2, 4, 6, 8, ...}
A 
 – при такой записи характеристическое 
свойство легко угадывается. Как правило, такие множества являются 
бесконечными – число их элементов нельзя указать. Но если элементы 
этого множества можно пронумеровать, то его называют счетным 
множеством, в противном случае – несчетным множеством. Приведенное выше множество 
{ |
четное натуральное число}
A
x x


 – счетное 
множество, примером несчетного множества могут быть множества 


( ,
) |
,
,
B
x y
x
R y
R



 


|
0,
A
x x
x R



 


|
0,
.
A
x x
x
R



 
Второе из этих множеств называют множеством неотрицательных чисел, 
третье – множеством неположительных чисел. Рассмотрим еще некоторые примеры. 

 |
,
,
,
X
x a
x
b
a b
R





 |
,
,
,
X
x a
x
b a b
R




 


 |
,
,
,
X
x a
x
b a b
R




 

 |
,
,
.
X
x a
x
b a b
R




 Первое множе
ство называется отрезком, обозначается как [ , ]
a b , второе – полуотрезком, открытым слева, обозначается как ( , ],
a b  третье – интервалом, 
обозначается как ( , )
a b , четвертое – полуотрезком, открытым справа, 
обозначается как [ , ).
a b   
Множества X служат определениями промежутков расширенной 
числовой прямой.  
Число элементов последних семи множеств бесконечное, их даже 
нельзя пронумеровать, их называют множествами мощности континуум. 
Мощность конечного множества равна числу элементов этого 
множества. 

В математике используется свой собственный язык – язык формул. 
Мы перейдем к нему постепенно, но некоторые элементы этого языка 
можно определить уже сейчас. 
Множество A  называется подмножеством (частью) множества B, 
если все элементы множества A принадлежат одновременно множеству B 
и существует элемент
,

b
B  множеству A не принадлежащий (
)
b
A

, 
записываем это так:

A
B  или 

B
A. Говорят при этом, что множество A включено в множество B. 
Примерами таких включений могут быть: 
,


Z
R Z
 множество 
целых 
чисел, 
,
Q
R Q

 
– 
множество 
рациональных 
чисел, 
,
N
Z
R N


 – множество натуральных чисел. 
Если элементы множеств A и B заданы перечислением их элементов, то факт, что 

A
B , сравнительно легко проверяется; если же 
множества A и B заданы характеристическими свойствами, то запись 

A
B  следует понимать так:  
a
A следует выполнение характеристического свойства множества B.  
Если для множеств A и B одновременно выполняются условия 
и
A
B
B
A


, то эти множества называются равными, т. е. они состоят из одних и тех же элементов. 
Следовательно, для доказательства равенства двух множеств нужно 
доказать оба включения 
,
.


A
B B
A  Структура доказательства 

A
B  выглядит так: «пусть 
,

a
A  тогда…, тогда…, …
»
a
B

. Аналогично для включения 

B
A .  
Из определения подмножества множества следует, что 
,
A
A

 каково бы ни было множество A. 
В теории множеств полезно понятие пустого множества – это множество не содержит никаких элементов никаких множеств, обозначается пустое множество символом  . Пустое множество принято считать подмножеством любого множества. Таким образом, каждое 
множество A имеет два подмножества: само себя и пустое множество: 
,
.
 

A A
A  Эти множества называются несобственными подмножествами – они ничего не добавляют к информации о множествах, все 
множества содержат такие подмножества. Все остальные подмножества множеств называются собственными.  
Часто в математических рассуждениях встречаются выражения 
«существует элемент а», «найдется элемент а», которые заменяются 

символом « a
 »; выражения «для любого элемента а», «каждый элемент а» заменяют символом «
».
a

 Символы ,
   называются кванторами существования и общности соответственно. Далее, символ «» 
в выражении 

P
Q  заменяет фразу «если справедливо P, то справедливо Q» или «из P следует Q»; символ «
»
  по смыслу означает « тогда и только тогда»; символ «df» означает «по определению». Эти обозначения делают словесное высказывание кратким, четким. 
Так, определение собственного подмножества A множества B  
можно записать коротко так: A
B
a
A
a
B

  


 и 
,
b
B
 
 
.
b
A

 Запятую в этой записи следует понимать как союз «и». 
Пусть имеем множества 

3
2
|
– кореньуравнения
2
A
x x
x
x



 

3
0
x


 и 


|
– студент I курса НГТУ
B
x x

.  
Элементы множества A будем выбирать из множества вещественных чисел по характеристическому свойству элементов множества; 
аналогично элементы множества B выбираем из множества студентов 
НГТУ. Следовательно, существуют более широкие множества, чем 
множество A в первом случае и множество B во втором случае, находящиеся в рассмотрении, из них набираются множества A и B. Эти более широкие множества, называют универсальными или фундаментальными, обозначают их буквой U. 

1.2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ 

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

 

Пусть заданы два множества A и B, являющиеся подмножествами 
одного и того же универсального множества U (далее факт принадлежности рассматриваемых множеств одному и тому же универсальному множеству U всегда будет иметь место при работе с множествами без указания на этот факт).  
1. Через 

A
B  обозначается множество, называемое их объединением или суммой, каждый элемент которого принадлежит хотя бы одному 
(по крайней мере одному) из множеств: или множеству A, или множе
ству B, или тому и другому одновременно:
или
|
.
и

df
A
B
x x
A
B









  

В этом случае грамматическая связка «или» содержит одновременно и 
грамматическую связку «и». 
 

 
 
2. Через 

A
B  (АВ) обозначают множество, называемое пересечением, каждый элемент которого принадлежит множествам A и B одновременно: 


|
и
.
A
B
x x
A
x
B




 
 

 
 
3. Через 
\
A B  обозначают множество, называемое разностью, состоящее из элементов, принадлежащих только множеству A и не принадлежащих множеству B: 


\
|
и
A B
x x
A
x
B



. 

Разность 
\
U
A называют дополнением множества А до множества U 
или просто дополнением множества A, обозначают символом 

:
\

A
A
U
A , т. е. 

 

\
|
,
|
.
U
A
x x
U
x
A
x x
A





 Равенство 

означает, что смысл записей 
и
x
A
x
A


 одинаков. Очевидно, что 

,
A
A U
A
A



  и 
\
.

U U
 
Для разности множеств 
\
A B  справедлива формула 
\
A B
AB



A
B


. 
Докажем это равенство, начнем с включения 
\

A B
AB : 

\
:
\
,
,
.











A B
AB
x
A B
x
A x
B
x
A x
B
x
A
B  Докажем 
включение: 
\
:
,
,
AB
A B
x
AB
x
A x
B
x
A







 
x
B


\
.
x
A B

 
Полученная формула 
\

A B
AB  дает возможность получить  
формулу, выражающую операцию объединения через другие опера
ции: 
или
|
{
,
}
{
,
}
{
,
и
A
B
x x
A
B
x
A x
B
x
A x
B
x
A

















 

}
x
B

 





|
\
|
\
|
.
x x
A B
x x
B A
x x
A
B
AB
AB
AB









 

Итак, 
.




A
B
AB
AB
AB  
Кроме того, по диаграмме Венна справедливость этих формул, а 
также формулы (
\
)
(
)
A B
A
B
A



 легко устанавливается. 

4. Через 

A
B  обозначают множество, называемое симметрической разностью, состоящее из всех тех элементов, которые принадлежат только одному из множеств A или B:
 |
и
или
A
B
x x
A
x
B




 


и
.
x
B
x
A


 
 

 
 
Из определения и диаграмм видим, что симметрическая разность – 
это объединение множеств A и B, но грамматическая связка «или»  
при этом не содержит в себе грамматической связки «и». Эта операция выражается через другие операции следующим образом: 
(
\
)
(
\
)
A
B
A B
B A



 (
)
(
)
.
A
B
B
A
AB
AB





 
5. Для множеств A и B вводится еще одна операция 

A
B , на- 
зываемая прямым или декартовым произведением множеств: 


( , ) |
и
.
A
B
x y
x
A
y
B




 Если множества A и B совпадают, то 

прямое произведение 
2


A
A
A  называют второй декартовой степенью множества A. Если сомножителей будет более двух, то результатом операции будут наборы по n элементов из множеств

1
2
3
4
,
,
,
,... n
A
A
A
A
A , взятых по одному и только по одному из каждого 
множества 
1
2
3
4
,
,
,
,... n
A
A
A
A
A . При совпадении множеств получаем 

прямое произведение 
...





n
n
A
A
A
A
A
A  – n-ю декартову степень 
множества A.  
Замечание 1. Операции объединения и пересечения могут быть 
естественным образом продолжены на любое конечное число операн
дов: 
1
1
,





n
n

k
k
k
k
A
A . 

Замечание 2. Последовательность выполнения операций по старшинству:  
 (дополнение как операция, результат A ), вычитание, пересечение, объединение, симметрическая разность: 
, \,
,
,
.




 

1.3. СВОЙСТВА ОПЕРАЦИЙ 

Справедливость свойств (законов) операций объединения, пересечения ( ,
)
   можно увидеть из рассмотрения соответствующих диаграмм Венна. 
1. Коммутативность операций: 
,
.
A
B
B
A
A
B
B
A






 
2. Ассоциативность операций: 
(
)
(
);
A
B
C
A
B
C
A
B
C








 
(
)
(
).
A
B
C
A
B
C
A
B
C








 
 

 
 
3. Дистрибутивные 
(распределительные) 
законы:
(
)
(
)
(
);
A
B
C
A
B
A
C






 
(
) (
)
(
).
A
B
C
A
B
A
C






  
Второе равенство для действительных чисел места не имеет. 
4. Законы универсального и пустого множеств: 
;
A
A
 
 
;
A  
;
.




A
U
U
A
U
A  
Эти четыре закона являются основными: все перечисленные ниже 
утверждения могут быть получены из этих основных, но они часто 
встречаются в вычислениях, поэтому целесообразно их записать 
(называть их будем также законами).  
5. Законы идемпотентности: 
,
A
A
A
A
A
A




.