Получить полином Жегалкина для логической функции

Задание относится к курсу дискретной математики, а конкретно — к разделу булевой алгебры (логические функции) и преобразованию логических выражений в полином Жегалкина.

Задача: Получить полином Жегалкина для логической функции: \[ f(x, y, z) = (x \land y \land z) \lor (\neg x \land y) \]

Шаги преобразования:

1. Составим таблицу истинности для функции:
   • Логическая функция имеет 3 переменные: \( x \), \( y \), \( z \).
   • Комбинируем все возможные значения для \( x \), \( y \), и \( z \) (всего 8 различных комбинаций булевых значений \( 0 \) и \( 1 \)).

   \( x \)	\( y \)	\( z \)	\( x \land y \land z \)	\( \neg x \land y \)	\( f(x, y, z) \)
   0	0	0	0	0	0
   0	0	1	0	0	0
   0	1	0	0	1	1
   0	1	1	0	1	1
   1	0	0	0	0	0
   1	0	1	0	0	0
   1	1	0	0	0	0
   1	1	1	1	0	1

2. Применим метод Жегалкина:

   Полином Жегалкина строится как линейная комбинация переменных с использованием операций \( \oplus \) (сложения по модулю 2) и умножения \( \land \) (конъюнкция):

   \[ f(x, y, z) = a_0 \oplus a_1 x \oplus a_2 y \oplus a_3 z \oplus a_4 xy \oplus a_5 xz \oplus a_6 yz \oplus a_7 xyz \]

   Для этого начинаем находить коэффициенты \( a \) методом последовательных разностей.

3. Нахождение коэффициентов:
   • \( a_0 \) — это значение функции при всех аргументах, равных нулю: \( f(0,0,0) = 0 \).
   • Следующие коэффициенты \( a_i \) вычисляются через последовательные разности значений функции:
   • \( a_1 = f(1,0,0) \oplus f(0,0,0) = 0 \oplus 0 = 0 \),
   • \( a_2 = f(0,1,0) \oplus f(0,0,0) = 1 \oplus 0 = 1 \),
   • \( a_3 = f(0,0,1) \oplus f(0,0,0) = 0 \oplus 0 = 0 \),
   • \( a_4 = f(1,1,0) \oplus f(1,0,0) \oplus f(0,1,0) \oplus f(0,0,0) = 0 \oplus 0 \oplus 1 \oplus 0 = 1 \),
   • \( a_5 = f(1,0,1) \oplus f(1,0,0) = 0 \oplus 0 = 0 \),
   • \( a_6 = f(0,1,1) \oplus f(0,1,0) = 1 \oplus 1 = 0 \),
   • \( a_7 = f(1,1,1) \oplus f(1,1,0) \oplus f(1,0,1) \oplus f(1,0,0) = 1 \oplus 0 \oplus 0 \oplus 0 = 1 \).
4. Запишем полином Жегалкина:

   Используя найденные коэффициенты, получаем:

   \[ f(x, y, z) = a_2 y \oplus a_4 xy \oplus a_7 xyz \]

   Подставляя коэффициенты:

Ответ:

Полином Жегалкина для функции \( f(x, y, z) = (x \land y \land z) \lor (\neg x \land y) \) равен: