А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями

А. А. Вороненко, В. С. ФедороваДИСКРЕТНАЯ МАТЕМАТИКА.ЗАДАЧИ И УПРАЖНЕНИЯ С РЕШЕНИЯМИУчебно-методическое пособиеМосква — 2012УДК 519.71Печатается по решению Редакционно-издательского советафакультета вычислительной математики и кибернетикиМГУ имени М. В. ЛомоносоваРецензенты: Алексеев В. Б., профессор, д. ф.-м. н.Дьяконов А. Г., доцент, к. ф.-м. н.Вороненко А. А., Федорова В. С.Дискретная математика.

Задачи и упражнения с решениями: Учебнометодическое пособие. — М.: Издательский отдел факультета ВМиК МГУ имениМ. В. Ломоносова (лицензия ИД № 05899 от 24.09.2001 г.); МАКС Пресс, 2012. —103 с.В пособии представлены решения задач, входящих в программу аудиторных занятий по по курсам «Дискретная математика» и «Дополнительные главы дискретной математики», читаемых студентам факультета вычислительной математики икибернетики МГУ имени М. В.

Ломоносова. Все задачи взяты из учебника Г. П. Гаврилова, А. А. Сапоженко «Задачи и упражнения по дискретной математике» (М.:Физматлит, 2004). Пособие рассчитано на студентов первого и третьего курсов.Авторы выражает благодарность Д. Кафтан, Д. Чистикову, ??? за помощь в подготовке пособия.E-mail: mk@cs.msu.ruc Факультет вычислительной математики икибернетики МГУ имени М. В. Ломоносова,2012c Вороненко А. А., Федорова В. С. 2012Часть 1.Курс «Дискретная математика»Занятие № 1.1Функции алгебры логики. Формулы.Существенные и фиктивные переменныеI.1.18(1). По заданным векторно функциям f (x1 , x2 ) и g(x1 , x2 ):αef = (0010), αeg = (1000), построить векторное представление функцииh(x1 , x2 , x3 ) = f (x1 , x3 ) & g(x2 , x1 ).J Составим таблицу значений соответствующих функций:x100001111x200110011x3 f (x1 , x3 ) g(x2 , x1 ) h(x1 , x2 , x3 )00101010000010000100100001001000Откуда получаем αeh = (0000 0000).II.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.J Составим таблицу значений соответствующих функций:x00001111y00110011z A3 B3 A4 B40 1 0 1 01 1 0 1 00 1 0 1 01 1 1 0 10 0 1 0 11 0 1 1 00 1 0 0 11 1 0 1 03Из таблицы видно, что обе пары формул не эквивалентны.II.1.20(4). Построив таблицу для функций x∨(y ∼ z) и (x∨y) ∼ (x∨z),убедиться в справедливости их эквивалентности.J Составим таблицу значений соответствующих функций:x00001111y00110011z x ∨ (y ∼ z) (x ∨ y) ∼ (x ∨ z)011001000111011111110111Из неё видно, что исходные функции эквивалентны.II.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).J1. С помощью преобразований приведем формулы A и B к одинаковому виду:A =========B ===(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,(x · y → x) → y =(x · y ∨ x) → yx → y;В преобразованиях использовалось тождествоx · K1 ∨ x · K2 = x · K1 ∨ x · K2 ∨ K1 · K2 ,4справедливое для любых элементарных конъюнкций K1 , K2 .2.

С помощью преобразований приведем формулы A и B к одинаковому виду:A =====B ======(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,(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. II.1.28(1, 2). Указать все фиктивные переменные функции f :1) f (ex3 ) = (10101010);2) f (ex3 ) = (01100110).J1.

Имеем: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 является единственной фиктивной переменной рассматриваемой функции.I5I.1.31(1, 2).1. Доказать, что если у функции f (exn ) (n > 1) имеются фиктивные переменные, то она принимает значение 1 на чётном численаборов.2.

Выяснить, верно ли утверждение, обратное к 1.J1. Пусть x1 — фиктивная переменная.Тогда, если на наборе (α1 , α2 , . . . , αn ) функция принимает значение 1, то на наборе (α1 , α2 , . . . , αn ) функция также принимаетзначение 1.Таким образом, число наборов переменных, на которых функцияпринимает значение 1, кратно 2.2. В общем случае обратное утверждение не верно. Например, функция f = x1 ⊕ x2 принимает значение 1 на чётном числе наборов,но не имеет фиктивных переменных.II.1.33(1, 2).

Выяснить, какие переменные функции f являются существенными:1) f (ex4 ) = (1001 0011 0011 0010);2) f (ex4 ) = (0110 0111 0111 0110).J1. Функция f (ex4 ) = (1001 0011 0011 0010) принимает значение 1на нечётном числе наборов, поэтому фиктивных переменных у неёнет.2. Функция f (ex4 ) = (0110 0111 0111 0110) не имеет фиктивных переменных, так как0 = f (0, 0, 0, 0) 6= f (0, 0, 0, 1) = 1 ⇒ x4 − существенная переменная;0 = f (0, 0, 0, 0) 6= f (0, 0, 1, 0) = 1 ⇒ x3 − существенная переменная;0 = f (0, 0, 1, 1) 6= f (0, 1, 1, 1) = 1 ⇒ x2 − существенная переменная;0 = f (0, 0, 1, 1) 6= f (1, 0, 1, 1) = 1 ⇒ x1 − существенная переменная.

II.1.34(5). Выяснить, при каких n (n > 2) функция f (exn ) = (x1 | x2 ) ⊕(x2 | x3 ) ⊕ . . . ⊕ (xn−1 | xn ) ⊕ (xn | x1 ) зависит существенно от всех своихпеременных.J Если n=2, то f = (x1 | x2 ) ⊕ (x2 | x1 ) ≡ 0, а следовательно, все переменные у неё фиктивные.Покажем, что при n > 3 у функции нет фиктивных переменных.Функция инвариантна относительно циклического сдвига переменных,поэтому все переменные либо существенны, либо фиктивны.

Посколькуf (1, . . . , 1) = 0, f (0, 0, 1, . . . , 1) = 1, то получаем, что все переменныеданной функции существенны.I6Занятие № 1.2ДНФ, КНФ, СФЭI.2.3(3). Представить в виде совершенной ДНФ следующую функцию:f (x, y, z) = (0101 0001).J Рассмотрим наборы, на которых функция принимает значение 1 (cоответстующие строки таблицы выделены):x00001111y00110011z01010101f01010001Совершенная ДНФ функции имеет вид:f (x, y, z) = x · y · z ∨ x · y · z ∨ x · y · z.II.2.12(1). Применяя преобразования вида A = A·x∨A·x и A∨A = A,построить из заданной ДНФ функции f (exn ) её совершенную ДНФ:f (ex3 ) = x1 x2 ∨ x3 .Jf (ex3 ) ====x1 x2 ∨ x3 =x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x3 ∨ x1 x3 =x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 =x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 . II.2.18(1).

Найти длину совершенной ДНФ функции f (exn ) (n > 2):_nf (ex )=xi xj .16i<j6nJ По определению, длина совершенной ДНФ равна количеству наборов,на которых функция принимает значение 1.В нашем случае легче посчитать число наборов, на которых функцияпринимает значение 0:7— n наборов, на которых ровно одна переменная равна 1,— 1 нулевой набор.Вычитая из общего числа наборов количество наборов, на которыхфункция принимает значение 0, получим длину совершенной ДНФ:2n − n − 1.II.2.4(5). Представить в виде совершенной КНФ следующую функцию:f (x, y, z) = (0101 1101).J Рассмотрим наборы, на которых функция принимает значение 0 (cоответствующие строки таблицы выделены):x00001111y00110011z01010101f01011101Совершенная КНФ функции имеет вид:f (x, y, z) = (x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z).IЗадание.