close

Вход

Забыли?

вход по аккаунту

?

О бесповторных булевых функциях в некоторых базисах.

код для вставкиСкачать
И.К. Шаранхаев. О бесповторных булевых функциях в некоторых базисах
УДК 519.71
ББК 22.176
© И.К. Шаранхаев
Бурятский государственный университет, Улан-Удэ
О бесповторных булевых функциях в некоторых базисах
Изучается реализация булевых функций в классе формул. Доказаны необходимые и достаточные
условия выразимости булевых функций бесповторными формулами в некоторых базисах.
Ключевые слова: булевы функции, бесповторные формулы.
© I.K. Sharankhaev
Buryat State University, Ulan-Ude
On repetition-free Boolean functions in some bases
The realization of Boolean functions by formulas is studied. The necessary and sufficient conditions of
representation of Boolean functions by repetition-free formulas in some bases are proved.
Key words: Boolean functions, repetition-free formulas.
Введение
Настоящая работа посвящена нахождению условий, равносильных бесповторности
булевых функций в конечных полных множествах (базисах).
Дадим необходимые определения и обозначения, все неопределяемые понятия можно
найти, например, в [1].
Формула Φ над базисом В называется бесповторной, если каждая переменная входит в
нее не более одного раза.
Функция f называется бесповторной в базисе B, если существует бесповторная формула
Φ над В, представляющая функцию f. В противном случае f называется повторной в B.
Функция, получаемая из f(x1,…,xn) подстановкой вместо некоторой переменной xi
константы σ , называется остаточной и обозначается f xσi . Индуктивно это определение
распространяется на подмножество переменных.
Назовем переменную xi функции f фиктивной, если f x0i = f x1i , и существенной в
противном случае. Множество всех существенных переменных функции f обозначим через
ρ (f), а множество всех фиктивных переменных функции f через δ (f).
Функция f называется слабоповторной в базисе B, если любая остаточная функция от
функции f является бесповторной, а сама f повторнa в базисе B. Через S B и PB обозначим
множество всех слабоповторных и бесповторных функций в базисе B , соответственно.
Базис B0={ ∨ , · , −, 0, 1} называется элементарным, а базис B0 ∪ {f}, где f слабоповторна
в B0, называется предэлементарным.
Описание всех предэлементарных базисов следует из [2]. В работе [3] введены
следующие обозначения для таких базисов:
B1, n=B0 ∪ {g1, n}, где g1, n = x1·…·xn ∨ x1 ·…· x n и n ≥ 2;
B2, n=B0 ∪ {g2, n}, где g2, n = x1(x2 ∨ ... ∨ xn) ∨ x2 ⋅…⋅ xn и n ≥ 3;
B3, n=B0 ∪ {g3, n}, где g3, n = x1(x2 ∨ x3 ⋅…⋅ xn) ∨ x2 x3 ⋅…⋅ xn и n ≥ 3;
B4=B0 ∪ {g4}, где g4= x1(x2 ∨ x3) ∨ x3x4;
B5=B0 ∪ {g5}, где g5= x1(x2 ∨ x3x4) ∨ x5(x3 ∨ x2x4).
В [3-10] найдены условия, равносильные бесповторности булевых функций для базисов
B0, B1, 2, B2, n, B3, 3, B5, где n ≥ 3. В данной статье получены необходимые и достаточные
условия бесповторности булевых функций в базисах B4 и B1, n, где n – нечетное число,
большее 1.
Будем говорить, что функции f и g связаны отношением ≺ , и писать f ≺ g, если для
любого набора σ~ выполняется f( σ~ ) ≤ g( σ~ ).
237
ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2010/9
Функция f называется обобщенно монотонной по переменной x, если выполняется либо
f ≺ f x1 , либо f x0 ≻ f x1 . Для краткости записи обобщенную монотонность функции f по
переменной x будем обозначать так: f ∈ Mx.
Функции f и g называются обобщенно однотипными, если
0
x
f ( x1 ,..., xn ) = g σ ( xiσ1 1 ,..., xiσn n ) ,
где (i1 ,..., in ) – некоторая перестановка чисел от 1 до n . Очевидно, что на множестве всех
булевых функций отношение обобщенной однотипности является отношением
эквивалентности.
Производной функции f ( x1 ,..., xn ) по переменной xi называется функция:
∂f
= f x0i ⊕ f x1i .
∂xi
Понятие производной функции по переменной распространяется индуктивно на
множество переменных следующим образом:


