Класс монотонных функций – M.

Функция f(x₁,…,x_n) называется монотонной, если на любой паре сравнимых наборов и таких, что p , выполнено f( )£f( ).

Пример 13. Функции 0, 1, x, Øx, x&y, xÚy, xyÚyzÚzx Î M, xÅy, x|y, x®y Ï M.

Лемма 13.[M]=M.

Лемма 14.(лемма о немонотонной функции) Если fÏM, то ØxÎ[{f,0,1}].

Задачи

23.Выяснить, являются ли функции f и g самодвойственными:

23.1. , a_g=(1001 1011 1011 1001);

23.2. , a_g=(1100 0011 1010 0101);

23.3. , a_g=(1101 0100 1011 0010);

23.4. , a_g=(1100 0011 0011 1100);

23.5. , a_g=(1001 0110 1001 0110);

23.6. , a_g=(1010 0101 0101 1010);

23.7. , a_g=(0101 0110 1000 0101);

23.8. , a_g=(0101 0100 1101 1010);

23.9. , a_g=(0101 0100 1100 0101);

23.10. , a_g=(0010 1000 1110 1011).

24.Заменить прочерки символами 0 и 1 так, чтобы получился вектор значений самодвойственной функции:

24.1.a_f=(0 1 – 0 – 0 – –);

24.2.a_f=(– – 01 – – 1 1);

24.3.a_f=(– 1 – 1 – 0 – 1);

24.4.a_f=(– 1 0 – 0 – – 1);

24.5.a_f=(1 – – 0 – 0 0 –);

24.6.a_f=(0 1 – – 0 1 – –);

24.7.a_f=(1 – 0 – 0 – 1 – );

24.8.a_f=(– 0 1 – 1 – – 0);

24.9.a_f=(– – 0 – 1 – 1 0);

24.10.a_f=(1 0 – 0 – 1 – – ).

25.Определить, какие переменные функции f следует заменить на x, а какие на с тем. Чтобы получить константу:

25.1.a_f=(0110 1000 1110 1011);

25.2.a_f=(1010 1110 1100 1010);

25.3.a_f=(1011 0100 1111 0010);

25.4.a_f=(1110 1000 0110 1000);

25.5.a_f=(0000 1111 0010 1111);

25.6.a_f=(1010 0101 0101 0011);

25.7.a_f=(1101 0001 1011 0100);

25.8.a_f=(0101 1101 0100 1111);

25.9.a_f=(0110 1001 0101 1101);

25.10.a_f=(1101 0000 1101 0000).

26.Представив функцию полиномом, выяснить, является ли она линейной:

26.1. ;

26.2. ;

26.3. ;

26.4. ;

26.5. ;

26.6. ;

26.7. ;

26.8. ;

26.9. ;

26.10. .

27.Выяснить, является ли линейной функция:

27.1.a _f =(0110 1001 0110 1001);

27.2.a_f =(1010 0101 0101 1010);

27.3.a_f =(0011 1100 1100 0011);

27.4.a_f =(1001 1001 0110 0110);

27.5.a_f =(1010 0110 0110 0101);

27.6.a_f =(1010 0101 1001 1100);

27.7.a_f =(1101 0010 1101 0010);

27.8.a_f =(0111 1001 1000 0110);

27.9.a_f =(0011 0010 1100 1101);

27.10.a_f =(0100 1100 1100 1011).

28.Заменить прочерки символами 0 и 1 так, чтобы получился вектор значений линейной функции:

28.1.a_f =(1 – – – – – – – – – – 0 – 1 1 0);

28.2.a_f =(– 1 1 – 1 – – – 1 – – – – – – 0);

28.3.a_f =(– – – 0 – 0 0 – 1 – 0 – – – – –);

28.4.a_f =(– 1 0 0 – – – 1 – 1 – – – – – –);

28.5.a_f =(– – – 1 – 1 1 – – 1 1 – 1 – 0 –);

28.6.a_f =(0 – 1 – – – – 1 – – – 1 – – – 0);

28.7.a_f =( – – – – 1 0 – – – – 0 – 0 1 – –);

28.8.a_f =(– 1 – – – – – – 0 0 – 1 – 1 – –);

28.9.a_f =(0 1 – – – – – – 1 – 1 – 1 – – –);

28.10.a_f =(– – 0 0 – – – – 1 1 – – – 0 – –).

29.Получить из функции f функцию xy:

29.1.a_f =(1101 1111 1100 1111);

29.2.a_f =(1111 0101 1111 1101);

29.3.a_f =(1001 0111 1111 1010);

29.4.a_f =(0111 1111 1110 1110);

29.5.a_f =(0111 1011 1111 1110);

29.6.a_f =(1101 1001 1001 0111);

29.7.a_f =(1011 1111 1001 1111);

29.8.a_f =(1011 0011 0010 1111);

29.9.a_f =(0010 1111 1111 0101);

29.10.a_f =(1111 1111 1110 1100).

30.Определить, являются ли функции f и g монотонными. Для немонотонных функций указать два соседних набора :

30.1. , a_g=(00010101);

30.2. , a_g=(01010111);

30.3. , a_g=(00110011);

30.4. , a_g=(00010111);

30.5. , a_g=(00010110);

30.6. , a_g=(00011111);

30.7. , a_g=(1001 1011);

30.8. , a_g=(1100 0011);

30.9. , a_g=(1101 0100);

30.10. , a_g=(1010 0101).