Дискретная математика. Задачи и упражнения с решениями

ДИСКРЕТНАЯ МАТЕМАТИКА

ЗАДАЧИ И УПРАЖНЕНИЯ 
С РЕШЕНИЯМИ

А.А. ВОРОНЕНКО
В.С. ФЕДОРОВА

2-е издание, исправленное и дополненное

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

УЧЕБНО-МЕТОДИЧЕСКОЕ  ПОСОБИЕ

Допущено УМО по классическому университетскому 
образованию в качестве учебного пособия для студентов 
высших учебных заведений, обучающихся по направлениям 
подготовки 01.03.02 «Прикладная математика и информатика»
и 02.03.02 «Фундаментальная информатика 
и информационные технологии»

УДК 51(075.8)
ББК 22.176я73
 
В75

Вороненко А.А.
В75  
Дискретная математика. Задачи и упражнения с решениями : учебно-методическое пособие / А.А. Вороненко, В.С. Федорова. — 2-е изд., 
испр. и доп. — Москва : ИНФРА-М, 2024. — 105 с. — (Высшее образование).

ISBN 978-5-16-019192-8 (print)
ISBN 978-5-16-111931-0 (online)
В учебно-методическом пособии представлены решения задач, входящих 
в программу аудиторных занятий по курсам «Дискретная математика» и «Дополнительные главы дискретной математики», читаемым студентам факультета вычислительной математики и кибернетики Московского государственного 
университета имени М.В. Ломоносова. Все задачи взяты из учебника Г.П. Гаврилова, А.А. Сапоженко «Задачи и упражнения по дискретной математике» 
(М.: Физматлит, 2004). 
Рассчитано на студентов первого и третьего курсов физико-математических вузов и факультетов.

Авторы выражают благодарность Д. Кафтан, Д. Чистикову, 
В. Подымову, Е. Платоновой, Е. Дорогуш и Т. Нагапетяну 
за помощь в подготовке пособия

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

Р е ц е н з е н т ы:
Алексеев В.Б., доктор физико-математических наук, профессор;
Дьяконов А.Г., доктор физико-математических наук, доцент

ISBN 978-5-16-019192-8 (print)
ISBN 978-5-16-111931-0 (online)
© Вороненко А.А., Федорова В.С., 
2020

 

ООО «Научно-издательский центр ИНФРА-М»
127214, Москва, ул. Полярная, д. 31В, стр. 1
Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29
E-mail: books@infra-m.ru        http://www.infra-m.ru

Подписано в печать 10.08.2023. 
Формат 6090/16. Бумага офсетная. Гарнитура Petersburg. 
Печать цифровая. Усл. печ. л. 6,56.
ППТ12. Заказ № 00000
ТК 431450-2082670-151219

Отпечатано в типографии ООО «Научно-издательский центр ИНФРА-М»
127214, Москва, ул. Полярная, д. 31В, стр. 1
Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11

Часть 1.
Курс «Дискретная математика»

Занятие №1.1

Функции алгебры логики. Формулы.
Существенные и фиктивные переменные

I.1.18(1). По заданным векторно функциям f(x1, x2) и g(x1, x2):
αf = (0010), αg = (1000), построить векторное представление функции
h(x1, x2, x3) = f(x1, x3) & g(x2, x1).

◀ Составим таблицу значений соответствующих функций:

x1 x2 x3 f(x1, x3) g(x2, x1) h(x1, x2, x3)
0
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0

1
0
0
1
0
0
1
0
1
0
0
0
1
1
0
1
0
0
1
1
1
0
0
0

Откуда получаем αh = (0000 0000).
▶

I.1.19(3, 4).
Построив таблицы соответствующих функций, выяснить, эквивалентны ли формулы Ai и Bi, i = 3, 4:
3) A3 = x → ((y → z) → y · z), B3 = (x ∨ (y → z)) · (x ⊕ y);
4) A4 = (x ↓ y) ∨ (x ∼ z) | (x ⊕ y · z), B4 = x · (y · z) ∨ x → z.

◀ Составим таблицу значений соответствующих функций:

