double arrow

Найдем значение функции f2 на противоположных наборах аргументов

Класс самодвойственных функций (U).

Класс монотонных булевых функций (М).

Класс функций, сохраняющих единицу (К1).

Класс функций, сохраняющих нуль (К0).

Класс линейных функций от n аргументов (Ln).

Основные классы функций алгебры логики.

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

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

В соответствии с теоремой Жегалкина любая булева функция представлена в виде полинома.

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

f(x1 x2 … xn)= α0α1 x1α2 x2 αn xn,

где α0, α1, … , αn – коэффициенты, равные 0 или 1.

Число различных линейных функций n переменных равно числу различных наборов вида <α0 α1 … αn > и равно 2n+1.

Пример. n=2. Класс L2 состоит из 8 функций:

f0(xy)=0; f3(xy)=x; f5(xy)=y;

f6(xy)= ; f9(xy)=1xy;

f10(xy)=1y; f12(xy)=1x; f15(xy)=1.

Отметим, что переключательные функции одного аргумента все линейны:

L1: f0(x)=0, f1(x)=x, f2(x)=1x, f3(x)=1.

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

Дано f1(x1 x2 … xn)= α0α1 x1αn xn;

φ1(y1 y2)= b10 b11 y1;

φ2(y1 y2)= b20 b21 y1;

. . . . . . . . . . . . . . . . . . . .

φn(y1 y2)= bn0 bn1 y1,

Подставим φi вместо xi функции f1 , получим выражение f2, в котором постоянные коэффициенты умножаются на линейные функции. Приведя подобные члены, получим представление функции f2 в виде линейного полинома.

Пример. f1(x1 x2 x3)=1 x1 x2 x3;

x11(y1 y2 y3 y4)= y1 y3y4;

x22(y1 y2)= 1 y1y2;

x33(y1 y2 y3 y4)= 1y1 y2y3y4;

f2(y1 y2 y3 y4)= 1 φ1(y1 y2 y3 y4) φ2(y1 y2) φ3(y1 y2 y3 y4)=

=1 y1y3y41 y1y21y1y2y3y4=1 y1.

При любых подстановках xi функция остается линейной.

Из линейных функций нельзя получить нелинейную, а наоборот можно.

Если функция на нулевом наборе аргументов <00…0> равна нулю, то говорят, что функция сохраняет нуль:

f(000…0)=0.

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

Пример. n=2. В класс К0входят следующие функции:

f0(xy), f1(xy) , f2(xy) , f3(xy) , f4(xy) , f5(xy) , f6(xy) , f7(xy).

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

Пусть имеем

f1(x1 x2 … xn), φ1(y1 y2), …, φn(y1 y2).

Все эти функции сохраняют нуль на нулевом наборе. Подставив вместо xi функции φi, получим новую функцию

f2(y1 y2)= f112, …,φn ).

Найдем значение f2 на нулевом наборе:

f2 (00 …0)= f1 (000 …0)=0.

Так как на нулевом наборе все аргументы равны нулю, то любая подстановка этих аргументов не изменит значение функции.

Если булева функция на единичном наборе <111…1> аргументов равна единице, то говорят, что эта функция сохраняет единицу:

f(111…1)=1.

Так как на одном наборе <11..1> значение функции зафиксировано, то остается 2n-1 независимых наборов, т.е. число функций, сохраняющих единицу, равно половине от всех функций n переменных, т.е. .

Пример. n=2. Класс К1содержит:

f1(xy), f3(xy) , f5(xy) , f7(xy) , f9(xy) , f11(xy) , f13(xy) , f15(xy).

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

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

Число функций класса М оценивается асимптотически:

≤ φn,

где φn – число монотонных функций от n аргументов; А– некоторая константа.

Пример. n=2. Класс М содержит

f0(xy), f1(xy) , f3(xy) , f5(xy) , f7(xy) , f15(xy).

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

f1(x1 x2 … xn);

φ1(y1 y2);

. . . . . . .

φn(y1 y2).

Пусть f2(y1 y2)= f112, …,φn).

Зафиксируем значение функции f2 на некотором наборе < y1 y2>, а затем увеличим этот набор. При этом значение любой монотонной функции φi<y1y2> уменьшиться не может, отсюда следует, что набор аргументов функции f1 не уменьшится с увеличением набора функции f2, а, следовательно, и значение функции f2 не уменьшится. Аналогично будет при подстановке аргументов.

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

или, что то же самое,

Пример. n=2. Класс U содержит

f3(xy) , f5(xy) , f10(xy) , f12(xy).

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

Имеем самодвойственные функции

f1(x1 x2 … xn);

φ1(y1 y2);

. . . . . . .

φn(y1 y2).

Подставляя функции φi вместо аргументов xi, получаем

f2(y1 y2)= f11φ2 …φn).

Поскольку функции φi самодвойственные, то из соотношения

находим

Таблица 15

 
 


x 0 0 1 1

y 0 1 0 1 L K0 K1 M U Примечание

 
 


f0 0 0 0 0 x x x

f1 0 0 0 1 x x x

f2 0 0 1 0 x

f3 0 0 1 1 x x x x x

f4 0 1 0 0 x

f5 0 1 0 1 x x x x x

f6 0 1 1 0 x x

f7 0 1 1 1 x x x

f8 1 0 0 0 f8 не принадлежит ни к

f9 1 0 0 1 x x одному из указанных

f10 1 0 1 0 x x классов функций

f11 1 0 1 1 x

f12 1 1 0 0 x x

f13 1 1 0 1 x

f14 1 1 1 0 f14 не принадлежит ни к

f15 1 1 1 1 x x x одному из указанных

классов функций

Так как f1 самодвойственная функция, то

Сравнивая последнее выражение с выражением f2 , окончательно получаем

,

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

Свойства функций двух переменных представлены в табл.15.


Сейчас читают про: