Совершенная конъюнктивная нормальная форма

Материал из Циклопедии
(перенаправлено с «СКНФ»)
Перейти к: навигация, поиск

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

Содержание

[править] Формула

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

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 в фиксированном наборе аргументов.

СКНФ01.JPG

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

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

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

[править] Пример

СКНФ11.JPG

[править] Другие формы:

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты