Синтез переключательных функций в одноэлементном базисе

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

f₈(x₁,x₂)

x1
x2
f8

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

f₈(x₁,x₂) = x₁x₂ = x₁x₂

или

x₁x₂ = x₁x₂

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

f(x₁,x₂,...x_n) = x₁x₂x₃... x_n = x₁x₂x₃...x_n

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

x₁x₂x₃...x_n = x₁x₂x₃...x_n = x₁ x₂ x₃ ... x_n

или:

x₁x₂x₃...x_n = x₁ x₂ x₃ ... x_n

т.е.

x₁x₂x₃...x_n = x₁ x₂ x₃ ... x_n

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

xx = xx = x

x₁x₂ = x₁x₂ = x₂x₁ = x₂x₁

x₁x₂x₃ = (x₁x₂)x₃ = x₁x₂x₃ x₁(x₂x₃),

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

x₁x₂x₃ = (x₁x₂)x₃ = x₁(x₂x₃)

x₁x₂x₃x₄ = (x₁x₂)(x₃x₄)

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

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

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

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

f = Q₁Q₂Q₃... Q_n

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

Q_i = (x_r x_p x_q ... x_w x_f x_e ... x_z)

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

Q_i = (x_r x_p x_q ... x_w x_f x_e ... x_z) = (x_r * x_p * x_q *... x_w * x_f * x_e *... * x_z)

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

Q_i = (x_rx_px_q...x_wx_f x_e...x_z)

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

f = Q₁Q₂Q₃...Q_n

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

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

Пример:

f(x₁x₂ x₃) = (x₁ x₂ x₃) (x₁ x₄) (x₂ x₄) = (x₁x₂x₃)(x₁x₄) (x₂x₄)

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

Принципиально можно избавиться от отрицаний, применив соотношение: x_i = x_ix_i, но тогда нельзя будет утверждать, что полученная форма будет минимальной!

Дата добавления: 2014-01-06