А.А. Вороненко - Решение избранных задач по курсу дискретной математики

УДК 5 )9.7) !075.8) ВВК 22. ! 7бя73 075 Занятие №1 7)енаюаенгоя но реигениго Редавяионно-юдательского оовегва фалзогьнгета выниояингеяьной гиагггеиангики и кибернетики :)Гоехевекоео гоеударемвенногоунивереигкема имени гУ»7). Ломоносова Рецензенты: г)яехееев В.)2 — д.ф.-м.н., профессор; Дьяконов Лд; — к.ф.-м.н., доцент воропенко А.А. Рамзе»»ие избраииыв задач по курсу дискретной математики: Учебно-методическое пособие — Мх Издательский отдел факультета ВМнК МГУ имени М.В, Ломоносова )лицензия ИД Х 05899 от 24.09.200 ! т,); МАКС Пресс, 2009.

— 5б с. !ВВН 978-5-89407-Зб5- ! )ВВ)х) 978-5-3 ! 7-02843-5 Г) пособии представлены решения задач, входящих в программу аудиторных занятий по курсу дискретной математики. Все задачи взяты нз у гебпнкв Г.П. Гввриш>ва, А.А. Сапе»конка е3алачн н упрагкнення по дискретной мьтемжнке г !М.: Фнзматлнт, 2004). Пособие рассчитано на студен.гов первого курса. Автор выражает благодарность студентам 82 Дорогуш, Д. Чистякову, в закис 'Г. ! )вгвнстян) за помощь в подготовке посооня.

УДК 508700758) ЬЬКо' )тб 7) 18Вй) 978-5-89407-3б5-1 1ЯВ)з) 978-5-317-02843-5 Неучиея бебе»метеке ййГУ аа666 62019249 Й Фдк)лыьт вычяелительиоГг миг»витию! и кябериетвки МГУ имени М.В. Лоиоиоеоие. 2009) © А.А. Вороненка, 2009 ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ. ФОРМУЛЫ. СУГЦЕСТВЕНН)з)Е И ФИКТИВНЫЕ ПЕРЕМЕННЫЕ 1.1.18(1). По фупкцияь» 2(х» жз) и д(я» яз) задщпгым векторно гзг = (0010), гз = (1000), построить векторное представление функции г»(*ы я21 яз) = .) (яы яз) 8с 9(тз~ х»). е Составим таблицу значений соответствующих функций: Откуда получаем стх = (00000000). $» 1.1.10(8,4), Построив таблицы соответствующих функций, выяснить.

эквивалентны ли формулы А и В: 8.Аз=я (Ь я) р в),.Вз=-(згУЬ л)).(таю); 4. А» = (ж»г,й) ьг(х з) ~(хб)й'я), В»=я'(р я)хуже — » ° Составим таблицу значений соответствующих функций: Из таблицы видно, что формулы Аз и Вз не эквивалентны, а формулы А» и В» эквивалентны. 1.1.20(4). Построив таблипу для функций хЧ(у - л) и (тУр) ° (жУя) убедиться в в справедливости их эквивалентности.

