Составители:
Рубрика:
22
При длинах векторов A и B, равных n, булева функция будет зада-
ваться на n наборах, а на 2
(2n-1)
– n наборах функция будет не определе-
на. Доопределение и минимизация булевой функции не однозначны.
Определение. Два набора A
i
и A
j
длины n будем называть связан-
ными сдвигом, если при некотором сдвиге одного набора относительно
другого у этих наборов совпадают позиции всех единиц. Например, A =
1 0 0 1 0 1 1 0 0 0 и B = 0 0 1 0 0 1 0 1 1 0 – наборы, связанные сдвигом.
Из приведенной выше теоремы сформулируем следствия.
Следствие 1. Если A
i
, i = 1, 2, 3, …, k – двоичные векторы, не свя-
занные сдвигом, и В – произвольный вектор, то существует одна булева
функция F, преобразующая любой вектор A
i
в вектор В, т. е. B = F(A
i
),
i = 1, 2, 3, …, k.
П р и м е р 1. Пусть A
1
= 1011; A
2
= 1001; A
3
= 0110; B = 0111.
Построим часть таблицы истинности функ-
ции F, выписывая только те наборы, на кото-
рых функция определена, при этом для удоб-
ства введем очевидные переобозначения
аргументов.
Упражнение. Постройте диаграмму Вей-
ча функции F и убедитесь в том, что при не-
котором способе доопределения функция
будет иметь вид
F = a ∨ c ∨ e
g
.
Проверьте, что эта функция из любой при-
веденной последовательности A
i
(i = 1, 2, 3)
строит одну и ту же последовательность В.
Следствие 2. Если A
i
и B
i
– произволь-
ные векторы, причем A
i
не связаны сдвигом,
то существует одна булева функция F, пре-
образующая каждый вектор A
i
в соответ-
ствующий ему вектор B
i
.
П р и м е р 2. Пусть требуется найти одну функцию F, преобразую-
щую векторы:
A
1
= 1011 в вектор B
1
= 0110,
A
2
= 0111 в вектор B
2
= 1001,
A
3
= 0101 в вектор B
3
= 1110.
abcdeghF
10 110
10 11 1
10 11 1
10 11 1
100 10
100 1 1
100 1 1
100 1 1
01100
0110 1
0110 1
0110 1
Пример 1
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
