Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 12
Текст из файла (страница 12)
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) где К, --. элементарная конъюнкция с номером у ( у = 1г 2, .... 2" — Ц. Вектор Др = (Во, В1, ..., Вг.
1) будем в дальнейшем называть вектором коэффициентов полинома Р(хи). Нам нужно найти неизвестные коэффициенты,Зо, В1, ..., )12- Поступаем так. Для каждого а й В" составляем уравнение Р(о) = = Д(ег), где Р(И) --- выражение, получающееся из формулы (16) при х = И, Это дает систему из 2" уравнений с 2" неизвестными; она имеет единственное решение. Решив систему, находим коэффициенты полинома Р(хи). 2.
Метод, б зируюгцийся на преобразовании вектора значений функции. Пад векторами из Вг определяется (индукцией по и) операция Т. а) Если и = 1 и гй = (оо,м1), то Т(И) = (мо, оо 61о1). б) Предположим, что операция Т уже определена для каждого 2" +' вектора д из Вг, и рассмотрим произвольный вектор а из В Пг1сть В = (ьго, ьг1, ..., ьгг 1, ув, 11, ..., 1'2 1) и т(Я, А, Вг" -1) = (бо, йгг . г бг 1), Т(70 ~1 12 — 1) (ео. е1 .. е2 — 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) над множеством переменных (хг, ..., х, ег). Воспользовавшись формулой (10),получаем У(х ') = Х21о ® хгЛ = 3о ~ хг Уо ® Л ) = — Р(0 Х2 ° ° х +г) агх!(Р(0 Х2 ° ° х +1) чгр(1; Х2 ° ° х ег))— =до.Кой)32 К1Ю Ю)32--г Кг--гйхг(РОЮ)32-) Ко9 ег (е31 чг 132 е1) ' Кг чг ° ° ег Фг — 1 9 )32 +' — 1) ' К2 — 1) 330 'КО 'ХР1 'Кг ~ 'ХР2 — 1 'Кг' — 1 Ю(РО чг(32 ) 'К2 Ог 9 Р1 бз 132 3-1) ' К2 -,'-1 9 « ° лп ()32 — 1 9 132 л~ — 1) ' К2'" л> — 1~ где конъюнкция К рассматривается над множеством (хы хг,... ...,х ег) и при у = О, 1, ..., 2 — 1 совпадает с К, а при 3 = 2"', 2'и + 1...., 2'"ег — 1 она Равна хг .
К г».. Таким обРазом, доказано, что ау = Т(3Р). Утверждение обосновано полностью. Используя доказанное утверждение, можно описать алгоритм построения вектора )3Р коэффициентов полинома Р(х "), реализующего функцию 3(х"), имеющую вектор значений ар 2" 11усть ау =(ао~ аы аг~ аз~ ° ~ агы агав-ы - ~ а2" — 2~ а2" — г) 1- биваем вектор ау~ на двумерные наГюры: 70 = (ао, аг), 72 = (аг, аз), Ъ (а2е, а2гл1), ..., Уг — 1 1 — (а2 2, а2 1). К каждому из них применяем операцию Т; Т(30) = (ао, ао пг аг), Т(Ъ) (а2 а2 9 аз)) ..., ТЬ) = (а2п а22 пг аг~~-1)) ° ~ Т(32" — ' — 1) — (а2'" — 2; а2 — 2 чг а2" — 1) ° Используя построенные наборы, конструируем такие четырехмерные наборы, которые получаются в результате применения операции Т к 56 Гл, 1.
Способы задания и еввйапва функиий алеебрь1 логики четырехмерным наборам, выделяемым из вектора Нг: Т(сто, о1, сгг сгз) = Т( уо у1) = (Т( уо) Т( уо) 9 Т( ~1)), Т(о41 1-14241 1141-1-2; 6141-1-3) = Т(у21~ 'у214-1) = (Т(у21) ~ Т(621) 9 Т(у214-1))~ Т(ог е и иг -з, ог--г, иг 1) = Т('уг-- 2, уг.— 1) = = (Т( ~2 — ~ 2)Т(ув--~ 2) 9 Т( ~2 -2 1)). Затем от четырехмерных наборов переходим (аналогичным образом) к восьмимерным и т.
д., пока не построим 2п-мерный набор. Он и будет искомым вектором коэффициентов полинома Р(х"). Замечание. Здесь 2'"-мерный вектор изображается многими способами: мы «расщепляем» его на «последовательные» двумерные, четырехмерные, восьмимерные и т.д. наборы, Например, для вектора (сво, аы ог; сгз, ил: сгз, ов, о7) применяются такие записи: ((1.10, 111), (Ог, СЗЗ), (О4: Оз) (Ов О7)) ((1.10., О1,. 112, Сгз), (СЛ4, ОЗ, С16, оу)). Сумма Н 61 13 наборов (векторов) одинаковой длины понимается нами обычным образом: это покомпонентная сумма по модулю 2, т.е. 649,3 = (6719(31, ..., оп 913„), если Н = (оз, ..., сг„) и 13 = ((31, ., 73 ). 3. Меп1од, бопируя17дийвж на преобразовании формул над лвнохвестгь вол связок ( де, — ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
