Главная » Просмотр файлов » Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике

Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 10

Файл №1055357 Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике) 10 страницаГ.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357) страница 102019-04-28СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

В самом деле, если, например. 1(0, хг) = сг, то функция г"(1, хг) должна быть равна тождественно а; но тогда (см. формулу (2)) (х~ при о = О, г(х ) =хгогхго= )— ~хг при о =1, т.е, фУнкциЯ 1(х ) зависит несУщественно от пеРеменной хг, что противоречит условию.

наложенному на функцию Г" (ха). Палее, так как функция 1(хг) существенно зависит от обеих переменных. то 1"(О, х ) ф 1'(1, хг) и 1'(хы 0) ф 1'(х, 1). действительно, если, например, ДО, хг) = 1(1, хг), то, используя формулу (2), получаем (ср. с решением примера 4): 1"(х ) = хг1"(О, хг)'дхг1'(1, хг) = хг1"(О, хг) Ч У хг1'(О.,хг) = (хг Ч хг) 1'(О, хг) = 1 4с 1'(О,хг) = 1(О,хг), т.е. переменная хз фиктивная. Это противоречит условию, наложенному на функцию 1(хзг). Из всего сказанного относительно функций 1(0, хг), 1'(1, хг) 1'(хы 0) и 1'(хы 1) следует,. что ДО, хг) = хг, .1'(1, хг) = = хго = хг — — хг, 1 (хы 0) = хг и ~(хы Ц = х' = х'.

Отсюда вытекает, что у функции у(юг) семь разных подфункций: она сама., О., 1, хсы у ец Специальные представления булевых функции 45 хы хг и х,. Нетрудно получить и выражение для функции 1(х ), воспользовавшись, например, формулой (10): з (х ) = хзх2 и хзх2 = (Х1 ч' 1) Х2 ® хз(Х2 йз 1) = хгх2 ~~ Х2 л' хзх2 ~~ хз х! ® 22 (Х4 хг, если П = О, = хз ег хг е4 и ев 1 = 4( (хзйхг, если п=1.

(Здесь, как и выше, мы использовали эквивалентности х, = х" Ю 1, а также очевидные тождества х = х - и = хааа.й 1.) 2.1. Рассматривая соответствующую компоненту функции 7'(хп) как функцию, зависящую от всех переменных хы хг, ..., Хп, представить ее в векторной форме: 1) з (Х ): Хз + (Х2 чг Хзхз), Х2-КОМПОНОНту 2) ((х ) = Хзхг ~ (Хг — 4 хгхз), хз-компоненту; 3) 7 (х ) = (Уз '4 х2 ~l хз) 4 (хз 4 (У2 е хз)), хыкомпоненту; 4) 2'(х ) = (01110100), хыкомпоненту; 5) 2 (х ) = (11001110), хг-компоненту; 6) з (х ) = (10011110), хз-компоненту; 7) з (х ) = (хз ез хг) — > (хз — 4 хзх4), хгхл-компоненту; 8) з (х ) (хз дх2хз Ч х4) аг (хзхгхз е х4), х1У2хз компоненту; 9) 7'(х~) = (0101011011100011), Угхв-компоненту; 10) ((х ) = (1101101100001001), хгхзх4-компоненту.

2.2. Используя хз — и У,-компоненты функции 7" (хп), построить в векторной форме ее х -компоненту, причем эту компоненту следует рассматривать как функцию, зависящую от всех перемен- НЫХ Хмхг~ . ~ Ха' Ц (1( 3) х > хз 74(хз) — Х2 хз кОмпоненту 2) л ( ) х е (х ) хз хз, хыкомпоненту; 3) лз(.-з) (00111100), фх ) = (Ш10000), хг-компонентУ ) 2(хз) (10101111) у2(хз) х, ~ хз, уз-компоненту; 5) ~~(Х ) =Т ЯЗХ4,(~(х ) =Х2 '4Х4) Х2 У 6) у2(х4) — х ) х Х4 Д(х4) = Узхзхв, х4"кОмшшснту~ 7) зо(х ) = хгхз ~Э х4, з'4 (х ) = (1011011110110111), хз-компоненту.

2.3. Представить в совершенной д.н.ф. следующие функции: 1) з (Х ) (хз ПХ2) е Хз 2) з (х ) (Х1 е Х2) е (хз ~ хгхЗ)~ 3) Д(х з) (01010001) 4) Д(х з) (01111000) 5) з'(х~) = (10001111); 6) з'(х~) = (хз -4 хгхзхл) (хз — + хзхг); 7) 1(х~) = (хзйзхг) (хз — 4 хгх4); 8) 1(х~) = (0100100011000010); 9) 7(х~) = (1000011100110001); 10) 7(х~) = (1100100010010011).

