Як потрібно перевіряти функції, які задані таким чином?

Question

Дан 1 ответ

Правильный ответ

1)
функция, заданная вектором
$(a_0,a_1,...,a_{2^n-1})$
является самодвойственной тогда и только тогда, когда она имеет вид
$(a_0,a_1,...,a_{2^{n-1}-1},\overline a_{2^{n-1}-1},\overline a_{2^{n-1}-2},...,\overline a_0)$

Данная функция удовлетворяет данному условию:
$a_0=1=\overline0=\overline a_7,a_1=0=\overline1=\overline a_6,\\a_2=0=\overline1=\overline a_5,a_3=1=\overline0=\overline a_4$
Значит является самодвойственной

2)
f - функция 3 переменных. Достаточно сравнить значения функции на соседних наборах.
Но здесь можно поступить проще:
на наборе (0,0,0) функция имеет значение 1. Набор (0,0,0) заведомо меньше любого другого набора (сравним с любым набором). Поэтому монотонной функция быть не может (монотонной функцией, дающей на наборе (0,0,0) значение 1 является только функция тождественная 1)

Если бы была другая задача и нужно бы было проверять на монотонность, то необходимо было бы проверить на всех соседних наборах:
$f(0,0,0)=1, f(0,0,1)=0,f(0,1,0)=0,f(1,0,0)=0\\(0,0,0)\ \textless \ (0,0,1),f(0,0,0)\ \textgreater \ f(0,0,1)\\(0,0,0)\ \textless \ (0,1,0),f(0,0,0)\ \textgreater \ f(0,1,0)\\(0,0,0)\ \textless \ (1,0,0),f(0,0,0)\ \textgreater \ f(1,0,0)\\f(0,1,1)=1,f(1,0,1)=1,f(1,1,0)=1\\(0,0,1)\ \textless \ (0,1,1),f(0,0,1)\ \textless \ f(0,1,1)\\(0,0,1)\ \textless \ (1,0,1),f(0,0,1)\ \textless \ f(1,0,1)\\(0,1,0)\ \textless \ (0,1,1),f(0,1,0)\ \textless \ f(0,1,1)\\(0,1,0)\ \textless \ (1,1,0),f(0,1,0)\ \textless \ f(1,1,0)\\(1,0,0)\ \textless \ (1,0,1),f(1,0,0)\ \textless \ f(1,0,1)\\(1,0,0)\ \textless \ (1,1,0),f(1,0,0)\ \textless \ f(1,1,0)\\f(1,1,1)=0\\(0,1,1)\ \textless \ (1,1,1),f(0,1,1)\ \textgreater \ f(1,1,1)\\(1,0,1)\ \textless \ (1,1,1),f(1,0,1)\ \textgreater \ f(1,1,1)\\(1,1,0)\ \textless \ (1,1,1),f(1,1,0)\ \textgreater \ f(1,1,1)$

3)
Можно найти полином Жегалкина и проверить его на линейность.
$f(x_1,x_2,x_3)=1\oplus x_1\oplus x_2\oplus x_3$ - линеен
Можно проверить, что значения на наборах, отличающихся лишь одной существенной переменной различны. Так как различны значения на наборах (0,0,0) и (0,0,1), (0,0,0) и (0,1,0), (0,0,0) и (1,0,0), то данная функция существенно зависит от всех трех переменных. Значит нужно проверить, что значения на всех соседних наборах различны. Это показано в пункте 2)
Значит функция линейна

ProGroomer_zn (18.9k баллов) 16 Май, 18