Задачи И Упражнения По Дискретной Математике, Гаврилов, Сапоженко, страница 13

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<г<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) У =ту, А = (хну, хну). 1.3.

Выписать все попарно неконгруэнтные функции 7'(х~), принадлежащие замыканию множества А: 1) А=(1,х); 2) А=(ху); 3) А=(х у); 4) А = (ху'1~ уг Ч гх): 5) А = (х Ю у В з й Ц:, 6) А =(хм у Р з); 7) А = (х — > у): 8) А = (ху Р г); 9) А = (ху): 10) А = (х(х'~ у)(у р у)(хМух)). 1.4. Из полной для класса ~А) системы выделить базис; 1) А=(0,1,х); 2) А=(хну,х у., Ц; 3) А=(х, хну, хбубзг); 4) А=(ху, хну, хуЧз); 5) А = (хну, х -э у); 6) А = (ху, ху); 7) А=(хзрувг,хуругргх, х); 8)А=(1,х у,хву~ЭзбзЦ:, 9)А=(ху,хуЧхг); 10) А = (х, х Ч у, х Ч у Ч г, ху 7 г). 1.5. Выяснить, какие из указанных ниже множеств являются замкнутыми множествами: 1) множество всех функций от одной переменной; 2) множество всех функций от двух переменных: 3) множество всех функций Дхы хг, ...

х„) таких, что 7'(1, 1, ... ...,1)=1., и>0; 4) множество всех функций Д(хо), и > О, таких, что 7"(1, 1, ... ..., 1) = 0; 5) множество всех симметрических функций, т.е. таких функ- /12... и1 ций 1" (хз, хг, ..., х„), что для любой подстановки ( .. ' ' ' . ~ спра~й 1г... ~..) ведливо равенство Дхы хг, ..., хн) = 1(хи, х„,,х;„); 6) множество всех функций 7(х") таких, что ~1зу ~ = 2" 7) множество всех функций, выражаемых полиномом Жегалкина не выше первой степени; 62 Гл. П. Залкндудпыс классы и полнота 8) множество всех функций, выражаемых полиномом Жегалкина не выше второй степени; 9) множество всех функций., допускающих представление в виде д.