46 Га. 1. Способы задания и свойыпва угупкиий ааеебрь~ возики 2.4. Представить в совершенной к.н.ф. следующие функции: 1) 7(х~) = хг 9 хг, 2) 7(хг) = хе .( хг., 3) 1(х') =х,хг гх,хз 1х,х,; 4) Дх') = х,х, Юхе; 5) 7'(х з) (01011101). 6) 7(х з) (0010П 10 7) 7(х ) = (хг У хг У хз) . х4 У хгхгхз,' 8) 1(х ) = хг — > (хг — > хзх4); 9) 7(х ) = (010111110111001Ц: 10) 7(хв) = (0110111011100101).

2.5. Представить в указанной форме соответствующую компонен- ту функции 1(хо) (рассматривая эту компоненту как функцию от «оставшихся» переменных): 1) 1(х ) = хгхг -Ф хз, хз-компоненту в совершенной к.н,фц 2) У(хз) = (хз ~ хг) хз, хз-компоненту в совершенной д.н.фб 3) ((х ) = хгхг (хг тз), хг-компоненту в совершенной д. н. фд 4) 7(х ) = (11101101), хг-компоненту в совершенной д.

н. ф.; 5) 7(х5з) = (01011011), хз-компоненту в совершенной к.н.фл 6) Дхха) = (хг М хг Ч хз)х4 Н хгхгхз, хгхз-компоненту в совершен- ной д. н. фл 7) У(хд~) = хг — > ((хгхз -+ х4) — > хг), хг-компоненту в совершен- ной к.

н. фд 8) У(х ) — ((хг ~ хг) (хз) ~ (хг.(х4), хз-компоненту в совершен- ной к. н. фд 9) Дх~) = (0110111010110111), хгхв-компоненту в совершенной д. н. ф.; 10) 7(х~) = (1011011101111000), х4-компоненту в совершенной к. н. ф. 2.6. Показать, .что число различных подфункций у функций 1" (хи) и д(ха) одинаковое, если: 1) функция д(ха) получается из функции 7(ха) переименованием переменных без отождествления; 2) функция д(х") получается из функции Д(х") заменой некото- рых (быть может, всех) переменных на ик отрицания; 3) д(хп) = 1'(х"); 4) функции 1"(х") и д(х") двойственные.

2.7. Подсчитать число различных подфункций у функции Дхо), хд- и хюкомпоненты которой известны (напоминаем, что подфунк- ции функции Д(х") следует рассматривать как функции, зависящие от всех переменных хы хг, ..., х„): 1) Д(хо) =хг 'д...'~хп, Й(х, ) = 1 (и Э 2); 2) уо(х") = хг 61 .. 61 ха Л(хп) = хг бз .. 6зхп (и ~ )2), 3) 1о(х ) =*я . хо Л(х ) = хг ..хо (и 3 2); 4) уо(хп) = тг ..хоЧхг...хп, Д(хп) = хг...х, (и > 2); 5) 1о(х ) = хг . хо; Л (х ) = хг у ... у х, (и 3 2); 5) Д(х ) =гг дхп Л(х ) хз о ° Лхо (п~)3)~ у г.

Саьциальиью предстпавлеиин булевых функций 47 7) уа)Хь) = ХЗ...Хь, Д)Х") = Х2'4 ХЗ )П ~ )3); 8) Уо~1х о) = хз -+ х„, 21 1хи) = хз... х„1п > 3). 2.8. Найти число функций 11х"), удовлетворяющих условию: 2оо21х") = Я1х") при всех 4, у таких, что 1 < 1 < у < и. 2.9. Показать, что число различных функций 2'1х"), для которых данная функция 21хь) является цодфункдией, не меньше 22 — 122 — 1)2 1к < и).

2. Днзъюнктнвные н конъюнктнвные нормальные формы. ФоРмУла х,'агх;ьзо ... ггх;', где оь 6)0, 1), х, — хц х, — хь~ ььс11,2,...,п), к=1,2,...,г )г>1 и п>1), называется конъюнкцией иад множеством Х" = 1х1, хэ, ..., х„). Аналогично, формула х~,' 12 х~,' 42... 42х," называется диэьюнкцией над .ииожестаои Х".

Если х,, у- 'х;,„при у ~ к, то конъюнкция 1соответственно дизъюнкция) называется элементарной (сокращенно э. к. и э. д, соответственно). Выражения вида х, ' называются буквами. Число букв в э. к. 1и в э. д.) называется рангом э. к. 1соответственно э. д.). Константа 1 считается по определению э. к. нулевого раигоь а константа 0— э.

