1.2.6. Недоопределенные бф и способы их задания. Простые импликанты недоопределенных бф.
На практике часто встречаются недоопределенные БФ.
Xn-1 |
Xn-2 |
… |
X1 |
X0 |
F~ |
|
0 |
0 |
… |
0 |
0 |
0 |
<1,0,~> |
0 |
0 |
… |
0 |
1 |
0 |
|
… |
… |
… |
… |
… |
… |
|
1 |
1 |
… |
1 |
0 |
1 |
|
1 |
1 |
… |
1 |
1 |
1 |
Недоопределенные БФ описываются тремя множствами: М1; М0; М~. Недоопределенная БФ строго определена на наборах М1; М0. Наборы входячие, в множество М~ не определены и могут не использоваться при реализации БФ. Использование наборов из множества М~ осуществляется по необходимости для минимизации исходной БФ. Наборы из этого множества могут доопределяться либо до «0» либо до «1». При выполнении процедуры доопределения необязательно доопределять все наборы.
F~ = F, если, M1(F~) M1(F), M0(F~) M0(F)
Рассмотрим пример.
X |
Y |
F~ |
F1 |
F2 |
F~ = F1 F~ = F2
|
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
~ |
0 |
1 |
|
1 |
0 |
~ |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
Д ля задания определенных БФ достаточно описать M1 (либо M0).
Для задания недоопределенных БФ нужно описать (M1 и M0), либо (M1 и M~), либо (M~ и M0).
На практике очень часто задается M1 и M0, так как обычно |М1|+|М0|<<2n.
Множество M1, как и M0, как и M~ можно описать, задав ДНФ равную 1 на наборах из этого множества. Такие ДНФ будем обозначать D1, D0, D~ , соответственно.
Рассмотрим пример.
D0(X,Y,Z) = XY XZ. Следовательно, М0 = (110,111,101).
Недоопределенные бф часто задают через D1 и D0.
Рассмотрим пример.
D1
=
D0
=
X |
Y |
Z |
F~ |
Вместо конъюнкций удобно использовать коды конъюнкций. При этом получаем D1 = 00- -00 D0 = 11- 1-1 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
~ |
|
0 |
1 |
1 |
~ |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Часто БФ задают таблично. В нашем примере это будет
-
X
Y
Z
F
Представление БФ показанное слева более компактно. Оно обобщает задание через M1 и M0.
X
Y
Z
F
0
0
-
1
0
0
0
1
-
0
0
1
0
0
1
1
1
1
-
0
1
0
0
1
1
-
1
0
1
0
1
0
1
1
0
0
1
1
1
0
Недоопределенные БФ можно задавать парой: БФ единичного доопределения F~(1) и БФ нулевого доопределения F~(0) .
F~(1) получается при доопределнии наборов M~ до «1» (перенос наборов в М1).
F~(0) получается при доопределении наборов M~ до «0» (перенос наборов в M0).
Xn-1Xn-2 …..X1X0 |
F~ |
F~(0) |
F~(1) |
|||
M0 |
0 |
0 |
0 |
|||
M~ |
~ |
1 |
||||
M1 |
1 |
1 |
||||
|
Исходная БФ |
БФ, доопределенная до «0» |
БФ, доопределенная до «1» |
|||
Для недоопределеных БФ простая импликанта определяется так:
К - простая импликанта F~ , если:
К - простая импликанта F~(1) и,
если в M1(К) есть хотя бы один набор из M1(F~ ).