Совершенная конъюнктивная нормальная форма — различия между версиями
м |
|||
| Строка 24: | Строка 24: | ||
[[файл:СКНФ11.JPG]] | [[файл:СКНФ11.JPG]] | ||
== Другие формы: == | == Другие формы: == | ||
| − | + | {{Список ЛФ}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Дискретная математика]][[Категория:Логика]] | [[Категория:Дискретная математика]][[Категория:Логика]] | ||
Версия 15:34, 21 ноября 2016
Совершенная конъюнктивная нормальная форма (СКНФ) для логической функции – это конъюнкция различных элементарных дизъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. При этом таблицы истинности для логической функции и её СКНФ совпадают.
Содержание
Формула
Введём обозначения:
n – число аргументов функции;
(x1,x2,…,xn) – набор аргументов функции;
f(x1,x2,…,xn) – логическая функция;
fСКНФ(x1,x2,…,xn) – СКНФ логической функции;
arg[f(x1,x2,…,xn)=0] – фиксированный набор аргументов функции, обращающий функцию в 0;
argj[f(x1,x2,…,xn)=0] – значение аргумента xj в фиксированном наборе аргументов.
– элементарная дизъюнкция.
- Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние нуля.
В элементарную дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
Пример
Другие формы:
- совершенная дизъюнктивная нормальная форма (СДНФ);
- совершенная конъюнктивная нормальная форма (СКНФ);
- минимальная дизъюнктивная нормальная форма (МДНФ);
- минимальная конъюнктивная нормальная форма (МКНФ);
- алгебраическая нормальная форма (АНФ).