< Состелнм таблицу значений соответствующих функций: (т у) (х у-( Озд)1= ( Чр) (х д (хву)Ух у твй= (хор)- (х у (х у~/х р)Ч(хЧд) (х дух-р)) = (х У у) - (2.". р У х д У х у) = (х7 у) У (2 У х р) = х ДУ2~х р= тих р= хЧр = А х — ~ у, В=(хр(хд Ч х) у У (х -~ р в)) - ((х -~ у) - в) =- удхнр з) (х.рчз) = Уу )-Ф уЧ )= ° гЧу яр х у г) Ч(х(уЧ з)р(худ)) = д ХЧу зЧх в, А = (х — (х = (х = (и Из нее видно, что исходные функции эквивалентны. 1,1,21(1,2). Используя основныо зквввалентности доказать эквивалентность формул А и В: 1. А = (т — у) — (х р (х 9 р)), В = (х у -+ х) -+ д; 2.

А = ( у ч (х р 4) ((х д) ), В = ( ' у) Е (у В 3). «Ф 1. В = (* у) Е (д Е х) = =- (х ~ у) (у - з) У Ф ~ Й (у 9 ) = (х ч д) (у ' 3 ~l у ' й) Ч х ' у ' (у ' х ~I у " г) = = х д.зЧх д Рдр зЧх.р з= — У д.рру.гЧх д г= — х р ° зЧр ° вУх ° в. в 1.1.28(1,2). Указать все фиктивные переменные функции 1: 1.

~(хз) = (10101010); 2. )'(т ) = (01100ПО). ° я 1. Имеем; г(0,0,0) = ДО, 1, О) = У(1, О, 0) = Х(1, 1, О) =- 1, У(О,О, 1) = У(0, 1, 1) = У(1, О, 1) =- У(1, 1, 1) = 0 откуда видно, что значение функции зависит только от значения переменной хз. 2. Имеем: У(О,О,О) = У(1,0,0) У(0,0,1) =У(1,0,1) У(0,1.,0) = У(1,1,0) ДО,1,1) = Д1,1,1), откуда видно, что значение функции не зависит от значения переменной хь На наборах (ООО) и (001) функция принимает различные значенпя, откуда следует, что переменная хэ существенная. На наборах (000) и (010) функция принимает различные значения, откуда следует, что переменная хг существенная. Ф' П.1,31(1,2). 1.

Доказать, гго если у функции у'(х") (и )» 1) имеются фиктивные переменные, то она принимает зпа ~ение 1 на четном числе наборов, 2. Выяснить, верно ли утверждение, обратное к 1. 1, Пусть х~ — фиктивная переменная. Тогда если на наборе (ам ггг,..., сг„) функция принимает значение 1, то на наборе (сгм сгэ,...,сг„) функция также принимает значение 1. Таким образом, чисчо наборов переменных, на которых функция принимает значение 1, кратно 2.

2. Обратное, вообще говоря, не верно. Например, функция у = х1 (Э хз принимает значение 1 на четном числе наборов, но не имеет фиктивных переме1п1ых. 1.1.33(1,2). Выяснить, какие переменные функции 1 являются существенными: У( 4) (1ДЦ УЦ1 ЦЦ1 0010). 2, у(х4) = (0110 0111 0111 0110). ° я 1. Функция 1(х4) = (1001 ООП 0011 0010) принимает значение 1 на нечетном числе наборов, позтому фиктивных перемсш1ых у пее нет; 2. Функция у(х4) = (0110 0111 0111 0110) не имеет фиктивных переменных, так как 0 = )'(О, О, О, О) ф у(0, О,О, 1) = 1 =~ х1 — существенная переменная О = у (О, О, О, О) ф )'(О, О, 1, 0) = 1 =~ хз — существенная переменная 0 = )'(0,0,1,1) ~ )'(0,1,1,1) = 1 =~ хз — существенная переменная 0 = )'(0,0,1,1) ф Д1,0,1,1) = 1 =~ х» — существенная переменная. в 1.1.34(5).

Выяснить, при каких и, (и > 2) функщ1я ~(хх) = (х1 ! хз) Ы (хз , 'хз) 9... 9 «х„1 ~ х„) 9 (х„~ х1) зависит существенно от всех своих переменных. Л Если п=2, то 1' =- (х1 ~ хз) 9 (хз ~ х1) = О, а следовательно, все переменные у нее фиктивные. Покажем, что при и > 3 у функции нет фиктивных перемоиных. Функция инвариант11а относительно циклического сдвига перемегп1ых, позтому все переменные либо существенны, либо фиктивны.

«(1'„..., 1) = О, ~(0, О, 1,, 1) = 1 ~ все существенные. в' Занятие №2 ДНФ, КНФ, СФЭ 1.2.3(3). Представить в совершенной д.н.ф. следующую функцию: 2 (-3) ~ Рассмотрим наборы, на которых функция принимает значение 1 (соответстующие строки таблицы выделены к11рсиаом). х У 2!Е :„'ЙЗ Соверше1п1ая д.н.ф. функции имеет вид: у (х, .р, 2) = х й р й 3 '11 х й д й 2 ч х й у й ". в 1.2.12(1). Применяя преобразования вида А — А УЧА х и А'~1А = А, построить из заданной д.н.ф, функпии 1(х') ее совершенную д н ф: у(х') = х1хз ~/ тз.

ДХЗ) = Х1ХЗЧХЗ= — Х1212ХЬ 4 Х1Х2ХЗ ~' Х1ХЗ 1~ ХГХЗ Х1Х2ХЗ Ч Х1Х2ХЗ Ч Х1Х2ХЗ ч Х1Х2ХЗ '~ Х1ХЗХЗ Ч Х1Х2ХЗ = Х1Х2ХЗ Ч Х1ХЗУЗ Ч Х1Х2ХЗ Ч Х1Х2ХЗ 4 Х1ХЗХЗ. З~ 1.2,18(1). Найти длину совершенной д.п.ф. фуш1ции У(х"): У(х ) = ~/ 1СЗ<зяп ~ Длина совершенной д.н.ф. равна количеству наборов, на которых функция принимает значение 1. Б нашем случае легче посчитать число наборов, нз которых функция принимает значение 0: — и наборов, па которых ровно одна переменная равна 1, — 1 нулевой набор.

Вычитая из общего числа наборов количество наборов, па которых функция принимает значение О, получим длину совершешюй д,п.ф.: :$ и 2 — и — 1, 1.2.4(5). Представить в совершенной к.н.ф. следующую функцию: ~(х~) = (01011101). О О О ОО1 ° Ф Упростим формулу: Составим систему: 1.2.3(3). У(, 3) = (01010001) ° е Рассмотрим наборы, на которых функция принимает значение 0 (со- ответстукяцие строки таблзщы выделены курсивом). Совершенная к.н.ф. функции имжт вид: Д(х, д, з) = (х ч и ч з) (х ч й ч з) (х ч й ч з), Построить СФЭ с уменьшением числа элементов для функций: 1.1.17(1). ((х + р) ч (х Ю г)) (р ~ г). Я -Р)ч(*е )) Ь~ )= ((х Ч р) Ч х: Ч хз)) (р Ч 2) = (Ф Ю) ч 2)) (Р ч =) = йч з = д8~з.

