Замкнутые классы.

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

Пусть K - некоторое подмножество функций из P₂. Замыканием K называется множество всех булевых функций, представимых с помощью операций суперпозиции и замены переменных функций из множества K. Замыкание множества K обозначается через [K].

В терминах замыкания можно дать другие определения замкнутости и полноты (эквивалентные исходным):

K- замкнутый класс, если K = [K];

K - полная система, если [K] = Р₂.

Примеры.

• {0}, {1} - замкнутые классы.

• Множество функции одной переменной - замкнутый класс.

• - замкнутый класс.

• Класс {1, x+y} не является замкнутым классом.

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

1. Т₀ - класс функций, сохраняющих 0.

Обозначим через Т₀ класс всех функций алгебры логики f(x₁, x₂, ... , x_n), сохраняющих константу 0, то есть функций, для которых f(0, ... , 0) = 0.

.

Легко видеть, что есть функции, принадлежащие Т₀ , и функции, этому классу не принадлежащие:

0, x, xy, xy, x+y  T₀;

1,  T₀ .

Из того, что  T₀ следует, например, что нельзя выразить через дизъюнкцию и конъюнкцию.

Поскольку таблица для функции f из класса Т₀ в первой строке содержит значение 0, то для функций из Т₀ можно задавать произвольные значения только на 2ⁿ - 1 наборе значений переменных, то есть

,

где - множество функций, сохраняющих 0 и зависящих от n переменных.

Покажем, что Т₀ - замкнутый класс. Так как xT₀ , то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

Пусть . Тогда достаточно показать, что . Последнее вытекает из цепочки равенств

.

2. T₁ - класс функций, сохраняющих 1.

Обозначим через Т₁ класс всех функций алгебры логики f(x₁, x₂, ... , x_n), сохраняющих константу 1, то есть функций, для которых f(1, ... , 1) = 1.

.

Легко видеть, что есть функции, принадлежащие Т₁, и функции, этому классу не принадлежащие:

1, x, xy, xy, xy  T₁;

0, , x+y  T₁ .

Из того, что x + y  T₀ следует, например, что x + y нельзя выразить через дизъюнкцию и конъюнкцию.

Результаты о классе Т₀ тривиально переносятся на класс Т₁ . Таким образом, имеем:

Т₁ - замкнутый класс;

.

3. L - класс линейных функций.

Обозначим через L класс всех функций алгебры логики f(x₁, x₂, ... , x_n), являющихся линейными:

.

Легко видеть, что есть функции, принадлежащие L , и функции, этому классу не принадлежащие:

0, 1, x, x+y, x₁  x₂ = x₁ + x₂ + 1, = x+1  L;

xy, xy  L .

Докажем, например, что xy  L .

Предположим противное. Будем искать выражение для xy в виде линейной функции с неопределенными коэффициентами:

.

При x = y = 0 имеем =0,

при x = 1, y = 0 имеем  = 1,

при x = 0, y = 1 имеем  = 1,

но тогда при x = 1, y = 1 имеем 1 1  1 + 1, что доказывает нелинейность функции xy.

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

Поскольку линейная функция однозначно определяется заданием значений n+1 коэффициента ₀, ... , _n , число линейных функций в классе L⁽ⁿ⁾ функций, зависящих от n переменных равно 2ⁿ⁺¹.

.

4. S - класс самодвойственных функций.

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

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

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

Легко видеть, что

0* = 1,

1* = 0,

x* = x,

,

(x₁  x₂)* = x₁  x₂,

(x₁  x₂)* = x₁  x₂.

Из определения вытекает, что (f*)* = f, то есть функция f является двойственной к f*.

Пусть функция выражена с помощью суперпозиции через другие функции. Спрашивается, как построить формулу, реализующую ? Обозначим через = (x₁, ... , x_n) все различные символы переменных, встречающиеся в наборах .

Теорема 2.6. Если функция  получена как суперпозиция функций f, f₁, f₂, ... , f_m, то есть

,

то

-

функция, двойственная к суперпозиции, есть суперпозиция двойственных функций.

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

*(x₁ ,...,x_n) =  f(x₁ ,...,x_n) =

Теорема доказана. 

Из теоремы вытекает принцип двойственности: если формула А реализует функцию f(x₁, ... , x_n), то формула , полученная из А заменой входящих в нее функций на двойственные им, реализует двойственную функцию f*(x₁, ... , x_n).

Обозначим через S класс всех самодвойственных функций из P₂:

S = {f | f* = f }

Легко видеть, что есть функции, принадлежащие S, и функции, этому классу не принадлежащие:

x,  S;

0, 1, xy, xy  S .

Менее тривиальным примером самодвойственной функции является функция

h(x, y, z) = xy  xz  yz;

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

h*(x, y, z)= (x  y)(x  z)  ( y  z) = x y  x z  y z; h = h* ; h  S.

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

,

так что на наборах и , которые мы будем называть противоположными, самодвойственная функция принимает противоположные значения. Отсюда следует, что самодвойственная функция полностью определяется своими значениями на первой половине строк стандартной таблицы. Поэтому число самодвойственных функций в классе S⁽ⁿ⁾ функций, зависящих от n переменных, равно :

.

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

.

5. М - класс монотонных функций.

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

Говорят, что набор предшествует набору (или “не больше ”, или “меньше или равен ”), и применяют обозначение , если _i  _i для всех i = 1, ... , n. Если и , то будем говорить, что набор строго предшествует набору (или “строго меньше”, или “меньше” набора ), и использовать обозначение . Наборы и называются сравнимыми, если либо , либо .В случае, когда ни одно из этих соотношений не выполняется, наборы и называются несравнимыми. Например, (0, 1, 0, 1)  (1, 1, 0, 1), но наборы (0, 1, 1, 0) и (1, 0, 1, 0) несравнимы. Тем самым отношение  (его часто называют отношением предшествования) является частичным порядком на множестве В_n . Ниже приведены диаграммы частично упорядоченных множеств В₂, В₃ и В₄.

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

Функция алгебры логики называется монотонной, если для любых двух наборов и , таких, что , имеет место неравенство . Множество всех монотонных функций алгебры логики обозначаетcя через М, а множество всех монотонных функций, зависящих от n переменных - через М⁽ⁿ⁾.

Легко видеть, что есть функции, принадлежащие M , и функции, этому классу не принадлежащие:

0, 1, x, xy, xy  M;

x+y, xy, xy  M .

Покажем, что класс монотонных функций М - замкнутый класс. Так как xМ , то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

Пусть . Тогда достаточно показать, что .

Пусть - наборы переменных, соответственно, функций , f₁, ... , f_m , причем множество переменных функции  состоит из тех и только тех переменных, которые встречаются у функций f₁, ... , f_m . Пусть и - два набора значений переменной , причем . Эти наборы определяют наборы значений переменных , такие, что . В силу монотонности функций f₁, ... , f_m

,

поэтому

,

и в силу монотонности функции f

.

Отсюда получаем

. 

Число монотонных функций, зависящих от n переменных, точно неизвестно. Легко может быть получена оценка снизу:

,

где [n/2] - есть целая часть от n/2.

Так же просто получается слишком завышенная оценка сверху:

.

Уточнение этих оценок - важная и интересная задача современных исследований.