Файл: Основы бортовых вычислительных машин.pdf

48 наборе значение цифры двоичного кода набора равно 1, то перемен- ная в записи конституенты инвертируется, если значение цифры – 0, то переменная записывается без инверсии.
Пример,
2 1
0
(3)
3 0
1 1
М
x
x
x
j
= ∨ ∨
=
На всех остальных наборах
)
( j
М
= 1.
Непосредственно из определения конституент следует справед- ливость следующей системы тождеств (
j
i
≠
):
)
(
j
K
=
)
( j
М
,
)
( j
М
=
)
( j
K
;
&
)
(i
K
)
( j
K
=1,
∨
)
(i
М
)
( j
М
=0.
1.5 Переключательные функции и их минимизация
1.5.1 Канонические формы функций
Для практической реализации цифровых устройств часто ис- пользуют ключевые схемы с двумя устойчивыми состояниями, по- этому логические функции, описывающие работу цифровых уст- ройств, называют переключательными функциями (ПФ).
Одна и та же функция может быть задана бесчисленным множе- ством формул. Неоднозначность представления функций в виде фор- мул существенно усложняет установление различных соотношений между функциями и задающими их таблицами, например, установле- ние тождества между функциями.
Поэтому из всех форм представления переключательных функ- ций особый интерес имеют формы однозначного представления. Та- кие формы называют стандартными или каноническими. Как и табли- цы истинности, канонические формы часто используют в качестве исходных форм задания переключательных функций.
В булевой алгебре используют две канонические формы – со- вершенную дизъюнктивную нормальную форму (СДНФ) и совер- шенную конъюнктивную нормальную форму (СКНФ).
Для получения СДНФ переключательной функции необходимо выполнить дизъюнкцию конституент единиц тех наборов, на которых
ПФ равна 1: СДНФ
)
(
1
j
K
f
W
j
∈
∨
=
Правило перехода от табличного способа задания цифрового устройства к СДНФ ПФ вытекает из определения. Например, для за-

49 данной случайным образом таблицы истинности (таблица 1.8) СДНФ переключательной функции имеет следующий вид:
СДНФ
0 1
2 0
1 2
0 1
2 0
1 2
)
4
(
)
3
(
)
1
(
)
,
,
(
x
x
x
x
x
x
x
x
x
K
K
K
x
x
x
f
∨
∨
=
∨
∨
=
Таблица 1.8
Значение аргументов
Номер набора
2
х
1
х
0
х
Значение функции
)
,
,
(
0 1
2
x
x
x
f
0 1
2 3
4 5
6 7
0 0
0 0
1 1
1 1
0 0
1 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
1 0
0 0
Рассмотрим несколько примеров получения СДНФ (таблицы 1.9,
1.10).
Таблица 1.9
Значение аргументов
Номер набора
2
х
1
х
0
х
Значение функции
)
,
,
(
0 1
2
x
x
x
f
0 1
2 3
4 5
6 7
0 0
0 0
1 1
1 1
0 0
1 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
1 1
0 0
0 1
СДНФ переключательной функции по данным таблицы 1.9 име- ет вид:
0 1
2 0
1 2
0 1
2 0
1 2
0 1
2
)
,
,
(
х
х
х
х
х
х
х
х
х
х
х
х
x
x
x
f
⋅
⋅
∨
⋅
⋅
∨
⋅
⋅
∨
⋅
⋅
=
Пусть на входе приемника действует последовательность из 4-х импульсов. Наличие импульса отметим 1, а отсутствие 0. Заполним таблицу истинности для устройства определяющего наличие не менее
3-х импульсов в пачке ( таблица 1.10).

50
Таблица 1.10
Значение аргументов
Номер набора
3
х
2
х
1
х
0
х
Значение функции
)
,
,
(
0 1
2
x
x
x
f
0 1
2 3
4 5
6 7
8 9
10 11 12 13 14 15 0
0 0
0 0
0 0
0 1
1 1
1 1
1 1
1 0
0 0
0 1
1 1
1 0
0 0
0 1
1 1
1 0
0 1
1 0
0 1
1 0
0 1
1 0
0 1
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
0 0
0 0
0 0
1 0
0 0
1 0
1 1
1
Искомая СДНФ переключательной функции имеет вид:
0 1
2 3
0 1
2 3
0 1
2 3
0 1
2 3
0 1
2 3
х
х
х
х
х
х
х
х
х
х
х
х
х
х
х
х
х
х
х
х
у
∨
∨
∨
∨
=
Совершенная конъюнктивная нормальная форма ПФ получается конъюнкцией конституент нуля тех наборов, на которых переключа- тельная функция равна нулю:
СКНФ
)
(
0
j
М
f
W
j
∈
Λ
=
СКНФ ПФ таблицы истинности
)
,
,
(
0 1
2
x
x
x
f
(см. таблицу 1.8) в соответствии с определением равна:
).
(
&
)
(
&
&
)
(
&
)
(
&
)
(
)
7
(
&
)
6
(
&
)
5
(
&
)
2
(
&
)
0
(
)
,
,
(
0 1
2 0
1 2
0 1
2 0
1 2
0 1
2 0
1 2
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
M
M
M
M
М
x
x
x
f
∨
∨
∨
∨
∨
∨
∨
∨
∨
∨
=
=
=

51
Очевидна справедливость следующих тождеств:
)
(
)
(
;
)
(
)
(
1 0
0 1
j
M
j
K
f
j
M
j
K
f
W
j
W
j
W
j
W
j
∈
∈
∈
∈
Λ
=
∨
=
Λ
=
∨
=
Кроме канонических форм, в булевой алгебре большую роль иг- рают более простые в смысле записи, а зачастую и в смысле схемной реализации функций формы, а именно:
Дизъюнктивная нормальная форма (ДНФ);
Конъюнктивная нормальная форма (КНФ).
ДНФ представляет собой дизъюнкцию (сумму) элементарных конъюнкций, необязательно являющихся конституентами единицы.
КНФ представляет собой конъюнкцию (произведение) элемен- тарных дизъюнкций, необязательно являющихся конституентами ну- ля.
Следует помнить, что ДНФ и КНФ уже не являются формами однозначного представления функций. На множестве ДНФ и КНФ решают задачу поиска наиболее простых по сложности формул пере- ключательной функции, эту задачу принято называть задачей мини- мизации функций.
1.5.2 Общие понятия о минимизации переключательных функ- ций
Выражение переключательной функции в СДНФ или CКНФ яв- ляется отправным при технической реализации логических схем циф- ровых устройств. Сложность логических схем (ЛС) определяется сложностью выражения ПФ, по которому ЛС реализуется. Поэтому раньше всего следует упростить ПФ или, как говорят, произвести ми- нимизацию переключательных функций.
Сущность задачи минимизации состоит в поиске способа позво- ляющего по некоторой исходной формуле функции, например СДНФ, находить другую формулу, имеющую наименьшую сложность.
Сложность ПФ оценивается числом переменных, входящих в ее выражение (с учетом повторения).
Задача минимизации является исключительно сложной и воб- щем виде практически неразрешимой (неизбежен перебор вариантов), поэтому от поиска абсолютных минимальных форм функций прихо- дится отказываться и ограничиваться нахождением минимальных форм лишь среди некоторого класса формул.

52
В булевой алгебре, в частности, ограничиваются минимизацией
СДНФ и СКНФ, и нахождением минимальных по сложности ДНФ и
КНФ, сокращенно обозначаемых через МДНФ и МКНФ соответст- венно.
Известны разные процедуры минимизации ПФ, но все они осно- ваны на применении некоторых тождественных преобразований та- ких как: операции полного и неполного склеивания; операции поглощения; операции удаления (или добавления) лишних членов и др.
Операция склеивания выражается тождествами:
.
А
)
х
А
(
)
х
А
(
;
А
х
А
х
А
=
∨
⋅
∨
=
⋅
∨
⋅
(1.6)
В этих выражениях члены А
⋅
х и
х
А
⋅
(так же, как
х
А
∨
и
х
А
∨
) отличаются только одной переменной, такие члены принято называть соседними. В отношении операции (1.6) говорят также, что члены А
⋅
х и
х
А
⋅
(
х
А
∨
и
х
А
∨
) склеиваются по переменной х .
Рассмотрим две соседние конституанты единицы четырех пере- менных:
0 1
2 3
8
х
х
х
х
К
⋅
⋅
⋅
=
и
0 1
2 3
9
х
х
х
х
К
⋅
⋅
⋅
=
В результате их склеивания по переменной х
о получаем
.
х
х
х
)
х
х
(
х
х
х
К
К
1 2
3 0
0 1
2 3
9 8
⋅
⋅
=
∨
⋅
⋅
⋅
=
∨
т.е. получаем новую конъюнкцию, ранг которой на единицу меньше ранга исходных конъюнкций. При этом переменная, по которой про- изведено склеивание, исключается, а результат склеивания содержит только переменные, входящие одинаковым образом (т.е. либо без ин- версии, либо с инверсией) в исходные конституенты К
8
и К
9
. Это правило является универсальным и применимо к любым соседним ло- гическим выражениям.
Операция неполного склеивания определяется соотношением
.
А
А
х
А
х
А
=
∨
⋅
∨
⋅
Операции поглощения выражаются тождественными соотноше- ниями
.
А
)
х
А
(
А
;
А
)
х
А
(
А
;
А
х
А
А
;
А
х
А
А
=
∨
⋅
=
∨
⋅
=
⋅
∨
=
⋅
∨
Операция удаления или добавления лишних членов (т.е. таких членов, которые принимают значение, равное 1, одновременно с ос- тавшимися членами выражения (ПФ) основана на тождестве:

53
.
А
А
...
А
А
=
∨
∨
∨
Если в СДНФ некоторой ПФ произвести всевозможные опера- ции склеивания и операции поглощения, получается сокращенная
ДНФ. В отличие от СДНФ в нее, в общем случае, входят конъюнкции разного ранга: от первого до (п-1) - го ранга.
После отбрасывания лишних членов из сокращенной ДНФ по- лучается ДНФ, называемая тупиковой. Ее особенностью является то, что она уже не допускает применения операций склеивание и погло- щения.
Тупиковых ДНФ может быть несколько, так как при выполне- нии операций склеивания и поглощения СДНФ могут объединяться по-разному. Та из тупиковых ДНФ, которая имеет наименьшее число вхождений (наименьшее количество логических переменных и опе- раций), называется минимальной ДНФ (МДНФ).
Приведем примеры, иллюстрирующие применение тождествен- ных соотношений с целью минимизации ПФ.
Требуется минимизировать ПФ вида
2 1
0 2
1 0
2 1
0 2
1 0
2 1
0
( , ,
)
у
f x x x
x
x x
x
x x
x
x x
x
x x
=
= ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅
Производя склеивание первого и третьего членов по x
2
, а также второго и четвертого членов тоже по x
2
, получим
.
x
x
x
x
)
x
x
(
x
x
)
x
x
(
x
x
у
0 1
0 1
2 2
0 1
2 2
0 1
⋅
∨
⋅
=
∨
⋅
∨
∨
⋅
=
К найденному выражению также можно применить операцию склеивания, но уже по x
1
:
.
x
)
x
x
(
x
y
0 1
1 0
=
∨
=
Пример. Требуется упростить ПФ вида
.
x
x
x
x
x
x
x
x
x
x
x
x
)
x
,
x
,
x
(
f
у
0 2
1 2
0 1
0 2
1 2
0 1
0 1
2 2
⋅
∨
⋅
∨
⋅
∨
⋅
∨
⋅
∨
⋅
=
=
В данной ПФнет членов, которые могли бы быть подвергнуты операциям склеивания и поглощения. Поэтому остается проверить, не являются ли лишними некоторые члены. Рассмотрим, например, член
0 2
x
x
⋅
. Он принимает значение, равное 1, только тогда, когда
0
x
= 1 и
2
x
= 0. Найдем значение остальной части функции при таких значени- ях переменных
2
x
и
0
x
:
.
x
x
x
x
x
x
1 0
1 1
0 0
1 1
1 1
1 1
1
=
∨
=
⋅
∨
⋅
∨
⋅
∨
⋅
∨
⋅
Из этого следует, что член
0 2
x
x
⋅
является лишним, так как, отбросив его, мы не изменим значения функции. Аналогичным путем можно показать, что члены
1 2
x
x
⋅
и
1 0
x x
⋅
также являются лишними.
Следовательно, ПФ можно записать в виде
.
x
x
x
x
x
x
)
x
,
x
,
x
(
f
у
0 2
1 2
0 1
0 1
2 2
⋅
∨
⋅
∨
⋅
=
=

54 1.5.3
Минимизация переключательных функций посредством диаграммы Вейча
Диаграмма Вейча (ДВ) для ПФ п переменных x
n-1
,..., х
0 пред- ставляет собой прямоугольник, разделенный на клетки, число кото- рых равно числу
n
x
L
2
=
всевозможных наборов переменных. При п =
2, 3, 4 разбиение осуществляется так, что для каждой переменной по- ловина площади большого прямоугольника соответствует
i
x
а вторая половина
i
x
−
. Способ разбиения показан на рисунке 1.4 ( п = 2 и 3) и на рисунке 1.5 ( п = 4 ). а)
Рисунок 1.4 б)
В случае п = 5 ДВ образуется путем состыковывания двух диа- грамм, соответствующих п = 4, причем одна из них ставится в соот- ветствие переменной х
4
, а другая
4
х
−
. Аналогично строится ДВдля
п
≥
6. Однако при п > 5 диаграмма Вейча становится громоздкой и не- удобной для пользования.
Каждая клетка ДВ соответствует некоторому набору перемен- ных с номером
α
. Рассмотрим, например, клетку, которая лежит на пересечении областей диаграммы, соответствующих переменным
0 1
2 3
х
,
х
,
х
,
х
Образуем из этих переменных конъюнкцию
0 1
2 3
х
х
х
х
⋅
⋅
⋅
. Она представляет собой конституенту единицы от четырех переменных для набора с номером
α
= 1010
(2)
= 10
(10)
. Поэтому присвоим данной клетке номер
α
= 10. Аналогично нумеруются остальные клетки (см. рисунок 1.5). Переменные
i
x
можно располагать по сторонам ДВ не обязательно в порядке, указанном на рисунке 1.5, но при этом полу- чится другая нумерация клеток.

