3.5 Полные системы булевых функций

Ранее было показано, что любая булева функция может быть представлена в ДНФ, в КНФ, или полиномом Жегалкина, то есть может быть выражена в базисах элементарных функций f¹; ¢; _g; или f1; ¢; ©g:

Определение. Подмножества функций © = ff1; : : : ; fmg; © µ Pn; через которые может быть выражена любая булева функция, называются функционально полными (ФП) системами булевых функций.

Теорема 3.10 Пусть ©1 функционально полная система и любая функция из нее может быть представлена суперпозицией функций из множества функций ©2. Тогда ©2 – функционально полная система.

Д о к а з а т е л ь с т в о . Булева функция f(x1; : : : ; xn) может быть представлена суперпозицией функций из полной

системы ©1 = ff0; f1; : : : ; fmg

f(x1; : : : ; xn) = f0(f1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)):

Но любая функция f0; f1; : : : ; fm может быть представлена суперпозицией функций из множества ©2; следовательно любая f(x1; : : : ; xn) также может быть представлена суперпозицией функций из ©2. Таким образом, ©2 – функционально полная система. £

Пример 3.24. © = f ¹ ; ¢; _g – полная система; f ¹ ; ¢g тоже полная, так как функцию _ можно представить суперпозицией функций: x _ y = x¹y¹; система f ¹ ; _g полная, так как функцию ¢ можно представить суперпозицией x ¢ y = x¹ _ y:¹ Полную систему f ¹ ; ¢g можно представить суперпозицией x¹ = x # x; xy = x¹ _ y¹ = (x # x) # (y # y), а полную систему f¹; _g суперпозицией x¹ = xjx; x _ y = x¹y¹ = (xjx)j(yjy): Значит системы f#g и fjg тоже полные. J

Теорема 3.10 служит основанием для выбора функционально полных систем функций. Традиционно за исходную

принимают полную систему f¹ ; ¢g и находят такую систему функций, в которой могут быть представлены функции ¹ и ¢:

Рассмотрим сначала такие множества функций, которые заведомо не являются функционально полными системами.

Определение. Множество © = ff1; : : : ; fmg

называется замкнутым классом функций, если суперпозиция любых функций из © принадлежит этому же множеству.

Множество всех булевых функций n переменных Pn = ffjf : f0; 1gn 7! 0f; 1gg – замкнутый класс, так как суперпозиция любых булевых функций есть булева функция. Рассмотрим некоторые из замкнутых подмножеств множества Pn:

1. Класс булевых функций, сохраняющих константу 0:

S0 = ffjf(0; 0; ¢ ¢ ¢ ; 0) = 0g

(на наборе всех нулей функция принимает значение 0). Классу S0 принадлежат, например, мажоритарная, ¢ и $

функции; j и # не принадлежат S0.

2. Класс функций, сохраняющих константу 1:

S1 = ffjf(1; 1; ¢ ¢ ¢ ; 1) = 1

(на наборе всех единиц функция принимает значение 1). Мажоритарная функция, ¢; _ сохраняют 1, а j и # не со-

храняют.

3. Класс самодвойственных функций

S¤ = ffjf = f¤g

(f(x1; : : : ; xn) = f¤(x1; : : : ; xn) = f¹(¹x1; : : : ; x¹n)).

Из элементарных функций самодвойственны только $ и ¹. 4. Класс монотонных функций

~ ~

SM = ffj~a 4 b ) f(~a) 6 f(b)g:

Функции ¢; _; мажоритарная монотонны, а j и # немонотонны. 5. Класс линейных функций

SL = ffjf = a0 © a1x1 © a2x2 © ¢ ¢ ¢ © anxng

(полином Жегалкина первой степени).

Линейны функции ¹ и $; а j; # и мажоритарная нелинейны.

Теорема 3.11 Классы S0; S1; S¤; SM ; SL замкнуты.

До к а з а т е л ь с т в о .

1.Суперпозиция функций из класса S0 сохраняет 0:

f(0; : : : ; 0) = f0(f1(0; : : : ; 0); : : : ; fk(0; : : : ; 0)) = f0(0; : : : ; 0) = 0:

2.Для класса S1 доказательство аналогмчно.

3.Класс самодвойственных функций S¤ замкнут:

f¤(x1; : : : ; xn) = f0¤(f1¤(x1; : : : ; xn); : : : ; fk¤(x1; : : : ; xn)) = f0(f1(x1; : : : ; xn); : : : ; fk(x1; : : : ; xn))

4. В суперпозиции монотонных функций

f0(f1(x1; : : : ; xn); : : : ; fk(x1; : : : ; xn))

~

подставим векторы ~a = (a1; : : : ; an) и b = (b1; : : : ; bn); такие,что

~

~a 4 b: Пусть

f(~a) = f0(f1(~a); : : : ; fk(~a)) = f0(~c);

как f0 монотонна, то f0(~c) 6 f0(d). Значит f(~a) 6 f(b), то есть класс SM замкнут.

5. В суперпозиции линейных функций

f0(f1(x1; : : : ; xn); : : : ; fk(x1; : : : ; xn))

каждую функцию можно представить в виде

f0(y1; : : : ; yk) = a0 © a1y1 © ¢ ¢ ¢ © akyk;

f1(x1; : : : ; xn) = b10 © b11x1 © ¢ ¢ ¢ © b1nx1;

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡¡; fk(x1; : : : ; xn) = bk0 © bk1x1 © ¢ ¢ ¢ © bknxn;

