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

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

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

Обозначения

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

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

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

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

Операции:

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

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

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

Формула

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

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

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

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

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

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

Другие понятия:

• Логический закон;
• Логические функции;
• Нормальные формы:
  • совершенная дизъюнктивная нормальная форма;
  • совершенная конъюнктивная нормальная форма;
  • минимальная дизъюнктивная нормальная форма;
  • минимальная конъюнктивная нормальная форма;
  • алгебраическая нормальная форма;
• Таблица истинности;
• Карта Карно;
• Трёхмерная карта Карно;
• Предикат;
• Исчисление высказываний;
• Специальное исчисление высказываний;
• Секвенции;
• Суждение;
• Умозаключения.

Ссылки

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