∂f

∂


x
x
∂
...
∂
∂f
i1
i s −1 

=
.
∂xi1 ...∂xis
∂xis
f x/i =
Функция называется нечетной, если число наборов, на которых функция равна 1,
является нечетным, и четной в противном случае.
Множество булевых функций P , содержащее тождественную функцию, называется
наследственным, если для любой функции f ∈ P любая остаточная функция f xσ ∈ P .
Множество булевых функций P называется инвариантным, если для любых функций
f (u~ , y ) , g (v~ ) ∈ P , где u~ ∩ v~ = ∅ , справедливо включение f (u~ , g (v~ )) ∈ P .
При доказательстве основных результатов будут использоваться следующие
утверждения.
Предложение 1 [9]. Множество булевых функций P является наследственным и
инвариантным тогда и только тогда, когда P есть множество всех бесповторных функций
над некоторым базисом B .
Следствие 1. Если для наследственного и инвариантного множества булевых функций
P и базиса B верно, что B ⊆ P и S B ∩ P = ∅ , то PB = P .
Таким образом, для доказательства того, что некоторое множество булевых функций P
совпадает с множеством всех бесповторных функций над некоторым базисом B ,
достаточно показать, что P обладает свойствами наследственности и инвариантности, и
проверить, что все слабоповторные в B функции не входят в P .
Предложение 2 [11]. Следующая система булевых функций является полной системой
представителей классов эквивалентности по отношению обобщенной однотипности для
булевых функций, слабоповторных в предэлементарном базисе B4:
x1(x2 ∨ x3x4) ∨ x5(x3 ∨ x2x4);
x1(x2 ∨ ... ∨ xk) ∨ x2 ⋅…⋅ xk, k ≥ 3;
x1(x2 ∨ x3 ⋅…⋅ xk) ∨ x2 x3 ⋅…⋅ x k , k ≥ 3;
x1 ⋅…⋅ xk ∨ x1 ⋅…⋅ x k , k ≥ 2;
x1 g(x2,…,x5) ∨ x1g(x3, x2, x5, x2);
x1 g(x2,…,x5) ∨ x1x3x5(x2∨x4);
x1 g(x2,…,x5) ∨ x1(x2x3∨x4x5);
x1 g(x2,…,x5) ∨ x1x3(x2∨x4x5);
x1 x2g(x3,…,x6) ∨ x1g(x2x3, x4, x5, x6).
238
И.К. Шаранхаев. О бесповторных булевых функциях в некоторых базисах
Предложение 3 [12]. Следующая система булевых функций является полной системой
представителей классов эквивалентности по отношению обобщенной однотипности для
булевых функций, слабоповторных в предэлементарном базисе B1, n, где n – нечетное
число, большее 1:
x1(x2 ∨ x3) ∨ x3x4;
x1(x2 ∨ x3x4) ∨ x5(x3 ∨ x2x4);
x1(x2 ∨ ... ∨ xk) ∨ x2 ⋅…⋅ xk, k ≥ 3;
x1(x2 ∨ x3 ⋅…⋅ xk) ∨ x2 x3 ⋅…⋅ x k , k ≥ 3;
x1 ⋅…⋅ xk ∨ x1 ⋅…⋅ x k , k ≥ 2, k ≠ n;
x1 g(x2,…,xn+1) ∨ x1⋅…⋅xn+1;
x1 ⋅…⋅ x n −1 g (xn,…,x2n-1) ∨ x1⋅…⋅x2n-1;
x1 ⋅…⋅ x n g(xn+1,…,x2n) ∨ x1⋅…⋅x2n.
Основные результаты
В этом разделе доказаны необходимые и достаточные условия бесповторности булевых
функций в базисах B4 и B1, n, где n – нечетное число, большее 1.
Функцию f будем называть 4 - нежесткой, если либо rang f < 2, либо для любого
x ∈ ρ (f) справедливо включение f ∈ Mx выполняется одно из условий:
1) для некоторой константы σ справедливы δ (f) ⊂ δ ( f xσ ) и δ (f) = δ ( f xσ ), причем
если δ ( f xσ ) \ δ (f)={ y }, то не выполняется соотношение δ (f) = δ ( f y0 ) = δ ( f y1 );
2)
δ (f) ⊂ δ ( f x0 ), δ (f) ⊂ δ ( f x1 ) и найдется переменная y ∈ ρ ( f x/ ), такая, что
δ ( f x/ ) ⊂ δ (( ( f x/ ) /y );
3) δ (f) ⊂ δ ( f x/ ).
Функцию f будем называть наследственно 4 - нежесткой, если сама f и все ее
остаточные функции являются 4 - нежесткими.
Теорема 1. Булева функция f бесповторна в базисе B4, тогда и только тогда, когда она
является наследственно 4 - нежесткой.
Доказательство. Для доказательства теоремы воспользуемся методом, основанным на
предложении 1.
Обозначим через Р множество всех наследственно 4 - нежестких функций. Множество Р
является наследственным по определению, покажем его инвариантность.
Пусть f (u~, v~ ) = g (u~, h(v~ )) , где g (u~, y ) , h(v~ ) ∈ P. Если u~ = ∅ или | v~ | = 1, то функция f
обобщенно однотипна с g или h, поэтому является наследственно 4 - нежесткой. Далее
считаем, что u~ ≠ ∅ или | v~ | > 1.
1. Пусть x ∈ v~ . Если для некоторой константы σ справедливы δ (h) ⊂ δ ( hxσ ) и δ (h) =
δ ( hxσ ), то выполняются δ (f) ⊂ δ ( f xσ ) и δ (f) = δ ( f xσ ). Причем если δ ( f xσ ) \ δ (f)={ y },
то δ ( hxσ ) \ δ (h)={ y } и не выполняется условие δ (f) = δ ( f y0 ) = δ ( f y1 ), так как неверно,
что δ ( f) = δ ( hy0 ) = δ ( h1y ).
Пусть δ (h) ⊂ δ ( hx0 ) и δ (h) ⊂ δ ( hx1 ). Найдется переменная z такая, что выполняется
δ ( hx/ ) ⊂ δ (( (hx/ ) /y ), а значит δ ( f x/ ) ⊂ δ (( ( f x/ ) /z ).
Пусть δ (h) ⊂ δ ( hx/ ). Так как справедливо f x/ = g y/ (u~, y ) ⋅ hx/ (v~ ) , выполняется строгое
включение δ (f) ⊂ δ ( f x/ ).
2. Пусть x ∈ u~ . Если для некоторой константы σ справедливы δ (g) ⊂ δ ( g σx ) и δ (g) =
δ ( g σx ) и при этом одновременно δ ( f xσ ) \ δ (f)={y} (выполнение последнего условия
239
ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2010/9
необязательно), тогда выполняется условие δ (f) = δ ( f y0 ) = δ ( f y1 ), так как неверно, что
δ (g) = δ ( g 0y ) = δ ( g 1y ).
Пусть δ (g) ⊂ δ ( g x0 ) и δ (g) ⊂ δ ( g 1x ). Если найдется переменная z, отличная от y и
такая, что δ ( g x/ ) ⊂ δ (( ( g x/ ) /z ), то δ ( f x/ ) ⊂ δ (( ( f x/ ) /z ). В противном случае выберем
произвольным образом z1 ∈ vɶ и рассмотрим ( f x/ ) /z1 = ( g x/ ) /y (uɶ, y ) ⋅ hz/1 (vɶ ) . В силу того, что
δ ( g x/ ) ⊂ δ (( ( g x/ ) /y ) справедливо δ ( f x/ ) ⊂ δ (( ( f x/ ) /z ).
1
Пусть δ (g) ⊂ δ ( g x/ ). Ясно, что δ (f) ⊂ δ ( f x/ ).
Доказательство того, что f ∈ Mx для любого x дословно совпадает с доказательством
аналогичного свойства в работе [4] (см. теорему 4). Таким образом, доказана
инвариантность P .
Теперь для наследственного инвариантного множества P найдем порождающий его
базис. Очевидно, что B4 ⊆ P . Проверим, что все слабоповторные функции в базисе B4 не
принадлежат P . Достаточно ограничиться проверкой функций из предложения 2, так как
если свойство 4-нежесткости не выполняется для некоторой функции, то оно не
выполняется и для всех обобщенно однотипных с ней функций.
a) f= x1(x2 ∨ x3x4) ∨ x5(x3 ∨ x2x4). Тогда
f x04 = x1x2 ∨ x3x5, f x14 = (x1 ∨ x5)(x2 ∨ x3), f x/4 = x1 x2 x3 x5 ∨ x1 x2 x3 x5 .
Функции f x04 , f x14 , f x/4 существенны, поэтому f ∉ P.
b) f = x1 ( x2 ∨ ... ∨ xn ) ∨ x2 ⋅ ... ⋅ xn , где n ≥ 3 .
f x01 = x2 ⋅…⋅ xn f x11 = x2 ∨ … ∨ xn, f x/1 = x2 ⋅ ... ⋅ xn ∨ x2 ⋅ ... ⋅ xn .
Функции f x01 , f x11 , f x/1 существенны, поэтому f ∉ P.
c) f = x1 ( x2 ∨ x3 ⋅ ... ⋅ xn ) ∨ x2 ⋅ x3 ⋅ ... ⋅ xn , где n ≥ 3 . Функция f ∉ P , так как f ∉ M x3 .
d) f = x1 ⋅ ... ⋅ xn ∨ x1 ⋅ ... ⋅ xn , где n ≥ 2 . Аналогично с), функция f ∉ P , так как f ∉ M x1 .
e) f = x1 g ( x2 ,..., x5 ) ∨ x1 g ( x3 , x2 , x5 , x4 ) . Тогда
f x01 = g ( x2 ,..., x5 ), f x11 = g ( x3 , x2 , x5 , x4 ), f x/1 = x2 x3 x4 x5 ⊕ x2 x3 x4 x5 .
Ситуация аналогична случаю b).
f) f = x1 g ( x2 ,..., x5 ) ∨ x1 x3 x5 ( x2 ∨ x4 ). Тогда
f x01 = g ( x2 ,..., x5 ), f x11 = x3 x5 ( x2 ∨ x4 ),
f x1/ = x2 x3 x4 x5 ∨ x2 x3 x4 x5 ∨ x2 x3 x4 x5 ∨ x2 x3 x4 x5 ∨ x2 x3 x4 x5 .
Функция f x/1 является нечетной, а значит, существенной. Ситуация аналогична случаю b).
g) f = x1 g ( x2 ,..., x5 ) ∨ x1 ( x2 x3 ∨ x4 x5 ). Тогда
f x01 = g ( x2 ,..., x5 ), f x11 = x2 x3 ∨ x4 x5 , f x/1 = x2 x3 x4 x5 .
Ситуация аналогична случаю b).
h) f = x1 g ( x2 ,..., x5 ) ∨ x1 x3 ( x2 ∨ x4 x5 ). Тогда
f x01 = g ( x2 ,..., x5 ), f x11 = x3 ( x2 ∨ x4 x5 ), f x1/ = x2 x3 x4 x5 ∨ x2 x3 x4 x5 ∨ x2 x3 x4 x5 .
Ситуация аналогична случаю f).
i) f = x1 x2 g ( x3 ,..., x6 ) ∨ x1 g ( x2 x3 , x4 , x5 , x6 ). Тогда
f x01 = x2 x3 x4 ∨ x2 x3 x5 , f x16 = g ( x2 , x3 x4 , x5 , x1 ).
Отсюда следует, что δ (f) ⊂ δ ( f x06 ), δ (f) = δ ( f x16 ), δ ( f x06 ) \ δ (f)={x1} и δ (f) = δ ( f x01 )
= δ ( f x11 ), что невозможно.
240
И.К. Шаранхаев. О бесповторных булевых функциях в некоторых базисах
Таким образом, S B4 ∩ P = ∅ и B4 ⊆ P . Теорема 1 доказана.
Функцию f будем называть (1,n) - нежесткой, где n ≥ 2, если либо rang f < 2, либо для
любого x ∈ ρ (f) выполняется одно из условий 1, 2, 3:
1) δ (f) = δ ( f x0 ) и δ (f) ⊂ δ ( f x1 );
2) δ (f) = δ ( f x1 ) и δ (f) ⊂ δ ( f x0 );
3) δ (f) = δ ( f x0 ) = δ ( f x1 ), f ∉ Mx и найдутся y1,…,yn-1 ∈ ρ ( f x/ ) такие, что


