Совершенная дизъюнктивная нормальная форма — различия между версиями

Материал из ALL
Перейти к: навигация, поиск
Строка 24: Строка 24:
 
[[файл:СДНФ11.JPG]]
 
[[файл:СДНФ11.JPG]]
 
== Другие формы: ==
 
== Другие формы: ==
*[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]);
+
* [[совершенная дизъюнктивная нормальная форма]] ([[СДНФ]]);
*[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]);
+
* [[совершенная конъюнктивная нормальная форма]] ([[СКНФ]]);
*[[Минимальная конъюнктивная нормальная форма]] ([[МКНФ]]).
+
* [[минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]);
 +
* [[минимальная конъюнктивная нормальная форма]] ([[МКНФ]]).
 
== Ссылки ==
 
== Ссылки ==
 
* [[Участник:Logic-samara]]
 
* [[Участник:Logic-samara]]
 
[[Категория:Дискретная математика]][[Категория:Логика]]
 
[[Категория:Дискретная математика]][[Категория:Логика]]

Версия 10:16, 31 января 2016

Совершенная дизъюнктивная нормальная форма (СДНФ) для логической функции – это дизъюнкция различных элементарных конъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. При этом таблицы истинности для логической функции и её СДНФ совпадают.

Формула

Введём обозначения:

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

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

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

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

arg[f(x1,x2,…,xn)=1] – фиксированный набор аргументов функции, обращающий функцию в 1;

argj[f(x1,x2,…,xn)=1] – значение аргумента xj в фиксированном наборе аргументов.

СДНФ01.JPG

СДНФ10.JPG – элементарная конъюнкция.

  • Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы.

В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0.

Пример

СДНФ11.JPG

Другие формы:

Ссылки