Упражнения. 6.1. Сколько существует различных булевых функций от одной переменной?

6.1. Сколько существует различных булевых функций от одной переменной? Составьте таблицы значений всех булевых функций от одной переменной. Выразите эти функции через отрицание и основные булевы функции от двух переменных.

6.2. Сколько существует различных булевых функций от двух переменных? Составьте таблицы значений каждой из них. Выразите эти функции через отрицание и основные булевы функции от двух переменных.

6.3. Постройте таблицы значений для следующих булевых функций:

а) f(x,y)=((x®y)Ùùy)®ùx;

б) f(x,y,z)=(((x®(yÚz))Ùù(yÙz))®x;

в) f(x,y,z)=ùx®(z«(y+(xÙz)));

г) f(x,y,z)=(((x/y)¯z)/y)¯z;

д) f(x,y,z)=((xÚùy)®z)Ù((x/y)«ùz).

6.4. Построив таблицы значений, выясните, равны ли следующие булевы функции:

a) f(x,y,z)=((xÚy)Úz)®((xÚy)Ù(xÚz)),

g(x,y,z)=x«z;

б) f(x,y,z)=(ùxÚy)Ù(yÚz),

g(x,y,z)=(xÚyÚz)Ù(ùxÚyÚz)Ù(ùxÚyÚùz);

в) f(x,y,z)=(x®y)®z,

g(x,y,z)=x®(y®z);

г) f(x,y)=((x+y)®(xÚy))Ù((ùx®y)®(x+y)),

g(x,y)=x/y;

6.5. Покажите, что:

а) xÙy=ù(ùxÚùy);

б) x®y=ùxÚy;

в) x«y=(x®y)Ù(y®x)=(ùxÚy)Ù(xÚùy);

г) x+y=ù(ùxÚy)Úù(xÚùy);

д) x¯y=ù(xÚy);

е) x/y=ùxÚùy.

6.6. С помощью таблиц значений проверьте справедливость следующих формул:

а) ùx=x+1;

б) x+y=y+x;

в) (x+y)+z=x+(y+z);

г) xÙ(y+z)=xÙy+xÙz;

д) x+x=0;

е) 0+0=0;

ж) x+0=x;

з) 1+1=0.

6.7. Выразите с помощью суперпозиций функции Ú,®,«,+,/,¯ через функции Ù и ù.

6.8. Выразите с помощью суперпозиций функции Ú,Ù,«,+,/,¯ через функции ® и ù.

6.9. Выразите с помощью суперпозиций булевы функции ù,Ù,Ú,®«,¯,+ через штрих Шеффера /.

6.10. Выразите с помощью суперпозиций булевы функции ù,Ù,Ú,®,«,/,+ через стрелку Пирса ¯.

6.11. Докажите полноту следующих систем булевых функций:

а) {Ù,Ú,ù};

б) {Ú,ù};

в) {Ù,ù};

г) {®,ù};

д) {/};

е) {¯}.

6.12. Докажите, что нельзя с помощью суперпозиций выразить:

а) ù через Ù, Ú, ® и «;

б) Ù через Ú, ®;

в) ® через Ù, Ú;

г) Ù через ù, «;

д) «через Ù, Ú.

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

Например, в задача n.в каждая из функций Ù и Ú сохраняет 0, т.е. 0Ù0=0 и 0Ú0=0. Следовательно, всякая суперпозиция функций Ù и Ú будет функцией, сохраняющей 0. Но функция ® не сохраняет 0, т.к. 0®0=1.

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

а) {Ù,Ú,®};

б) {Ù}.

6.14. Докажите полноту системы {+, Ù, 1}.

6.15. Докажите, что любую булеву функцию можно представить в виде полинома Жегалкина (причем это представление единственно).

6.16. Постройте многочлен Жегалкина для функций:

а) x®y;

б) (x®y)Ù(y¯z);

в) (x/y)¯z;

г) ((x®y)Úz)/x;

д) (x«y)Ùz.

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

6.18. Является ли функция g двойственной к функции f, если:

а) f=x+y g=x«y;

б) f=x®y g=y®x;

в) f=(xÙy)Ú(xÙz)Ú(yÙz) g=(xÙy)+(xÙz)+(yÙz);

г) f=x+y+z g=x+y+z;

д)f=(ùxÙùy)Ú(xÙ(y«z)) g(x,y,z)=(01101101)

6.19. Раскладывая функцию f в полином Жегалкина, выясните является ли она линейной:

а) f(x₁,x₂,x₃)=((x₁Ùx₂)Ú(ùx₁Ùùx₂))+x­₃;

б) f(x₁,x₂)=x₁Ùx₂Ù(x₁+x₂);

в) f(x₁,x₂,x₃)= ((x₁®x₂)Ù(x₂®x₁))«x­₃;

г) f(x₁,x₂,x₃,x₄)= (ùx₁Ùx₂)Ú(ùx₂Ùx₃)Ú (ùx₃Ùx₄)Ú(ùx₄Ùx₁);

6.20. Среди булевых функций от одного и двух аргументов найдите все функции, принадлежащие классам Т₀, Т₁, L, M, S.

6.21. Какие из перечисленных функций являются монотонными:

а) x®(x®y);

б) x®(y®x);

в) xÙyÙ(x+y);

г) (xÙy)+(yÙz)+(zÙx)+z;

д) f(x₁,x₂,x₃)=(00110111);

е) f(x₁,x₂,x₃)=(01100111).

6.22. Используя теорему Поста, выясните, полна ли система:

а) {+,Ú,1};

б) {x®y, x®ùyÙz};

в) {xÙùy, ùx«yÙz};

г) {(01101001),(10001101),(00011100)}.

Решение: а) Составим таблицу Поста.

В клетках таблицы будем писать знак «+» или «-» в зависимости от того, принадлежит рассматриваемая функция данному функционально замкнутому классу или нет.

f	T0	T1	S	L	M
X+y	+	-	-	+	-
XÚy	+	+	-	-	+
	-	+	-	+	+

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

Принадлежность функции x+y класса T₀, L и непринадлежность классу Т₁ очевидна. Эта функция не самодвойственная, т.к. (x+y)*=ù(ùx+ùy)=((x+1)+(y+1))+1=x+y+1. Функция x+y немонотонная, т.к. (1,0)£(1,1), а 1+0=1 и 1+1=0.

Функция xÚy, очевидно, принадлежит классам Т₀ и Т₁. Она несамодвойственная, т.к. двойственная ей функция есть хÙу. Она нелинейная, т.к. многочлен Жегалкина этой функции имеет вид xÚy=ху+х+у. Монотонность функции легко проверяется по ее таблице истинности.

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

Т.к. каждый столбец таблицы Поста содержит по меньшей мере один знак “-“, то система {+, Ú, 1} – полная.