∂f x/
 .
δ ( f x/ ) ⊂ δ 
 ∂y1 ,..., ∂y n −1 
Функцию f будем называть наследственно (1,n) - нежесткой, если сама f и все ее
остаточные функции являются (1,n) - нежесткими.
Теорема 2. Булева функция f бесповторна в базисе B1,n, где n – нечетное число, большее
1, тогда и только тогда, когда она является наследственно (1,n-1) - нежесткой.
Доказательство. Для доказательства теоремы воспользуемся методом, основанным на
предложении 1.
Обозначим через Рn-1 множество всех наследственно (1,n-1) - нежестких функций.
Множество Рn-1 является наследственным по определению, покажем его инвариантность.
Пусть f (u~, v~ ) = g (u~, h(v~ )) , где g (u~, y ) , h(v~ ) ∈ Pn-1. Если u~ = ∅ или | v~ | = 1, то функция
f обобщенно однотипна с g или h, поэтому является наследственно (1,n-1) - нежесткой.
Далее считаем, что u~ ≠ ∅ или | v~ | > 1.
3. Пусть x ∈ v~ . Если выполняется одно из строгих включений δ (h) ⊂ δ ( hx0 ) или
δ (h) ⊂ δ ( h1x ), то соответственно либо δ (f) ⊂ δ ( f x0 ), либо δ (f) ⊂ δ ( f x1 ).
Пусть δ (h) = δ ( hx0 ) = δ ( h1x ). Рассмотрим f x/ = g y/ (u~, y ) ⋅ h x/ (v~ ) . Очевидно, что

