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

Материал из Циклопедии
Перейти к: навигация, поиск
Мат.Логика. Полином Жегалкина [10:22]
Лекция 14: Многочлены Жегалкина // НОУ ИНТУИТ [1:09:58]

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

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

Содержание

[править] Обозначения

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

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

(x1,x2,…,xn) – набор аргументов функции;

P(x1,x2,…,xn) – полином Жегалкина.

[править] Операции:

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

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

ПЖ03.JPG

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

ПЖ04.JPG

[править] Формула

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

ПЖ10.JPG

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

[править] Примеры полиномов:

[править] С одной переменной

ПЖ01.JPG

[править] С двумя переменными

ПЖ02.JPG

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

[править] Другие понятия:

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты