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


ВЫСШЕЕ ОБРАЗОВАНИЕ - БАКАЛАВРИАТ

серия основана в 1 996 г.





В.Б. АЛЕКСЕЕВ


ДИСКРЕТНАЯ МАТЕМАТИКА
УЧЕБНИК




                           Рекомендовано Межрегиональным учебно-методическим советом профессионального образования в качестве учебника для студентов высших учебных заведений, обучающихся по укрупненной группе специальностей 01.00.00 «Математика и механика» (квалификация (степень) «бакалавр») (протокол № 9 от 28.09.2020)



znanium.com

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

УДК [519.71+519.1](075.8)
ББК 22.176я73

     А47











      Алексеев В.Б.
А47 Дискретная математика : учебник / В.Б. Алексеев. — Москва :

       ИНФРА-М, 2022. — 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

                Введение





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

3

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

4

Глава 1





                Функции алгебры логики





            1.1  Функции алгебры логики. Равенство функций. Тождества для элементарных функций



1.1.1 Функции алгебры логики.
Определение. Пусть E2 = {0,1} — множество, состоящее из двух элементов. Тогда положим E% = {(о1,..., aₙ) |V(ai E E₂)}. Всюду определённой булевой функцией назовём отображение f (x ।,..., xₙ) : E% ^ E2. Множество всех булевых функций обозначим P2.

   Булеву функцию можно задать таблично. Например, для n = 1:

                          x
                          О’
                          1

О о о

1 x x
1 б 1
1 1 О

   Здесь в первом столбце указаны возможные значения переменной, а в следующих столбцах все четыре возможных варианта значений функции от одной переменной. В первой строке указаны обозначения этих функций. При этом функция 0 называется константой нулём, функция 1 — константой единицей, функция x — тождественной, а функция X — отри-

5

цамием x. Для последней функции используется также иное обозначение: x = —x.
   Для n = 2 рассмотрим следующие функции:

x у f 1 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 и у имеются четыре комбинации их значений, которые можно рассматривать как двоичную запись натуральных чисел. При заполнении таблицы удобно выписывать наборы значений переменных в порядке возрастания соответствующих натуральных чисел. Указанные функции имеют специальные названия и обозначения:
   f 1 — дизъюнкция, фующия «или»: f 1 = x V у;
   f2 — конъюнкция, фующия «и»: f2 = x N у = x & у = x • у = xy;
   fз — сложение no модулю f (исключающее «или»): f3 = x ф у;
   f4 — имплUKayxsi: f4 = x ^ у;
   f5 — эквивалентносту: f5 = x ~ у;
   f6 — штрих Шеффеуа: f6 = x\y,
   f7 — стрел fa Пирса: f7 = x ^ у.
Лемма 1.1.1 (о числе слов). В алавите A = {a 1,..., aᵣ} из r букв можно построить ровно rm различных слов длины, т.
тказательство. Проведём индукцию по т. Для т = 1 утверждение очевидно. Пусть утверждение леммы верно для т = k, то есть существует ровно rk различных слов длины k. Для каждого такого слова длины k существует ровно r возможностей добавить одну букву в конец. Поэтому число различных слов длины k + 1 получитея равным r • rk = rk⁺¹. Лемма доказана.                                                  □
   Рассмотрим таблицу некоторой функции алгебры логики от 11 переменных:

6

x1    x2    . .            f   
0         0 . ..    0   a 0    
0         0 . . 1       a 1    
...     ... . . ...     ...    
1   1       . .       1 a 2 --1

   По лемме 1.1.1 число различных наборов значений переменных равно 2п, то еств в таблице 2п строк. Для задания функции необходимо и достаточно определитв её значения на всех 2п наборах. Таким образом, получаем, что всего различных функций от 11 переменных столько, сколько существует различных наборов из нулей и единиц длины 2п, т.е. 2²".
   Используя последний факт, можно, например, получить оценку числа функций от 10 переменных. Всего таких функций 2²¹⁰ = 2¹⁰²⁴ > (2¹⁰)¹⁰⁰ > (1000)¹⁰⁰ = 10³⁰⁰. Таким образом, при росте числа переменных число функций возрастает очень быстро.

1.1.2 Равенство функций.
В обычной алгебре справедливо равенство x+y—y = x, несмотря на то, что в левой части записана функция от двух переменных, а в правой — от одной. Таким образом, функции от разного числа переменных могут быть одинаковыми, что даёт повод ввести понятие существенных, и фиктивных переменных.

Определение. Переменная xi называется существенной пе-рехенной функции алгебры логики f(х 1 ,...,хп), если существуют такие а 1,..., ai- 1, ai₊₁,... ,ап е E₂, что

f ⁽а 1 , . . . , ai- 1, ⁰, ai +1 , ... , ап⁾ = f ⁽а 1 , . . . , ai- 1, ¹, ai +1 , ... , ап⁾ .

(Такие наборы, отличающиеся значением лишь одной переменной xi, называются соседними хо xi). В противном случае переменная xi называется фиктивной (или несущественной).

   Если xi — фиктивная переменная функции f, то значение функции f на наборе однозначно определяется значениями

7

ai,..., ai-1, ai+1,..., aₙ, то есть функцию f можно рассматривать как некоторую функцию g (x ₁,..., xi-₁ ,xi+₁,..., xₙ) (фиктивную переменную можно удалить). Наоборот, таблицу любой функции можно расширить введением любого числа фиктивных переменных.
Определение. Две функции алгебры логики называются равными, если одну из них можно получить из другой путём добавления и изъятия любого числа фиктивных переменных.

1.1.3 Формулы.
Определение. Пусть имеется некоторое множество функций
A = {f 1(... ) ,f2(... ) ,...,fn (... ),... }.
   Введем понятие формулы над A:
   1) Любая функция из A называется формулой над A.
   2)    Если f (x ₁,..., xₙ) е An Hi для л юбого i — либо переменная, либо формула над A, то выражение вида f (H₁, H2,..., Hₙ) является также формулой над A.
   3)    Только те объекты называются формулами над A, которые можно построить с помощью пунктов 1 и 2 данного определения.
Замечание. Среди H₁, H2,..., Hₙ могут быть одинаковые.
   Будем считать, что каждая формула реализует функцию, которая определяется индуктивно следующим образом. Формуле из пункта 1) сопоставляется просто соответствующая функция. Функция для формулы из пункта 2) определяется так: на любом наборе значений переменных сначала вычисляются значения функций, соответствующих формулам H₁, H2,..., Hₙ (по предположению индукции эти функции уже определены), а затем берется значение функции f на полученном наборе.
Определение. Две формулы называются эквивалентными, если реализуемые ими функции равны.

8

1.1.4 Основные эквивалентности.

Коммутативность:              Законы поглощения:               
x V y = y V x                 xVx=x                            
xy = yx                       Д' • Д' = Д',                    
                              •Лэ                              
x ф y = y ф x                 x V x = 1                        
x ~ y = y ~ x.                x ■ x = 0                        
                              xV1=1                            
Ассоциативность:              x ■ 1 = x                        
(x V y) V z = x V (y V z)     xV0=x                            
(xy)z = x(yz)                 x ■ 0 = 0                        
(x ф y) ф z = x ф (y ф z).    x ф 0 = x                        
                              x ф x = 0.                       
Дистрибутивность:             Другие эквивалентности:          
(x ф y) z = (xz) ф (yz)       x = x                            
(x V y) z = (xz) V (yz)       x = x ф 1                        
(xy) V z = (x V z) ■ (y V z). x\y = xMy                        
                              x J. y = x V y                   
Правила де Моргана:           x ^ y = x V y                    
x V y = x ■ y                 x ф y = (x ■ y) V (x ■ y)        
xMy = x V y.                  x ~ y = x ф y = (x ■ y) V (x ■ y)

    Будем считать, что конъюнкция выполняется раньше, чем дизъюнкция и сумма по модулю 2. Благодаря этому и свойству ассоциативности, часть скобок можно опускать. Имеют место следующие очевидные утверждения:
    x I ■ X2 ■ ... ■ xₙ = 1 ^^ Vi (Xi = 1),
    xi V x₂ V ... V xₙ = 1 ^^ 3i(xi = 1).


9

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


Определение. Определим функцию х в степени сигма, следующим образом:

х⁷

Хх, (х,

если а = 1,
если а = 0,

то есть х¹ = х, х⁰ = х.

    Легко видеть, что х⁷ = 1 ^^ х = а.

Теорема 1.2.1 (о разложении функции алгебры логики по переменным). Для любой функции алгебры логики f(х 1 ,...,хп) и для любого к (1 < k < n) справедливо следующее равенство:


  f (х 1, ...,хп) =
          \/     х⁷¹ • х⁷² • ... • х^ • f(а 1 ,...,ак,хк+1 ,...,хп).
     (а 1,... ,ак)ееk


Здесь имеется в виду дизъюнкция 2k выражений, построенных кля каждого набора клины к.

Доказательство. Для любого набора а = (а 1, а2,..., ап) вычислим значение правой части на этом наборе. Как только хотя бы один из сомножителей будет равен нулю, вся конъюнкция обратится в нуль. Таким образом, из ненулевых конъюнкций останется лишь одна — та, в которой ai = ai для i = 1,..., к, и

       V         а ⁷¹ ■а ⁷ ⁷²
(71,... ,7k) еЕk

  . ■ а⁷ ■ f (а 1, ...,ак, ак+1, ...,ап) =


= 0 V ... V 0 V а а¹ • а а², •... • окф • f (а 1, а 2,..., ап), а в силу того, что хх = 1, последнее выражение равно f (а 1, а2,..., ап), то есть совпадает со значением левой части на наборе а. Теорема доказана.                          □

10