Как найти двойственную функцию

X1 X2

F=Х1ÚХ2

G=X1|X2

G*=X1 X2

Теорема о двойственных функциях

Если F* двойственна к F, то F двойственна к F*.

Доказательство. F*(X1, . Xn) = ( 1, . N). Найдем двойственную функцию к F*, т. е. (F*( X1, . Xn))* = ( ( 1, . N))* = ( 1, . N) = F(X1, . Xn).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.

Принцип двойственности

Теорема: Пусть функция H(X1, . Xn) реализована формулой H(X1, . Xn) = =G(G1, . Gm) = G(F1(X1, . Xn), . Fm(X1, . Xn)), где какие-то переменные могут быть фиктивными. Тогда H*( x1, . Xn) = G*(F1*( X1, . Xn), . Fm*(X1, …, Xn)), это означает, что если функция задана некоторой формулой, то чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.

Доказательство. H*(X1, . Xn) = ( 1, . n) = (F1( 1, . n), . Fm( 1, . n)) = ( 1( 1, . n), . ( 1, . n)) = G(( ), . (( ) = G*(F1*( X1, . Xn), . Fm*( X1, . Xn)), что и требовалось доказать.

Если функция H(X1, . Xn) реализуется формулой N[F1, . Fn], то формулу, полученную из N заменой Fi, входящих в нее, на Fi* и реализующую функцию H*(X1, . Xn), будем называть двойственной и обозначать N*(X1, . Xn).

Пример 4. Построить формулу, реализующую F*, если F = ((X Y) Ú Z) (Y (XÅYz)). Покажем, что она эквивалентна формуле N = Z(XÅY).

Найдем (XÅY)* и (X Y)*.

X Y

(X Y)*

Из таблиц видно, что

(X Y)* = X

Y = = X Y 1, X Y = Y X ,

(X Y)* = Y X Y = Y.

По принципу двойственности:

F* = Yz ( (X (Y Z) 1)) = Yz Z(X (Y Z) 1) = Z( YÚ( XÅ ZÅ )) = Z( YÚ (XÅZÅ1)) = Z( YÚ (XÅ )) = Z YÚ(Z XÅZ ) = Z( YÚX ) = Z(XÅY).

Тогда F = (F*)* = [Z(XÅY)]* = ZÚ(X

Пример 5. Найти формулу для f* и показать, что она эквивалентна формуле N = (XÚ(ZÅT)) , если F = (Xyz

(TÚX />))Ú />T.

F* = ((XÚYÚZ)ÅT( ÚY))( ÚT) = ( T( ÚY)Ú(XÚYÚZ) )( ÚT) =

= ( TÚ(XÚYÚZ)( ÚX ))( ÚT) = TÚ(XÚYÚZ)( ÚX ÚTx ) =

= TÚ(XÚYÚZ)( ÚX ) = ( XÚ TÚ ZÚXÚXz) = ( TÚXÚ ZÚXz)

= (XÚ(ZÅT)).

Лемма о несамодвойственной функции

Подстановкой функций и в несамодвойственную функцию можно получить одну из констант.

Доказательство. Пусть – несамодвойственная функция. Тогда существует набор , для которого . Построим функцию , заменив единицы в на , а нули – на . Так как , то . Заметим, что .

Тогда , т. е. . Следовательно, функция есть одна из констант.

1.7. Двойственная функция

Определение. Функция называется двойственной к функции , если =.

Таблица двойственной функции получается из таблицы функции инвертированием столбца значений функции и последующим переворачиванием полученного столбца.

Пример. Для функции f (,,) построим двойственную функцию:

f (,,)

(,,)

(,,)

Пары двойственных элементарных функций представлены в табл. 1.11.







/



Рассмотрим функцию .

Функция f зависит от m аргументов, которые, в свою очередь, тоже являются функциями.

.

Как получить функцию ? Ответ на этот вопрос дается следующей теоремой.

Теорема 1.3. =.

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

===

= = = = = .

Теорема 1.4 (принцип двойственности). Если формула B = C[] реализует функцию , то формула = C[], то есть формула, полученная из B заменой функций на двойственные им функции , соответственно реализует функцию .

Пусть существует некоторая формула A = C[0, 1, x, , , ], тогда = = C[1, 0, x, , , ].

Пример. Задана формула . Используя принцип двойственности, построим двойственную формулу ()()().

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

Пусть задана некоторая система булевых функций, не обязательно конечная, M = <>.

Определение. Система M называется полной, если каждую функцию f   можно представить формулой над M.

Теорема 1.5 (теорема I о полноте систем булевых функций). Пусть система M = <> полна и любая ее функция может быть представлена формулой над множеством N = <>, тогда система N тоже является полной.

Доказательство. Так как система M полна, то любую булеву функцию можно представить формулой над M: h = C[]. Представим функции формулами над N:

= [],

= [],

= [].

Тогда h = C[[],[],…,[]] = =[]. Итак, имеем: любая функция из может быть представлена формулой над N, следовательно, система N полна.

Пример. Система M = <, , > является полной, покажем, что система N = <, > также полна. Функции <, > системы N входят в систему M, осталось выразить функцию  через , . Используя эквивалентные соотношения, можно записать: () = x  y. Итак, все функции системы M выражены через функции системы N, то есть система N является полной.

Определение. Задана система M = <>. Замыканием над M (обозначается [M]) называется множество всех булевых функций, представимых формулами над M. [M] обязательно содержит M.

Отметим некоторые свойства замыкания:

1. [[M]] = [M].

2. [] = .

3. Если M  N, то [M]  [N].

4. [M]  [N]  [MN].

Определение. Класс M называется замкнутым если [M] = M.

Пример. – замкнутый класс, так как [] = . [[M]] = [M] также является замкнутым классом.

Определение. Система M полна, если ее замыкание совпадает с множеством всех булевых функций, [M] =.

Рассмотрим основные замкнутые классы.

1 класс. – класс булевых функций, которые на наборе из всех нулей принимают значение 0. Если f (0, 0,…, 0) = 0, то f .

Например, функции , , , 0 принадлежат классу , а функции /,

, , 1 этому классу не принадлежат.

Число функций от n переменных, попадающих в класс , равняется .

Покажем, что – замкнутый класс. Доказательство замкнутости здесь и далее сведем к рассмотрению одного шага подстановки, при котором новая функция оказывается принадлежащей тому же классу.

Покажем, что функция = = , если . Подставим в правую и левую части равенства вместо переменных нули:

== f(0,…,0)  .

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

2 класс. – класс всех булевых функций, которые на наборе из всех единиц принимают значение 1. Если f (1, 1,…, 1) = 1, то f .

, , 1 принадлежат классу , а функции , 0, /,  этому классу не принадлежат.

Замкнутость класса />доказывается аналогично классу .

3 класс. S – класс самодвойственных функций. Если = = (двойственная функция для f), то f  S.

Функция называется двойственной к функции , если =.

Например, функции x, принадлежат классу S, а функции ,  этому классу не принадлежат.

Определение. Наборы и называются противоположными.

Свойство самодвойственной функции. Самодвойственная функция на противоположных наборах принимает противоположные значения. Поэтому число самодвойственных функций от n переменных равно .

Пример. Рассмотрим мажоритарную функцию f =. Ее значение на любом наборе равно значению большинства аргументов набора. Покажем, что функция f самодвойственна:

= ()()() = ()() =.

f (,,)

Докажем, что класс S замкнут, рассматривая, как и ранее, один шаг подстановки: = принадлежит S, если  S.

Построим = =====, то есть  S. Итак, S – замкнутый класс.

Лемма о несамодвойственной функции. Если функция  S, то из нее путем замены переменных на x или можно получить несамодвойственную функцию одной переменной, то есть константу.

Доказательство. Так как f  S, то существует такой набор значений переменных , что =.

Строим функцию , где , i = (). Будем иметь в виду, что и . Заметим, что получена из заменой ее аргументов на x или . Если в наборе  равно 0, то аргумент заменяется на , иначе – на . Это значит, что получена из несамодвойственной функции в соответствии с условием леммы. Выясним свойства .

===== ===  функция константа.

Пример. Получим константу из несамодвойственной функции по лемме. Пусть f =. f (0, 1) = f (1, 0) = 1,  = (0, 1), =, =,

== x = 1.

4 класс. M – класс монотонных функций.

Определение. Рассмотрим два набора значений переменных , и , будем говорить, что  предшествует  (), если , (0 предшествует 1).

Например, набор  = (0, 1, 0, 1, 0, 0) предшествует  = (0, 1, 1, 1, 1, 0), то есть .

Определение. Пара наборов (, ) сравнимы, если один из них предшествует другому. Иначе – несравнимы.

Например,  = (0, 1, 0, 1) и  = (1, 0, 0, 1) – несравнимы.

Определение. Функция называется монотонной, если для любых двух наборов  и  таких, что , имеет место неравенство f ()  f ().

Например, функции 0, 1, x,  принадлежат классу M, а функции ,

этому классу не принадлежат.

Покажем, что класс монотонных функций замкнут. Для этого выясним, является ли функция = монотонной, если  M.

Пусть заданны два набора значений переменных , и таких, что . Подставим наборы в обе части равенства:

=

=.

,

.

Так как  M, то

,

 />.

Так как f  M, то справедливо неравенство



, из которого следует

, то есть  M.

Следовательно, класс монотонных функций замкнут.

Лемма о немонотонной функции. Если  M, то из нее путем замены переменных на константы 0, 1 и x можно получить немонотонную функцию одной переменной, а именно .

Доказательство. Сначала докажем, что если функция немонотонна, то для нее найдется пара соседних наборов и таких, что и f () > > f ().

Наборы ,  называются соседними по i-й переменной, если они отличаются значениями только этой переменной. Соседние наборы сравнимы.

Если функция немонотонна, то для нее найдется пара наборов , для которых f () > f () (из определения монотонности). Если  и  соседние, то цель достигнута. Рассмотрим ситуацию, когда  и  не соседние. Пусть наборы отличаются значениями в t компонентах (t > 1), причем эти t компонент в наборе  имеют значение 0, а в наборе  – 1. Поэтому между  и  можно вставить t – 1 промежуточных наборов таких, что

 ….

Очевидно, что наборы, стоящие в этой цепочке рядом, будут соседние. Пусть и – соседние элементы этого ряда ( ), на которых происходит смена значения функции. Пусть они отличаются в i-й компоненте, тогда >, причем

и .

Рассмотрим функцию .

(x) получена из f(,…,) заменой i-й переменной на x, а всех остальных переменных – на константы из наборов , (эти наборы отличаются только по i-й переменной). Это значит, что (x) получена из немонотонной функции f(,…,) в соответствие с леммой. Выясним свойства (x).

Имеем >.

Последнее означает, что и , то есть .

Пример. Получим функцию из немонотонной функции f =.

= (1, 0), = (1, 1), наборы , являются соседними по переменной , f (1, 0) > f (1, 1), (x) = 1  x = .

5 класс. L – класс линейных функций.

Определение. Формула

называется полиномом Жегалкина булевой функции, коэффициенты   <0, 1>определяют какие конъюнкции входят в полином.

Например, – полином Жегалкина.

В дальнейшем будем иметь ввиду следующие тождества:

1. =,

2. () = ,

3.  1 = ,

4.

если число слагаемых четно,

если число слагаемых нечетно.

Эти тождества позволяют любую ДНФ преобразовать в полином Жегалкина.

Пример. Приведем к полиному Жегалкина рассмотренную ранее мажоритарную функцию f = = ()  = =()  () = ==.

Теорема 1.6. Любую булеву функцию можно представить полиномом Жегалкина единственным образом.

Доказательство. Рассмотрим всевозможные произведения булевых переменных без инверсий. Их столько, сколько всевозможных подмножеств из n переменных, то есть (пустое подмножество соответствует константе 1). Каждое из произведений может либо входить в полином, либо нет. Это значит, что одному полиному сопоставляется некоторое подмножество из рассматриваемых произведений. Всевозможных полиномов столько, сколько подмножеств из элементов, то есть . Известно, что есть число булевых функций от n переменных. Следовательно, каждая булева функция представима полиномом Жегалкина единственным образом.

Определение. Линейным полиномом называется формула

,

где  <0, 1>.

Пример. – линейный полином.

Определение. Функция, представимая линейным полиномом, называется линейной булевой функцией.

Множество всех линейных функций образует класс линейных функций (L).

Например, функции 1, 0, x, ,  являются линейными, а функции ,  – нет.

Покажем замкнутость класса линейных функций.

Докажем, что функция = принадлежит L, если  L.

== =.

После раскрытия скобок получим линейный полином, то есть  L. Следовательно, класс линейных функций замкнут. Всего линейных функций от n переменных .

Лемма о нелинейной функции. Если функция нелинейная, то из нее путем замены переменных на константы 0, 1, x, , и, быть может, путем инвертирования самой функции можно получить нелинейную функцию, а именно конъюнкцию.

Доказательство. Представим функцию в виде полинома Жегалкина, поскольку f  L, то в полиноме найдется слагаемое, содержащее 2 и более переменные (конъюнкция ранга 2). Без ограничений общности предположим, что это слагаемое содержит произведение переменных . Тогда полином функции f(,…,) можно представить следующим образом:

Формула называется полиномом Жегалкина булевой функции, коэффициенты  <0, 1>определяют, какие конъюнкции входят в полином.

.

Собрав вместе слагаемые, содержащие , и вынеся за скобки, получим в скобках функцию ; собрав далее вместе слагаемые, содержащие , и вынеся за скобки, получим в скобках функцию ; собрав вместе слагаемые, содержащие , и вынеся за скобки, получим в скобках функцию , оставшиеся слагаемые образуют функцию .

Пусть – набор, на котором функция = 1. Этот набор обязательно существует, так как полином функции содержит конъюнкции ранга 2. Тогда = = = , где , ,   <0, 1>.

получена из нелинейной заменой переменных на константы из набора , что согласно лемме допустимо. В результате функции ,, превратились в константы , , .

Рассмотрим функцию , получаемую из , следующим образом:

=.

Это значит, что получается из заменой переменной () либо на себя, если  = 0 ( = 0), либо на инверсную переменную, если  = 1 ( = 1). Кроме того, если выражение  есть константа 1, функция  заменяется на инверсную. Все эти изменения допускаются леммой. Следовательно, получена из в соответствии с условием леммы. Исследуем . Надо раскрыть скобки и привести к подобию

=

==.

Пример. Получим функцию из нелинейной функции f, заданной в виде f =  = 111, здесь ===1, а =. Пусть = (1, 1), тогда = 1,  =  =  = 1.

=  1 = ( 1)(  1)  (  1)  (  1)  1  1 =  1  1   1  1  1  1 = .