∂hx/
существуют переменные x1,…,xn-2 ∈ ρ ( hx/ ) такие, что δ ( hx/ ) ⊂ δ 
 ∂x1 ,..., ∂x n−2
справедливо равенство:
∂f x/
∂hx/
,
= g y/ (u~ , y ) ⋅
∂x1 ,..., ∂x n −2
∂x1 ,..., ∂x n −2

 . Так как



∂f x/
 .
то δ ( f x/ ) ⊂ δ 
 ∂x1 ,..., ∂x n−2 
Докажем от противного, что f ∉ Mx. Пусть для определенности f x0 ≺ f x1 . Тогда при
любых u~, v~1 , v~2 выполняется
g (u~, h(v~1 ,0, v~2 )) ≤ g (u~, h(v~1 ,1, v~2 )).
Так как h ∉ Mx, для любого u~ имеют место неравенства
g (u~,0) ≤ g (u~,1),
g (u~ ,0) ≥ g (u~,1).
Отсюда следует, что g 0y = g 1y , то есть переменная y фиктивна, что невозможно.
4. Пусть x ∈ u~ . В случае выполнения одного из строгих включений δ (g) ⊂ δ ( g x0 )
или δ (g) ⊂ δ ( g 1x ) справедливо ровно одно из строгих включений δ (f) ⊂ δ ( f x0 ) или δ (f)
⊂ δ ( f x1 ).
Пусть δ (g) = δ ( g x0 ) = δ ( g 1x ). Рассмотрим
f x/ = g x/ (u~, h(v~ )) . Если для g x/ (u~, y )

