Содержание к диссертации
Введение
Глава 1. Основные понятия и результаты 7
1. Основные понятия и терминология 7
2. Обзор результатов по слабоповторным и бесповторным булевым функциям 13
Глава 2. Слабоповторные булевы функции в предэлементарных немонотонных базисах 24
3. Свойства бесповторных булевых функций в предэлементарных базисах 24
4. Слабоповторные булевы функции в серии предэлементарных немонотонных базисов 28
Глава 3. Слабоповторные булевы функции в предэлементарных парасимметрических базисах 74
5. Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка 5 74
6. Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка 4 99
Заключение 128
Список литературы 129
- Обзор результатов по слабоповторным и бесповторным булевым функциям
- Слабоповторные булевы функции в серии предэлементарных немонотонных базисов
- Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка
- Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка 4
Введение к работе
Теория дискретных функций образует одно из главных направлений исследований в дискретной математике. Простейшим и в то же время важнейшим классом таких функций является класс булевых функций. Из различных способов задания булевых функций основным является представление их с помощью суперпозиции выделенных базисных функций, которое в теории булевых функций называют термальным или формульным.
Представление булевых функций термами над заданным базисным множеством функций относится к основным этапам логического проектирования дискретных устройств [6, 7, 46, 47]. Поэтому неудивителен интерес, проявляемый к термальным представлениям [1, 16, 27, 36, 37, 39]. Существенным в изучении таких представлений явился результат Э. Поста об описании всех порожденных с помощью суперпозиции классов булевых функций, так называемых замкнутых классов булевых функций [43, 44]. Первоначальное доказательство этого результата было упрощено и изложено в более доступной форме [19, 20, 38].
Теоретический, а также практический интерес вызывают вопросы, касающиеся сложности представлений булевых функций термами. С одной стороны, имеем асимптотическую оценку сложности термальных представлений булевых функций над произвольными полными базисами. О. Б. Лупановым доказано [18], что почти все булевы функции имеют сложность 2n/log п. С другой стороны, при получении эффективных нижних оценок сложности возникают определенные трудности [17, 33, 49]. На сегодняшний день все известные эффективно заданные последовательности булевых функций имеют лишь полиномиальные оценки сложности [3, 21, 31, 32, 40, 41, 42, 45]. Таким образом, можно сказать, что исследования в этом направлении еще далеки от завершающей стадии.
_4-
При изучении вопросов сложности представлений булевых функций термами возникают такие понятия как бесповторность и слабоповтор-ность булевых функций. Бесповторные булевы функции, то есть функции, для которых существует представление в виде терма, в котором каждая переменная встречается не более одного раза, изучались еще с 50-х годов прошлого века, когда в работе А. В. Кузнецова [15] было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности. Повторные булевы функции в некотором базисе В, у которых все собственные остаточные подфункции являются бесповторными в В, называются слабоповторными в базисе В. Из результата Н. А. Перязева [25] следует, что все неразделимые булевы функции есть слабоповторные функции в некотором базисе.
Кроме того, добавление к базису бесповторной в нем функции не улучшает его в смысле сложности представлений функций термами, а слабоповторной делает улучшение базиса минимальным, что позволяет эффективно сравнивать базисы по сложности термальных представлений [35]. Отметим также, что такое расширение базиса существенно увеличивает число бесповторных булевых функций [10].
Бесповторные булевы функции интересны как функции наименьшей сложности, и это прекрасно объясняет тот факт, что при проектировании микропроцессоров используются в большей части бесповторные функции в базисе из конъюнкции, дизъюнкции и отрицания [4]. Важность изучения бесповторных функций подтверждает и указанный выше результат А. В. Кузнецова, из которого следует, что по многим вопросам изучение всех булевых функций сводится к изучению неразделимых функций.
Полное описание слабоповторных функций над некоторым базисом может быть полезным при исследовании свойств данного базиса. Например, в работе К. Д. Кириченко [И] описан метод, использующий описа-
ние слабоповторных функций, который позволяет достаточно легко доказывать критерии бесповторности для произвольных базисов.
Изучение слабоповторных булевых функций в различных базисах позволяет создать классификацию неразделимых булевых функций, которая может быть использована как в теоретических, так и в практических целях.
О. Б. Лупановым замечено (результат сформулирован в [30]), что элементарный базис Во ={V, , —,0,1} является самым плохим по сложности реализаций функций термами. Слабоповторные булевы функции в этом базисе в терминах обобщенной однотипности были найдены В. А. Стеценко, им же было доказано, что предплохие базисы имеют следующий вид BqU {/}, где / - слабоповторная функция в Во [28, 29, 48]. В обратную сторону это утверждение доказано Д. Ю. Черухиным [34]. Таким образом, все базисы, описанные В. А. Стеценко, являются предэле-ментарными.
Следующий шаг в этом направлении был сделан Н.А. Перязевым [26], описавшим слабоповторные булевы функции в предэлементарном базисе В\ ={, V, , —,0,1}. Затем К. Д. Кириченко дал описание всех слабоповторных булевых функций для двух серий предэлементарных базисов [13].
Во второй и третьей главах данной диссертации автор завершает описание слабоповторных булевых функций в предэлементарных базисах, рассмотрев парасимметрические и серию немонотонных базисов, тем самым поставив точку в описании базисов, непосредственно предшествующих предэлементарным.
Диссертация состоит из введения, трех глав, разбитых на 6 параграфов, заключения и списка литературы.
Во введении дается обоснование актуальности темы исследований.
В первой главе определяются основные понятия и терминология, принятая при изложении результатов, а также делается обзор основных
результатов, в том числе автора, по вопросам, рассматриваемым в диссертации.
Во второй главе исследуются свойства бесповторных булевых функций в предэлементарных базисах. С использованием этих свойств далее получено полное описание слабоповторных булевых функций в серии предэлементарных немонотонных базисов.
В третьей главе получены полные описания слабоповторных булевых функций в предэлементарных парасимметрических базисах порядка 4 и 5.
По результатам, изложенным в диссертации, опубликовано 6 научных работ [50] - [55], отражающих основное содержание диссертации. Результаты диссертации были представлены на XII Байкальской международной конференции (Иркутск, 2001), XIII Международной конференции "Проблемы теоретической кибернетики "(Казань, 2002), IV Российской конференции "Дискретный анализ и исследование операций"(Новосибирск, 2002), II Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003), а также неоднократно докладывались на семинарах Иркутского государственного университета и Иркутского государственного педагогического университета.
В диссертации принята сквозная нумерация утверждений. Теоремы, принадлежащие другим авторам, нумеруются римскими числами. Список литературы приводится в алфавитном порядке, работы автора расположены в конце списка в хронологическом порядке.
Обзор результатов по слабоповторным и бесповторным булевым функциям
Прежде, чем перейти непосредственно к результатам по слабоповторным булевым функциям, необходимо привести важные результаты по бесповторным булевым функциям в силу уже отмечавшейся неразрывной связи этих понятий. Вначале небольшая историческая справка. Понятие неразделимых булевых функций возникло в шестидесятых годах при изучении мости-ковых схем, то есть таких контактных схем, которые нельзя составить из контактов путем одних лишь параллел только тогда, когда они являются близкими. Из этой теоремы следует, что представление булевой функции в виде бесповторной суперпозиции неразделимых булевых функций является в некотором смысле единственным, то есть при фиксации определенного порядка переменных, например по возрастанию индексов, при бесскобочной записи для ассоциативных функций, когда отрицание встречается только над переменными, получаем канонический вид для представления функции в виде бесповторной суперпозиции неразделимых булевых функций. Для нахождения такой суперпозиции для конкретных функций использовался следующий критерий. Теорема II ([15]) 1) Множество переменных v является выделимым в фунщии /(й, v) тогда и только тогда, когда среди остаточных подфункций f по v найдется не более 2 различных. 2) Мноэюество переменных й является ковыделимым в функции /(й, v) тогда и только тогда, когда всякая остаточная подфункция f по й равна либо константе, либо некоторой функции t(v), либо t(v). Еще один такой критерий был получен К. Д. Кириченко. Теорема III ([14]) 1) Мноэюество переменных v функции /(й, v) является выделимым тогда и только тогда, когда имеется переменная у Є й такая, что v совместно выделимо в fy и fy. 2) Множество переменных й функции /(й, v) является основным тогда и только тогда, когда имеется переменная у Є v такая, что и является совместно основным в fy и fy. Первый критерий бесповторности в базисе BQ принадлежит Б. А. Субботовской. Теорема IV ([30]) Функция f является бесповторной в базисе Во тогда и только тогда, когда для всех д, где g = /, либо g - остаточная подфункция функции f, выполняется следующее свойство: для любой существенной переменной у функции д, среди остаточных функций д и ду ровно одна имеет фиктивные переменные, которые являются существенными в д. Следуя [2], объединим все критерии бесповторности для базисов Во и В\ в общие теоремы. Булева функция называется вырожденной, если эквивалентная ей существенная функция является четной.
Булева функция / называется жесткой, если она неунарная, и существует переменная х Є p(f) такая, что выполняются равенства 6(f) = 5(/ ) = (/х1) Булева функция называется строго нежесткой, если для любой переменной х Є р либо 6(f) ф S(f), либо 6(f) ф 5(f];) или она унарная. Булева функция g называется недиффузной, если любая простая им пликанта К функции g имеет ровно одну общую переменную с любой простой импликантой J функции д, то есть х(-Ю П х( ) = 1 Теорема V ([2ьных и последовательных соединений. Из инженерной практики был отмечен факт, что уже для некоторых простейших схем булевы функции, соответствующие этим схемам, не удается представить в виде такой суперпозиции функций двух переменных, чтобы каждая из переменных встречалась не более одного раза. Представляет большой интерес следующий результат А. В. Кузнецова, исследовавшего эту проблему. Термы Ф и Ф над базисным множеством В будем называть близкими (обозначение: Ф Ф), если существует последовательность термов Фі,...,Фт такая, что Ф = Фі, Ф = Фт и ФАН-І получается из Ф (к = 1,..., т — 1) применением одного из следующих тождеств близости: Теорема I ([15]) Два бесповторных терма над множеством неконстантных неразделимых функций являются эквивалентными тогда и только тогда, когда они являются близкими. Из этой теоремы следует, что представление булевой функции в виде бесповторной суперпозиции неразделимых булевых функций является в некотором смысле единственным, то есть при фиксации определенного порядка переменных, например по возрастанию индексов, при бесскобочной записи для ассоциативных функций, когда отрицание встречается только над переменными, получаем канонический вид для представления функции в виде бесповторной суперпозиции неразделимых булевых функций. Для нахождения такой суперпозиции для конкретных функций использовался следующий критерий. Теорема II ([15]) 1) Множество переменных v является выделимым в фунщии /(й, v) тогда и только тогда, когда среди остаточных подфункций f по v найдется не более 2 различных. 2) Мноэюество переменных й является ковыделимым в функции /(й, v) тогда и только тогда, когда всякая остаточная подфункция f по й равна либо константе, либо некоторой функции t(v), либо t(v). Еще один такой критерий был получен К. Д. Кириченко. Теорема III ([14]) 1) Мноэюество переменных v функции /(й, v) является выделимым тогда и только тогда, когда имеется переменная у Є й такая, что v совместно выделимо в fy и fy. 2) Множество переменных й функции /(й, v) является основным тогда и только тогда, когда имеется переменная у Є v такая, что и является совместно основным в fy и fy. Первый критерий бесповторности в базисе BQ принадлежит Б. А. Субботовской. Теорема IV ([30]) Функция f является бесповторной в базисе Во тогда и только тогда, когда для всех д, где g = /, либо g - остаточная подфункция функции f, выполняется следующее свойство: для любой существенной переменной у функции д, среди остаточных функций д и ду ровно одна имеет фиктивные переменные, которые являются существенными в д. Следуя [2], объединим все критерии бесповторности для базисов Во и В\ в общие теоремы. Булева функция называется вырожденной, если эквивалентная ей существенная функция является четной. Булева функция / называется жесткой, если она неунарная, и существует переменная х Є p(f) такая, что выполняются равенства 6(f) = 5(/ ) = (/х1) Булева функция называется строго нежесткой, если для любой переменной х Є р либо 6(f) ф S(f), либо 6(f) ф 5(f];) или она унарная. Булева функция g называется недиффузной, если любая простая им пликанта К функции g имеет ровно одну общую переменную с любой простой импликантой J функции д, то есть х(-Ю П х( ) = 1 Теорема V ([2]) Для любой булевой функции f равносильны следующие условия: являются Б. А. Суб-ботовская [30] (наследственные нежесткость и строгая нежесткость), В. А. Гурвич [8, 9] (недиффузность), Н. А. Перязев [23] (наследственная невырожденность).
Слабоповторные булевы функции в серии предэлементарных немонотонных базисов
В этом параграфе найдены слабоповторные функции в серии предэлементарных немонотонных базисов. Основными утверждениями являются Лемма 9 Для булевой функции g(x\,X2,x$) = Х\(х24х$)Ух2Х и базиса В = BQ U {д} булева функция / слабоповторна в В и неслабоповторна в BQ тогда и только тогда, когда f обобщенно однотипна с одной из следующих функций: ДОКАЗАТЕЛЬСТВО. Достаточность. Непосредственной проверкой легко убедиться в том, что все остаточные подфункции указанных функций являются бесповторными в В, а сами функции повторны в В в силу леммы 5. Необходимость. Функция д обладает следующими очевидными свойствами: Это означает, что всегда можно избавиться от отрицания над функцией д, а обобщенная однотипность совпадает с однотипностью. Выпишем все остаточные подфункции функции #(2:1,2:2,2:3) по одной переменной. Для любой функции /, слабоповторной в В и неслабоповторной в Бо, rang / 3 потому, что / имеет остаточную подфункцию, бесповторную в В, но повторную в Во. Поочередно будем искать слабоповторные функции ранга 4, 5 и ранга большего 5. Найдем слабоповторные функции ранга 4. Имеется существенная переменная у такая, что остаточная функция /у = ga(x\l, ха2 , хаъг). Тогда функция h(y, xi, х2, хз) = fa(yf, х11,х22,23) такова, что hy = #(2:1,2:2,2:3). Очевидно, что либо hy = д(х ,х? , х? ), либо hy существенна бесповторна в Во, либо h\ несущественна бесповторна в BQ. Пусть hy = д(х ,х ,х ). Рассмотрим остаточную функцию hXz = ух2Ууд3(ха , х , х ). Пусть переменная xi3 отлична от х%. Тогда в силу свойства 1 функции д считаем, что х\х равна х$. Рассмотрим остаточную функцию hX3 = ух2 V yg3 (х, х%, х%). Пусть ах = 1. Тогда h% = ух2 V ух%х% и h\3 = ухх V у(х% V з3). При xi2 = Х2 по лемме 7 (7{2 = 7j3 = 1. При ХІ3 = а?2 по лемме 7 сгг-2 = 1 и 7j3 = 0. Отсюда имеем функции h\ = уд(х\,Х2, х3) V уд(хз,х2,хі) и Лг = 2/р(жь ж2, ж3) V 2/р(жз, а?ь 2). Пусть о"1 = 0. Тогда hX3 = ух2 V у(х% V а3) и /і 3 = Sfri V yxfix . При ггг-2 = 2 по лемме 7 стг-2 = 1 и 7г-3 = 0. При агг-3 = х2 по лемме 7 (Тг-2 = (jf3 = 1. Отсюда имеем еще две функции /із = У9Іхіі х2- хз)Ууд(хз, х2, хі) и h4 = уд{хъх2,ж3) V ур(ж3 xi,х2). Пусть теперь яг-3 равна х3. Тогда Л3 = ух2 V уд х х , х%3). Пусть 7з = 1. Тогда /i3 = ух2 V уж?2 и hlX3 = ух\ V уж?1. Переменная Х{2 отлична от х2, иначе функция h = 7(жі,Ж2,жз), что невозможно. Поэтому получаем следующие функции h$ = уд(хі,Х2, жз) V уд(х2,хі,хз), he = уд(хі,х2,х3) V уд(х2,хі,х3), h7 = уд{хі,х2,х3) У уд(х2,хі,х3), Ы = 2/0(жі,ж2,ж3) V (a?2,«i,a:3). При аз = 0 также имеем функции h$ - h&. Таким образом, нужно проверить на слабоповторность в В функции h\ - hs-
Нетрудно заметить, что he - функция первого типа леммы 9, а следующие остаточные подфункции функций hi,...,h,hj,hs повторны в В, так как они слабоповторны в BQ и необобщенно однотипны с д\ hhc2 = 2/{ж ж3) Уу(ж3Ужі), h2Xl = yx2xzVyx2x3, h3\2 = y(xiVх$)Уух&ъ, hAlXi = y(x2 V ж3) V y(x2 V ж3), hbxi\2 = у 0 ж3. /i7 = уж2жз V 2/х2а?з, /г8?2 = yxixz V ужіж3. Отметим, что и в дальнейшем проверка функций на слабоповторность в В будет сводиться к нахождению остаточных подфункций, слабоповторных в Во и необобщенно однотипных с д, т. е. повторных в В. Так как это означает, что сами функции неслабоповторны в В. Пусть h = уд(х\,Х2, X3)Vyt(x\,X2, #з), где функция t - существенная и бесповторная в В$. Выпишем остаточные функции hXl = УХ2Х3 V ytXi, ЛЇІ = У(х2 V х3) V ytlXi, hX2 = yxix3 V ytX2, h\2 = у(хі V х3) V yt\2. Функция t бесповторна в Во. По теореме IV для любой переменной Х( либо tTx. = tx., т. е. Х{ фиктивна в t, либо если Хі ф tTx., то только одна из этих остаточных функций существенна. У функции t нет фиктивных переменных, поэтому только одна из остаточных функций tXl и tXl существенна. Аналогичная ситуация с tX2 и t\2. Рассмотрим случаи, когда каждая из этих остаточных функций существенна, и выясним, какой вид она имеет. Пусть tx существенна. Остаточная функция hXl либо бесповторна в Во, либо однотипна с д. Если hXi бесповторна в Во, то по теореме IV ft = #2 3- Если hXi однотипна с д, то из вида остаточных подфункций функции д либо tXl = Х2 V Х3, либо tXl = Х2 V хз Пусть tlXi существенна. Если h\ бесповторна в Во, то остаточная функция t\ = Х2 V хз- Если hlt однотипна с д, то либо tlXl = X2X3, либо tlXi = х2х3. Пусть tx существенна. Если hX2 бесповторна в Бо, то по теореме IV tX2 = X1X3. Если hX2 однотипна сд, то либо ftX2 = X1VX3, либо ftX2 = хі\/х3. Пусть tl существенна. Если hlX2 бесповторна в Во, то по теореме IV tl2 = х\ V хз- Если hl2 однотипна с д, то либо tlX2 = х\Хз, либо tlX2 = х\х3 Учитывая, что нормальное представление функции, бесповторной в Во, очень схоже с нормальным представлением существенной остаточной функции по любой существенной переменной, можно легко построить вид самой функции. К примеру, возьмем остаточную подфункцию 0 = 2а;з- Очевидно, что t может быть равна одной из следующих функций: Ж1Ж2Х3, х\ Va?2X3, (#1 Ух2)х3 и (х\Ухз)%2- Так как известен вид существенной остаточной функции по X2, остаются функции х\Х2Х3, #і Х/а з и (xi V хз)х2. После рассмотрения всех случаев имеются функции: зсі#2#з, i V Х2Хз, Х2 V Х\Х3, Х\ У Х2 V Жз, X2 V Жі з, Ж1Х2Х3, Жі V х2х3, Х\У х2У хз, (хі У хз)х2, xi(x2 V х3), xi(x2 У жз) и (5i V х3)х2. Остается проверить на слабоповторность в В следующие функции hi = yg(xi,x2,x3) У ух\х2хз, h2 = уд(хі,х2,хз) У у(хі У x2x3), h3 = У (жі, x2, хз) V t/(z2 V яіяз)- /ц = ( ь 2, з) V у{х\ У х2У ж3), frs = уд(хі, х2, хз)Уу(х2Ухіх3), h6 = yg{xi,x2j х3)Уух1х2х3, h7 = уд(хгіх2, х3)У у(хі У х2хз), h8 = уд{хі,х2,хз) У у(хі У х2 У я3), /ід = М ъ хз) V 2/( 1 V 3) 2, /ію = 27#(яі,Я2,яз) V 2/яі(ж2 V ж3), Лц = уу(а;і,я;2,а;з) V ухі(х2 У о?з), /гі2 = уд{хі,Х2,хз) У у(х\ У #з)#2- Легко заметить, что hi(y,xi,x2,x3) = h6(y,х2,хі,хз) = h±{y,xi,x2, x3) — Н (у,х2,хъхз), h2(y,xhx2,x3) = Нз(у,х2,хі,хз) = Ъ,ъ(у,х2,хъхз) = 7іп(у,хі,х2,хз), 1ЇЬ(У,ХІ,Х2,ХЗ) = h7(y,x2, хі,хз) = hio(y,x2,xi,x3) = Ы2(у,хъх2,х3). Остаточная функция h-jX2\3 = у ф х\ повторна в В, поэтому h7 неслабо-повторна в В, a, h\ к h2 - функции второго и третьего типов леммы 9 соответственно. Пусть h = уд{х\, х2,хз)\/yt(x\,х2,Х3), где функция t- несущественная и бесповторная в Во. Все переменные не являются одновременно фиктивными в t, иначе h бесповторна в В. Пусть фиктивна одна переменная. Из свойства 1 функции д следует, что достаточно рассмотреть случаи, когда фиктивны Х\ и хз Пусть h = уд(хі,х2,хз) У yt(x2,X3). Рассмотрим hXl = ух2хз У yt(x2,X3) и hXl = у{х2Ухз)Уyt(x2, хз). По лемме 7 и теореме IV функция t равна х2х3 или х2 У яз, но тогда h бесповторна в В. Пусть h = yg{xi,x2,X3)Vyt(xi,x2). Рассмотрим hQX3 = yx2Vyt(xi,X2) и hlX3 = ух\ У yt{x\,x2). Отсюда по лемме 7 имеем h\ = уд(х\,х2,хз) У ух\х2 и h2 = yg{xi}x2,x3) У у(х\ У х2). Очевидно, что hi(y,xi,x2,x3) = 2(2/, #1, 2, #з) и hi - функция четвертого типа леммы 9. Пусть фиктивны две переменные. Достаточно рассмотреть случаи, когда существенны xi и Хз- Тогда имеем hi — уд(х\,х2ухз) У yxi, h2 = уд(хих2,хз) У ухі, /г3 = уд{хих2,хз) У ух3, /ц = уд(хі,х2,х3) У ухз.
Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка
В этом параграфе получено описание слабоповторных булевых функций в предэлементарном парасимметрическом базисе порядка 5. Основным утверждением является Лемма 11 Для булевой функции д(х\,...,х$) = xi(x2 V#32:4) V2:5(2:3 V 2:22:4) и базиса В — Во U {д} булева функция f слабоповторна в В и неслабоповторна в BQ тогда и только тогда, когда f обобщенно однотипна с одной из следующих функций: ДОКАЗАТЕЛЬСТВО. Достаточность. Непосредственной проверкой легко убедиться в том, что все остаточные подфункции указанных функций являются бесповторными в Б, а сами функции повторны в В в силу леммы 3. Необходимость. Функция g обладает следующими очевидными свойствами: 1) д{х\, х2,ж3,х4, х5) = g(xh х5,х3, х4, х2). Это означает, что всегда можно избавиться от отрицания над функцией д, а обобщенная однотипность совпадает с однотипностью. -Из вида остаточных подфункций функции д следует, что нормальное представление остаточных подфункций функции, обобщенно однотипной с д, записывается термами определенных видов. К примеру, если нулевая остаточная подфункция по некоторой переменной представляется в виде терма Фі(Фг V ФзФ-і)» то единичная - термом Фі V 2( 3 V Ф4). Далее, если известно нормальное бесповторное в BQ представление одной остаточной подфункции по любой переменной, можно построить ровно две функции, однотипные с д, которые имеют такую остаточную подфункцию. Например, пусть / однотипна с д и f = #1(2:2 V 2:3X4). Стоит задача расстановки переменных. В силу свойства 1 функции д фиксируем переменную у на первой позиции. Из вида остаточных подфункций функции д переменная 2:1 на пятой позиции, 2 - на третьей. Так как 2:3 и х4 симметричны в остаточной функции fy, получаем два варианта для /: Для любой функции /, слабоповторной в В и неслабоповторной в В0, rang / 5 потому, что / имеет остаточную подфункцию, бесповторную в В, но повторную в Во. Поочередно будем искать слабоповторные функции ранга б, ранга 7 и ранга большего 7. Найдем слабоповторные функции ранга 6. Имеется существенная переменная у такая, что / = g(J(xall,..., 2:55). Тогда для h(y, xi,...,x5) = fa{yf, х\\ ..., 2:55) выполняется hQy = #(2:1,..., хъ). Для любых Xk и о в ЩаХк все переменные входят без отрицаний, поэтому в силу леммы 2 все переменные входят в hi без отрицаний. Очевидно, что либо hy = д(х{1,... ,Х{Ъ), либо hy существенна бесповторна в Во, либо hy несущественна бесповторна в
Во. Пусть hy = д(х(1,... ,Х{5). Рассмотрим остаточную функцию hXi = у(х\х2 \Zx3xs) Ууд х ,..., ХІ5). Из вида остаточных подфункций функции д следует, что переменная х4 находится на 4-ой позиции, т. е. h = уд{х\,...,хъ) V уд(х ,xi2,xi3,x4,xib). Учитывая свойство 1 функции д, остается проверить на слабоповторность функции h\ = уд{х\,..., 5) V yg(xi,X2,x5,x4,x3), h2 = yg{xi,...,x5)Vyg(xi,x3,х2,х4,х5), h3 = yg{xY, ,5) V yg(xi,x3,x5,x4,x2), h4 = yg(xi,...,x5) V уд{хх,хъ,x2,x4,x3) и 5 — ( 1,...,15) V yg(xi,X5,x3tX4,x2). Следующие остаточные подфункции функций hi,..., hr, повторны в В, так как они слабоповторны в Во и необобщенно однотипны с д: /iii3i4J5 = ХЛХ2 V у) V х2у, h2xiXiXb = ух2 V yx3, h3\lXiXb = ух2 V ух3, /i4x224S5 = УХі V ух3, hblX2XlXb = ухх V ух3. Отметим, что и в дальнейшем проверка функций на слабоповторность в В будет сводиться к нахождению остаточных подфункций, слабоповторных в Во и необобщенно однотипных с д, т. е. повторных в В. Так как это означает, что сами функции неслабоповторны в В. Пусть h = уд{х\,..., х$) Vyt(xi,..., х$), где функция t - существенная и бесповторная в Во- Выпишем остаточные функции hXl = ух {х3 V х2х4) V ytXi, hlXl = у(х2 V х3(х4 V хъ)) V ytlXl, hX2 = yx3(xix4 V хъ) V ytX2, hlX2 = y(xi V x5(x3 V x4)) V yt\2. Функция t бесповторна в Во- По теореме IV для любой переменной Х{ либо tTx. = tTx., т. е. Х{ фиктивна в t, либо если tT ф tTx., то только одна из этих остаточных функций существенна. У функции t нет фиктивных переменных, поэтому только одна из остаточных функций tXl и t\ существенна. Аналогичная ситуация с tX2 и tX2. Рассмотрим случаи, когда каждая из этих остаточных функций существенна, и выясним, какой вид она принимает. Пусть tXl существенна.
Остаточная функция hXl либо бесповторна в BQ, либо однотипна с д. Если hXl бесповторна в Во, то по теореме IV tx = х$(хз V X2X4). Если hx однотипна с д, то способом, описанным в начале доказательства леммы 11, находим; что либо tx = Х2 V2:3( 4VX5), Либо tQXl = Х4 V хз{х2 V х$). Пусть tXx существенна. Если hXl бесповторна в Во, то остаточная функция tlXi = Х2 V хз(х4 V xs). Если hlXi однотипна с д, то либо tlXl = Х {хз V Х2Х4), Либо tlXi = Х4{хз V Х2Х5). Пусть tX2 существенна. Если hX2 бесповторна в Во, то по теореме IV tX2 = хз(хіХ4\/Х5). Если hX2 однотипна с д, то либо tX2 = Х\ Vx${x?, VХ4), либо tX2 = (хіхз V Х5). Пусть t\2 существенна. Если hX2 бесповторна в Во, то по теореме IV tlX2 — х\ V хг, (х$ V Х4) Если hx однотипна с д, то либо tx = Х3 {х\Х4 V х), либо 2 = Х4 (3:1X3 V б) Учитывая, что нормальное представление функции, бесповторной в Во, очень схоже с нормальным представлением существенной остаточной функции по любой существенной переменной, можно легко построить вид самой функции. К примеру, возьмем остаточную подфункцию tXi = х (хз V 0:2X4). Очевидно, что t может быть равна одной из следующих ФУНКЦИЙ: XiVX5(x3VX2X4), Xs(xi VX3VX2X4), (х\ V Х5)(х3 V Х2Х4), 5 3 V (х\ V 0:2)3:4), 0:5( 3 V 2(3:1 V Х4)). Так как известен вид существенной остаточной функции по Х2, остается только функция Х\ V х${х$ V Х2Х4). После рассмотрения всех случаев имеются следующие функции х\ V 5(3:3 V 2 ), 3:2 V3:3(3:13:4 V3:5) и 3:4(3:13:3 V 3:23:5). Остается проверить на слабоповторность в В функции h\ = уд{х\,... ,3:5)Уу{х\ N/3:5(3:3Х/з з )), Ь.2 - yg{xi,... ,xr0)\Zy(x2\/ x3(xix4\/ х5)), h3 = yg(xi,..., x5) V 2/x4(xix3 V 3:2X5). Легко заметить, что h\(y, X\,X2, X3, X4, X5) = /12(2/, X2, x\, X5, X4, X3), остаточная функция h\QX2lXi = x\(y VX3) V X3X5 повторна в Во, поэтому h\ неслабоповторна в В, а /із - функция первого типа леммы 11. Пусть h = yg(xi,..., х5) V yt(xh ..., х5), где функция t - несущественная и бесповторная в Во. Все переменные не являются одновременно фиктивными в t, иначе h бесповторна в В.
Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка 4
В этом параграфе получено описание слабоповторных булевых функций в предэлементарном парасимметрическом базисе порядка 4. Основным утверждением является Лемма 12 Для булевой функции g(xi,... ,х4) = х\(х2 V х ) V х$х4 и базиса В = BQU {g} функция f слабоповторна в В и неслабоповторна в Во тогда и только тогда, когда f обобщенно однотипна с одной из следующих функций: ДОКАЗАТЕЛЬСТВО. Достаточность. Непосредственной проверкой легко убедиться в том, что все остаточные подфункции указанных функций являются бесповторными в В. Функции 1-4 типа повторны в В по лемме 5. Функция 5 типа повторна в В в силу следующих соображений: если функция ранга б бесповторна в В и по некоторой переменной имеет остаточную подфункцию х2д(х3,...,Хб), то другая остаточная подфункция но этой переменной несущественна, что легко проверяется. Необходимость. Функция д обладает очевидными свойствами: 1) 9{xi,x2,x3,x4) = д{х3,х4,хъх2), 2) g{xi,x2,x3,x4) = g(xi,x4,x3,x2). Это означает, что всегда можем избавиться от отрицания над функцией д, а обобщенная однотипность совпадает с однотипностью. Выпишем все остаточные подфункции функции д{х\,..., #4) по одной переменной. Из вида остаточных подфункций функции д следует, что нормальное представление остаточных подфункций функции, обобщенно однотипной с д, записывается термами определенных видов. К примеру, если нулевая остаточная подфункция по некоторой переменной представима термом Фі(Фг\/Фз), то единичная - термом Фі V 24f3. Если известно нор мальное бесповторное в Во представление одной остаточной подфункции по любой переменной, можно построить ровно две различные функции, однотипные с д, которые имеют такую остаточную подфункцию. Например, пусть / однотипна с д и /J" = х\(х2 V х3). Стоит задача расстановки переменных. В силу свойства 1 функции д фиксируем переменную у на второй позиции. Из вида остаточных подфункций функции д переменная xi на третьей позиции. Так как х2 и х3 симметричны в остаточной функции f, получаем два варианта для /: д(х2,yf,xi,x3) и д(х3,ут,х\,х2). Очевидно, что для любой функции /, слабоповторной в В и несла-боповторной в Во, rang / 4, так как она должна иметь остаточную подфункцию бесповторную в В, но повторную в J5Q. Поочередно будем искать слабоповторные функции ранга 5, ранга б и ранга большего 6. Найдем слабоповторные функции ранга 5. Имеется существенная переменная у, такая что /J" = да{х [1,..., х4). Тогда для h(y, х\,..., Х4) = fa{yT, хах\ ..., rcj4) выполняется hy = g(xi,..., х4). Для любых Xk и а в hyk все переменные входят без отрицаний, поэтому в силу леммы 2 все переменные входят в hy без отрицаний. Для остаточной функции hy нужно рассмотреть три случая: hly = д(х ,... ,гг;4); hy бесповторна в Во и не имеет фиктивных переменных; hy бесповторна в Во и имеет фиктивные переменные. hb = yg{x\,. hi = yg{xu. h = У9Ы,. hi = yg{xi, Пусть hi = g(xixi..., хІ4). Тогда h = уд{хъ ..., х4)Ууд{хІІ,хІ2, хіз, хІ4).
Учитывая свойство 1 функции д, возможны следующие функции h\ = уд(хи...,х4) V уд(х1,х2,Х4,х3), h2 = yg(xi,..., x4) V yg(xux3,x2,x4), h3 = 2/0( 1,..., 4) Vyg{xi, x3,x4,x2),h4 = yg{xi,...,x4)Vyg(xi,X4,x2,x3), , х4)Ууд(хі, x4, x3, x2), h6 = уд(хъ ..., x4)Vyg{x2, x\, x3, x4), , x4)Vyg(x2, xi, x4, x3), h8 = yg(xu -, x4)Vyg(x3, хъ x2, x4), , x4)Vyg(x3, xi, x4, x2), hio = уд{хъ ..., x4)Wyg(x4, xu x2, x3), ., x4) V yg(x4, x\, x3, x2). Следующие остаточные функции от hi,..., /іб, h%7..., h\\ повторны в В, так как они слабоповторны в Во и необобщенно однотипны с д: h\l = 0:4(2:3 V у) V х3у, h2\ = ух3 V ух2, h-j - функция первого типа леммы 12. Отметим, что и в дальнейшем проверка функций на слабоповтор-ность в В будет сводиться к нахождению остаточных подфункций, слабоповторных в Во и необобщенно однотипных с д, т. е. повторных в В. Так как это означает, что сами функции неслабоповторны в В. Пусть h = уд{х\,..., х$) Vyt(x\y...,х$), где функция t - существенная и бесповторная в BQ. Выпишем следующие остаточные функции: hX2 = Функция t бесповторна в Во, по теореме IV для любой переменной Х{, либо tTx. = tTx., то есть ХІ фиктивна в t, либо если tx. ф tx., то одна и только одна из этих остаточных функций существенна. Так как в t нет фиктивных переменных, одна и только одна из остаточных функций tX2 и t\2 существенна, аналогичная ситуация с tX4 и tl4. Из предположения, что каждая из остаточных функций может быть существенна, рассмотрим все эти случаи и выясним, какой вид при этом они могут иметь. Пусть tX2 существенна. Остаточная функция hX2 может быть, либо бесповторной в Во, либо однотипной с д. Если hX2 бесповторна в Во, то по теореме IV tX2 = хз{х\Ух4). Если hX2 однотипна с д, то tX2 = x\Vx$x4, либо х4 V х\х%. Пусть tl существенна. Если hlX2 бесповторна в BQ, то tlX2 = х\ V х$х4. Если /42 однотипна к д, то t\ = х$(х\ V х4), либо х4{х\ V 0:3) Пусть tXi существенна. Если hX4 бесповторна в Бо, то по теореме IV tXi = х\(х2\/хъ). Если hXi однотипна с д, то tXi = x\x2Vx$, либо х\ХзУх2. Пусть t\. существенна. Если hlX4 бесповторна в BQ, то 4 = х\х2 Ух%. Если /І 4 однотипна с д, то tlX4 = х\(х2 V хз), либо х2(х\ V хз). Известно, что функция t существенна и бесповторна в BQ ОТ четы рех переменных, и переменные входят в нормальное представление t без отрицаний. Учитывая, что нормальное представление функции, бесповторной в Во, очень схоже с нормальным представлением существенной остаточной функции по любой существенной переменной, можно легко построить вид самой функции. К примеру, возьмем остаточную подфункцию t = 2:3(2:1 V х\). Очевидно, что t может быть равна одной из следующих функций: Х2 V хз(хі V хд), {х\ V 2:4)(2:2 V 2:3), 2:3(2:1 V Х2 V 4). Так как известен вид существенной остаточной функции по х\, остаются функции {х\ V 2:4)(0:2 V 3) и %2 V хз(х\ V Хд).
