Функции, сохраняющие константу

 

Если в функции f(x1,x2,…,xn) вместо всех переменных поставить одну переменную х, то возможно 4 различных варианта:
 f(x, x, …, x)Î{x, 0, 1,`x} . В зависимости от этого функцию называют

· a-функция, если f = x;

· b-функция, если f = 1;

· c-функция, если f = 0;

· d-функция, если f =`x;

Рассмотрим множество a- и b - функций. Для них f(1,1,…,1) = 1, поэтому эти функции называют функциями, сохраняющими 1. Можно показать, что суперпозиция этих функций будет снова сохранять константу 1. Значит, множество этих функций замкнуто и образует класс функций, сохраняющих единицу. Этот класс обозначают как С1.

Аналогично можно показать, что множество a- и c-функций образуют класс функций, сохраняющих константу 0, так как для них f(0,0,…,0) = 0. Этот класс принято обозначать как С0.

Функциональная полнота

 

Мы выделили 5 классов функций алгебры логики. Различных классов функций гораздо больше: так, a-функции образуют свой класс, пересечение классов снова будет классом.

Американский математик Э.Пост установил, что классы М, D, L, C1 и C0 являются предполными, и других предполных классов в С нет.

Решение задачи формулируется как теорема  Э.Поста.

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

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

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

Пусть множество содержит функцию f₀, не сохраняющую константу ноль, f₁, не сохраняющую константу единица, f₂ – немонотонную, f₃ – несамодвойственную и f₄ – нелинейную функцию (все функции не обязательно различные).

f₀(0,0,…,0) = 1. Для этой функции возможны два варианта значений

f₀(1, 1,…,1). 

Если f₀ (1, 1,…,1) = 1, то функция является b-функцией, и при подстановке вместо всех аргументов произвольного одного аргумента она превращается в константу 1. Имея константу 1, из функции f₁ получаем константу 0, так как f₁(1, 1,…,1) = 0.  

Если f₀ (1, 1,…,1) = 0, то функция является d-функцией и при подстановке вместо всех аргументов произвольного одного аргумента она превращается в инверсию. В этом случае рассмотрим функцию f₃. Для неё найдется набор значений аргументов <a₁, a₂,…, a _n>, такой, что

 f(a₁, a₂,…, a_n) = f(`a<sub>1</sub>, `a₂,…, `a_n).

В функцию f₃ поставим произвольную переменную в прямой форме, если компонента набора a_i равна 1, и в инверсной форме, если равна 0, то получим константу, равную f(a₁, a₂,…, a_n). Из неё с помощью инверсии получается вторая константа.

С помощью констант из функции f₂ можно получить инверсию.

Для неё найдется два соседних набора, таких, что на меньшем наборе функция равна единице, а на большем – нулю. Если подставим в f₂ константы этого набора, где они совпадают, и произвольную перемен-ную, где наборы отличаются, получим инверсию этой переменной.

 Константы и инверсия позволяют получить конъюнкцию перемен-ных из функции f₄. Запишем эту функцию в виде полинома Жегалкина, выделим в нём первое вхождение переменных в конъюнкцию, и все пе-ременные, кроме переменных конъюнкции, заменим константой 0, а переменные в конъюнкции заменим произвольно на два различных аргумента, например на x и y. В результате возможны, с точностью до инверсии (константы С₀ в полиноме), следующие варианты:

1) xy; 

2) xyÅx;

3) xyÅy;

4) xyÅxÅy.

Таблица 3.3
f	M	D	L	C1	C0
0	+	х	+	х	+
1	+	х	+	+	х
‘x	х	+	+	х	х
xÚy	+	х	х	+	+
x×y	+	х	х	+	+
x®y	х	х	х	+	х
xÅy	х	х	+	х	+
x»y	х	х	+	+	х
‘(x×y)	х	х	х	х	х
`(xÚy)	х	х	х	х	х

В первом случае получаем конъюнкцию, что и необходимо получить, во втором варианте полученная функция равна функции `xy, из которой с помощью инверсии получим конъюнкцию. То же самое можно сказать и о третьем варианте, где функция равна `yx. Для последнего варианта функция равна дизъюнкции.

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

В табл. 3.3 показана при-надлежность простейших функций к предполным классам. Здесь + озна-чает, что функция принадлежит, а
 х – означает, что функция не принадлежит к классу, символом ‘ обозначена инверсия.

Из таблицы видно, что функциональной полнотой обладают множества {` x , x Ú y }, {` x , x × y }, { x × y , x Å y , 1}. { x ® y, 1}. Особый интерес представляют 2 последние функции, составляющие монофункциональ-ный базис. Такие функции, отве-чающие всем условиям теоремы Поста, получили название функций шефферовского типа.

Теорема позволяет определить, является ли заданное множество функционально полным, если нет, то какой функции в нём не хватает. Можно решать задачу построения функции шефферовского типа от более чем двух переменных. Это должна быть d-функция, так как она не сохраняет константы. Как  d-функция она немонотонна, и дальше нужно распределить единицы и нули в таблице так, чтобы функция была нелинейной и несамодвойственной.

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: