Представить в виде полинома Жегалкина функцию f(x1, x2, x3) = (x1 | x2) ∨ x3 ∨ (x1 ↓ x3)

Для решения задачи приведем функцию к полиному Жегалкина. Напомним обозначения: 1. Штрих Шеффера: $x_1 | x_2 = \neg(x_1 \land x_2) = x_1 x_2 + 1$ 2. Стрелка Пирса: $x_1 \downarrow x_3 = \neg(x_1 \lor x_3) = (x_1 + 1)(x_3 + 1) = x_1 x_3 + x_1 + x_3 + 1$ 3. Дизъюнкция: $A \lor B = A + B + AB$ Подставим выражения в функцию: $f(x_1, x_2, x_3) = (x_1 x_2 + 1) \lor x_3 \lor (x_1 x_3 + x_1 + x_3 + 1)$ Сначала выполним операцию $(x_1 x_2 + 1) \lor x_3$: $A = x_1 x_2 + 1$, $B = x_3$ $A \lor B = (x_1 x_2 + 1) + x_3 + (x_1 x_2 + 1)x_3 = x_1 x_2 + 1 + x_3 + x_1 x_2 x_3 + x_3 = x_1 x_2 + 1 + x_1 x_2 x_3$ Теперь к полученному результату применим дизъюнкцию с $(x_1 x_3 + x_1 + x_3 + 1)$: $A = x_1 x_2 x_3 + x_1 x_2 + 1$, $B = x_1 x_3 + x_1 + x_3 + 1$ $f = A + B + AB = (x_1 x_2 x_3 + x_1 x_2 + 1) + (x_1 x_3 + x_1 + x_3 + 1) + (x_1 x_2 x_3 + x_1 x_2 + 1)(x_1 x_3 + x_1 + x_3 + 1)$ После раскрытия скобок и приведения подобных слагаемых (в поле $GF(2)$, где $x^2 = x$ и $x + x = 0$): $f = x_1 x_2 x_3 + x_1 x_2 + 1 + x_1 x_3 + x_1 + x_3 + 1 + (x_1 x_2 x_3 + x_1 x_2 x_3 + x_1 x_2 x_3 + x_1 x_2 x_3 + x_1 x_2 + x_1 x_2 x_3 + x_1 x_3 + x_1 x_2 x_3 + x_1 x_3 + x_1 + x_3 + 1)$ Упрощая выражение, получаем: $f = x_1 x_2 + x_1 x_3 + x_2 x_3 + 1$ **Ответ:** Первый вариант $x_1 x_2 + x_1 x_3 + x_2 x_3 + 1$.