Канонические формы представления логических функций

Синтез логического устройства распадается на несколько этапов. На первом этапе требуется функцию, заданную в словесной, табличной или другой формах, представить в виде логического выражения с использованием некоторого базиса. Следующие этапы сводятся к получению минимальных форм функций, обеспечивающих при синтезе наименьшее количество электронного оборудования и рациональное построение функциональной схемы устройства. Для начального представления функции обычно используется базис И, ИЛИ, НЕ независимо от того, какой базис будет использоваться для построения логического устройства.

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

44. Теорема разложения.

Пусть s(sigma) - параметр, равный 0 или 1. Введем обозначение

| x, если s=1,

x^s=|

| ~x, если s=0.

Тогда x^s=1, если x=s и x^s=0, если x=/=s (это легко проверить

подстановкой значений x,s in {0,1}).

Теорема Шеннона. Любая переключательная функция f(x1,...,xn) может

быть представлена в следующем виде:

f(x1,...,xk,xk+1,...,xn)=\/ x1^s1*...xk^sk*f(s1,...,sk,xk+1,...xn),

s1,...,sk

где k<=n, а дизъюнкция берется по всем 2^k наборам значений переменных

x1,...,xk. Это равенство называется РАЗЛОЖЕНИЕМ ПО ПЕРЕМЕННЫМ

x1,...,xk.

### n=4, k=2. Разложение имеет вид:

f(x1,x2,x3,x4)=~x1~x2*f(0,0,x3,x4) \/ ~x1 x2*f(0,1,x3,x4) \/

x1~x2*f(1,0,x3,x4) \/ x1 x2*f(1,1,x3,x4).

Доказательство. Подставим в обе части равенства произвольный набор

всех переменных a1,..,ak,ak+1,..,an. Так как x^s=1 только когда x=s,

то среди 2^k конъюнкций x1^a1*..xk^ak в правой части в единицу обра-

тится только одна - та, в которой x1=a1,...,xk=ak, все остальные конъ-

юнкции будут равны 0. Поэтому получим:

f(a1,...,an)=a1^a1*...ak^ak*f(a1,...,ak,ak+1,..an)=f(a1,...,an), т.е.

тождество.

При k=n разложение принимает вид:

f(x1,...,xn)=\/ x1^s1*...xn^sn*f(s1,...,sn),

s1,...,sn

которое для f(x1,...,xn)=/=0 может быть преобразовано к виду

f(x1,...,xn)=\/ x1^s1*...xn^sn*f(s1,...,sn)=\/ x1^s1*...xn^sn,

s1,...,sn s1,...,sn

f(s1,...,sn)=1 f(s1,...,sn)=1

где дизъюнкция берется по всем наборам s1,...,sn, на которых функция

обращается в 1. Такое разложение называется СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ

НОРМАЛЬНОЙ ФОРМОЙ (СДНФ).

Свойства СДНФ:

- является дизъюнкцией s>=1 различных конъюнкций ранга n, где s -

число единичных наборов;

- каждому единичному набору s1,...,sn соответствует единственная

конъюнкция всех переменных, в которую xi входит с отрицанием, если

si=0, и без отрицания, если si=1; такая конъюнкция называется КОНСТИ-

ТУЕНТОЙ 1 и обозначается Kl, где l - десятичный эквивалент соответс-

твующего единичного набора;

- для любой ПФ представление в СДНФ единственно (с точностью до

порядка букв и конъюнкций);

- существует взаимно-однозначное соответствие между таблицами

функции и ее СДНФ: каждой конституенте 1 в СДНФ соответствует одна

строка в таблице истинности и одна клетка в карте Карно;

- единственная функция, не имеющая СДНФ - Константа 0.

- для любой ПФ, не являющейся константой 0, можно использовать за-

дание функции в виде списка номеров конституент 1 (единичных наборов):

f=\/1 (i1, i2, i3,..., is)

### ----------------- x2

----------------- x3

00 01 11 10

+--------+--------+--------+--------+

0|f(0,0,0)|f(0,0,1)|f(0,1,1)|f(0,1,0)| f=~x1*~x2*~x3 \/

| 1 | 0 | 1 | 0 | ~x1* x2* x3 \/

+--------+--------+--------+--------| x1*~x2* x3 \/

|1|f(1,0,0)|f(1,0,1)|f(1,1,1)|f(1,1,0)| x1* x2*~x3

| | 0 | 1 | 0 | 1 |

+--------+--------+--------+--------+ f=\/1 (0, 3, 5, 6)

x1

45. Двойственная теорема разложения. СКНФ.

На основании законов двойственности (законов де-Моргана) нетрудно

получить другое специальное представление формул ПФ. Для этого запишем

формулу функции ~f(x1,...,xn), инверсной по отношению к исходной функ-

ции f(x1,...,xn) (единичные и нулевые наборы меняются местами!!!) в

форме СДНФ, которая для ~f(x1,...,xn)=/=0 имеет вид:

~f(x1,...,xn)=\/ x1^s1*...xn^sn

s1,...,sn

~f(s1,...,sn)=1

Применим операцию отрицания к обеим частям полученной СДНФ. На основа-

нии обобщения законов де-Моргана и закона двойного отрицания получим:

~(~f(x1,...,xn))=f(x1,...,xn)=~(\/ x1^s1*...xn^sn)=

s1,...,sn

~f(s1,...,sn)=1

=& (x1^ ~s1 \/...\/xn^ ~sn)=

s1,...,sn

f(s1,...,sn)=0

Это представление называется СОВЕРШЕННОЙ КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ

ФОРМОЙ (СКНФ).

Свойства СКНФ:

- является конъюнкцией s>=1 различных дизъюнкций ранга n, где s -

число нулевых наборов;

- каждому нулевому набору s1,...,sn соответствует единственная

дизъюнкция всех переменных, в которую xi входит с отрицанием, если

si=1, и без отрицания, если si=0 (сравните с СДНФ!!!); такая дизъюнк-

ция называется КОНСТИТУЕНТОЙ 0 и обозначается Dl, где l - десятичный

эквивалент соответствующего нулевого набора;

- для любой ПФ представление в СКНФ единственно (с точностью до

порядка букв и дизъюнкций);

- существует взаимно-однозначное соответствие между таблицами

функции и ее СКНФ: каждой конституенте 0 в СКНФ соответствует одна

строка в таблице истинности и одна клетка в карте Карно;

- единственная функция, не имеющая СКНФ - Константа 1.

- для любой ПФ, не являющейся константой 1, можно использовать за-

дание функции в виде списка номеров конституент 0 (нулевых наборов):

f=&0 (i1, i2, i3,..., is).

### ----------------- x2

----------------- x3

00 01 11 10

+--------+--------+--------+--------+

0|f(0,0,0)|f(0,0,1)|f(0,1,1)|f(0,1,0)| f=(x1 \/ x2 \/ ~x3) &

| 1 | 0 | 1 | 0 | (x1 \/ ~x2 \/ x3) &

+--------+--------+--------+--------| (~x1 \/ x2 \/ x3) &

|1|f(1,0,0)|f(1,0,1)|f(1,1,1)|f(1,1,0)| (~x1 \/ ~x2 \/ ~x3)

| | 0 | 1 | 0 | 1 |

+--------+--------+--------+--------+ f=&0 (1, 2, 4, 7)

x1

На основании теоремы Шеннона можно указать еще один способ уста-

новления эквивалентности двух различных формул. Обе формулы приводятся

к СДНФ(СКНФ) и признаются эквивалентными тогда и только тогда, когда

их СДНФ(СКНФ) совпадают.

46. Минимизация переключательных функций.