Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 13
Текст из файла (страница 13)
Строят некоторую формулу Ф над множеством связок ( вс, — ), реализующую заданную функцию у. Затем заменяют всюду подформулы вида А на А 9 1, раскрывают скобки, 1юльзуясь дистрибутивным законом А (В 9 С) = А В 9 А. С, и применяют эквивалентности А А = А, А . 1 = А, А 61 А = 0 и А 9 0 = А. П р и м е р 11. Методом неопределенных коэффициентов построить полипом Жеголкина для функции 3(х, у) = х Ч у. Решение. Р(х,у) = (уо 9131 т 9Г32 у 9132 ху. Выписываем систему уравнений для коэффициентов 13о, 121, 132, 17з.' У(0, 0) = О =)3о 9131 09Г32 09дз О. у(0,1) = 1=РО9|31 09,32 09,3з О, у(1, 0) = 1 = (36 9 )31 1 9 132 .
0 9 )3з . О; Г(1, 1) = 1=1309Д 09132 19133 1. Решая эту систему, получаем 73о — — О, 731 = 132 — — 732 — — 1. Следовательно, хну = ху9х9 у. Пример 12. Преобразуя вектор значений функции, построить полипом жегалкина для функции Дхз) = х1хг у хзхзч хгхз. Решение. Имеем Ну = (00010111). Разбиваем этот вектор на «последовательные»двумерные наборы: уо = (О, 0), у1 = (О, 1),.
уг = = (О, 1), уз = (1, 1). Затем последовательно применяем операцию Т к соответствующим векторам: Т( уо) = (О, 0 9 0) = (О, 0), Т( уг') = (О, 0 9 1) = (О, 1), у Я. Специальные предетавлепцн булевых функций 57 л (7о, 7з) = (л (7о), л (7о) Ю л (7з)) = = ((О, 0), (О,. 0) Ю (О, 1)) = (О, О., О, 1), л (Уз~ Уз) (Х(Уз), л (Уз) ЮТ(73)) = = ((О, 1), (О, Ц Ю (1, 0)) = (О, 1, 1, 1); Т(оу) = Т(7о, 7ы 7з; 7з) = (Т(7о, 7з), Т(7о, 71) 9 Т(7з, 7з)) = = ((О, О, О, 1), (О, О, О, 1) 9 (О, 1, 1, 1)) = (О, О, О, 1, О, 1, 1, 0) = Вр. Таким образом, Р(х )=О.Ко90 К190.Кз91 Кз90 К491.КзЮ Ю 1 .
Кв Ю 0 Ку — — хзхз Ю х1хз Ю х1хз. Пример 13. Представив функцию у"(х, у) = х в у формулой над множеством связок (4е, — ), преобразовать затем полученную формулу в полипом Жегалкина. Решение. Имеем х-+у= хНу=х у=х у=т.(у91)91= =хуЮх91. Пример 14. На скольких наборах из В" обращается в 1 полипом Р(х") = НУ хх, (и > 2)7 з<~<адп Решение. бранный полипом можно записать в следующем виде: Р(х )=хзхзЮ(хзЮхз) хзЮ 9(хзЮ .
Юх — з) х — 19 9(х, Ю...Юхп,).х„. В силу симметричности вхождения в него всех переменных достаточно рассмотреть наборы вида (1, ..., 1, О....., 0), 0 < 1 < и (при 1 = 0 это будет нулевой набор 0 = (О, .О, ..., 0)). Если х,лз =... ... = х„ = О, то Р(хы ..., х„ О, ..., 0) = хз хз Ю (хз Ю хз) 3ехз 9 ... ... Ю (хз Ю...
Ю х; з) х,; здесь число произведений вида хнх~ равно, очевидно, ( ) (2 < 1 < и), а при 1 = 1 и 1 = 0 таких произведений нет. Значит, Р(1, ..., 1, О,..., 0) равно 0 или 1 в зависимости от ю 'Уз того, четно или нечетно число (2) (при з, = 1 и 1 = 0 значение полинома на соответствующем наборе есть 0). Выясним теперь, прн каких 1 число ( ) является нечетным. Если 1 = 4й или 1 = 4й+ 1 (й > 1), то (2) равно 2й. (4й — 1) или (4й+ 1) . 2й соответственно, а если г = 4й + 2 или 1 = 4й + 3 (й > 0), то ( ' ) равно (2й + 1) (4й + 1) или (4й+ 3)(2й+ 1). Следовательно, число ( ) является нечетным только тогда, когда 1 = 2, 3, 6, 7, ..., 4й+ 2, 4й -~-3, ... Учитывал этот факт, заключаем, что число наборов, на которых полипом Р(х") обращается в 1, равно О,— зП4' Ол — з~Ул; Е (Я+2) ' Ел (4~':3) 58 Гл. 1. Способы задания и сводыпва функций алгебрь1 логики В частности, если п = 2, то существует только один такой набор ( в этом случае вторая сумма вырождается в нуль: ~ ( й 3) = 0), 1 О ~М4- а если п = 3, то таких наборов четыре (Е(а+2) Е(а -3) (2) (3) ) 2.22.
Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций: Ц 1(х ) = х1 ~ хг, 2) )(х~) = (0100); 3) )(х~) = х1 хг Чхз); 4) 1" (хе) = х1 — 4 (хг 4 хз)' 5) Дхз) = (0110100Ц' 6) Дх з) (10001110). 7) ((х з) (0000011Ц 8) Дхз) = (01100110) 9) 7(хл) = (100000000000000Ц 10) У(х') = (0000100010010000). 2.23. Преобразуя вектор значений функции 7'(хо), построить по- дином поганкина для этой функпии, если; Ц 7"(хг) = (1000): 2) 7"(хг) = (0010); 3) У(хз) (01101110).
4) У(хе) (0111001Ц 5) У(хз) (10101110); 6) Х(х,з) (10000100) 7) Дх4) = (000001000110011Ц; 8) Дхл) = (1010101010110110); О) У(х,л) = (0100000000010ООЦ; 10) У(хл) = (ООООООО100010ООЦ. 2.24. Представив функцию Д(хп) формулой над множеством свя- зок (8с, — ), преобразовать затем полученную формулу в полипом Жегадкина функции Д(хи) (испопьзуя эквивалентности А = А ~Э 1, А.(ВЮС)=А ВбзА С, А А=А, А 1=А, АбзА=О и АЮ 450 = А): Ц 1(х ) =:с1 -+ (хг 4 Хгхг);. 2) 1(х ) = х1 (хг хгхг); 3) 1(х ) = (х1 4 хг) ~(хг ф хз); 4) 7(х ) = (х1 Ь'хг) (хг ~хз); с) е( 3) . ) (( .
~ х ) ~ х 6) Дх ) = (х1 -4 (хг -4 хз)) .((х1 -4 хг) 4 хз), 7) гл(Х ) = (Х1 Ю Хг)'в'(Хг ). ХЗ); 8) 1(х~) = (х1 -о хг) †(хз †х1хл); О) 1(х ) — х1 " (тг 4 ((хз схг) с хл))~ 10) 1 (х ) = х1 Ч хго хз) х4 о хгхгхз. 2.25. Показать, что х; является существенной переменной функ- ции дхо') тогда и только тогда, когда х; явно входит в полипом Жегалкина этой функции. 2.26. Найти число: Ц монотонных элементарных конъюнкций ранга г над множест- вом переменных Х" = (х1, хг, ..., х„) (О ( г ~ (и); 2) полиномов Жегалкина степени г над множеством перемен- ныхХп (0(г(п); у й Специалвиые предегпавле~пн булевых бгупкццц 59 3) полиномов Жегалкина степени г над множеством Х", обращающихся в 1 на наборе 1 (О < и < п); 4) полиномов Жсгадкина длины 1е над множеством Х", обращающихся в О на наборах О и 1 (О < й < 2и); 5) попиномов Жегалкина степени г над множеством Х', удовлетворяющих условию; в попиноме не могут содержаться одновременно (в качестве слагаемых) конъюнкции одинакового ранга (О < г < и).
2.27. Выяснить, на скольких наборах из В" обращается в 1 полипом Р(хи): 1) Р(х ) =хг'хзчгх1'хзЮ...Юхг'хи — <г)хгхг г'=-2 и 2) Р(х ) — хг ' хз чг а 3 ги ° гх хи — хгхз ги (х) 3) Р(х ) =юг 'хач хг 'хзгихлге ° .гехи = хгхз гхг хгхз пг сгг хгг гг, ~ )4; и г'=4 4) Р(хи) = хгхгхз 6~ гтг х, и. > 4; г=л б) Р(хи) =х, ...х, Ехя„..,х„, 1 < й < п; и б) Р(хи) = ® хг... хе бг 1, и > 1; г=1 7) Р(хи) = ()) хг... х, гхг+г... хиг п > 2; 8)Р(хи)=хгОЗ 9 т,хч п>2; 1<г<д<и и 9) Р(х") = (Э х,х., ~Э (() х„п > 2. 1<г<1<и г=у 2.28.
Найти функцию 7"(хи), у которой длина попинома Жегапкина в 2и раз превосходит длину ее совершенной д. н, ф. (и > 1). 2.29. Локазатьг что функция Дхи), реализуемая попиномом Жегалкина степени й > О, принимает каждое из значений О и 1 не менее чем на 2" Я наборах из В" (т.е. ~Лгу( > 2" " и ~йу~ > 2" ~). 2.30. Показать, что дпя всякого 1 (О < 1 < 2и) существует попином Жегалкина Р(хи), обращающийся в 1 ровно на 1 наборах из В" и имеющий длину, не превосходящую и.
2.31. Показать, что всякая бупева функция Дхи), отличная от константы О, представима в виде (-)) К,г где К; (г = 1г ..., в) г=г различные элементарные конъюнкции, каждая из которых содержит не более одного отрицания переменной, а в < 2и 2.32. Пусть функция 7"(хи'), где п > 3, зависит существенно от всех своих переменных и реализуется попиномом Жегапкина степени и. Локазатги что найдутся две такие переменные, отождествление которых уменьшает число существенных переменных ровно на 1.
Глава П ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА СИСТЕМ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ 8 1. Понятия функциональной замкнутости и полноты Замыканием [К) множества К функций алгебры логики называется совокупность всех функций из Рг, являющихся суперпозициями функций из множества Л. Множество Л называется [функционально) за,мкнутьгм, если [К) = К. Замкнутые множества называются также замкнутыми классами. Подмножество Р функций из замкнутого множества К называется (функционально) полным в К, если [Р) = К.
Полное в замкнутом классе К множество Р называется базисом класса Л, если для всякого собственного подмножества Р' С Р выполнено [Р') ф К. Подмножество Р функций из замкнутого класса К называется иреднолным классом в К, если [Р) ф К и для всякой функции 7 Е К~,Р выполняется равенство [Р ьз' (Д) = К. Функции тг и гг назовем конгрузнтными, если одна из них может быть получена из другой заменой переменных (без отождествления).
Например, функции ху и уг конгрузнтны, а функции ху и гг не являются конгрузнтными. При рассмотрении вопросов, связанных с замкнутыми классами, бывает удобно указывать по одному представителю из множества попарно конгруэнтных функций. Например, класс (х, у, г, ..., хы хг, ... ), состоящий из всех тождественных функций, будет обозначаться через (х). Если А — некоторое множество функций, то через А(Х") или, короче, через А" будет обозначаться множество всех тех функций из А, которые зависят только от переменных хы хг, ..., хо.
1.1. Построить множество всех функций, зависящих от переменных хы хг и принадлежащих замыканию множества А: Ц А = (х); 2) А = (хг 63 хг); 3) А = (О, х); 4) А = (хгхг); 5) А = (хгхгохгхз '' хзхь); б) А = (хг Ч хг); 7) А = (О, хг - хг):, 8) А = (хьхг, хг Ф хг); 9) .4 = (хг бЗ хг Ф хз); 10) -4 = (хьхг у хгхз у хзхг); 1Ц А = (хг ьо хг Ф хз ег Ц: 12) А = (хгхг); 1 1. Пониизин функциональной замкнутости и иолноюы 61 13) А = (хзхг Р хгхз Р хзхг); 14) А = (хз'4 хг Мхз); 15) А = (хзхг Ч хз). 1.2. Показать, что 7" Е [А], выразив 7" формулой над множеством А: 1) 7'=х, А=(О.,хэу); 2) 7'=хну, А=(х(11); 3)~=х, А=(хну); 4)7'=херах, А=(х-у); 5)7'=О, А=(хубзз); 6)1"=х, А=(ху); 7) у=хчу, А=(хру); 8) 7'=х, А=(хунуг~lзх); 9)~=ху, А=(хуаз); 10) з = хуг Ч 1(х р у у з), А = (ху р уя'4 гх); 11) 7"=хбзуйз, А=(х,хуЧугЧгх); 12*) 7" = х 9 у 9 г, А = (ху Р ура Ух); 13) У = х Е у, А = (ху, х р у); 14) У = х ' 7у, А = (х -+ у): 15) У =ту, А = (хну, хну).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
