Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 12
Текст из файла (страница 12)
Ч хп равна 1 на всяком наборе, кроме нулевого: 0 = (О, О, ... ..., 0). Таким образом, получаем ~2Ч1 ~ = 2" — 2. 2.10. С помощью эквивалентных преобразований построить д. н. ф. функции ~(у"): 1) ~(х ) = 1сУ1 Ч хг Ч хз) . (Х1 хг Ч хз); 2) 11х ) = (Узхг 9 Хз) . (Угхз 4 Хг); 3) 7(х ) =(Х1 хг)ч(хзхз6'1хг -эхз)); 4) ~(х~) = (Х1 4 хгхз) 4 ИУ1 ~ хг) ) хз); 5) ~(х ) = х1 — + (хг 4 хз) 63 (Х1 ~ (хг Ю ХЗ))', 6) ~(х ) = хгх2 ч Уз (х1 4 Х2хз); 7) 11'ХЗ) = (Х1 Ч хгхз) .
(Х1Уг Ч Хз) 1хгхг Ч хз); 8) г(ХУ ) = (Х1 Ч хгхзх4) ' Ях~ Ч Х4) В хгх ) Ч Уг (хз Ч Х1У4):, 9) ~(х ) = (Х1 4 Х2) (Хг 1 ХЗ) ' (ХЗ 1 Х1Х4)~ 10) 2 (Х ) 1Х1 4 Х2) (1хг ~ 2'3) Х1Х4) 1Х1 4 1ХЗ ~ Х4)) 2.11. Используя эквивалентные преобразования, построить к.н.ф. функции 7(хо): 1) ~(х ) = ((Х1 с У2) Ю (Х1 ~ У2)) ' (Х1 22 ' (Х1 с Х2)); 2),7(х ) = х1Х2 1 (х1 ф (хг (х1 + хг)))) 3) ~(х~) = хзтг Ч хгхз Ч (х1 — 4 хгхз); 4) Дх 3) = (У1 — 4 (хг — 4 хз)) 61 х1хгхз, 5) 11х ) = (х1 (хг -4 хз)) Ч (хг — 4 хгхз); 6) 1 (х ) = хзхг Ч хгхз Ч хзх4 Ч хгх4,' 7) ~(х ) = (Х1 хг)Ч (Х1хз Х4)Ч хгхз. 2.12. Применяя преобразования вида А = А . т Ч А . х и А Ч А = = А, построить из заданной д.н.ф. функции Дхп) ее совершенную Д.Н, фс У(х ) х1х2 " 23 2) 7(х ) — ХЗУ2 ч Х223 1' х123; 3) У(х~) = т1 Чхгхз ЧУгхз, 4) 7(х') = хгхг Чхгхз ЧУЗ', 5) 1(х~) = Х1 ЧУг Ч Х1хз; 6) 1(х~) = х1хгхз Ч хзхзх4'; 7) 1"1Х ) = хгхг Ч Угха Ч хзх4, 8) 1(У ) = х1 Ч 1сгхз Ч хгх4.
2.13. С помощью преобразований вида А = (А Ч х) (А Ч х) и А . А = А построить из заданной к. н. ф. функции Дхп) ее совершен- ную к.н. фс ~(х ) = (Х1 ~ У2) ' ХЗ', 2) 1 1Х ) = (Х1 Ч .'с2) ' (Уг ХЗ) ' тз', 3) 1(х ) = (Х1 22) ' (Х1 Ч хз) ' (хг Ч хз); 4) Г(хз) = Х1. Хг ' (У1 Ч хз) (х1 ЧУЗ)' 5) 141х~) = 1У1'Ч хг) ° хг ° '1х1'Ч Уз) ° 1Уг Ч хз); 6) 11Х ) = (Х1 Чхг 1 хз) ' 1Х1 ЧхгЧХ4) 7) 1(Х ) = (Х1 ЧХ2) '(ХЗЧХЗ) (ХЗ ЧХ4); 8) 7 (х ) = х1 Уг хз . 1Х1 Ч Уг Ч хз Ч 24).
у 2. Спеииальпые предеппавлеаин булевых фупкиий 51 2.14. Используя дистрибутивный закон х(у Ч г) = ху Ч хг и эквивалентности х х=х, х х= О, А 0=0, АЧО= А и АЧ ЧА В = А, перейти от заданной к.н.ф. функции 7'(хп) к д,н,фл 1) 1(х з) = (У, Ч У,) . х„Ч з) (Уг Ч Уз). 2) 1(х~) = хг (хг Ч хг Ч Уз) . (хг ЧУз); 3) ((х ) = (хг Ч хг) ° (хг Ч хз) (хг Ч хг Ч хз); 4) гл(х ) = (Уг Ч хг) (Уг Ч хз) (Уг Ч хз) (хг Ч хз); 5)1(х )=(хгЧхгЧхз). хгЧхгЧхз) (хгЧхгЧхз); 6) ((х~) = (хг Ч хг) (хг ЧУз) (хг Ч ха) (хз ЧУл); 7) 1(х ) = (хУг Чхг Чхз Чха) хг ЧУнЧхз) (хг Ч хл).
2.15. Используя дистрибутивный закон х Ч у г = (х Ч у) Ус (т Ч г) и эквивалентности хЧ х = х, хЧ У = 1, А Ч 1 = 1, А 1 = А и А (А Ч В) = А, перейти от заданной д.н.ф. функции 7"(хп) к ее к. н. фл 1) 1(х ) =хгУг'Чхе', 2) 1(х ) = хзйг Ч ггхз Ч хгхз; 3) 1(х ) = Уг Ч хгхз Ч хгхз', 4) 1(х ) = Уг Ч хг Ч хгУгхз', 5) ((х ) =УгУг ЧУг Ч хгУз, '6) ге(х ) = хгхг Ч хгхз ЧУгхл Ч хзхл,' 7) 1(х ) = хгхгУзхл Ч хгхгхз Ч хгхл:, 8) Х(х ) = хг Чхгхз'ЧУгхзхл'Чхгхзхл. 2.16.
Доказать, что переменная х; функции 7'(хп) У': 0 является фиктивной тогда и только тогда, когда совершенная д.н.ф, этой функции вместе с каждой элементарной конъюнкцией К содержит также конъюнкцию Кп отличающуюся от К.. только г-й буквой, т.е. К = х~* К и К~ = х~*К, где К -- конъюнкция ранга п. — 1. Замечание. Справедливо также утверждение, двойственное задаче 2.16: переменная х, является фиктивной переменной функ- ции 7'(хп) ~ 1 тогда и только тогда, когда совершенная к.н. ф.
этой функции вместе со всякой элементарной дизъюнкцией Р содержит такую элементарную дизъюнкцию Рп которая отличается от Р лишь г-й буквой, т.е. Р =х,* ЧР и Р~ =х,* ЧР, где Р дизъюнкция ранга п — 1. 2.17. Подсчитать число функций 7(хп), у которых совершенная д. н. ф. удовлетворяет следующему условикп 1) отсутствуют элементарные конъюнкции, у которых число букв с отрицаниями равно числу букв без отрицаний; 2) каждая элементарная конъюнкция содержит котя бы две буквы с отрицаниями (и ) 2); 3) отсутствуют элементарные конъюнкции, содержащие нечетное число букв с отрицаниями; 4) в каждой элементарной коныонкции число букв с отрицаниями не больше числа букв без отрицаний; 5) какова бы ни была элементарная конъюнкция Км найдется (другая) элементарная конъюнкция Кп отличающаяся от К только первой буквой (т.е. К = х 'К и К~ = хв'К, где К -- конъюнкция ранга п, — Ц; 52 Гл, й Способы задания и ввойапва функций алввбрьт логики 6) какова бы ни была элементарная конъюнкция Км натщется элементарная конъюнкция Кт, отличающаяся от Кг двумя первыми буквами (т.е.
К, = хв'хвгК и Кт = хт'х~~'К, где К вЂ”. коньюнкция ранга и, — 2 (и, > 2)). 2.18. Найти длину совершенной д. н. ф, функдии т'(хи); 1)Дхп)= )/ х;х, п>2; 1« т< 2) т"(хп) = т~г (х, т х,), п > 2; тйь<1<п 3) У(х") = (((хт ~ хг) ~ хз) ~ ~ хп — т) ~ хп, тт ) 2; 4) У(хй ) = хт — т (хг т (хз т ° т (ха — 1 т хп) ° ° )) тт 3 2; 5) .т (х ) — ( ° ((хт > хг) + хз) т ° ° хп — 1) > хп и > 2~ 6) т'(хп) = (хт''Охг) (хт М хг) — т тг ...
х, и > 3; 7) У(хп)=хтхг...х бтхзто...~Зх, п>3: 8) Дхп) = (хт ттхг М хз '~ . Л х„) — ~ ((...(хз ха) хп т) х„), тт > 4. 2.19. Пусть множества Х = (хы ..., х ) и У" = (Ут,, У ) не пересекаются. Предполагая, что длины совершенных д. н. ф. функций 1(х'и) и д(у") равны соответственно к и 1, найти длины совершенных д. н. ф.
следующих функций: 1) У(х )ттд(д"), 2) У(х ) д(у"); 3) У(х ) ОЗ д(у"); 4) У(х") -+ д(туп). 2.20. Найти длину совершенной д.н.ф. функции т"(х") ~Э д(х"), если известны длины совершенных д. н. ф. следующих функций; 1) т" (Хп) д(Х") И т' Х ') тгд(Х" ) 2) ((хп) т д(х") и д(хп) т ((х").
2.21. Показать, что среди булевых функций, зависящих только от двух переменных хт и хг, .причем от каждой из них существенным образом: 1) ровно восемь функций имеют д. н. ф. сложности 2; 2) не существует функций, у которых минимально возможная сложность д. н, ф, равна 3.
3. Полиномы лКегалкина. Элементарная конъктнкция называется монотонной, если она не содержит отрицаний переменных. Константтта 1 (т.с. элементарная конъюнкция нулевого ранга) считается по определению монотлонной элементарной конъюнкцией. Выажение ви а Р д КтйтКг6 . ЮК„ (15) где К, (т = 1, 2, ..., в) --- попарно различные монотонные элементарные конъюнкции над фиксированным множеством переменных (в частности, над множеством Х", п > 1), называется полиномом 2Кегалктгна (или полиномом тот модулю 2). Рассматривается также полипом Жегалкина, соответствующий в = О. Такой полином обозначают через О (независимо от множества переменных) и считают по определению, что он равен константе О.
Наибольший из рангов элементарных конъюнкций, входящих в полипом, называется шле- у ег'. Специальные предегиавленин булевых функций 53 пенью этого полинома. Степень полинома О считается неопределенной. Число в называется длиной полинома (15). Справедлива следующая Теорема (И. И. Жегалкин). Всякая булева функция единственным образом представимо в виде гюлинома ?Кегалкина. Замечание. Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях.
И в дальнейшем мы считаем одинаковыми полиномы, различающиеся только порядком слагаемых в сумме и/или порядком сомножителей в конъюнкциях. Указанная единственность представления булевой функции поли- номом Жегалкина позволяет применять разнообразные методы построения соответствуюгцих данной функции полиномиальных выражений, заботясь лишь о том, чтобы результирующий полинам был приведенным, т. е. не содержал одинаковых сомножителей в конъюнкциях и одинаковых слагаемых. Опишем три метода построения полиномов Жегалкина. Сначала введем специальную нумерацинг монотонных элементар- НЫХ КОНЪЮНКЦИЙ (Э.
К.) НаД МНОжсетВОМ ПЕРЕМСННЫХ Хи = (Х1г Хг,... ..., х„). Монотонной э.к. К сопоставляем вектор о(К) = (ег1, ог,... ..., ои) из В"', в котором о, = 1 тогда и только тогда, когда х, входит п в К. Номером э, к. К будем называть число р(д(К)) = 2 и; 2" г=1 Константа 1 в этой нумерации будет иметь номер О. 1. Метод неопределенных коэффициентов. Пусть Р(х") - . искомый полинам Жегалкина (реализующий заданную функцию 1(хгг)). Запишем его в виде Р(х") =А 19А К1 ейск Кг йз евА--1 Кг- — 1г (16) где К, --.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