x y z
A3 B3
A4 B4

0 0 0
1
0
1
0
0 0 1
1
0
1
0
0 1 0
1
0
1
0
0 1 1
1
1
0
1

1 0 0
0
1
0
1
1 0 1
0
1
1
0
1 1 0
1
0
0
1
1 1 1
1
0
1
0

3

Из таблицы видно, что обе пары формул не эквивалентны.
▶

I.1.20(4). Построив таблицу для функций x∨(y ∼ z) и (x∨y) ∼ (x∨z),

убедиться в справедливости их эквивалентности.

◀ Составим таблицу значений соответствующих функций:

x y z x ∨ (y ∼ z) (x ∨ y) ∼ (x ∨ z)
0 0 0
1
1

0 0 1
0
0

0 1 0
0
0

0 1 1
1
1

1 0 0
1
1

1 0 1
1
1

1 1 0
1
1

1 1 1
1
1

Из неё видно, что исходные функции эквивалентны.
▶

I.1.21(1, 2). Используя основные эквивалентности, доказать эквива
лентность формул A и B:

1) A = (x → y) → (x · y ∼ (x ⊕ y)), B = (x · y → x) → y;
2) A = (x · y ∨ (x → y · z)) ∼ ((x → y) → z), B = (x → y) ⊕ (y ⊕ z).

◀
1. С помощью преобразований приведем формулы A и B к одинаковому виду:

A = (x → y) → (x · y ∼ (x ⊕ y)) =

= (x ∨ y) → (x · y · (x ⊕ y) ∨ x · y · x ⊕ y) =
= (x ∨ y) → (x · y · (x · y ∨ x · y) ∨ (x ∨ y) · (x · y ∨ x · y)) =
= (x ∨ y) → (x · y ∨ x · y ∨ x · y) =
= (x ∨ y) ∨ (x ∨ x · y) =
= x · y ∨ x ∨ x · y =
= x ∨ x · y =
= x ∨ y =
= x → y.

B = (x · y → x) → y =

= (x · y ∨ x) → y
= x →

В преобразованиях использовалось тождество

x · K1 ∨ x · K2 = x · K1 ∨ x · K2 ∨ K1 · K2,

4

y.

справедливое для любых элементарных конъюнкций K1, K2.
2. С помощью преобразований приведем формулы A и B к одинаковому виду:

A = (x · y ∨ (x → y · z)) ∼ ((x → y) → z) =
= (x · y ∨ x ∨ y · z) ∼ (x · y ∨ z) =
= (x ∨ y · z) ∼ (x · y ∨ z) =
= (x · z ∨ y · z ∨ x · y · z) ∨ (x(y ∨ z)z(x ∨ y)) =
= x · y · z ∨ y · z ∨ x · z,
B = (x → y) ⊕ (y ⊕ z) =
= (x ∨ y) · (y ∼ z) ∨ (x ∨ y) · (y ⊕ z) =
= (x ∨ y) · (y · z ∨ y · z) ∨ x · y · (y · z ∨ y · z) =
= x · y · z ∨ x · y · z ∨ y · z ∨ x · y · z =
= x · y · z ∨ y · z ∨ x · y · z =
= x · y · z ∨ y · z ∨ x · z.
▶

I.1.28(1, 2). Указать все фиктивные переменные функции f:
1) f(x3) = (10101010);
2) f(x3) = (01100110).

◀
1. Имеем:

f(0, 0, 0) = f(0, 1, 0) = f(1, 0, 0) = f(1, 1, 0) = 1,

f(0, 0, 1) = f(0, 1, 1) = f(1, 0, 1) = f(1, 1, 1) = 0,
откуда видно, что значение функции зависит только от значения
переменной x3, то есть переменные x1, x2 — фиктивные.
2. Имеем:
f(0, 0, 0) = f(1, 0, 0),
f(0, 0, 1) = f(1, 0, 1),
f(0, 1, 0) = f(1, 1, 0),
f(0, 1, 1) = f(1, 1, 1),
откуда видно, что значение функции не зависит от значения переменной x1.
На наборах (000) и (001) функция принимает различные значения, откуда следует, что переменная x3 существенная.
На наборах (000) и (010) функция принимает различные значения, откуда следует, что переменная x2 существенная.
Таким образом, x1 является единственной фиктивной переменной рассматриваемой функции.
▶

