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

Если з > 2, то формула Р, Рг ....Р, нс может быть д.н.ф., так как в каждой элементарной дизъюнкции Р, содержится не менее двух букв. Значит, нужно исследовать только случай, когда в = 1. Имеем Г(хп)=х 'ЧхвЧ...ЧХ„", где п,б(0,1) (1=1,2,...,и). Каждая такая функция однозначно определяется заданием набора (а1, иг,..., и„). Следовательно, число соответствующих функций равно 2" (при любом и > 1).

П р и м е р 10. Найти длину совершенной д. н. ф, функции у'(х " ) = =(х1ЧхгЧ... Чх„) (х1ЧхгЧ... Чх„), и,>2. Решение. Принимая во внимание определение длины д.н.ф. булевой функции и процедуру построения совершенной д. н. ф., описанную в з 1, заключаем, что длина совершенной д. н. ф. равна мощности множества 1Чу (множества наборов, на которых функция у обрагцается в 1).

Следовательно, достаточно выяснить, на скольких наборах значений переменных выполняется равенство (Х1 Ч Уг Ч... Ч Уп) . (х1 Ч Х2 1 ° Ч Хл) — 1. Очевидно, что это равенство справедливо тогда и только тогда, когда х1 Чхг Ч... Ч х, = 1 и х1 ЧхгЧ ... Чхо = 1. Палее, элементарная дизъюнкция х ' Ч х,' Ч... Ч х„обращается в 1 на любом нв; боре, кроме набора (о1, ог, ..., пп), ибо если х, = ее, для нскоторо- 4 Г. П. Гаврилов, А. А. Саножепко 50 Га. й Способы задания и свойыпва 21уикпий аягебрь1 возики Значит, дизъюнкция х1 Ч Уг Ч... Ч х„равна 1 на всех наборах, за исключением единичного набора 1 = (1, 1, ..., 1), а дизъюнкция х1 Ч "хг Ч...

Ч хп равна 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),~(х ) = х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) 11У ) = х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) ~(х~) = (хУг Чхг Чхз Чха) хг ЧУнЧхз) (хг Ч хл). 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). Справсдлива следующая Теорема (И. И. Жегалкин). Всякая булева функция единственным образом представимо в виде гюлинома ?Кегалкина. Замечание. Здесь единственность понимастся с точностью до порядка слагаемых в суммс и порядка сомножителей в конъюнкциях. И в дальнейшем мы считаем одинаковыми полиномы, различающиеся только порядком слагаемых в сумме и/или порядком сомножителей в конъюнкциях.

Указанная единственность представления булевой функции поли- номом Жегалкина позволяст применять разнообразные методы построения соответствующих данной функции полиномиальных выражений, заботясь лишь о том, чтобы результирующий полинам был приведенным, т. е. не содержал одинаковых сомножителей в конъюнкциях и одинаковых слагаемых.