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

Москва

ИНФРАМ

2022

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

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

С РЕШЕНИЯМИ

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

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

Допущено УМО по классическому университетскому 

образованию в качестве учебного пособия для студентов 

высших учебных заведений, обучающихся по направлениям 

подготовки 01.03.02 «Прикладная математика и информатика»

и 02.03.02 «Фундаментальная информатика 

и информационные технологии»

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

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

Вороненко А.А. 
Дискретная математика. Задачи и упражнения с решениями : учебно-методическое пособие / А.А. Вороненко, В.С. Федорова. — Москва : 
ИНФРАМ, 2022. — 104 с. — (Высшее образование: Бакалавриат). — 
DOI 10.12737/753.

ISBN 9785160066011 (print)
ISBN 978-5-16-106349-1 (online)

В пособии представлены решения задач, входящих в программу аудиторных занятий по курсам «Дискретная математика» и «Дополнительные главы дискретной математики», читаемых студентам факультета 
вычислительной математики и кибернетики МГУ имени М.В. Ломоносова. Все задачи взяты из учебника Г.П. Гаврилова, А.А. Сапоженко 
«Задачи и упражнения по дискретной математике» (М.: Физматлит, 
2004). Пособие рассчитано на студентов первого и третьего курсов.
Авторы выражают благодарность Д. Кафтан, Д. Чистикову, 
В. Подымову, Е. Платоновой, Е. Дорогуш и Т. Нагапетяну за помощь 
в подготовке пособия.
ББК 22.1я73 

В75

Подписано в печать 17.07.2015.
Формат 6090/16. Печать цифровая. 
Бумага офсетная. Гарнитура. 
Усл. печ. л. 6,5. Уч.-изд. л. 5,23.
ПТ20.
Цена свободная.

ТК 431450-521421-250213

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

ISBN 9785160066011 (print)
ISBN 978-5-16-106349-1 (online)
© Вороненко А.А., Федорова В.С., 2013

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

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)

αh = (0000 0000)


Ai
Bi i = 3

A3 = x → ((y → z) → y · z) B3 = (x ∨ (y → z)) · (x ⊕ y)
A4 = (x ↓ y) ∨ (x ∼ z) | (x ⊕ y · z) B4 = x · (y · z) ∨ x → z



x y z
A3 B3
A4 B4



x∨(y ∼ z)
(x∨y) ∼ (x∨z)



x y z x ∨ (y ∼ z) (x ∨ y) ∼ (x ∨ z)



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


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 → y;

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

K1 K2

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.


f

f(x3) = (10101010)
f(x3) = (01100110)



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

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



f(xn) (n  1)


x1

(α1, α2, . . . , αn)

(α1, α2, . . . , αn)

f = x1 ⊕ x2



f

f(x4) = (1001 0011 0011 0010)
f(x4) = (0110 0111 0111 0110)


f(x4) = (1001 0011 0011 0010)

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 −
. 

n (n  2)
f(xn) = (x1 |x2)⊕
(x2 | x3) ⊕ . . . ⊕ (xn−1 | xn) ⊕ (xn | x1)


f = (x1 | x2) ⊕ (x2 | x1) ≡ 0

n  3

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



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


1

x y z f

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

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.


f(xn) n  2

f(xn) =


1i<jn
xixj.



1

0

n
1

1

0

2n − n − 1.


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


0

x y z f

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

((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.

x
y
z

f

¬

&



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).



f(x3) = (0110 1001)



α ⊕ β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


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



T

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).