55 2
х
2
х
12 13 9 8 1
х
3
х
14 15 11 10 1
х
6 7 3 2 3
х
4 5 1 0 1
х
0
х
0
х
0
х
Рисунок 1.5
С помощью
ДВ задаем
ПФ.
Пусть, например,
ПФ
3 2
1 0
( ,
, ,
)
y
f х х х х
=
равна 1на наборах переменных с номерами
α
= 0,
2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14 и равна нулю на всех остальных набо- рах. Аналитическое выражение такой ПФ в СДНФ получается весьма громоздким:
0 2
4 5
6 7
8 10 11 12 13 14
y
K
K
K
K
K
K
K
K
K
K
K
K
=
∨
∨
∨
∨
∨
∨
∨
∨
∨
∨
∨
=
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
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
x x
x
x
x x
x
x
x x
= ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨
∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨
∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅
(1.7)
Ранее было показано, что при склеивании двух соседних консти- туент единицы ранга п образуется конъюнкция ранга п - 1, в которой содержатся только переменные, входящие одинаковым образом в ис- ходные конституенты единицы. Применим это правило к конституен- там К
12
, К
13
и К
4
,
К
5
(рисунок 1.6), в результате получим:
1 2
3 5
4 2
1 2
3 13 12 1
x
x
x
K
K
P
;
x
x
x
K
K
P
⋅
⋅
=
∨
=
⋅
⋅
=
∨
=
Соседние конъюнкции Р
1
и Р
2
склеиваются по переменной х
3
, при этом получается конъюнкция
1 2
2 1
1
x
x
P
P
Z
⋅
=
∨
=

