Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 12
Текст из файла (страница 12)
Используя дистрибутивный закон х Ч у з = (х Ч у) Ус (т Ч з) и эквивалентности хЧ х = х, хЧ У = 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(хгг)). Запишем его в виде Р(х") =1эв 19А К1 Гй132 Кг йэ иг122--1 Кг- — 1г (16) где К, --. элементарная конъюнкция с номером у ( у = 1г 2, .... 2" — Ц.
Псктор Вр = (Во, А, г А 1) будем в дальнейшем называть вектором коэффициентов полинома Р(хи). Нам нужно найти неизвестные коэффициенты,Зо, А, ..., )12- Поступаем так. Для каждого а й В" составляем уравнение Р(о) = = Д(сг), где Р(И) --- выражение, получающееся из формулы (16) при х = И, Это дает систему из 2" уравнений с 2" неизвестными; она имеет единственное решение. Решив систему, находим коэффициенты полинома Р(хи). 2. Метод, б зируюгцийся на преобразовании вектора значений функции. Пад векторами из Вг определяется (индукцией по и) операция Т. а) Если и = 1 и гй = (оо,м1), то Т(И) = (мо, оо 61о1).
б) Предположим, что операция Т уже определена для каждого 2" +' вектора д из Вг, и рассмотрим произвольный вектор а из В Пусть гй = (ьго, ьг1, ..., ьгг 1, ув, 11, ..., 12 1) и т(Я, А, Вг" -1) = (бо, йгг . г бг 1), Т(70 ~1 12 — 1) (зо. в1 .. вг — 1) 54 Гл, 1.
Способы задание и сввйапва 41упкиий алгебры логики (б, и е по индуктивному предположению известны). Полагаем Т(о) = (до, ды ..., бг- ч; до 9 го, бз 9 ем . дг- г 9ег- г). Мы сейчас покажем, что вектор ааг значений функции»(хп) Х связан с вектором 13р коэффициентов полинома Р(х"), реализующего функцию»(хп), следующим образом: Др = Т(а») и а» = Т(1)р).
Сделаем это с помощью индукции по п. Базис индукции: и = 1. Тогда а» = (ао, аг) и в силу формулы (10) имеем»'(х1) = гц»"(0) 9 хг»'(1) = ао Уо 9 а1 хг = =ао.(хг91)9а1 х1=ао 19(оо9а1).хы т.е. А =(ао,ао9 9аг) = Т(а»). Обратно, если 1»р = (11о, 1эд), то Р(хг) = 13о 19 9 1эг . хы а следовательно, »(0) = Р(0) = 1эо и»" (1) = Р(1) =,Зо 9 Д, т, е, а» = Т()др). Базис индукции обоснован. Индуктивный шаг.
Предположим, что утверждение верно для и = т > 1, и установим его справедливость при п = т+ 1. Пусть вектором значений функции»"(хйпеы) будет а» = (ао,аы ... ..., аг- ы аг-, аг-лз» ..., аг-л~ г). Тогда вектор значений хг-компоненты функции»(х~+г) есть а»1 = (ао, аы ..., аг- г), а вектор значений хыкомпоненты есть ар = (аг, аг-эы ..., аг»л~ 1).
1 (Здесь обе компоненты рассматриваются как функции, зависящие от переменных хг, ..., хв,. ы и наборы значений этих переменных считаются стандартно упорядоченными при естественном, по возрастанию номеров индексов, упорядочении самих переменных.) Используя индуктивное предположение, можем написать Т(о», ) = Т((ао, аы ..., .аг- г)) = (бо, бы ..., дг- — г), Т(а»1 ) = Т((аг, аг *+1,..., ог л1 — 1)) = (ео, еы ..., ег 1), 1 где (бо, бы ..., дг- г) — вектор коэффициентов полинома Ро(хг, ... ..., х~, 1), реализуюгцего хыкомпоненту Д, а (ео, гы ..., ег- 1) вектор коэффициентов полинома Р,(хг, ..., х,„ъг), реализующего хыкомпоненту»'г .
Применяя формулу (10) и расписывая полиномы Ро и Р, в виде (16), имеем »е(х™+1) = х1»о 9 хг»1 — — х1(бо Ко 9 дг . Кг 9... 9 дг г Кг — г) 9 9х„(ео Ко 9ег Кг 9...9ег-* г Кг- — г) = ба Ко 9бг Кг 9 . 9 бг --г Кг -1 9 хг((бо 9 го) Ло 9 (бг 9 ег) Кз 9... 9 (бг" — г 9 ег- — г) Лг- — г), где К вЂ” конъюнкция с номером» (» = О, 1, ..., 2 — 1) над множеством переменных (хг, ..., х,„лг ). Если конъюнкцию К, рассматривать над множеством (хы хг,..., х тг), то ее номер не изменится, так как в соответствующем ей новом наборе первая координата нулевая. В то же время номер конъюнкции хгЛ равен 2'и+», »' = О, 1,... ..., 2п' — 1. Отсюда следует, что вектор коэффициентов полино- г Я. Специальиые предспгавлеипн булевых фракций 55 ма Р(х"'+'), реализующего функцию 1(хп'+г), имеет вид )3р = (бо, бы ..., бг ы до 61ео, бг югы ..., дг г бзег 2), т.е. совпадает с тем, который указан в определении операции Т.
Итак, установлено, что (3р = Т(ау). Докажем теперь обратное утверждение, т.е, что ау = Т((3Р). Пусть РР = РО, 33ы..., )32 1, 332, 132 . 1, ..., )32 ь 1). Тогда )3Р, = (130, 33ы ., 132- — 2) и )3Р~ = ()32, )32 е-ы 132"*'-1 — 2) где Ро и Рг - полиномы, реализующие соответственно хюкомпоненту 302 и хг-компоненту )г' функции 3(х~+г). Очевидно, что г (О, Хг, ..., Хпльг) = Р(0, Х2, ..., Хтпз-' )— — )30 ' КО 6~ е31 ' К1 чг ° ° ° бз е32 — 1 ' К2' — 1 ~ 3(1,х~,...,х +2)=Р(1,хг,...,х, +1)= =132 'Коб~дг' 01'К1~Э...Ю)32'"'1 — 1'К2 — 1 где К вЂ” конъюнкция с номером 3 (3 = О, 1, ..., 2 — 1) над множеством переменных (хг, ..., х, ег).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