д. иулсоого ранга. Формула вида о~ К уК 12 12К 113) ( краткая запись 1„4 К4), где К; .. попарно различные элементарные конъюнкции 11 = 1, 2,..., 2) и э > 1, называется диэъюиктиоиой нормальной формой 1сокра4ценно д. и. ф.). Формула вида Уб — Р1 ьг Р2 ьг ° ~ Рз 114) (краткая запись Й Р4), где Р, попарно различные элементарные дизъюнкции 14 = 1,2, ..., 2) и э > 1, называется конъюнктионой нормальной формой 1сокращенно к. и. ф.). Число я в формулах 113) и 114) называется соответственно длиной д.

и. ф. и длиной к. и,. ф. Сумма рангов всех конъюнкций, входящих в д. н. ф., называется сложностью д. н. ф. Аналогично, сумма рангов всех дизъюнкций, входящих в к. н. ф., называется сложностью к. и. ф. Дизъюнктивная 1соотвотственно конъюнктивная) нормальная форма над множеством переменных Х" = 1х1, хз, ...., х„) называется сооери1еииой., если она составлена из элементарных конъюнкций 1соответственно элементарных дизъюнкций) ранга и 1ср. с определением в и. Ц. Простейший (но весьма громоздкий) способ построения дизъюнктивных и конъюнктивных нормальных форм для булевых функций состоит в использовании эквивалентных преобразований.

Пример 6. С помощью эквивалентных преобразований построить д н.ф фуНКЦИИ 11х ) = 1121 2 хгТ2) ' 122 9 хзх4) 2 х1хгх4)42 "Х112 ° 48 Гя. 1. Способы задания и свобыпва фуикиий аягебрь1 возики Решение. Используя основные эквивалентности из 31, преобразуем «постепенно» части формулы, задающей функцию 11Х~), к д. н. фл Х1 с Х2ХЗ Х1 Ч Х2ХЗ (см. 8, в)) хг 1Х хзх4 = хгхзха Ч Угхзхз = хг(УЗ Ч ха)Ч Угхзха; (см.

8, .а) и 4, а)) (Х1 1 Х2ХЗ)(хг Ю ХЗХ4) + У1хгхя = = (х1 Н хгУЗ) (хг(хз ~1 УЗ) Ч Угхзха) -+ Угхгхя — — 1см. 8, в)) = (У1 Ч ХЗУЗ)(хг(УЗ Ч Уа)Н Угхзха) Ц Угхгха = (см. 4, а)) = У1 и Хгхз 11 Хг 1УЗ и УЗЬУЗХЗХ4 11У1хгх4 = (см. 4, б)) Х1 Х2ХЗ 1 Х21УЗ 3 Ув) ссУгхзх4 Н Угхгхв = (см. 7 д) и 4 а)) = х1 хг Ч хз) с (хгя Уз Ч Х4)(хг Ц хз Ч ха)Ч Ч Х1Х2Х4 (см. 3, в), 4, б), 7, д) ) = хгхг ' ' 21хз ' ' (хг Н хзхв) хг 1гхз Ч Ув)Ч Х1хгх4— (см. 3, в), 7, а), 7, в) ) = х1хг о х1хз Ня хгхз с хгх4 'с хгхзхе Чс хгхгх4 11; ~(х ) = х1х2 Ч х1хз Ч х2хз Ч УЗУЗ Г хгхзх4 ч У1хгха Ч У1Х2— (см. 4,а), 7,д)) = ХЗУЗ Ц хгхз ЧУгУЗ Ц УЗУ4 Ч хгхзхв 2 Угхгха с 'сХ1 'Х2 — Х2ХЗХ4 3 1хгх4 г 1 схг— — 'гхзх4 'с Х224 'с Х1 с Х2 (см.

5,а)) (см. 6,а)) (см. 5,а)) (см. 6,а)) = Хгхя Ч Х1 Ч У2 =Х1 'с Хг СХ4. Очевидно, что полученная д, н, ф. является и к, н, ф. Если булева функция задана некоторой д.н.ф., то совершенную д. н. ф. этой функции можно получить, используя преобразования вида А = А хЧ А.х и АЧА = А.

Аналогично, совершенная к.н.ф, булевой функции может быть построена из какой-либо к, н, ф, этой функции спомощьюпреобразовапийвица А = (А''х) (АОУ) и А А = А. Дистрибутивный закон х . (у Ч 2) = х у'д х, . 2 (см. 3, а) в 3 1) совместно с эквивалентностями х х = х, х х = О, А . О = О, А Ч О = А и законом поглощения А Ч А В = А позволяет переходить от к. н, ф. булевой функции к некоторой д. н. ф., задающей эту же функцию. Аналогично, используя дистрибутивный закон х Ч у 2 = (х Ч р) . 1Х, Ч 2) (см.

Характеристики

Тип файла
DJVU-файл
Размер
3,29 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6521
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее