Алгебраическая нормальная форма - История изменений

Logic-samara в 10:12, 13 января 2024

2024-01-13T10:12:20Z

Logic-samara в 17:32, 1 ноября 2017

2017-11-01T17:32:17Z

Logic-samara в 15:35, 21 ноября 2016

2016-11-21T15:35:47Z

Logic-samara в 06:34, 10 февраля 2016

2016-02-10T06:34:08Z

Logic-samara в 19:37, 9 февраля 2016

2016-02-09T19:37:01Z

Logic-samara в 19:18, 9 февраля 2016

2016-02-09T19:18:28Z

Logic-samara в 19:17, 9 февраля 2016

2016-02-09T19:17:02Z

Logic-samara в 18:52, 9 февраля 2016

2016-02-09T18:52:52Z

Logic-samara в 18:50, 9 февраля 2016

2016-02-09T18:50:49Z

Logic-samara: Новая страница: «'''Алгебраическая нормальная форма (АНФ)''' для '''логической функции'…»

2016-02-09T18:48:48Z

Новая страница: «'''Алгебраическая нормальная форма (АНФ)''' для '''логической функции'…»

Новая страница

'''Алгебраическая нормальная форма (АНФ)''' для '''[[Логическая функция|логической функции]]''' – это упрощённый '''[[полином Жегалкина]]''', построенный для данной функции.
== Обозначения ==
Введём обозначения:

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

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

'''f(x1,x2,…,xn)''' – логическая функция;

'''fАНФ(x1,x2,…,xn)''' – АНФ логической функции;

'''P(x1,x2,…,xn)''' – полином Жегалкина.
== Общий вид ==
Полином Жегалкина имеет следующий вид:

[[файл:ПЖ10.JPG]]
* Заметим, что коэффициенты '''ai1...ik''' принимают значения из множества '''{0,1}''', причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено.
== Методы построения АНФ: ==
* метод эквивалентных преобразований;
* метод неопределённых коэффициентов.
=== Эквивалентные преобразования ===
Метод использует для преобразования СДНФ логической функции. Для этого операция отрицания переменной в СДНФ заменяется на сумму по модулю два константы 1 и переменной. Операция элементарной конъюнкции сохраняется в виде произведения. Операция дизъюнкции заменяется на сложение по модулю два, т. к. в СДНФ при любых значениях входных переменных в единицу обращается не более одного дизъюнкта, т.е. операция дизъюнкции эквивалентна операции разделительной дизъюнкции (сложению по модулю два). После этого проводятся необходимые упрощения: раскрываются скобки и сокращаются чётные повторения.
=== Метод неопределённых коэффициентов ===
Метод использует таблицу истинности логической функции. Для этого берётся общий вид полинома Жегалкина, в него подставляются наборы аргументов и приравниваются к соответствующим значениям логической функции из таблицы истинности. Полученную систему уравнений упрощают и решают относительно коэффициентов. Нулевые коэффициенты опускают, а для единичных коэффициентов выписывают АНФ логической функции.
== Другие формы: ==
*[[Совершенная дизъюнктивная нормальная форма]] ([[СДНФ]]);
*[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]);
*[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]);
*[[Минимальная конъюнктивная нормальная форма]] ([[МКНФ]]);
*[[Алгебраическая нормальная форма]] ([[АНФ]]).
== Ссылки ==
* Википедия.
* [[Участник:Logic-samara]]
[[Категория:Дискретная математика]][[Категория:Логика]]

@@ Строка 2: / Строка 2: @@
 При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её АНФ совпадают.
 == Обозначения ==
 '''n''' – число аргументов функции;
@@ Строка 13: / Строка 11: @@
 == Формула ==
 [[файл:АНФ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 и переменной. Операция элементарной конъюнкции сохраняется в виде произведения. Операция дизъюнкции заменяется на сложение по модулю два, т. к. в СДНФ при любых значениях входных переменных в единицу обращается не более одного дизъюнкта, т.е. операция дизъюнкции эквивалентна операции разделительной дизъюнкции (сложению по модулю два). После этого проводятся необходимые упрощения: раскрываются скобки и сокращаются чётные повторения.
@@ Строка 22: / Строка 20: @@
 Метод использует таблицу истинности логической функции. Для этого берётся общий вид полинома Жегалкина, в него подставляются наборы аргументов и приравниваются к соответствующим значениям логической функции из таблицы истинности. Полученную систему уравнений упрощают и решают относительно коэффициентов. Нулевые коэффициенты опускают, а для единичных коэффициентов выписывают АНФ логической функции.
 == [[Логическая функция|Другие формы:]] ==
-{{Список ЛФ}}
+{{Список ЛФор}}
 == Ссылки ==
-* Википедия.
+*Википедия.
-* [[Участник:Logic-samara]]
+*[[Участник:Logic-samara]]
-[[Категория:Дискретная математика]][[Категория:Логика]]
+[[Категория:Математика]][[Категория:Дискретная математика]][[Категория:Логика]]

@@ Строка 13: / Строка 13: @@
 == Формула ==
 [[файл:АНФ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}''', причём если коэффициент равен нулю, то соответствующее слагаемое должно быть опущено.
 == Методы построения АНФ: ==
 * метод эквивалентных преобразований;

@@ Строка 10: / Строка 10: @@
 '''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>)''' – АНФ логической функции.
-−
-'''P(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – полином Жегалкина.
 == Формула ==
-[[файл:ПЖ10.JPG]]
+[[файл:АНФ01.JPG]]
 * Заметим, что коэффициенты '''a<sub>i<sub>1</sub>...i<sub>k</sub></sub>''' принимают значения из множества '''{0,1}''', причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено.
 == Методы построения АНФ: ==

@@ Строка 13: / Строка 13: @@
 '''P(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – полином Жегалкина.
-== Общий вид ==
+== Формула ==
-Полином Жегалкина имеет следующий вид:
-−
 [[файл:ПЖ10.JPG]]
 * Заметим, что коэффициенты '''a<sub>i<sub>1</sub>...i<sub>k</sub></sub>''' принимают значения из множества '''{0,1}''', причём если коэффициент равен нулю, то соответствующее слагаемое может быть опущено.

@@ Строка 22: / Строка 22: @@
 Метод использует таблицу истинности логической функции. Для этого берётся общий вид полинома Жегалкина, в него подставляются наборы аргументов и приравниваются к соответствующим значениям логической функции из таблицы истинности. Полученную систему уравнений упрощают и решают относительно коэффициентов. Нулевые коэффициенты опускают, а для единичных коэффициентов выписывают АНФ логической функции.
 == Другие формы: ==
-*[[Совершенная дизъюнктивная нормальная форма]] ([[СДНФ]]);
+{{Список ЛФ}}
-*[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]);
-*[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]);
-*[[Минимальная конъюнктивная нормальная форма]] ([[МКНФ]]);
-*[[Алгебраическая нормальная форма]] ([[АНФ]]).
 == Ссылки ==
 * Википедия.
 * [[Участник:Logic-samara]]
 [[Категория:Дискретная математика]][[Категория:Логика]]

@@ Строка 1: / Строка 1: @@
 '''Алгебраическая нормальная форма (АНФ)''' для '''[[Логическая функция|логической функции]]''' – это упрощённый '''[[полином Жегалкина]]''', построенный для данной функции.
 == Обозначения ==
 Введём обозначения:

@@ Строка 20: / Строка 20: @@
 * метод эквивалентных преобразований;
 * метод неопределённых коэффициентов.
-=== Эквивалентные преобразования ===
+=== Метод эквивалентных преобразований ===
 Метод использует для преобразования СДНФ логической функции. Для этого операция отрицания переменной в СДНФ заменяется на сумму по модулю два константы 1 и переменной. Операция элементарной конъюнкции сохраняется в виде произведения. Операция дизъюнкции заменяется на сложение по модулю два, т. к. в СДНФ при любых значениях входных переменных в единицу обращается не более одного дизъюнкта, т.е. операция дизъюнкции эквивалентна операции разделительной дизъюнкции (сложению по модулю два). После этого проводятся необходимые упрощения: раскрываются скобки и сокращаются чётные повторения.
 === Метод неопределённых коэффициентов ===