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

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

Покупка
Основная коллекция
Артикул: 179850.11.01
Доступ онлайн
от 160 ₽
В корзину
Учебник написан на основе курса лекций по дискретной математике, читаемого студентам факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова. Включает в себя введение в такие разделы дискретной математики, как булевы функции, k-значные функции, графы, коды, автоматы, реализация булевых функций схемами. Может использоваться для чтения курса «Дискретная математика», а также для самостоятельного изучения основ дискретной математики.
5
Тематика:
ББК:
УДК:
ОКСО:
ГРНТИ:
Алексеев, В. Б. Дискретная математика : учебник / В.Б. Алексеев. — Москва : ИНФРА-М, 2023. — 133 с. — (Высшее образование: Бакалавриат). — DOI 10.12737/1172256. - ISBN 978-5-16-016520-2. - Текст : электронный. - URL: https://znanium.com/catalog/product/1915507 (дата обращения: 28.11.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
В.Б. АЛЕКСЕЕВ
ДИСКРЕТНАЯ 
МАТЕМАТИКА
УЧЕБНИК
Рекомендовано Межрегиональным учебно-методическим 
советом профессионального образования в качестве 
учебника для студентов высших учебных заведений, 
обучающихся по укрупненной группе специальностей 
01.00.00 «Математика и механика» 
(квалификация (степень) «бакалавр») 
(протокол № 9 от 28.09.2020)
Москва
ИНФРА-М
202


УДК [519.71+519.1](075.8)
ББК 22.176я73
 
А47
Алексеев В.Б. 
А47  
Дискретная математика : учебник / В.Б. Алексеев. — Москва : 
ИНФРА-М, 2023. — 133 с. — (Высшее образование: Бакалавриат). — 
DOI 10.12737/1172256.
ISBN 978-5-16-016520-2 (print)
ISBN 978-5-16-108788-6 (online)
Учебник написан на основе курса лекций по дискретной математике, 
читаемого студентам факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова. Включает в себя введение в такие разделы дискретной математики, как 
булевы функции, k-значные функции, графы, коды, автоматы, реализация 
булевых функций схемами. 
Может использоваться для чтения курса «Дискретная математика», 
а также для самостоятельного изучения основ дискретной математики.
УДК [519.71+519.1](075.8)
ББК 22.176я73
ISBN 978-5-16-016520-2 (print)
ISBN 978-5-16-108788-6 (online)
© Алексеев В.Б., 2021


Введение
В последние десятилетия дискретная математика получила
широкое развитие. При этом имеются разные мнения о предмете и границах дискретной математики. По традиции, сложившейся в нашей стране, к ней относят в первую очередь те разделы, которые связаны с проблемами построения дискретных
управляющих систем, с дискретной обработкой информации.
Это теория булевых и многозначных дискретных функций, реализация дискретных функций схемами и автоматами, комбинаторика и теория графов, коды, алгоритмы на дискретных
структурах.
Книга написана на основе курса лекций по дискретной
математике, читаемого студентам факультета ВМК МГУ им.
М.В. Ломоносова. Этот курс является вводным в проблематику
дискретной математики, которая развивается затем в курсах
Дополнительные главы дискретной математики, Основы кибернетики, Сложность алгоритмов и специальных курсах по
отдельным разделам дискретной математики. Книга включает
в себя введение в такие разделы дискретной математики, как
булевы функции, k-значные функции, графы, коды, автоматы,
реализация булевых функций схемами.
По сравнению с первым изданием 2012 года в книгу добавлены метод Нельсона построения сокращенной дизъюнктивной
нормальной формы булевых функций, быстрый алгоритм построения полинома Жегалкина, теоремы о представлении kзначных функций 2-й формой и полиномами, алгоритм построения кратчайшего остовного дерева, теорема Кенига о раскрас3


ке графа в 2 цвета, линейные коды, теорема о несуществовании
эксперимента, определяющего начальное состояние автомата.
Книга может использоваться для чтения курса Дискретная математика, а также для самостоятельного изучения основ дискретной математики. Для практической проработки вопросов, изложенных в книге, можно использовать задачник
Г.П. Гаврилова и А.А. Сапоженко Задачи и упражнения по
курсу дискретной математики и привязанное к нему учебнометодическое пособие А.А. Вороненко и В.С. Федоровой Дискретная математика. Задачи и упражнения с решениями.
Книга в первую очередь ориентирована на студентов бакалавриата. Она позволяет выработать основные компетенции в
области дискретной математики. Ее освоение позволяет узнать
основные понятия, определения и факты теории булевых функций, теории многозначных функций, теории графов, теории кодирования, теории автоматов; развить умения решать задачи,
связанные с эквивалентными преобразованиями и специальными представлениями дискретных функций, с представимостью
одних функций через другие, со структурой, изоморфизмом,
планарностью графов, с построением, использованием и распознаванием свойств взаимно однозначных и оптимальных кодов,
кодов, исправляющих ошибки, с анализом, синтезом и оптимизацией автоматов; овладеть методами доказательства утверждений дискретной математики.
4


