Составители:
Рубрика:
24
Таблица истинности этой функции будет
иметь следующий вид.
Одно из возможных решений
F = a b ∨ g ∨ bc ∨ eh.
Представляет интерес определение коли-
чества наборов длины n, не связанных сдви-
гом, и их доли в общем числе двоичных на-
боров длины n.
Расчет произведем для наборов длины n
веса q (т. е. содержащих ровно q единиц).
Для этого заметим, что если в младшем раз-
ряде поставить 1, а остальные q – 1 единиц
на оставшихся n – 1 позициях расставить так,
чтобы получить разные двоичные коды, то
мы получим все наборы, не связанные сдви-
гом, содержащие ровно q единиц. Тогда чис-
ло таких наборов
1
1
(, ) ( , 1)
q
n
Sn q Pn q q C
−
−
=−−=
.
Поскольку общее число наборов длины n веса q равно
q
n
C
, то
доля наборов, не связанных сдвигом, составляет q/n. Так, например,
при n = 20, q = 10 S(20, 10) = 92378.
2.3. Минимизация слабо определенных булевых функций
Возьмем теперь произвольный вектор A (1 0 0 1 1 1 0 1 0 0 0 1) и
некоторую функцию F = a
i
& a
i – 3
∨ a
i + 2
⊕ a
i + 5
. Применив преобразо-
вание F к вектору A, получим вектор B (1 1 0 1 0 1 1 1 0 1 0 0). Для того
чтобы найти функцию, которая по вектору B восстанавливала бы век-
тор A, можно построить таблицу истинности частично определенной
функции 23 аргументов (табл. 6.).
Если из данной матрицы выделить минимальный набор столбцов так,
чтобы в матрице, построенной только из этих столбцов, строки, на кото-
рых элементы вектора A принимают значение 1, отличались бы от строк,
на которых элементы вектора A принимают значение 0, то выделенные
столбцы будут составлять минимальный набор аргументов функции F.
Обратная к F функция, которая восстанавливает вектор A по векто-
ру B, определена всего на 12 наборах аргументов, а на N = 2
23
– 12
Пример 4
abcdeghF
11010
1101 1
1101 1
1101 0
01101
0110 0
0110 0
0110 1
10011
1001 1
1001 0
100 1 1
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
