01 (1006312), страница 2
Текст из файла (страница 2)
f = Q1
Q2 Q3 . . . Qn
Итак: чтобы от КНФ перейти к базису Пирса и инверсии необходимо:
-
заменить операции дизъюнкции операциями Пирса
-
заменить операции конъюнкции операциями Пирса
-
заключить в скобки все те группы букв, которые соответсвуют конъюнктивным членам.
Пример:
f(x1x2 x3) = (x1 
x2 x3) (x1 x4) (x2 x4) = (x1 x2 x3) (x1 x4) (x2 x4)
Замечание. Так как в этих произведениях число букв не увеличивается, и если исходная форма функции была минимальной, то вновь полученная также будет минимальной (в действительности дело обстоит сложнее, поскольку мы рассматриваем не базис " ", а другой, то есть " " и "-" - операцию Пирса и инверсию).
Принципиально можно избавиться от отрицаний, применив соотношение: xi = xi xi, но тогда нельзя будет утверждать, что полученная форма будет минимальной!
Операция штрих Шеффера
| x1 | 0 | 0 | 1 | 1 |
| x2 | 0 | 1 | 0 | 1 |
| f14 | 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)
То же самое можно утверждать относительно минимальной формы.
В заключение необходимо отметить, что в настоящее время вопросы синтеза функций в одноэлементном базисе приобретают большое значение, так как соответствующие элементы используют операцию Пирса и Шеффера. Однако в полной мере теоретически методы синтеза разработаны не столь детально, как это сделано в базисе "и", "или", "инверсия".
Минимальные конъюнктивные нормальные формы
Как было отмечено, для получения минимальной формы функции нужно построить как МДНФ так и МКНФ.
Рассмотрим построение МКНФ.
В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:
-
Представить ФАЛ в СКНФ. Если она задана таблицей, то произвести запись функции по нулям, как это было сформулировано ранее. Если дана СДНФ, то из нее легко получить СКНФ:
f(x1x2x3) = x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 = (x1 x2 x3) (x1 x2 x3) (x1 x2 x3),
т.е. нужно функцию представить в виде конъюнкции недостающего числа дизъюктивных членов с соответсвенно расставлеными отрицаниями.
-
При задании функции в произвольной конъюктивной форме, применяя
формулы развертывания:
x = (x y)(x y) = xx xy yx yy (x y) = (x y z)(x y z)
. . . . . . . . . . . .,
получить СКНФ.
-
Выполнить все операции неполного склеивания:
(x y)(x y) = x(x y)(x y)
и поглощения: x(x y) = x, получить сокращенную КНФ.
-
Применить любой из методов минимизации: испытание членов, диаграммы Вейча, метод импликантных матриц.
-
При выполнении метода испытания членов необходимо каждый конъюктивный член приравнять нулю. Найти значения аргументов, которые обращают его в нуль, удалить его из выражения функции и найти значение функции при найденных значениях аргументов. Если функция обратится в нуль, то конъюктивный член является лишним.
-
По возможности отбросить одновременно несколько членов, поступить как и при минимизации функции ДНФ.
-
При использовании диаграмм Вейча ищутся правильные конфигурации, образованные нулями.
-
При применении метода импликантных матриц поступают как и в случае ДНФ, только колонкам присваивают имена конституент "0" функции, записанной в СКНФ, а горизонтальным рядам – простых импликант. Далее ищут оптимальное покрытие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