5

I.1.31(1, 2).
1. Доказать, что если у функции f(xn) (n ⩾ 1) имеются фиктивные переменные, то она принимает значение 1 на чётном числе
наборов.
2. Выяснить, верно ли утверждение, обратное к 1.

◀
1. Пусть x1 — фиктивная переменная.
Тогда, если на наборе (α1, α2, . . . , αn) функция принимает значение 1, то на наборе (α1, α2, . . . , αn) функция также принимает
значение 1.
Таким образом, число наборов переменных, на которых функция
принимает значение 1, кратно 2.
2. В общем случае обратное утверждение не верно. Например, функция f = x1 ⊕ x2 принимает значение 1 на чётном числе наборов,
но не имеет фиктивных переменных.
▶

I.1.33(1, 2). Выяснить, какие переменные функции f являются существенными:
1) f(x4) = (1001 0011 0011 0010);
2) f(x4) = (0110 0111 0111 0110).

◀
1. Функция f(x4) = (1001 0011 0011 0010) принимает значение 1
на нечётном числе наборов, поэтому фиктивных переменных у неё
нет.
2. Функция f(x4) = (0110 0111 0111 0110) не имеет фиктивных переменных, так как

0 = f(0, 0, 0, 0) ̸= f(0, 0, 0, 1) = 1 ⇒ x4 − существенная переменная;

0 = f(0, 0, 0, 0) ̸= f(0, 0, 1, 0) = 1 ⇒ x3 − существенная переменная;
0 = f(0, 0, 1, 1) ̸= f(0, 1, 1, 1) = 1 ⇒ x2 − существенная переменная;
0 = f(0, 0, 1, 1) ̸= f(1, 0, 1, 1) = 1 ⇒ x1 − существенная переменная. ▶

I.1.34(5). Выяснить, при каких n (n ⩾ 2) функция f(xn) = (x1 |x2)⊕
⊕(x2 | x3) ⊕ . . . ⊕ (xn−1 | xn) ⊕ (xn | x1) зависит существенно от всех своих
переменных.

◀ Если n = 2, то f = (x1 | x2) ⊕ (x2 | x1) ≡ 0, а следовательно, все
переменные у неё фиктивные.
Покажем, что при n ⩾ 3 у функции нет фиктивных переменных.
Функция инвариантна относительно циклического сдвига переменных,
поэтому все переменные либо существенны, либо фиктивны. Поскольку
f(1, . . . , 1) = 0, f(0, 0, 1, . . . , 1) = 1, то получаем, что все переменные
данной функции существенны.
▶

6

Занятие №1.2

ДНФ, КНФ, СФЭ

I.2.3(3).
Представить в виде совершенной ДНФ следующую функцию:
f(x, y, z) = (0101 0001).

◀ Рассмотрим наборы, на которых функция принимает значение 1 (cоответствующие строки таблицы выделены):

x y z f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Совершенная ДНФ функции имеет вид:

f(x, y, z) = x · y · z ∨ x · y · z ∨ x · y · z.
▶

I.2.12(1). Применяя преобразования вида A = A·x∨A·x и A∨A = A,
построить из заданной ДНФ функции f(xn) её совершенную ДНФ:

f(x3) = x1x2 ∨ x3.

◀

f(x3) = x1x2 ∨ x3 =
= x1x2x3 ∨ x1x2x3 ∨ x1x3 ∨ x1x3 =
= x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3 =
= x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3.
▶

I.2.18(1). Найти длину совершенной ДНФ функции f(xn) (n ⩾ 2):

f(xn) =
1⩽i<j⩽n
xixj.

◀ По определению, длина совершенной ДНФ равна количеству наборов,
на которых функция принимает значение 1.
В нашем случае легче посчитать число наборов, на которых функция
принимает значение 0:

