Алгебраическая нормальная форма — различия между версиями
| Строка 13: | Строка 13: | ||
'''P(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>)''' – полином Жегалкина. | ||
| − | == | + | == Формула == |
| − | + | ||
| − | + | ||
[[файл:ПЖ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}''', причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено. | ||
Версия 19:18, 9 февраля 2016
Алгебраическая нормальная форма (АНФ) для логической функции – это упрощённый полином Жегалкина, построенный для данной функции. При этом таблицы истинности для логической функции и её АНФ совпадают.
Содержание
Обозначения
Введём обозначения:
n – число аргументов функции;
(x1,x2,…,xn) – набор аргументов функции;
f(x1,x2,…,xn) – логическая функция;
fАНФ(x1,x2,…,xn) – АНФ логической функции;
P(x1,x2,…,xn) – полином Жегалкина.
Формула
- Заметим, что коэффициенты ai1...ik принимают значения из множества {0,1}, причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено.
Методы построения АНФ:
- метод эквивалентных преобразований;
- метод неопределённых коэффициентов.
Метод эквивалентных преобразований
Метод использует для преобразования СДНФ логической функции. Для этого операция отрицания переменной в СДНФ заменяется на сумму по модулю два константы 1 и переменной. Операция элементарной конъюнкции сохраняется в виде произведения. Операция дизъюнкции заменяется на сложение по модулю два, т. к. в СДНФ при любых значениях входных переменных в единицу обращается не более одного дизъюнкта, т.е. операция дизъюнкции эквивалентна операции разделительной дизъюнкции (сложению по модулю два). После этого проводятся необходимые упрощения: раскрываются скобки и сокращаются чётные повторения.
Метод неопределённых коэффициентов
Метод использует таблицу истинности логической функции. Для этого берётся общий вид полинома Жегалкина, в него подставляются наборы аргументов и приравниваются к соответствующим значениям логической функции из таблицы истинности. Полученную систему уравнений упрощают и решают относительно коэффициентов. Нулевые коэффициенты опускают, а для единичных коэффициентов выписывают АНФ логической функции.
Другие формы:
- Совершенная дизъюнктивная нормальная форма (СДНФ);
- Совершенная конъюнктивная нормальная форма (СКНФ);
- Минимальная дизъюнктивная нормальная форма (МДНФ);
- Минимальная конъюнктивная нормальная форма (МКНФ);
- Алгебраическая нормальная форма (АНФ).
Ссылки
- Википедия.
- Участник:Logic-samara