тогда

f(x1; : : : ; xn) = f0(f1(x1; : : : ; xn); : : : ; fk(x1; : : : ; xn)) =

a0 © a1f1(x1; ¢ ¢ ¢ ; xn) © ¢ ¢ ¢ © akfk(x1; ¢ ¢ ¢ ; xn) =

a0 © a1(b10 © b11x1 © ¢ ¢ ¢ © b1nxn) © ¢ ¢ ¢ © ak(bk0 © bk1x1 © ¢ ¢ ¢ bknxn) = (a0©a1b10©¢ ¢ ¢©akbk0)©(a1b11©¢ ¢ ¢©akbk1)x1©¢ ¢ ¢©(anb1n©¢ ¢ ¢©akbkn)xn:

Каждая скобка есть константа, значит функция f(x1; : : : ; xn) линейна и класс SL замкнут. £

Следствие. Классы функций S0; S1; S¤; SM ; SL не являются полными.

Действительно, суперпозиции функций из каждого класса дают функции из того же класса.

Подход к построению функционально полной системы заключается в следующем. Используя функции, не сохраняющую константу 0, не сохраняющую константу 1 и

несамодвойственную можно представить константы 0 и 1. С помощью констант и немонотонной функции можно получить отрицание. С помощью констант, отрицания и нелинейной функции можно получить конъюнкцию или дизъюнкцию. Таким образом, суперпозицией этих функций можно представить функционально полные системы функций f¹; ¢g или f¹; _g: По теореме 3.10 такое множество функций также функционально полно.

Теорема 3.12 (Теорема Поста) Множество © 2 Pn булевых функций функционально полно тогда и только тогда, когда оно не является подмножеством ни одного из классов S0, S1, S¤; SM , SL. Другими словами, функционально полная система

функций должна содержать хотя бы одну функцию, не сохраняющую константу 0, хотя бы одну функцию, не сохраняющую константу 1, хотя бы одну нелинейную функцию, хотя бы одну несамодвойственную функцию и хотя бы одну немонотонную функцию.

До к а з а т е л ь с т в о .

Необходимость.

Предположим, что © содержит хотя бы одну функцию из любого из классов S 2 fS0, S1, S¤; SM , SLg. Так как класс S замкнут, то функция f 62S не может быть представлена никакой суперпозицией функций из S. Значит © не является функционально полным множеством.

Достаточность.

1.Из любой функции, не сохраняющей константу 0, можно получить либо константу 1, либо отрицание.

Пусть f(x1; : : : ; xn) не сохраняет 0. Тогда f(0; 0; : : : ; 0) = 1: Если f(1; 1; : : : ; 1) = 1; то функция одной переменной g(x) = f(x; x; : : : ; x) дает константу 1. Если f(1; 1; : : : ; 1) = 0; то g(x) = f(x; x; : : : ; x) = x:¹

Аналогично, из любой функции, не сохраняющей константу 1, можно получить либо константу 0, либо отрицание.

2.Из любой несамодвойственной функции с помощью отрицания можно получить константы 0 и 1.

Для несамодвойственной функции

f(x1; : : : ; xn) =6 f¤(x1; : : : ; xn)

существует такой набор ~a = (a1; : : : ; an), что f(a1; : : : ; an) 6= f¹(¹a1; : : : ; a¹n);

то есть

Заменим каждый аргумент xi функции f(x1; : : : ; xn) на xai : Напомним, что 0x = x;¹ 1x = x: Для полученной функции одной переменной g(x) = f(xa1 ; : : : ; xan )

g(0) = f(0a1 ; : : : ; 0an ) = f(¹a1; : : : ; a¹n);

g(1) = f(1a1 ; : : : ; 1an ) = f(a1; : : : ; an):

Учитывая равенство (?); получим, что g(0) = g(1): Таким образом, g(x) – одна константа, g¹(x) – другая константа.

3. Из любой немонотонной функции и констант 0 и 1 можно получить отрицание.

такие компоненты, для которых ai < bi (ai = 0; bi = 1) и подставим переменную x вместо ai = 0. Для полученной таким образом функции g(x) одной переменной имеем

g(0) = f(a1; : : : ; an) = 1; g(1) = f(b1; : : : ; bn) = 0;

то есть g(x) = x¹.

4. Из любой нелинейной функции с помощью подстановки констант и отрицания можно получить конъюнкцию или дизъюнкцию.

В представлении нелинейной функции полиномом Жегалкина сгруппируем конъюнкции таким образом, что первое слагаемое содержит конъюнкцию x1x2, второе содержит x1 и не содержит x2, третье слагаемое содержит x2 и не содержит x1; четвертое слагаемое содержит все остальные конъюнкции:

f(x1; : : : ; xn) = x1x2f1(x3; : : : ; xn) © x1f2(x3; : : : ; xn)©

© x2f3(x3; : : : ; xn) © f4(x3; : : : ; xn)

x1x2f1(x3; : : : ; xn) 6= 0, так как найдется хотя бы одна конъюнкция, содержащая x1x2 (x1 и x2 выбраны произвольно без нарушения общности). Это значит, что найдется такой набор a3; : : : ; an; что f1(a3; : : : ; an) = 1. Тогда

f(x1; x2; a3; : : : ; an) = x1x2 © x1f2(a3; : : : ; an)© ©x2f3(a3; : : : ; an) © f4(a3; : : : ; an) =

Если c3 = 1, то все варианты получаются как отрицания вариантов при c3 = 0 (x © 1 = x¹).