Дискретная математика. Задачи и упражнения с решениями
Собственные конкурсы:
- АКАДЕМУС, 2018, Физико-математические науки, Победитель
Дискретная математика: задачи и упражнения с решениями – краткий обзор
Эта книга представляет собой учебно-методическое пособие, предназначенное для студентов высших учебных заведений, изучающих дискретную математику. Она охватывает широкий спектр тем, от основ алгебры логики до теории автоматов и основ теории вычислимости. Пособие содержит решения задач и упражнений, взятых из известного учебника Г.П. Гаврилова и А.А. Сапоженко, что делает его ценным инструментом для самостоятельной работы и подготовки к экзаменам.
Алгебра логики и булевы функции
Первая часть пособия посвящена основам дискретной математики, включая алгебру логики. Рассматриваются функции алгебры логики, методы построения формул, совершенные дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ), а также совершенные формы Жегалкина (СФЭ). Особое внимание уделяется анализу существенных и фиктивных переменных, а также методам упрощения булевых выражений. В этой части разбираются методы представления булевых функций в различных формах, включая полиномы Жегалкина, и рассматриваются вопросы линейности функций.
Замкнутые классы и полнота
Следующий раздел посвящен изучению замкнутых классов функций и их свойств. Рассматриваются различные классы функций, такие как классы сохранения, классы монотонных функций, классы самодвойственных функций и другие. Особое внимание уделяется понятию полноты системы функций и методам определения полноты. В книге представлены критерии полноты, такие как критерий Слупецкого, и рассматриваются различные полные системы функций.
Графы и их свойства
Вторая часть пособия посвящена теории графов. Рассматриваются основные понятия, такие как изоморфизм, связность, деревья, планарность, раскраски и орграфы. Приводятся примеры решения задач, связанных с определением изоморфности графов, нахождением минимальных остовных деревьев, определением планарности графов и раскраской графов.
Алфавитное кодирование и коды, исправляющие ошибки
В этой части рассматриваются основы теории кодирования, включая алфавитное кодирование и методы построения оптимальных кодов, например, с использованием алгоритма Хаффмена. Обсуждаются вопросы однозначного декодирования и применения неравенства Макмиллана. Также рассматриваются коды, исправляющие ошибки, и их свойства, такие как кодовое расстояние, обнаружение и исправление ошибок.
Автоматы и машины Тьюринга
В заключительных разделах рассматриваются основы теории автоматов и машин Тьюринга. Обсуждаются различные типы автоматов, включая детерминированные и ограниченно-детерминированные автоматы, а также методы их представления с помощью диаграмм Мура, канонических таблиц и канонических уравнений. Рассматриваются операции над автоматами, такие как композиция и итерация. Также рассматриваются основы теории вычислимости, включая машины Тьюринга, примитивно рекурсивные и частично рекурсивные функции.
В целом, данное пособие представляет собой ценный ресурс для студентов, изучающих дискретную математику, и обеспечивает глубокое понимание основных концепций и методов этой важной области математики.
- ВО - Бакалавриат
- 01.03.02: Прикладная математика и информатика
- 02.03.02: Фундаментальная информатика и информационные технологии
ДИСКРЕТНАЯ МАТЕМАТИКА ЗАДАЧИ И УПРАЖНЕНИЯ С РЕШЕНИЯМИ А.А. ВОРОНЕНКО В.С. ФЕДОРОВА 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. Формат 6090/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).