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