Глава 1
Функции алгебры логики
1.1
Функции алгебры логики. Равенство
функций. Тождества для элементарных функций
1.1.1
Функции алгебры логики.
Определение. Пусть E2 = {0, 1}  множество, состоящее из
двух элементов. Тогда положим En
2 = {(α1, . . . , αn)|∀i(αi ∈
E2)}. Всюду определ¼нной булевой функцией назов¼м отображение f(x1, . . . , xn) : En
2 →E2. Множество всех булевых функций обозначим P2.
Булеву функцию можно задать таблично. Например, для
n = 1:
x
0
1
x
¯
x
0
0
1
0
1
1
0
1
1
0
Здесь в первом столбце указаны возможные значения переменной, а в следующих столбцах все четыре возможных варианта значений функции от одной переменной. В первой строке
указаны обозначения этих функций. При этом функция 0 называется константой нул¼м, функция 1  константой единицей, функция x  тождественной, а функция ¯
x  отри5


цанием x. Для последней функции используется также иное
обозначение: ¯
x = ¬x.
Для n = 2 рассмотрим следующие функции:
x
y
f1
f2
f3
f4
f5
f6
f7
0
0
0
0
0
1
1
1
1
0
1
1
0
1
1
0
1
0
1
0
1
0
1
0
0
1
0
1
1
1
1
0
1
1
0
0
Для переменных x и y имеются четыре комбинации их значений, которые можно рассматривать как двоичную запись натуральных чисел. При заполнении таблицы удобно выписывать
наборы значений переменных в порядке возрастания соответствующих натуральных чисел. Указанные функции имеют специальные названия и обозначения:
f1  дизъюнкция, функция ¾или¿: f1 = x ∨y;
f2  конъюнкция, функция ¾и¿: f2 = x ∧y = x&y = x · y =
xy;
f3  сложение по модулю 2 (исключающее ¾или¿): f3 =
x ⊕y;
f4  импликация: f4 = x →y;
f5  эквивалентность: f5 = x ∼y;
f6  штрих Шеффера: f6 = x|y;
f7  стрелка Пирса: f7 = x ↓y.
Лемма 1.1.1 (о числе слов). В алфавите A = {a1, . . . , ar} из
r букв можно построить ровно rm различных слов длины m.
Доказательство. Провед¼м индукцию по m. Для m = 1 утверждение очевидно. Пусть утверждение леммы верно для m = k,
то есть существует ровно rk различных слов длины k. Для каждого такого слова длины k существует ровно r возможностей
добавить одну букву в конец. Поэтому число различных слов
длины k + 1 получится равным r · rk = rk+1. Лемма доказана.
Рассмотрим таблицу некоторой функции алгебры логики от
n переменных:
6


x1
x2
. . .
xn
f
0
0
. . .
0
a0
0
0
. . .
1
a1
. . .
. . .
. . .
. . .
. . .
1
1
. . .
1
a2n−1
По лемме 1.1.1 число различных наборов значений переменных равно 2n, то есть в таблице 2n строк. Для задания функции
необходимо и достаточно определить е¼ значения на всех 2n наборах. Таким образом, получаем, что всего различных функций от n переменных столько, сколько существует различных
наборов из нулей и единиц длины 2n, т.е. 22n.
Используя последний факт, можно, например, получить
оценку числа функций от 10 переменных. Всего таких функций 2210 = 21024 >

210100 > (1000)100 = 10300. Таким образом,
при росте числа переменных число функций возрастает очень
быстро.
1.1.2
Равенство функций.
В обычной алгебре справедливо равенство x+y−y = x, несмотря на то, что в левой части записана функция от двух переменных, а в правой  от одной. Таким образом, функции от разного числа переменных могут быть одинаковыми, что да¼т повод
ввести понятие существенных и фиктивных переменных.
Определение. Переменная xi называется существенной переменной функции алгебры логики f(x1, . . . , xn), если существуют такие α1, . . . , αi−1, αi+1, . . . , αn ∈E2, что
f(α1, . . . , αi−1, 0, αi+1, . . . , αn) ̸= f(α1, . . . , αi−1, 1, αi+1, . . . , αn).
(Такие наборы, отличающиеся значением лишь одной переменной xi, называются соседними по xi). В противном случае переменная xi называется фиктивной (или несущественной).
Если xi  фиктивная переменная функции f, то значение функции f на наборе однозначно определяется значениями
7