56
Рисунок 1.6
Таким образом, при склеивании четырех соседних конституент единицы ранга п = 4 образуется конъюнкция ранга п - 2 = 4 – 2 = 2, содержащая только переменные, одинаковым образом входящие в выражения четырех соседних конституент единицы, т.е. в К
4
, К
5
, K
12
и K
13
. Данное правило является универсальным. Применим его к группе четырех соседних конституент единицы, включающей К
0
, К
2
,
K
8
и K
10
, и к группе четырех соседних конституент единицы, вклю- чающей К
4
, К
6
, К
12
, K
14
Производя склеивание в той или другой группе, получим
0 2
3 0
2 2
x
x
Z
;
x
x
Z
⋅
=
⋅
=
Конъюнкции Z
2
и Z
3
также являются соседними, так как они разли- чаются одной переменной. Поэтому они склеиваются и дают конъ- юнкцию W =
0
х
. Таким образом, при склеивании восьми соседних конституент единицы ранга п = 4 образуется конъюнкция ранга п - 3 =
4 - 3 = 1, содержащая только те переменные, которые одинаковым об- разом входят во все восемь соседних конституент единицы.
Обобщая полученные результаты, можно сформулировать про- цедуру минимизации ПФ посредством диаграммы Вейча.
Определяются всевозможные группы соседних конъюнкций, ох- ватываемые прямоугольными контурами и содержащие по 1,2,4,8,16 и т.д. конституент единицы (см. рисунок 1.6), при этом одна и та же конституента может входить в несколько разных групп. При п
≤
4 соседними следует считать не только конституенты, находящиеся в