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

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

Покупка
Основная коллекция
Артикул: 431450.11.01
К покупке доступен более свежий выпуск Перейти
Частному лицу
Бумажная книга
793 ₽
Купить
Купить в составе основной коллекции от 1 490 ₽

Собственные конкурсы:

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

Дискретная математика: задачи и упражнения с решениями – краткий обзор

Эта книга представляет собой учебно-методическое пособие, предназначенное для студентов высших учебных заведений, изучающих дискретную математику. Она охватывает широкий спектр тем, от основ алгебры логики до теории автоматов и основ теории вычислимости. Пособие содержит решения задач и упражнений, взятых из известного учебника Г.П. Гаврилова и А.А. Сапоженко, что делает его ценным инструментом для самостоятельной работы и подготовки к экзаменам.

Алгебра логики и булевы функции

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

Замкнутые классы и полнота

Следующий раздел посвящен изучению замкнутых классов функций и их свойств. Рассматриваются различные классы функций, такие как классы сохранения, классы монотонных функций, классы самодвойственных функций и другие. Особое внимание уделяется понятию полноты системы функций и методам определения полноты. В книге представлены критерии полноты, такие как критерий Слупецкого, и рассматриваются различные полные системы функций.

Графы и их свойства

Вторая часть пособия посвящена теории графов. Рассматриваются основные понятия, такие как изоморфизм, связность, деревья, планарность, раскраски и орграфы. Приводятся примеры решения задач, связанных с определением изоморфности графов, нахождением минимальных остовных деревьев, определением планарности графов и раскраской графов.

Алфавитное кодирование и коды, исправляющие ошибки

В этой части рассматриваются основы теории кодирования, включая алфавитное кодирование и методы построения оптимальных кодов, например, с использованием алгоритма Хаффмена. Обсуждаются вопросы однозначного декодирования и применения неравенства Макмиллана. Также рассматриваются коды, исправляющие ошибки, и их свойства, такие как кодовое расстояние, обнаружение и исправление ошибок.

Автоматы и машины Тьюринга

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

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

Текст подготовлен языковой моделью и может содержать неточности.

53
Вороненко, А. А. Дискретная математика. Задачи и упражнения с решениями : учебно-методическое пособие / А.А. Вороненко, В.С. Федорова. — 2-е изд., испр. и доп. — Москва : ИНФРА-М, 2024. — 105 с. — (Высшее образование). - ISBN 978-5-16-019192-8. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2082670 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
ДИСКРЕТНАЯ МАТЕМАТИКА
ЗАДАЧИ И УПРАЖНЕНИЯ 
С РЕШЕНИЯМИ
А.А. ВОРОНЕНКО
В.С. ФЕДОРОВА
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


Из таблицы видно, что обе пары формул не эквивалентны.
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,
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 является единственной фиктивной переменной рассматриваемой функции.


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, то получаем, что все переменные
данной функции существенны.


Занятие №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:


— 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.
Строим схему из функциональных элементов:


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


◀Для функции трёх переменных полином Жегалкина имеет вид:
α ⊕β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).


К покупке доступен более свежий выпуск Перейти
Частному лицу
Бумажная книга
793 ₽
Купить
Купить в составе основной коллекции от 1 490 ₽