Полином Жегалкина — различия между версиями
Материал из ALL
м |
|||
| (не показано 18 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Полином Жегалкина''' — это [[логическая функция]], использующая две операции: конъюнкцию и разделительную дизъюнкцию. Полином предложен российским математиком Иваном Ивановичем Жегалкиным в 1927 году. | '''Полином Жегалкина''' — это [[логическая функция]], использующая две операции: конъюнкцию и разделительную дизъюнкцию. Полином предложен российским математиком Иваном Ивановичем Жегалкиным в 1927 году. | ||
| + | |||
| + | Назначение полинома Жегалкина - это алгебраическое выражение логических функций. | ||
| + | == Обозначения == | ||
| + | '''n''' – число аргументов функции; | ||
| + | |||
| + | '''(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – набор аргументов функции; | ||
| + | |||
| + | '''P(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – полином Жегалкина. | ||
== Операции: == | == Операции: == | ||
| − | * конъюнкция; | + | *конъюнкция; |
| − | * разделительная дизъюнкция. | + | *разделительная дизъюнкция. |
| − | '''Конъюнкция''' | + | '''Конъюнкция''' — это логическая операция аналогичная арифметическому произведению. Для констант используется обозначение точкой, а для переменных точка опускается. |
[[файл:ПЖ03.JPG]] | [[файл:ПЖ03.JPG]] | ||
| − | '''Разделительная дизъюнкция''' | + | '''Разделительная дизъюнкция''' — это логическая операция аналогичная арифметическому сложению по модулю 2. Используется обозначение знаком плюс в кружке. |
[[файл:ПЖ04.JPG]] | [[файл:ПЖ04.JPG]] | ||
| − | == | + | == Формула == |
| − | Полином Жегалкина | + | Полином Жегалкина имеет следующий вид: |
[[файл:ПЖ10.JPG]] | [[файл:ПЖ10.JPG]] | ||
| − | * Заметим, что коэффициенты '''a<sub>i<sub>1</sub>...i<sub>k</sub></sub>''' принимают значения из множества '''{0,1}''', причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено. | + | *Заметим, что коэффициенты '''a<sub>i<sub>1</sub>...i<sub>k</sub></sub>''' принимают значения из множества '''{0,1}''', причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено. |
| − | * Полином Жегалкина, состоящий только из слагаемых с единичными коэффициентами (с опущенными слагаемыми с нулевыми коэффициентами), называется алгебраической нормальной формой (АНФ) соответствующей логической функции. | + | *Полином Жегалкина, состоящий только из слагаемых с единичными коэффициентами (т. е. с опущенными слагаемыми с нулевыми коэффициентами), называется '''[[Алгебраическая нормальная форма|алгебраической нормальной формой]] ([[АНФ]])''' соответствующей логической функции. |
== Примеры полиномов: == | == Примеры полиномов: == | ||
=== С одной переменной === | === С одной переменной === | ||
| Строка 22: | Строка 30: | ||
=== С двумя переменными === | === С двумя переменными === | ||
[[файл:ПЖ02.JPG]] | [[файл:ПЖ02.JPG]] | ||
| − | * Значения полиномов Жегалкина задаются с помощью [[Таблица истинности|таблицы истинности]] или определяются по формулам. | + | *Значения полиномов Жегалкина задаются с помощью [[Таблица истинности|таблицы истинности]] или определяются по формулам. |
| − | * Полином Жегалкина является [[предикат]]ом, определённым на множестве '''{0,1}'''. | + | *Полином Жегалкина является [[предикат]]ом, определённым на множестве '''{0,1}'''. |
| − | == Другие понятия: == | + | == [[Логические понятия|Другие понятия:]] == |
| − | + | {{Список ЛПон}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
| − | * [[Участник:Logic-samara]] | + | *Википедия. Полином Жегалкина. |
| − | [[Категория:Дискретная математика]][[Категория:Логика]] | + | *[[Участник:Logic-samara]] |
| + | [[Категория:Математика]][[Категория:Дискретная математика]][[Категория:Логика]] | ||
Текущая версия на 05:00, 13 января 2024
Полином Жегалкина — это логическая функция, использующая две операции: конъюнкцию и разделительную дизъюнкцию. Полином предложен российским математиком Иваном Ивановичем Жегалкиным в 1927 году.
Назначение полинома Жегалкина - это алгебраическое выражение логических функций.
Содержание
Обозначения
n – число аргументов функции;
(x1,x2,…,xn) – набор аргументов функции;
P(x1,x2,…,xn) – полином Жегалкина.
Операции:
- конъюнкция;
- разделительная дизъюнкция.
Конъюнкция — это логическая операция аналогичная арифметическому произведению. Для констант используется обозначение точкой, а для переменных точка опускается.
Разделительная дизъюнкция — это логическая операция аналогичная арифметическому сложению по модулю 2. Используется обозначение знаком плюс в кружке.
Формула
Полином Жегалкина имеет следующий вид:
- Заметим, что коэффициенты ai1...ik принимают значения из множества {0,1}, причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено.
- Полином Жегалкина, состоящий только из слагаемых с единичными коэффициентами (т. е. с опущенными слагаемыми с нулевыми коэффициентами), называется алгебраической нормальной формой (АНФ) соответствующей логической функции.
Примеры полиномов:
С одной переменной
С двумя переменными
- Значения полиномов Жегалкина задаются с помощью таблицы истинности или определяются по формулам.
- Полином Жегалкина является предикатом, определённым на множестве {0,1}.
Другие понятия:
- отрицание;
- дизъюнкция;
- конъюнкция;
- разделительная дизъюнкция;
- импликация;
- обратная импликация;
- эквиваленция;
- стрелка Пирса;
- штрих Шеффера;
- полином Жегалкина;
- Нормальные формы:
- совершенная дизъюнктивная нормальная форма;
- совершенная конъюнктивная нормальная форма;
- минимальная дизъюнктивная нормальная форма;
- минимальная конъюнктивная нормальная форма;
- алгебраическая нормальная форма;
Ссылки
- Википедия. Полином Жегалкина.
- Участник:Logic-samara
