Полином Жегалкина — это логическая функция, использующая две операции: конъюнкцию и разделительную дизъюнкцию. Полином предложен российским математиком Иваном Ивановичем Жегалкиным в 1927 году.
Назначение полинома Жегалкина - это алгебраическое выражение логических функций.
Обозначения
Введём обозначения:
n – число аргументов функции;
(x1,x2,…,xn) – набор аргументов функции;
P(x1,x2,…,xn) – полином Жегалкина.
Операции:
- конъюнкция;
- разделительная дизъюнкция.
Конъюнкция — это логическая операция аналогичная арифметическому произведению. Для констант используется обозначение точкой, а для переменных точка опускается.
Разделительная дизъюнкция — это логическая операция аналогичная арифметическому сложению по модулю 2. Используется обозначение знаком плюс в кружке.
Формула
Полином Жегалкина имеет следующий вид:
- Заметим, что коэффициенты ai1...ik принимают значения из множества {0,1}, причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено.
- Полином Жегалкина, состоящий только из слагаемых с единичными коэффициентами (т. е. с опущенными слагаемыми с нулевыми коэффициентами), называется алгебраической нормальной формой (АНФ) соответствующей логической функции.
Примеры полиномов:
С одной переменной
С двумя переменными
- Значения полиномов Жегалкина задаются с помощью таблицы истинности или определяются по формулам.
- Полином Жегалкина является предикатом, определённым на множестве {0,1}.
Другие понятия:
Логический закон
Логические функции:
отрицание
дизъюнкция
конъюнкция
разделительная дизъюнкция
импликация
обратная импликация
эквиваленция
стрелка Пирса
штрих Шеффера
полином Жегалкина
Нормальные формы:
совершенная дизъюнктивная нормальная форма
совершенная конъюнктивная нормальная форма
минимальная дизъюнктивная нормальная форма
минимальная конъюнктивная нормальная форма
алгебраическая нормальная форма
Таблица истинности
Карта Карно
Трёхмерная карта Карно
Предикат
Секвенции
Суждение
Умозаключения:
превращение
обращение
противопоставление предикату
противопоставление субъекту
чисто условные умозаключения
силлогизм
условно-категорические умозаключения
разделительно-категорические умозаключения
эквивалентно-категорические умозаключения
Диаграммы:
Ссылки
- Википедия. Полином Жегалкина.
- Участник:Logic-samara