Упражнения.

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

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

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).

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;

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. С помощью таблиц значений проверьте справедливость следующих формул:

а) 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.

7. Выразите с помощью суперпозиций функции ,,,+,/, через функции  и .

8. Выразите с помощью суперпозиций функции ,,,+,/, через функции  и .

9. Выразите с помощью суперпозиций булевы функции ,,,,,+ через штрих Шеффера /.

10. Выразите с помощью суперпозиций булевы функции ,,,,,/,+ через стрелку Пирса .

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

а) {,,};

б) {,};

в) {,};

г) {,};

д) {/};

е) {}.

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

а)  через , ,  и ;

б)  через , ;

в)  через , ;

г)  через , ;

д)  через , .

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

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

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

а) {,,};

б) {}.

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

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

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

а) xy;

б) (xy)(yz);

в) (x/y)z;

г) ((xy)z)/x;

д) (xy)z.

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

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)

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₁);

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

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).

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

а) {+,,1};

б) {xy, xyz};

в) {xy, xyz};

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

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

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

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

Принадлежность функции 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} – полная.