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

Аналитическое представление функции в СКНФ будет равно логическому произведению сумм значений функции на i-ом наборе и i-ого махтерма. Запись функции будет иметь вид

Таким образом, функция представленная таблицей 1.11, запишется в следующем виде

F(X₁,X₂,X₃)=(0+М₀)·(0+М₁)·(1+М₂)·(1+М₃)·(0+М₄)·(1+М₅)·(0+М₆)·(1+М₇) =

=

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

Если дизъюнкции не содержат все переменные (аргументы или их инверсии), то эта запись будет простой конъюнктивной нормальной формой (КНФ). Например:

.

Не является КНФ запись, содержащая более сложную функцию, чем простая дизъюнкция. Например, выражение;

.

не является КНФ, так как содержит более сложную функцию (инверсию дизъюнкции X₂+X₃).

Получение логических выражений скнф и сднф

Для записи СДНФ или СКНФ надо иметь функцию, заданную в виде таблицы.

Из таблицы 1.11 видно, что функция Y принимает значение единицы четыре раза: при наборах аргументов X₁,X₂,X₃ – 010, 011, 101 и 111, что можно записать так: функция Y равна 1 при наборе значений аргументов ИЛИ 010, ИЛИ 011, ИЛИ 101, ИЛИ 111.

Только в одной из четырех строго заданных ситуаций (наборов значений входных переменных) функция равна единице. Каждая ситуация определяется конкретными значениями входных переменных. Например, для первой ситуации должны быть одновременно аргументы И X₁=0, И X₂=1, И X₃=0, что можно представить конъюнкцией этих аргументов, а чтобы их произведение стало равно единице при требуемых значениях переменных, необходимо в этой конъюнкции проинвертировать аргументы X₁ и X₃: . Соответственно для второго набора (конъюнкции) надо инвертировать Х₁, для третьего – Х₂, а для четвертого инвертировать ничего не надо, так как произведение значений аргументов в последнем случае равно единице. СДНФ рассматриваемой функции имеет вид:

Каждый член полученного выражения только в одном случае равен единице, во всех же остальных он равен нулю, поэтому и все выражение примет значение единицы только в четырех случаях.

Правило записи СДНФ:

Для записи функции в СДНФ надо записать столько членов суммы в виде конъюнкции всех аргументов, сколько единиц имеет функция; для каждого набора, обращающего функцию в 1, аргумент в соответствующей конъюнкции записывается с инверсией, если его значение в наборе равно 0.

Для записи СКНФ надо рассматривать значения функции, равные нулю. Для того, чтобы на нескольких наборах значений аргументов функция принимала нулевое значение, надо взять произведение элементарных функций (дизъюнкций), каждая из которых обращается в 0 только на своем наборе значений аргументов. Такой функцией является дизъюнкция. Чтобы дизъюнкция на определенном наборе была равна нулю, надо записать сумму аргументов этого набора (махтерм), проинвертировав те из них, значения которых равны единице в заданном наборе. Дизъюнкция аргументов принимает значение равное 1 на всех наборах, отличных от заданного хотя бы для одного аргумента и, следовательно, если значение аргумента функции не совпадает ни с одним из заданных наборов, то произведение дизъюнкций, то есть вся функция окажется равной единице, что и должно быть.

Для рассматриваемого примера надо в первом наборе (первая строка таблицы функции) взять все исходные значения аргументов (они все равны нулю), во второй – проинвертировать Х₃ (он равен единице), в пятой – проинвертировать Х₁, а в седьмой – Х₁ и Х₂:

.

Правило записи СКНФ:

Для записи СКНФ надо записать конъюнкцию стольких членов в виде дизъюнкции всех аргументов, сколько нулей имеет функция; причем для каждого набора, обращающего функцию в 0, аргумент в соответствующей дизъюнкции записывается с инверсией, если его значение в наборе равно 1.