Строим схему иэ функциональных элементов: и У Е о Дх, О, з) = (х ч и ч з) (х ч д ч з) (х ч й ч з) = = (х ч з)(р ч х) = = хдчз. Строим схему иэ функциональнык элементов: х У х Занятие № 3 Полиномы и линейные оуункции 1.2,22(5). Методом неопределенных коэффициентов найти полипом Жегалкипа для функции Дахз) = (ОП01001). ° Для х полипом Жеталкина им~ет вид: сз 9 Дх~ В дзхз 9 4зхз Ь '11х1хз эз 7зх|хз ~В 7зхзхз 9 сх1хзхз 1 1 1 ,'1=а9А9,бз9Рз9 У19.узВ Уэбб Отсюда получим коэффициенты полинома Жегалкина: о = 01 В, = 1, В, = 1, Вз = 1, у, = О, уз = О, уз = О, б = О Следовательно, искомая функция у = х4 9 хз Ф хз.

1,2.23(7). Преобразуя вектор значений функции Дх~) = (0000 0100 0110 0111), построить полипом Жегалкина для этой функции. ° я Будем преобразовывать вектор значений функции так (с. 53): Над векторами из В~ определяется (индукцией по и) операция Т. — Если п = 1 и а = (ао, а1), то Т(а) = (ао, ао б. 4х1). — Предположим, что операция Т уже определена для каждого вектора 4р из Вз, и рассмотрим произвольный вектор а из Вз "'. Пусть о = (Д,А, ° °,Я вЂ” ь'уор 11 ° 'узц-л) и Т(А,А,,А -1) = (4),А, Аз.-4) Т('уо,'уь..., "~х 1) = (ео,еь..., ез 1) (б, и е, по индуктивному предположению известны). Тогда Т(с1) = (доц дь -, бз.-41 А) 9 ео, б4 6~ еь бз..1 9 ез -1).

В процессе преобразований будем получать векторы: (0000 0100 0110 0111), (0000 0100 0111 0110), (0000 0101 0110 0111), (ОООО 0101 ОПО 0001), (ОООО 0101 0110 0100). Получим вектор коэффициентов полинома Жегалкина: 1ру = (ОООО 0101 0110 0100).

Таким образом, У = хзх4 Ю хзхзх4 6 хгх4 4в хгхз 4в Х1хзх4 в 1.2.28. Найти функцию у(х"), у которой длина ползпюма Жегалкипа в 2" раз превосходит длину ее совершенной д.н.ф. (и > 1). < Так как длина полинома не превосходит 2", то длина совершенной д.н.ф, не превосходит 1. Зпачитц длина полинома — 2", а. вектор коэфф ц * ц 111 = (1111...1111~.Т Ц * р . р функции г = (Х1 9 1) ... (х„ Ю 1) = х1 ... х„.

В 10 П.3.1(б). Представив функцию у = ((х -+ р)(р — рх)) з полиномом, выяснить, является ли она линейной, я Преобразуем функцию у; У = Их р)(р х))-з ((х Ч р)(р ~l х) з) ((х р) - з) = ХФрФз Следовательно, функция у линейна. 9» П.3.7. 1) Показать, что если функцию Дх") можно представить в виде ДР) = Х„Я рд, где у не зависит от х„ц то ~Уу~ = 2" '. 2) Показать, что если Г' лннейна и отлична от константы, то ~1уу~ = 211 1 < 1) При фиксированных хь, .., х„1 функция Х„9 р принимает значение 1 ровно для одного значения х„. Следовательно, ~Жу~ = 2' '. 2) Так как функция у лицейна и отлична от константы, то можно выделить слагаемое хь.

Оставшаяся часть не зависит от хзо следовательноц можно воспользоваться фактом, доказанным в пункте 1. Таким образом (Уу( = 2" ', П.3.2(10). Выяснить, является ли линейной функция с вектором значений ау = (0110 1001 0110 1001). ° и 1-й способ: Найдем вектор,Ву коэффициентов полинома Жегалкнца для функции г". Получим 3г = (0110 1000 0000 ОООО). Отличны от нуля лишь компоненты дьА,А с номерами, являющимися степенями двойки, Следовательно, функция линейна.