∂g x/
существуют x1,…,xn-2 ∈ ρ ( g x/ (u~, y ) ), отличные от y, такие, что δ ( g x/ ) ⊂ δ 
 ∂x1 ,..., ∂x n−2
241

 ,

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
тогда
2010/9


∂f x/
 . В противном случае существуют
δ ( f x/ ) ⊂ δ 
 ∂x1 ,..., ∂x n−2 
y1,…,yn-3 ∈ ρ ( g x/ (u~, y ) ), отличные от y такие, что справедливо
справедливо
переменные


∂g x/
 . Выберем произвольно существенную z ∈ v~ и рассмотрим
δ ( g x/ ) ⊂ δ 
 ∂y1 ,..., ∂y n −3 ∂y 


∂g x/
∂f x/
∂g x/

=
⋅ h z/ (v~ ). В силу того, что δ ( g x/ ) ⊂ δ 
∂y1 ...∂y n−3 ∂z ∂y1 ...∂y n −3 ∂y
 ∂y1 ,..., ∂y n −3 ∂y 
справедливо
∂f x/
∂f x/
.
=
∂y1 ...∂y n −3 ∂z ∂y1 ...∂y n −3 ∂z
Докажем от противного, что f ∉ Mx. Пусть для определенности f x0 ≺ f x1 . Тогда при
любых u~1 , u~2 , v~ выполняется
g (u~1 ,0, u~2 , h(v~ )) ≤ g (u~1 ,1, u~2 , h(v~ )).
Отсюда следует, что при любых u~1 , u~2 выполняются неравенства
g (u~1 ,0, u~2 ,0) ≤ g (u~1 ,1, u~2 ,0), g (u~1 ,0, u~2 ,1) ≤ g (u~1 ,1, u~2 ,1).
Тогда g ∈ Mx, получаем противоречие. Таким образом, инвариантность Рn-1 доказана.
Осталось для наследственного инвариантного множества Рn-1 найти порождающий его
базис. Очевидно, что B1, n ⊆ Рn-1. Покажем, что все слабоповторные функции в базисе B1, n
при нечетном n не принадлежат Рn-1. Достаточно ограничиться проверкой функций из
предложения 2, так как если свойство (1,n-1) - нежесткости не выполняется для некоторой
функции, то оно не выполняется и для всех обобщенно однотипных с ней функций.
b) f= x1(x2 ∨ x3) ∨ x3x4. Тогда
f x01 = x3x4,
f x11 = x2 ∨ x3.
Обе эти остаточные функции имеют фиктивную переменную существенную в f, поэтому
f ∉ Pn-1.
c) f= x1(x2 ∨ x3x4) ∨ x5(x3 ∨ x2x4). Тогда
f x04 = x1x2 ∨ x3x5,
f x14 = (x1 ∨ x5)(x2 ∨ x3).
Функции f x04 , f x14 существенны и f ∈ M x4 , поэтому f ∉ Pn-1.
d)
f= x1(x2 ∨ ... ∨ xk) ∨ x2 ⋅…⋅ xk, где k ≥ 3. Функция f ∉ Pn-1, так как f x01 , f x11 существенны, а
f ∈ M x1 .
e)
f= x1(x2 ∨ x3 ⋅…⋅ xk) ∨ x2 x 3 ⋅…⋅ xk , где k ≥ 3. При k=3 f x03 =x2 и f x13 =x1. Обе эти
остаточные функции имеют фиктивную переменную существенную в f, поэтому f ∉ Pn-1.
При k>3 ситуация аналогична с).
f) f= x1 ⋅…⋅ xk ∨ x1 ⋅…⋅ xk , где k ≥ 2 и k ≠ n. При k=2 функция f ∉ Pn-1, так как
f x01 , f x11 существенны и f x/1 =1. При k ≥ 3
f x01 = x 2 ⋅…⋅ x k, f x11 = x2 ⋅…⋅ xk, f x/1 = x2 ⋅…⋅ xk ∨ x 2 ⋅…⋅ xk .
Легко заметить, что функции
f x01 ,
f x11 ,
что
f x/1 существенны и найдутся ровно k-2
справедливо
строгое
включение
переменных
z1,…,zk-2
таких,
/


