Доказательство окончено. Определим число самодвойственных функций, имеющих n переменных

Пример.Пусть U = . Тогда
U* = .

Определим число самодвойственных функций, имеющих n переменных. Из условия самодвойственности следует, что на противоположных наборах значений переменных всякая принимает противоположные значения. Поэтому всякая однозначно определяется своим заданием на наборах верхней половины табличного задания булевских функций n переменных, то есть на 2^n-1 наборах.

Следовательно, число функций n переменных вS равно .

Покажем, что множество функций S является замкнутым классом. Поскольку тождественная функция f(x) = x является самодвойственной, то для доказательства замкнутости класса всех самодвойственных функций достаточно проверить, что если
h = , где f, g₁, . . . , g_n - это самодвойственные функции, то h = h*.

Воспользуемся теоремой о формуле для двойственной функции. Тогда h* = = = = h, т.е. S -это замкнутый класс.

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

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

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

Пусть f S. Тогда найдётся таких два противоположных набора и , что f = f . Определим вспомогательные функции:

, где i =1,..., n.

Тогда функция h(x) = f( совпадает с одной из функций констант.

Определим значения h(0) и h(1):

h(0) = f ( = f .

h(1) = f( = f .

Следовательно, h(0) = h(1).

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

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

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

МОНОТОННЫЕ ФУНКЦИИ

На множестве двоичных наборов длины n определим отношение предшествования наборов.

Пусть и . Тогда набор предшествует набору , если .

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

Например, наборы (0, 1, 0, 0, 1, 0) и (0, 1, 1, 0, 1, 1) находятся в отношении предшествования, а наборы
(1, 1, 0, 0, 1, 0) и (1, 0, 1, 0, 1, 1) оказываются несравнимыми в отношении .

Упражнение. Проверить, что отношение предшествования наборов является отношением частичного порядка.

Рассмотрим представление отношения на множестве с помощью диаграммы для этого отношения, представленной на рис 4.6. Пусть n = 3.

1 1 1

0 1 1 1 0 1 1 1 0

1 0 0 0 1 0 0 0 1

0 0 0

Рис. 4.6

На приведенной диаграмме не указана ориентация дуг, которые всегда считаются ориентированными в направлении верхней из двух вершин, соединяемых дугой.

Все наборы единичного n-мерного куба, имеющие равное число единиц, несравнимы между собой и образуют слой в таком кубе. В случае произвольного значения n в диаграмме для отношения содержится n +1 слоев.

Упражнение. Нарисовать диаграмму отношения для
n = 4.

ОПРЕДЕЛЕНИЕ

Булевская функция f(x₁, . . . , x_n) называется монотонной, если для любых наборов и , для которых , справедливо неравенство .

Множество всех монотонных булевских функций обозначается как M.

Примеры.

1. Функция f (x₁, x₂)= x₁ ® x₂ немонотонна, так как

(0, 0) (1, 0), но f(0, 0) > f (1, 0).

2. Функции & и являются монотонными.

Множество всех монотонных функций является замкнутым классом. Поскольку тождественная функция f(x) = x - монотонна, то для доказательства замкнутости M достаточно проверить, что при

h = (1),

где f, g₁ ,..., g _n - монотонные функции, M.

Пусть x₁, . . . , x_n все различные символы переменных, которые встречаются в формуле (1). Возьмем два набора и значений этих переменных, для которых . Тогда для наборов и , составленных из значений переменных функций g₁, . . . , g_n, взятых из наборов и , справедливы соотношения:

Следовательно, для i = 1, . . . , n. Поэтому . Поскольку M, то , т.е. . Поэтому M.

Замечание. Доказанное свойство монотонных функций позволяет просто устанавливать монотонность функций, представленных формулами составленными из монотонных функций. Например, монотонной является функция, представляемая формулой

.

Простейшей немонотонной функцией можно считать функцию , поскольку три остальные функции одной переменной являются монотонными. Покажем, что отрицание (или простейшая немонотонная функция) может быть получено из всякой немонотонной функции. Последнее свойство можно сформулировать иначе: всякая немонотонная функция содержит отрицание, которое может быть выражено из этой функции.

Лемма. (О немонотонной функции)

Если M, то подстановкой вместо переменных этой функции функций-констант и тождественной функции f(x) = x можно получить функцию .

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

Пусть f(x₁,...,x_n) M. Тогда найдутся такие два набора и значений переменных x₁,. . . , x_n, что и . Возьмем эти наборы. Предположим, что они различаются в k компонентах.

Построим цепочку двоичных наборов, последовательно заменяя значения 0, 1, . . . , k разрядов, в которых набор отличается от набора :

. (1)

Очевидно, что всякие два соседних набора этой последовательности различаются ровно в одной компоненте.

Рассмотрим значения f на наборах цепочки (1).

. (2)

Поскольку и , то в (2) найдутся последовательно идущие значения 1 и 0.

Рассмотрим наборы = и = = , на которых функция f принимает значения 1 и 0.

Тогда .

Действительно,

h (0) = h = 1 и

h (1) = h )= 0.

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

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

Рассмотрим пример использования леммы о немонотонной функции. Пусть задана функция f = x₁ ® (x₂® x₃). Тогда наборы
(0, 1, 0) и (1, 1, 0) являются соседними и на этих наборах нарушается монотонность f:

f(0, 1, 0) = 1иf(1, 1, 0) = 0.

Поэтому f(x, 1, 0) = .

Упражнение.

1. Докажите утверждение, обратное утверждению, сформулированному в лемме о немонотонной функции.

2. Проверьте справедливость следующего утверждения: Если ф.а.л. f(x₁,...,x_n) отличнаот тождественной единицы, то всякая минимальная ДНФ для f не содержит элементарных конъюнкций, содержащих отрицания переменных.

ЛИНЕЙНЫЕ ФУНКЦИИ

Напомним, что линейными называются функции, представимые в виде , где a₁, . . . , a_n+1 - двоичные коэффициенты при переменных и свободном члене, равном 1.

Класс линейных функций обозначается как L.

Из установленного способа представления линейных функций следует, что существует ровно 2ⁿ⁺¹ различных линейных функций, зависящих от n переменных. Действительно, записи линейных функций являются частным случаем полиномов Жегалкина, поэтому представление всякой линейной функции в виде единственное. Поэтому линейных функций от n переменных ровно столько, сколько имеется способов составления различных записей вида: .

Класс L является замкнутым, поскольку преобразование всякой суперпозиции линейных функций к виду полинома Жегалкина не приводит к появлению нелинейных слагаемых.

Замечание. Только две линейные функции n переменных существенно зависят от всех своих переменных:

и .

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

Все 4 функции одной переменной: 0, 1, x и являются линейными.

Простейшим примером нелинейной функции можно считать x₁&x₂, поскольку ее представление в виде полинома Жегалкина содержит одно произведение переменных. Покажем, что эта простейшая нелинейная функция может быть выражена из любой нелинейной функции.

Лемма (О нелинейной функции)

Если f(x₁, . . . , x_n) L, то подстановкой вместо переменных этой функции функций-констант 0, 1, тождественных функции x и отрицанию , а также применением отрицания к f можно получить функцию .

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

Пусть f(x₁, . . . , x_n) L.

Возьмем полином Жегалкина R для f. Так как f - это нелинейная функция, то в полиноме R содержится слагаемое, включающее произведение некоторых двух переменных. Без ограничения общности можно считать, что такое произведение содержит вхождения переменных x₁и x₂.

(Если все произведения двух и большего числа переменных не содержат одновременно эти переменные, то необходимо произвести соответствующее переименование переменных в f, используя подстановки переменных вместо переменных функции.)

Сгруппируем слагаемые в R и, вынося переменные x₁ и x₂ за скобки, представим его в виде

(1).

Здесь полином R₁ содержит хотя бы одно ненулевое слагаемое и поэтому представляет булевскую функцию, отличную от тождественного нуля.

Пусть . Подставим вместо переменных x₃, . . . , x_n конкретные значения . Тогда имеет место равенство:

= (2)

Здесь и .

Заменим x₁ на x₁ + b и х₂ на x₂ +a. При этом, если a или b, равно нулю, то соответствующая переменная не заменяется. В противном случае соответствующая переменная заменяется на отрицание этой переменной.

В результате такой замены выражение (2) преобразуется к виду

. (3)

Если , то функция x₁&x₂уже получена.

В противном случае применим отрицание к функции вида (3) и также получим x₁&x₂.