Логическую функцию будем называть монотонной, если для любых двух наборов и таких, что , выполнено f( ) f( ). Класс всех монотонных функций обозначим через М. Он содержит, в частности, функции 0,1,x, & , , а функции , , , ему не принадлежат.

Рассмотрим суперпозицию (1.8) монотонных функций g и ,..., . Пусть и - произвольные двоичные наборы длины n и такие, что . Положим = , (i =1,…,k) и , =( ). Из монотонности функций вытекает, что и, следовательно, . С учетом этого и монотонности функции g получаем

.

Итак, и замкнутость класса М установлена. Достаточно простой метод распознавания монотонности будет изложен в §2.4.

22.L - линейные функции.

Класс L линейных функций. Всякая логическая функция может быть единственным образом представлена в виде полинома Жегалкина. Функции, для которых полином Жегалкина имеет степень не выше первой (т. е. содержит конъюнкции длины не более 1), называются линейными. Класс L всех линейных функций содержит, в частности, функции , а функции , , ему не принадлежат.

Всякая линейная функция может быть записана в виде

,

где (i=0,1,…,n). Легко видеть, что коэффициенты (i=0,1,…,n) связаны со значениями функции следующим образом:

На основе этого может быть предложен следующий способ распознавания линейности. По приведенным формулам нужно вычислить коэффициенты . Если функция реализуется полиномом , то она линейна, а в противном случае — нелинейна.

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

Помимо приведенных 5 замкнутых классов существуют и другие. Это следует, например, из того, что пересечение замкнутых классов снова образует замкнутый класс. Но, как мы увидим дальше, классы , , S, М и L играют решающую роль в вопросах полноты.

Критерий полноты.

23. Доказательство утверждения о несамодвойственной функции.

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

,

и, следовательно, g(x) совпадает с одной из констант.

24. Доказательство утверждения о немонотонной функции.

. Из всякой немонотонной функции путем подстановки констант 0 и 1 и функции можно получить функцию . Для немонотонной функции f найдутся наборы и такие, что и . Образуем функцию g(x), подставив в на место тех переменных, которым соответствуют одинаковые разряды наборов и , значения соответствующих разрядов, а на место остальных переменных — функцию . С учетом условия заключаем, что .

Последнее означает, что g(0) = 1 и g(1) = 10 Таким образом, g(x) совпадает с .

25. Доказательство утверждения о нелинейной функции.

. Из всякой нелинейной функции путем подстановки констант можно получить нелинейную функцию двух аргументов. Для доказательства рассмотрим полином Жегалкина , реализующий функцию . В силу нелинейности в нем найдется член, содержащий не менее двух множителей (без ограничения общности можно считать, что среди множителей есть и ). Путем вынесения за скобки преобразуем полином к виду

.

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

является нелинейной.

Сформулируем и докажем основной результат.

26. Доказательство критерия о полноте класса функций.

Теорема 1.4 (о функциональной полноте). Базис является полным тогда и только тогда, когда он целиком не содержится ни в одном из пяти замкнутых классов , , S, М и L.

Доказательство. Если базис целиком принадлежит одному из перечисленных классов, то в силу того, что классы замкнуты и содержат тождественные функции x, формулами над могут быть реализованы лишь функции из данного класса. Но ни один из этих классов не содержит всех логических функций. Следовательно, базис неполон.

Докажем теперь, что базис , целиком не содержащийся ни в одном из классов , , S, М, L, является полным.

Установим вначале, что формулами над могут быть реализованы константы 0 и 1. В базисе имеется функция g, не сохраняющая 0, т. е. такая, что g(0,…,0)=1. Вычислим ее значение на наборе из единиц.

а) Если окажется, что g(1,..., 1) = 1, то функция (х) = g(х,...,х) является константой 1 (ибо (0) = g(0,...,0) = 1, (1)=g(1,...,1) = 1). Вторую константу получим, взяв в функцию, не сохраняющую 1, и подставив вместо ее аргументов функцию 1= (х).

б) Если g(1,...,1)=0, то функция (х) = g(x,...,х) совпадает с (ибо (0) = g(0,..., 0) = 1, (1)=g(1,..., 1) = 0). С помощью и содержащейся в несамодвойственной функции на основании вспомогательного утверждения получим одну из констант. Из нее с использованием образуем вторую константу.

Тем самым возможность реализации констант установлена.

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

.

Преобразуем последнюю:

.

Подставив вместо и функции и (отрицание у нас есть), получим функцию , если , либо функцию , если . Полнота базиса вытекает в первом случае из полноты системы {&, }, а во втором — из полноты штриха Шеффера.

Вопросы полноты. Базис называется полным, если формулами над реализуются все функции k-значной логики. Из представления (1.10) следует, что множество функций

{0,1,..., k-1, } образует полную систему. При любом имеются полные базисы из одной функции. Таким, в частности, является базис, состоящий из функции Вебба:

(этот факт сообщаем без доказательства). При = 2 функция Вебба совпадает со стрелкой Пирса, ибо

.

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

Теорема 1.5 (А. В. Кузнецов). При любом 2 можно построить такую конечную систему замкнутых классов функций -значной логики, что базис полон тогда и только тогда, когда он целиком не содержится ни в одном из этих классов.

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

Доказательства фактов, приведенных в данном параграфе, и некоторые дальнейшие результаты содержатся в [11] (раздел 1).

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

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

27. Понятие действительного многочлена двоичной функции. Примеры для функций от двух переменных.

I) Основные понятия.

Многочленом Жегалкина (приведенным многочленом) называется представление двоичной функции f(x₁,x₂,…,x_n) от n переменных формулой вида

f(x₁,x₂,…,x_n) = a₀    … a_1,2,…,nx₁x₂…x_n

где a₀, a₁, …, a_n, a_1,2,…, a_1,2,…n F₂

Ранее в курсе логики было доказано , что для каждой дво­ичной функции существует единственный многочлен Жегалкина.

Конъюнкции , входящие в многочлен Жегалкина, назы­ваются одночленами. Степенью одночлена называется число входящих в него переменных ( ранг конъюнкции). Степенью не­линейности ( порядком) многочлена Жегалкина функции f (обозначается deg f ) называют максимальную из степеней вхо­дящих в него одночленов.

Двоичные функции можно задавать многочленами, в которых используются операции сложения, вычитания и умножения дейст­вительных чисел. Так непосредственной проверкой легко убе­диться, что двоичные функции x₁x₂, x₁x₂, x₁x₂, представимы в виде действительных многочленов

x₁x₂= x₁ x₂

x₁x₂= x₁+ x₂ – x₁ x₂

x₁x₂= x₁+ x₂ –2 x₁ x₂

= 1- x₁

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

= 1- x₁= 1- 2x₁- x₁²= 1- x₁²= 1- 3x₁² - 2x₁⁴= …