А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726)
Текст из файла
А. А. Вороненко, В. С. ФедороваДИСКРЕТНАЯ МАТЕМАТИКА.ЗАДАЧИ И УПРАЖНЕНИЯ С РЕШЕНИЯМИУчебно-методическое пособиеМосква — 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Задание.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