α1, . . . , αi−1, αi+1, . . . , αn, то есть функцию f можно рассматривать как некоторую функцию g(x1, . . . , xi−1, xi+1, . . . , xn) (фиктивную переменную можно удалить). Наоборот, таблицу любой
функции можно расширить введением любого числа фиктивных переменных.
Определение. Две функции алгебры логики называются равными, если одну из них можно получить из другой пут¼м добавления и изъятия любого числа фиктивных переменных.
1.1.3
Формулы.
Определение. Пусть имеется некоторое множество функций
A = {f1(. . . ), f2(. . . ), . . . , fn(. . . ), . . . }.
Введем понятие формулы над A:
1) Любая функция из A называется формулой над A.
2) Если f(x1, . . . , xn) ∈A и Hi для любого i  либо переменная, либо формула над A, то выражение вида f(H1, H2, . . . , Hn)
является также формулой над A.
3) Только те объекты называются формулами над A, которые можно построить с помощью пунктов 1 и 2 данного определения.
Замечание. Среди H1, H2, . . . , Hn могут быть одинаковые.
Будем считать, что каждая формула реализует функцию,
которая определяется индуктивно следующим образом. Формуле из пункта 1) сопоставляется просто соответствующая
функция. Функция для формулы из пункта 2) определяется так: на любом наборе значений переменных сначала вычисляются значения функций, соответствующих формулам
H1, H2, . . . , Hn (по предположению индукции эти функции уже
определены), а затем берется значение функции f на полученном наборе.
Определение. Две формулы называются эквивалентными,
если реализуемые ими функции равны.
8


1.1.4
Основные эквивалентности.
Коммутативность:
x ∨y = y ∨x
xy = yx
x ⊕y = y ⊕x
x ∼y = y ∼x.
Ассоциативность:
(x ∨y) ∨z = x ∨(y ∨z)
(xy)z = x(yz)
(x ⊕y) ⊕z = x ⊕(y ⊕z).
Законы поглощения:
x ∨x = x
x · x = x
x ∨x = 1
x · x = 0
x ∨1 = 1
x · 1 = x
x ∨0 = x
x · 0 = 0
x ⊕0 = x
x ⊕x = 0.
Другие эквивалентности:
Дистрибутивность:
(x ⊕y)z = (xz) ⊕(yz)
(x ∨y)z = (xz) ∨(yz)
(xy) ∨z = (x ∨z) · (y ∨z).
Правила де Моргана:
x ∨y = x · y
x · y = x ∨y.
x = x
x = x ⊕1
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).
Будем считать, что конъюнкция выполняется раньше, чем
дизъюнкция и сумма по модулю 2. Благодаря этому и свойству
ассоциативности, часть скобок можно опускать. Имеют место
следующие очевидные утверждения:
x1 · x2 · . . . · xn = 1 ⇐
⇒∀i(xi = 1),
x1 ∨x2 ∨. . . ∨xn = 1 ⇐
⇒∃i(xi = 1).
9


1.2
Теорема о разложении функции алгебры логики по переменным. Теорема
о совершенной дизъюнктивной нормальной форме
Определение. Определим функцию x в степени сигма следующим образом:
xσ =

x, если σ = 1,
x, если σ = 0,
то есть x1 = x, x0 = x.
Легко видеть, что xσ = 1 ⇐
⇒x = σ.
Теорема 1.2.1 (о разложении функции алгебры логики по переменным). Для любой функции алгебры логики f(x1, . . . , xn)
и для любого k (1 ≤k ≤n) справедливо следующее равенство:
f(x1, . . . , xn) =
xσ1
1 · xσ2
2 · . . . · xσk
k · f(σ1, . . . , σk, xk+1, . . . , xn).
=

(σ1,. . . ,σk)∈Ek
2
Здесь имеется в виду дизъюнкция 2k выражений, построенных для каждого набора длины k.
ασ1
1 · ασ2
2 · . . . · ασk
k · f(σ1, . . . , σk, αk+1, . . . , αn) =
Доказательство. Для любого набора ˜
α = (α1, α2, . . . , αn) вычислим значение правой части на этом наборе. Как только хотя
бы один из сомножителей будет равен нулю, вся конъюнкция
обратится в нуль. Таким образом, из ненулевых конъюнкций
останется лишь одна  та, в которой αi = σi для i = 1, . . . , k, и

(σ1,. . . ,σk)∈Ek
2
= 0 ∨. . . ∨0 ∨αα1
1 · αα2
2 , · . . . · ααk
k · f(α1, α2, . . . , αn),
а в силу того, что xx
=
1, последнее выражение равно
f(α1, α2, . . . , αn), то есть совпадает со значением левой части
на наборе α. Теорема доказана.
10


Доступ онлайн
от 160 ₽
В корзину