∂f x1
 . Но k ≠ n, поэтому f ∉ Pn-1.
δ ( f x/1 ) ⊂ δ 
 ∂z1 ,..., ∂z k −2 


g) f= x1 g(x2,…,xn+1) ∨ x1⋅…⋅xn+1. Тогда
f x01 = g(x2,…,xn+1), f x11 = x2⋅…⋅xn+1, f x/1 = x 2 ⋅…⋅ x n −1 .
242
И.К. Шаранхаев. О бесповторных булевых функциях в некоторых базисах
Функции f x01 , f x11 , f x/1 существенны и для любых z1,…,zn-2 ∈ ρ ( f x/1 ) не выполняется


∂f x/1
 , поэтому f ∉ Pn-1.

строгое включение δ ( f ) ⊂ δ
 ∂z1 ,..., ∂z n −2 


h) f= x1 ⋅…⋅ x n −1 g (xn,…,x2n-1) ∨ x1⋅…⋅x2n-1. Тогда
/
x1
f x0n = x1 ⋅…⋅ x n −1 (xn+1∨…∨x2n-1),
f x1n = x1 ⋅…⋅ x n −1 ( xn +1 ∨…∨ x2 n −1 ) ∨ x1⋅…⋅xn-1⋅xn+1⋅…⋅x2n-1,
f x/n = x1⋅…⋅xn-1⋅ xn+1⋅…⋅x2n-1∨ x1 ⋅…⋅ x n −1 ⋅xn+1⋅…⋅x2n-1∨ x1 ⋅…⋅ x n −1 ⋅ xn +1 ⋅…⋅ x2 n −1 .
Остаточные функции f x0n и f x1n существенны. В силу того, что представление f x/n
является совершенной дизъюнктивной нормальной формой, нетрудно заметить, что
функция f x/n нечетная, то есть существенная. Очевидно, что производная нечетной
функции по любой переменной есть нечетная функция, поэтому имеем ситуацию,
аналогичную f).
i) f= x1 ⋅…⋅ xn g(xn+1,…,x2n) ∨ x1⋅…⋅x2n. Тогда
f x01 = x 2 ⋅…⋅ xn g(xn+1,…,x2n),
f x11 = x2⋅…⋅x2n,
f x/1 = x2⋅…⋅x2n∨ x 2 ⋅…⋅ xn xn+1⋅…⋅x2n∨ x 2 ⋅…⋅ xn ⋅ xn +1 ⋅…⋅ x2 n .
Ситуация аналогична g).
Таким образом, S B1, n ∩ Pn −1 = ∅ и B1, n ⊆ Pn −1 . Теорема 2 доказана.
Заключение
В настоящей работе описан в терминах остаточных функций класс булевых функций,
бесповторных в некоторых предэлементарных базисах. Дальнейшим продвижением в этом
направлении видится получение аналогичных результатов во всех предэлементарных
базисах.
Литература
1. Перязев Н. А. Основы теории булевых функций. – М.: Физматлит, 1999. – 112 с.
2. Стеценко В. А. О предплохих базисах в P2 // Математические вопросы кибернетики. – М.: Наука,
1992. – Вып.4. – С. 139-177.
3. Шаранхаев И. К. О бесповторных булевых функциях в предэлементарных монотонных базисах //
Дискретная математика. – 2009. – Т. 21, вып.2. – С. 88-93.
4. Перязев Н. А., Шаранхаев И. К. Критерии бесповторности булевых функций в предэлементарных
базисах ранга 3 // Дискретная математика. – 2005. – Т. 17, вып.2. – С. 127-138.
5. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами //
Докл. АН СССР. – 1963. – Т. 149, №4. – С. 784-787.
6. Гурвич В. А. Критерии бесповторности функций алгебры логики // Докл. АН СССР. – 1991. – Т.
318, №3. – С. 532-537.
7. Перязев Н. А. Реализация булевых функций бесповторными формулами в некоторых базисах //
Алгебра, логика и приложения. – Иркутск, 1994. – С. 143-154.
8. Перязев Н. А. Реализация булевых функций бесповторными формулами // Дискретная математика.
– 1995. – Т. 7, №3. – С. 61-68.
9. Кириченко К. Д. О критериях бесповторности булевых функций в различных базисах //
Оптимизация, управление, интеллект. – Иркутск, 2000. – Вып. 4. – С. 93-101.
10.Шаранхаев И. К. О реализации булевых функций бесповторными формулами в одном базисе //
Сибирский мат. журнал. – 2009. – Т. 50, №1. – С. 231-237.
11.Шаранхаев И. К. О булевых базисах второго яруса // Известия вузов. Математика. – 2004. – №3. –
С. 81-82.
12.Кириченко К. Д. Слабоповторные булевые функции в некоторых предэлементарных базисах //
Иркутский университет. Серия: Дискретная математика и информатика. – Иркутск, 2000. – Вып. 13. – 60
с.
243
Документ
Категория
Без категории
Просмотров
6
Размер файла
193 Кб
Теги
функция, булевых, бесповторных, базиса, некоторые
1/--страниц
Пожаловаться на содержимое документа