Полином Жегалкина

Версия 05:33, 23 февраля 2018

Полином Жегалкина — это логическая функция, использующая две операции: конъюнкцию и разделительную дизъюнкцию. Полином предложен российским математиком Иваном Ивановичем Жегалкиным в 1927 году.

Назначение полинома Жегалкина - это алгебраическое выражение логических функций.

Содержание

1 Обозначения
2 Операции:
3 Формула
4 Примеры полиномов:
- 4.1 С одной переменной
- 4.2 С двумя переменными
5 Другие понятия:
6 Логический закон
7 Логические функции:
8 Нормальные формы:
9 Таблица истинности
10 Карта Карно
11 Трёхмерная карта Карно
12 Предикат
13 Секвенции
14 Суждение
15 Умозаключения:
16 Диаграммы:
- 16.1 диаграмма Венна
- 16.2 диаграмма Эйлера
17 Ссылки

Обозначения

Введём обозначения:

n – число аргументов функции;

(x₁,x₂,…,x_n) – набор аргументов функции;

P(x₁,x₂,…,x_n) – полином Жегалкина.

Операции:

конъюнкция;
разделительная дизъюнкция.

Конъюнкция — это логическая операция аналогичная арифметическому произведению. Для констант используется обозначение точкой, а для переменных точка опускается.

Разделительная дизъюнкция — это логическая операция аналогичная арифметическому сложению по модулю 2. Используется обозначение знаком плюс в кружке.

Формула

Полином Жегалкина имеет следующий вид:

Заметим, что коэффициенты a_{i₁...i_k} принимают значения из множества {0,1}, причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено.
Полином Жегалкина, состоящий только из слагаемых с единичными коэффициентами (т. е. с опущенными слагаемыми с нулевыми коэффициентами), называется алгебраической нормальной формой (АНФ) соответствующей логической функции.

Примеры полиномов:

С одной переменной

С двумя переменными

Значения полиномов Жегалкина задаются с помощью таблицы истинности или определяются по формулам.
Полином Жегалкина является предикатом, определённым на множестве {0,1}.

Диаграммы:

диаграмма Венна

диаграмма Эйлера

Ссылки

Википедия. Полином Жегалкина.
Участник:Logic-samara

@@ Строка 34: / Строка 34: @@
 * Значения полиномов Жегалкина задаются с помощью [[Таблица истинности|таблицы истинности]] или определяются по формулам.
 * Полином Жегалкина является [[предикат]]ом, определённым на множестве '''{0,1}'''.
-== Другие понятия: ==
+== [[Логические понятия|Другие понятия:]] ==
 {{Список ЛП}}
 == Ссылки ==

Полином Жегалкина — различия между версиями