Логические и арифметические основы и принципы работы ЭВМ

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


f8(x1,x2)

x1x2f8
0011
0101
1000

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

f8(x1,x2) = x1x2 = x1

x2

или

x1

x2 = x1x2

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

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

x2
x3
. . .
xn = x1x2x3 . . .xn

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

x1

x2
x3
. . .
xn = x1x2x3 . . .xn = x1
x2
x3
. . .
xn

или:

x1

x2
x3
. . .
xn = x1
x2
x3
. . .
xn

т.е.

x1

x2
x3
. . .
xn = x1
x2
x3
. . .
xn

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

x

x = xx = x

x1

x2 = x1x2 = x2x1 = x2
x1

x1

x2
x3 = (x1x2)
x3 = x1x2x3
x1
(x2x3),

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

x1

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

x1

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

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

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

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

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

f = Q1Q2Q3 . . . Qn

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

Qi = (xr

xp
xq
. . .
xw
xf
xe
. . .
xz)

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

Qi = (xr

xp
xq
. . .
xw
xf

xe

. . .
xz) = (xr * xp * xq * . . .
xw * xf * xe * . . . * xz)

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

Qi = (xr

xp
xq
. . .
xw
xf

xe

. . .
xz)

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

f = Q1

Q2
Q3
. . .
Qn

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

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

Пример:

f(x1x2 x3) = (x1

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

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

", а другой, то есть "
" и "-" - операцию Пирса и инверсию).

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

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



Содержание раздела