2.3.8. Монотонные функции алгебры логики

Упорядочим множество {0,1}, полагая 0 < 1. Так как нам придется иметь дело с функциями от нескольких переменных, введем частичное упорядочение двоичных наборов одной длины.

Определение 1. Пусть и - двоичные наборы. Говорят, что предшествует (младше) (обозначается: < ), если для всех i, причем, по крайней мере, для одного i имеет место строгое неравенство.

Это упорядочение является только частичным, так как оно не позволяет сравнить любые наборы.

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

.

Удовлетворяющие этому условию булевы функции правильнее было бы назвать «неубывающими», но так как мы не будем иметь дело с «невозрастающими» функциями, мы будем называть их просто «монотонными».

Пример 1. монотонна ли функция ху?

Да, так как она равна 1 лишь на наборе (1,1), которому предшествуют все остальные наборы.

Пример2. - немонотонна, так как при = (0), = (1) имеем < , но > .

2.3.9. Функционально замкнутые классы

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

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

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

В общем виде задача ставится следующим образом:

Имеется некоторое множество F функций алгебры логики (f₁, f₂, ..., f_n). Для всякой ли булевой функции существует равносильная ей суперпозиция из множества F.

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

Пусть F = {f₁,f₂, ..., f_n}, (Р_n – множество булевых функций от n переменных).

Определение. Замыканием F (обозначается ) называется множество всех булевых функций, реализуемых формулами над F: .

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

Определение. Класс (множество) функций F называется замкнутым, если [F] = F.

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

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

Доказать можно по индукции.

Очевидно, что сами функции из F реализованы как суперпозиции 0 ранга над F. Таким образом, остается обосновать суперпозиционные переходы для рассматриваемых функций.

I. Класс функций, сохраняющих 0: T₀= {f| f(0,0,0,..,0) = 0}. Пусть f, f₁, f₂, ..., f_n и Ф = f(f₁(x₁, ..., x_n), ..., f_n(x₁, ..., x_n)), тогда подставим в Ф нулевой набор. Так как f_i сохраняет нуль, то при этом в f подставляется нулевой набор, а так как f тоже сохраняет 0, то получим, что и Ф сохраняет нуль:

Ф(0, …,0) = f(f₁ (0, ...,0), ..., f_n(0, ...,0)) = f (0, ..., 0) = 0, т.е. .

II. Класс функций, сохраняющих 1: Т₁ = {f|f(1, ..., 1) = 1}.

Пусть f, f₁, f₂, ..., f_n и Ф = f(f₁(x₁, ..., x_n), ..., f_n(x₁, ..., x_n)).

Тогда Ф(1, …,1) = f(f₁ (1, ...,1), ..., f_n(1, ...,1)) = f (1, ..., 1) = 1, т.е. .

III. Класс самодвойственных функций: Т_* : {f|f = f^*}.

Пусть f, f₁, f₂, ..., f_n и Ф = f(f₁(x₁, ..., x_n), ..., f_n(x₁, ..., x_n)). Тогда по закону двойственности:

Ф^* = f^*(f₁^*(x₁, ..., x_n), ..., f_n^*(x₁, ..., x_n)) =

= f(f₁(x₁, ..., x_n), ..., f_n(x₁, ..., x_n)) = Ф. Следовательно, Ф .

IV. Класс монотонных функций:

, где

, , .

Пусть f, f₁, f₂, ..., f_n и Ф = f(f₁(x₁, ..., x_n), ..., f_n(x₁, ..., x_n)). Тогда

т.е. .

V. Класс линейных функций: T_L = {f|f = c₀ + c₁x₁+...+c_nx_n}, где + означает сложение по модулю 2, а знак конъюнкции опущен.

Пусть f, f₁, f₂, ..., f_n и Ф = f(f₁(x₁, ..., x_n), ..., f_n(x₁, ..., x_n)). Тогда

f = c₀ + c₁x₁+...+c_nx_n,

f₁= c₀¹ + c₁¹x₁+...+c_n¹x_n,

.......................................,

.

Подставим эти формулы в Ф. Имеем:

Ф(х₁, …,х_n) = c₀ + c₁ (c₀¹ + c₁¹x₁+...+c_n¹x_n,) + ... + = d₀ + d₁x₁ + +d_nx_n.

Следовательно, .

Таким образом, доказано, что классы Т₀, Т₁, Т_*, , Т_L функционально замкнуты.

Рассмотренные классы попарно различны, не пусты и не совпадают с P_n

ПримерL. Является ли объединение функционально замкнутых классов функционально замкнутым классом?

Решение. Нет

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

0	+	-	-	+	+
1	-	+	-	+	+
	-	-	+	-	+
х1^x2	+	+	-	+	-

Выпишем таблицу принадлежности некоторых булевых функций рассмотренным замкнутым классам:

	Т0	Т1	Т*		ТL

Определение. Функционально замкнутые классы, отличные от пустого класса и от совокупности всех булевых функций (P_n), называются собственными функционально замкнутыми классами.