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