7

— n наборов, на которых ровно одна переменная равна 1,
— 1 нулевой набор.

Вычитая из общего числа наборов количество наборов, на которых
функция принимает значение 0, получим длину совершенной ДНФ:

2n − n − 1.
▶

I.2.4(5).
Представить в виде совершенной КНФ следующую функцию:

f(x, y, z) = (0101 1101).

◀ Рассмотрим наборы, на которых функция принимает значение 0 (cоответствующие строки таблицы выделены):

x y z f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

Совершенная КНФ функции имеет вид:

f(x, y, z) = (x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z).
▶

Задание. Построить СФЭ для функции из номера I.1.17(1) с уменьшением числа элементов:

((x → y) ∨ (x ⊕ z)) · (y | z).

◀ Упростим формулу:

((x → y) ∨ (x ⊕ z)) · (y | z) =
= ((x ∨ y) ∨ xz ∨ xz) · (y ∨ z) =
= (x ∨ y ∨ z) · (y ∨ z) =

= y ∨ z = y & z.

Строим схему из функциональных элементов:

8

x
y
z

f

¬

&

▶

Задание. Построить СФЭ для функции из номера I.2.3(3) с уменьшением числа элементов:

f(x, y, z) = (0101 0001).

◀

f(x, y, z) = x · y · z ∨ x · y · z ∨ x · y · z =
= x · y · z ∨ y · z =
= z · (y ∨ x · y) =
= z · (y ∨ x).

Строим схему из функциональных элементов:

▶

Занятие №1.3

Полиномы и линейные функции

I.2.22(5). Методом неопределённых коэффициентов найти полином
Жегалкина для функции f(x3) = (0110 1001).

9

◀ Для функции трёх переменных полином Жегалкина имеет вид:

α ⊕ β1x1 ⊕ β2x2 ⊕ β3x3 ⊕ γ1x1x2 ⊕ γ2x1x3 ⊕ γ3x2x3 ⊕ δx1x2x3.

Составим систему:

x1 x2 x3 f
0
0
0
0 = α,
0
0
1
1 = α ⊕ β3,
0
1
0
1 = α ⊕ β2,
0
1
1
0 = α ⊕ β2 ⊕ β3 ⊕ γ3,

1
0
0
1 = α ⊕ β1,
1
0
1
0 = α ⊕ β1 ⊕ β3 ⊕ γ2,
1
1
0
0 = α ⊕ β1 ⊕ β2 ⊕ γ1,
1
1
1
1 = α ⊕ β1 ⊕ β2 ⊕ β3 ⊕ γ1 ⊕ γ2 ⊕ γ3 ⊕ δ

Отсюда получим коэффициенты полинома Жегалкина:

α = 0, β1 = 1, β2 = 1, β3 = 1, γ1 = 0, γ2 = 0, γ3 = 0, δ = 0.

Полином Жегалкина исходной функции имеет вид f = x1⊕x2⊕x3.
▶

I.2.23(7). Преобразуя вектор значений функции

f(x4) = (0000 0100 0110 0111),

построить полином Жегалкина для этой функции.

◀ Будем преобразовывать вектор значений функции с помощью определённой по индукции операции T (подробнее см. [2, с. 53]):

— Если n = 1 и α = (α0, α1), то T(α) = (α0, α0 ⊕ α1).
— Предположим, что операция T уже определена для каждого вектора σ из B2n, и рассмотрим произвольный вектор α из B2n+1.
Пусть α = (β0, β1, . . . , β2n−1, γ0, γ1, . . . , γ2n−1) и

T(β0, β1, . . . , β2n−1) = (δ0, δ1, . . . , δ2n−1),

T(γ0, γ1, . . . , γ2n−1) = (ε0, ε1, . . . , ε2n−1)

(δi и εj по индуктивному предположению известны). Тогда

T(α) = (δ0, δ1, . . . , δ2n−1, δ0 ⊕ ε0, δ1 ⊕ ε1, . . . , δ2n−1 ⊕ ε2n−1).

10