Совершенная дизъюнктивная нормальная форма — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
|||
| Строка 1: | Строка 1: | ||
'''Совершенная дизъюнктивная нормальная форма (СДНФ)''' для '''[[Логическая функция|логической функции]]''' – это дизъюнкция различных элементарных конъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. | '''Совершенная дизъюнктивная нормальная форма (СДНФ)''' для '''[[Логическая функция|логической функции]]''' – это дизъюнкция различных элементарных конъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. | ||
При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её СДНФ совпадают. | При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её СДНФ совпадают. | ||
| − | |||
== Формула == | == Формула == | ||
Введём обозначения: | Введём обозначения: | ||
| Строка 20: | Строка 19: | ||
[[файл:СДНФ10.JPG]] – элементарная конъюнкция. | [[файл:СДНФ10.JPG]] – элементарная конъюнкция. | ||
| − | |||
* Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы. | * Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы. | ||
В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0. | В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0. | ||
| − | |||
== Пример == | == Пример == | ||
[[файл:СДНФ11.JPG]] | [[файл:СДНФ11.JPG]] | ||
| − | |||
== Другие формы: == | == Другие формы: == | ||
*[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]); | *[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]); | ||
*[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]); | *[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]); | ||
*[[Минимальная конъюнктивная нормальная форма]] ([[МКНФ]]). | *[[Минимальная конъюнктивная нормальная форма]] ([[МКНФ]]). | ||
| − | |||
== Ссылки == | == Ссылки == | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Дискретная математика]][[Категория:Логика]] | [[Категория:Дискретная математика]][[Категория:Логика]] | ||
Версия 16:15, 15 января 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 в фиксированном наборе аргументов.
– элементарная конъюнкция.
- Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы.
В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0.
Пример
Другие формы:
- Совершенная конъюнктивная нормальная форма (СКНФ);
- Минимальная дизъюнктивная нормальная форма (МДНФ);
- Минимальная конъюнктивная нормальная форма (МКНФ).
