Решение: Реши задачу: Реши все задания которые тут пре

Задание 27. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Совершенной полиномиальной нормальной формой называется

1. представление функции алгебры логики в виде ДНФ, КНФ
2. представление функции алгебры логики в виде полинома Жегалкина
3. представление функции алгебры логики в виде сокращенной ДНФ, КНФ
4. представление функции алгебры логики в виде совершенной ДНФ, КНФ

Ответ: 4) представление функции алгебры логики в виде совершенной ДНФ, КНФ

Задание 28. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Функция вида \(a_1x_1 \oplus a_2x_2 \oplus \dots \oplus a_nx_n \oplus a_0\), где \(a_i \in \{0,1\}\), \(i = 0,1,\dots,n\) называется

1. сохраняющими 0
2. сохраняющими 1
3. самодвойственными
4. линейными
5. монотонными

Ответ: 4) линейными

Задание 29. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если \(f(0,0,\dots,0)=0\) функция называется

1. сохраняющими 0
2. сохраняющими 1
3. самодвойственными
4. линейными
5. монотонными

Ответ: 1) сохраняющими 0

Задание 30. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если \(f(x_1,\dots,x_n) = \overline{f(\overline{x_1},\dots,\overline{x_n})}\) функция называется

1. сохраняющими 0
2. сохраняющими 1
3. самодвойственными
4. линейными
5. монотонными

Ответ: 3) самодвойственными

Задание 31. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если из условия \(\alpha = (\alpha_1,\dots,\alpha_n)\) < \(\beta = (\beta_1,\dots,\beta_n)\) следует, что \(f(\alpha_1,\dots,\alpha_n) \le f(\beta_1,\dots,\beta_n)\) функция называется

1. сохраняющими 0
2. сохраняющими 1
3. самодвойственными
4. линейными
5. монотонными

Ответ: 5) монотонными

Задание 32. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Арифметическим полиномом не является

1. \(xyz \oplus xy \oplus z \oplus x\)
2. \(xyz \oplus xy \oplus zzzz\)
3. \(xyz \oplus xy \oplus 1 \oplus 1\)
4. \(xyz \oplus 1 \oplus xy \oplus yyyz\)

Ответ: 2) \(xyz \oplus xy \oplus zzzz\)

Задание 33. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Выберите справедливые равносильности

1. \(x \oplus x = 1\)
2. \(x \oplus x = 0\)
3. \(x \oplus x = x\)
4. \(x \oplus x = \overline{x}\)

Ответ: 2) \(x \oplus x = 0\)

Задание 34. Решите задачу. Заполнить таблицу Поста

Таблица Поста для функции \(f(x,y) = x \overline{y} \vee \overline{x} y\)

Функция \(f(x,y) = x \overline{y} \vee \overline{x} y\) является функцией "исключающее ИЛИ" (XOR).

Заполним таблицу Поста:

T₀ (сохранение 0): \(f(0,0) = 0 \overline{0} \vee \overline{0} 0 = 0 \cdot 1 \vee 1 \cdot 0 = 0 \vee 0 = 0\). Функция сохраняет 0. Значит, в столбце T₀ ставим '+'.

T₁ (сохранение 1): \(f(1,1) = 1 \overline{1} \vee \overline{1} 1 = 1 \cdot 0 \vee 0 \cdot 1 = 0 \vee 0 = 0\). Функция не сохраняет 1. Значит, в столбце T₁ ставим '-'.

S (самодвойственность): Функция \(f(x_1,\dots,x_n)\) самодвойственна, если \(f(x_1,\dots,x_n) = \overline{f(\overline{x_1},\dots,\overline{x_n})}\).

Проверим для \(f(x,y) = x \overline{y} \vee \overline{x} y\):

\(\overline{f(\overline{x},\overline{y})} = \overline{\overline{x} \overline{\overline{y}} \vee \overline{\overline{x}} \overline{y}} = \overline{\overline{x} y \vee x \overline{y}}\)

По законам де Моргана: \(\overline{\overline{x} y \vee x \overline{y}} = \overline{(\overline{x} y)} \wedge \overline{(x \overline{y})} = (x \vee \overline{y}) \wedge (\overline{x} \vee y)\)

Раскроем скобки: \(x \overline{x} \vee x y \vee \overline{y} \overline{x} \vee \overline{y} y = 0 \vee x y \vee \overline{x} \overline{y} \vee 0 = x y \vee \overline{x} \overline{y}\)

Так как \(f(x,y) = x \overline{y} \vee \overline{x} y\) и \(\overline{f(\overline{x},\overline{y})} = x y \vee \overline{x} \overline{y}\), то \(f(x,y) \ne \overline{f(\overline{x},\overline{y})}\). Функция не самодвойственна. Значит, в столбце S ставим '-'.

L (линейность): Функция линейна, если её полином Жегалкина имеет вид \(a_0 \oplus a_1x_1 \oplus \dots \oplus a_nx_n\).

Построим полином Жегалкина для \(f(x,y) = x \overline{y} \vee \overline{x} y\).

Известно, что \(x \overline{y} \vee \overline{x} y = x \oplus y\).

Полином Жегалкина для \(x \oplus y\) имеет вид \(x \oplus y\). Это линейный полином. Функция линейна. Значит, в столбце L ставим '+'.

M (монотонность): Функция монотонна, если для любых наборов \(\alpha\) и \(\beta\) таких, что \(\alpha \le \beta\), выполняется \(f(\alpha) \le f(\beta)\).

Проверим монотонность для \(f(x,y) = x \oplus y\).

Рассмотрим наборы: \((0,0) \le (0,1)\): \(f(0,0) = 0\), \(f(0,1) = 0 \oplus 1 = 1\). \(0 \le 1\), условие выполняется.

\((0,0) \le (1,0)\): \(f(0,0) = 0\), \(f(1,0) = 1 \oplus 0 = 1\). \(0 \le 1\), условие выполняется.

\((0,1) \le (1,1)\): \(f(0,1) = 1\), \(f(1,1) = 1 \oplus 1 = 0\). \(1 \not\le 0\). Условие не выполняется.

Функция не монотонна. Значит, в столбце M ставим '-'.

Итоговая таблица Поста: