XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 70
Текст из файла (страница 70)
Если С = Те, то у(0) = Дд1(0),...,да(0)) = ДО,...,0) = О, так как у, дм ..., д„е Те. Следовательно, у е Те. 2. При С = Т1 рассуждаем точно так же. 3. Пусть С = Я. Фиксируем произвольно набор а Е (О, Ц". Вычислим (используя самодвойственность всех функций): р(а) = У(91(а),.",д (й)) = У(д1(а),".,%(а)) = =УЫИЛ),",д (а)) =р(а). Следовательно, ~р Е Я. 4.
С= М. Берем произвольно наборы а и ~3 так, что а <,о. Докажем, что у Е М. Имеем р(й)=У(д1(й), ", д (й))<У(д(д), ", д Р))=рФ), так как все функции д;, 1 = 1, и, монотонны и тем самым вектор (91(а),...,д„(а)) не больше вектора (д1 ф),...,д„ф)), а функция у также монотонна. Тогда ясно, что у е М. 5. Если же С = Ь, то очевидно, что при подстановке в линейную функцию (полипом Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция.
Итак, мы доказали замкнутость каждого класса Поста. ~ Докажем теперь теорему, характеризующую одно важное свойство немонотонных функций. Теорема 6.6. Если функция у не является монотонной, т.е. у ф М, то найдутся два таких набора а,,в, что а=(ам ...,а, мО,п1+и ...,и„), Р = (пм ", си-и 1, <~*.+и ", пп), 439 б.7. Теорема Поста и Д(а) = 1, У(13) = О, т.е.
зти два набора различаются значениями в точности одной компоненты, а значение функции равно 0 на большем наборе и равно 1 на меньшем. ~ Так как функция ~ не является монотонной, то найдутся такие два набора 7 и Б, что 7 < б, но Д7) = 1, Дб) =О. Строгое неравенство 7 < Б означает, что найдутся такие номера (не меньше одного) 1 < в1 < вз « ... вь < о, что 7 =(71» ° "7>з-1>0>7>з+1»" 7>з — 1> О» "° 7>з+1» "° 7вз-1> О> 7вз+1» 7а)> а = (71» "° 7>в-1> 1> 7вз+1» "° 7вз-1> 1» " 7вз+1» ° " 7зз-1> 1> 7>в+1» ° " 7а)> т.е. все компоненты наборов, кроме выделенных, с номерами вм вг, ..., ва соответственно совпадают, а все компоненты с выделенными номерами у меньшего набора равны О, а у большего равны 1.
Построим монотонно возрастаюпгую последовательность наборов 7=7с <71 <7з « ... 7ь =6 так, что для каждого а Е (1, 2, ..., Ц набоР 7з полУчаетсЯ из набоРа 7з 1 заменой нулевого значения компоненты с номером в, единичным. Поскольку у(7) = 1, а у'(б) = О, то обязательно найдется такое а Е (1, 2,..., Ц, что У(7з 1) = 1, а ~(7з) = 0 (на наборе 7, з значение функции еще равно 1, а на наборе у, оно уже равно 0).
Полагая о = 7з 1 и ~3 = 7з, получим доказываемое. ~ь Теорема В.Т (критерий Поспва). Множество Р булевых функций полно тогда и только тогда, когда оно не содержится целиком ни в одном из классов Поста. й Необходимость условия теоремы доказывается просто: если бы для некоторого класса Поста С выполнялось Р С С, то всякая суперпозиция над Р, согласно теореме 6.5, снова лежала бы в С. Между тем существуют функции, не содержащиеся ни в 440 6. БУЛЕВЫ ФУНКЦИИ одном из классов Поста, например штрих Шеффера (см.
пример 6.9). Таким образом, нашлась бы функция, которую нельзя представить в виде суперпоэиции над Р, что противоречит предположению о полноте Р. Переходим к доказательству достаточности условия теоремы. Для доказательства полноты множества Р, удовлетворяющего условию теоремы, построим формулы над Р для функций отрицания и конъюнкции, поскольку, как было замечено выше, множество, образованное этими функциями, полно. Тогда в силу теоремы 6.3 будет полным и множество Р. Для немонотонной функции ~м Е Р~ М, согласно теореме 6.6, найдутся два таких набора а и,8, что й = (с>ь "° ж-1 О %+1 ° ° ° >х») Р = (п1» "° <~>-1> 1> %+1> "° > >х»)> Л (й)=1, Л (Д)=0.
Тогда х = ~м(ам...,ол их,а;+1,...,а„), т.е. отрицание может быть получено из немонотонной функции подстановкой вместо некоторого ее переменного х, переменного х, а вместо остальных переменных констант >х>, ..., ол 1, с>>ььм ..., а», определяемых выбранными вьппе наборами а и,9. Но, вообще говоря, система Р может и не содержать констант.
Поэтому константы 0 и 1 необходимо представить некоторыми формулами над Р. Рассмотрим два случая. Первый случай. В Р существует функция уе, не сохраняющая константу О, которал сохраняет константу 1; или существует функция ум не сохраняющая константу 1, но сохраняющал константу О. Если существует функция уе ф Те и уе Е Тм то константа 1 представляется формулой 441 б.Т. Теорема Поста так как Уо(0,..., 0) = 1 и Уо(1,..., 1) = 1. Чтобы выразить кон- станту О, используем любую функцию д Е Р, не сохраняющую константу 1: О=я(1 ... 1) =9Це(х,... х) ... уо(х ...
х)). Если же указанная функция уе не существует, но найдется функция 11 Е То1Т1, то константы представляем формулами над Р аналогично (двойственным образом). Второй случай. Любм функция иэ Р, не сохраняющая константу О, не сохраняет и константу 1, и, наоборот,любм функция из Р, не сохраняющая константу 1, не сохраняет и константу О. Пусть уе(0,...,0) = 1, а Я1,...,1) = О.
Тогда мы получаем возможность представить отрицание следующей формулой: х = уе(х,...,х). Переходим к построению формул для констант, так как они потребуются нам далее при построении формулы для коньюнкции. Чтобы представить константы формулами над Г, воспользуемся несамодвойственной функцией уб из Р. Для этой функции найдется такой набор а, что уб(а) = Уб(се).
Введем функцию от одного переменного Ь(х) = ~я(хо',...,Хо") (в предположении, что а = (сею ... „се„)). Легко видеть, что Ь(0) = = уб(се) = Яа) = Ь(1), так как для любого и Е (О, 1) )1, а=О; 10, о=1, о /11 '10, и = О. Итак, значение Ь(х) есть константа. Если она равна О, то константу 1 представляем через функцию, не сохраюпощую константу 0; если же Ь(х) = 1, то константу 0 представляем через функцию, не сохраняющую константу 1. Опишем построение формулы для конъюнкции. Берем нелинейную функцию ~ь из Г. В полиноме Жегалкина для этой 442 б.
БУЛЕВЫ ФУНКЦИИ функции выберем произвольное нелинейное слагаемое, содержащее наименьшее число переменных; пусть это будет слагаемое х;„..., х; при 2 < й < и. Вместо каждого переменного х,в функции ~~„где тп ф (зм ..., 1ь), подставим константу О, т.е. заменим нулем все переменные, которые не вошли в выбранную ранее конъюнкцию. Получим „редуцированную" функцию и Уь —— х;, ... х;, Ю а;, я;, 9... 9 а;„х;, 9 ае = =,Яо,...,о,х;„О,...,о,х,„,о,...,о). Заметим, что коль скоро мы уже представили константы формулами над Р, то функция Д тоже представлена формулой над Р. Разобьем теперь множество переменных (х;„..., х;„~ произвольно на две части: (х;„ ...,т; ) и (х; +,,..., кч ), где 1 < т ( (Й вЂ” 1, и заменим все переменные первой части переменным х, а переменные второй части — переменным у. В результате получим функцию от двух переменных К(т,у) =хуЮахЮЬуЮс, где а=а;,9...9а;, Ь=а;, Ю...Юа;„, с=аз. Ясно также, что функция К может быть представлена такой формулой над Р: Х(х,у) = ~ь(о,".,О, *,О,...,О, *,О ...
О ц 1пв т.е. функция К получена из нелинейной функции ~ь Е Р путем подстановки на место ее переменных с номерами 1м ..., ьв переменного я, на место переменных с номерами з +1, ..., бь — переменного у, а на место всех остальных переменных— константы О, уже представленной формулой над Р (см. вьппе).
Определим функцию 1Ь(х, у) = К(х Ю Ь у Ю а) Ю аЬ Ю с. 6.7. Теорема Поста 443 Выразив эту функцию из полинома Жегалкина для х, получим 6:(х у) = л(х Ю Ь, у ср а) В аЬ Ю с = = (х 9 Ь) (у ® а) Ю а(х щ Ь) 9 Ь(у В а) ® с Е аЬ са с = = ху®ах®Ьу®аЬ®ах®аЬФЬуЮаЬйтсетаЬВс = ху, поскольку сумма по модулю 2 любого четного числа равных слагаемых равна О. Итак, функция ф и есть конъюнкция. Так как прибавление к любой функции константы по модулю 2 есть либо сама исходная функция, либо ее отрицание, а отрицание уже представлено формулой над базисом Р, то тем самым и конъюнкция представлена такой формулой. ~ь Чтобы исследовать полноту конкретного множества функций Р = Цм уг,..., у 1, нужно построить так называемую иритериальную таблицу (табл.
6.6). Строки таблицы соответствуют Таблица 6.6 функциям исследуемого множества, а столбцы — классам Поста. В ре- Т, Т„ зультате анаяиза функций множества Р клетки таблицы заполняются: если функция у; принадлежит некоторому классу Поста С, то в Д„ соответствующей клетке критериальной таблицы ставится знак „+а (плюс), а если нет, то— знак „вЂ”" (минус).
Множество Р тогда полно, если и только если в каждом столбце таблицы стоит хотя бы один знак „вЂ” ". Пример 6.21. а. Пусть Р = (, Ч, 0). Ниже приведены результаты исследования элементов этого множества на принадлежность к классам Поста, а также эаполненнал критериальная табли- Таблица 6.7 ца (табл. 6.7). То Т, 8 М При этом 1 = х х, так как ° — + — — + функция (эквивалентность) не у сохраняет константу О, но сохра- О няет константу 1 (т.е.имеет место б. БУЛЕВЫ ФУНКЦИИ первый случай из доказательства достаточности условия теоремы Поста).
Константа 0 принадлежит самому множеству Р. Поскольку х = х ° О, то ввиду полноты множества (Ч, ) будет полным и рассматривамое множество. Конъюнкцию можно представить формулой над Г, следуя доказательтву теоремы Поста. Берем единственную нелинейную функцию данного множества, дизъюнкци, и записываем для нее полипом Жегалкина: Х1 Ч Х2 = Х2 ' Х2 Щ Х1 ® Х2. Видно, что этот полипом есть не что иное, как функция Х(Х1, Х2) при а = Ь = 1 и с = О. Следовательно, х1 'Х2 Х(Х1 Е 1~Х2 Е 1-) ®1. Но так как х=х О, то Х1 Х2 = Их1 ° 0)Ч(х2 ° 0)) ° О. Этот же результат (в данном конкретном случае) можно получить и гораздо проще: Х1.х2 =х1 Чх2 = КХ1 ° 0) Ч(х2 0)) О. Итак, исходное множество является полным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
