Минимальные конъюнктивные нормальные формы

Как было отмечено, для получения минимальной формы функции нужно построить как МДНФ так и МКНФ.

Рассмотрим построение МКНФ.

В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:

Представить ФАЛ в СКНФ. Если она задана таблицей, то произвести запись функции по нулям, как это было сформулировано ранее. Если дана СДНФ, то из нее легко получить СКНФ:

f(x1x2x3) = x1x2x3

x1x2x3

= (x1

x3) (x1

x3),

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

При задании функции в произвольной конъюктивной форме, применяя

формулы развертывания:

x = (x

y)(x

y) = xx

yy (x

y) = (x

z)(x

. . . . . . . . . . . .,

получить СКНФ.

Выполнить все операции неполного склеивания:

y)(x

y) = x(x

y)(x

и поглощения: x(x

y) = x, получить сокращенную КНФ.

Применить любой из методов минимизации: испытание членов, диаграммы Вейча, метод импликантных матриц. При выполнении метода испытания членов необходимо каждый конъюктивный член приравнять нулю. Найти значения аргументов, которые обращают его в нуль, удалить его из выражения функции и найти значение функции при найденных значениях аргументов. Если функция обратится в нуль, то конъюктивный член является лишним.

По возможности отбросить одновременно несколько членов, поступить как и при минимизации функции ДНФ.

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

Операция штрих Шеффера

x1x2f14

0	0	1	1
0	1	0	1
1	1	1	0

Заметим, что эта функция дуальна по отношению к f8, поэтому все свойства являются по существу дуально вытекающими из рассмотренных.

f14 (x1,x2) = x1

x2 (запись функций по нулям)

x1 | x2 = x1

x2 = x1

x2 = x1x2 = x1 x2

на основе принципа суперпозиции:

x1 | x2 | . . . | xn = x1x2...xn

Рассмотрим некоторые эквивалентности:

x | x = x

x = x

x1 | x2 | x3 = (x1 x2)| x3 = x1| (x2 x3)

x1 | x2 | x3| x4 = (x1 x2)| (x3 x4)

Сформулируем правила перехода от ДНФ функции к выражению с использованием операции "Штрих Шеффера".

заменить все операции дизъюнкции на операции Шеффера заменить все операции конъюнкции на операции Шеффера группы букв, которые соответствуют дизъюнктивным членам, заключить в скобки.

Пример:

f(x1x2 x3) = x1x2 x3

x1x2

x1x2x3 = = (x1|x2|x3)|(x1|x2)|(x1|x2|x3)

То же самое можно утверждать относительно минимальной формы.

В заключение необходимо отметить, что в настоящее время вопросы синтеза функций в одноэлементном базисе приобретают большое значение, так как соответствующие элементы используют операцию Пирса и Шеффера. Однако в полной мере теоретически методы синтеза разработаны не столь детально, как это сделано в базисе "и", "или", "инверсия".

Операция (стрелка) Пирса

f8(x1,x2)

x1x2f8

0	0	1	1
0	1	0	1
1	0	0	0

Эту функцию можем представить, записав по "единицам":

f8(x1,x2) = x1x2 = x1

или

x2 = x1x2

На основе принципа суперпозиции:

f(x1,x2,...xn) = x1

. . .

xn = x1x2x3 . . .xn

Применяя правило де Моргана:

. . .

xn = x1x2x3 . . .xn = x1

. . .

или:

. . .

xn = x1

. . .

т.е.

. . .

xn = x1

. . .

Рассмотрим некоторые соотношения для операции Пирса:

x = xx = x

x2 = x1x2 = x2x1 = x2

x3 = (x1x2)

x3 = x1x2x3

(x2x3),

т.е. операция Пирса не обладает свойством ассоциативности

x3 = (x1

x2)

x3 = x1

(x2

x3)

x4 = (x1

x2)

(x3

x4)

При этом порядок выполнения операций в формулах, где есть операции Пирса такой:

раскрываются скобки выполняются операции инверсии выполняются операции Пирса

Синтез логических функций в базисе Пирса удобно производить, имея запись функции в КНФ.

Допустим, что ФАЛ задана в конъюктивной форме

f = Q1Q2Q3 . . . Qn

Подставим член Qi в виде:

Qi = (xr

. . .

xz)

Возьмем двойное отрицание от обеих частей этого равенства, применив правило де Моргана

Qi = (xr

. . .

xz) = (xr * xp * xq * . . .

xw * xf * xe * . . . * xz)

Применяя соотношение, полученное на основе принципа суперпозиции:

Qi = (xr

. . .

xz)

Или, применяя это преобразование к исходной форме, получим:

f = Q1

. . .

Итак: чтобы от КНФ перейти к базису Пирса и инверсии необходимо:

заменить операции дизъюнкции операциями Пирса заменить операции конъюнкции операциями Пирса заключить в скобки все те группы букв, которые соответсвуют конъюнктивным членам.

Пример:

f(x1x2 x3) = (x1

x3) (x1

x4) (x2

x4) = (x1

x3)

(x1

x4) (x2

x4)

Замечание. Так как в этих произведениях число букв не увеличивается, и если исходная форма функции была минимальной, то вновь полученная также будет минимальной (в действительности дело обстоит сложнее, поскольку мы рассматриваем не базис "

", а другой, то есть "

" и "-" - операцию Пирса и инверсию).

Принципиально можно избавиться от отрицаний, применив соотношение: xi = xi

xi, но тогда нельзя будет утверждать, что полученная форма будет минимальной!