Составители:
Рубрика:
20
2. БУЛЕВЫ ПРЕОБРАЗОВАНИЯ
ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
2.1. Постановка задачи
Пусть имеются две двоичные последовательности A(a
1
, a
2
, …, a
n
) и
B(b
1
, b
2
, …, b
n
). При этом a
i
, b
i
∈ {0, 1}, i = 1, 2, 3, …, n. Элементы
последовательности B будем получать булевым преобразованием пос-
ледовательности A, при этом b
i
будет результатом булевого преобразо-
вания, зависящего от a
i
и некоторых элементов из окружения a
i
. Мак-
симальное число аргументов булевой преобразующей функции F равно
N = 2n – 1. Так, для n = 3 N = 5; для n = 4 N = 7; для n = 5 N = 9.
Рассмотрим методы нахождения функций F.
2.2. Теорема о преобразованиях
двоичных последовательностей
Сформулируем теорему, на основании которой можно строить буле-
вы функции, преобразующиe одну последовательность в другую. Эта
теорема являeтся аналогом теоремы, доказанной в литературе
1
.
Теорема. Для того чтобы существовала булева функция F, преобра-
зующая произвольную последовательность А в произвольную последо-
вательность В, необходимо и достаточно, чтобы А была ненулевой пос-
ледовательностью. Число аргументов F не превышает 2n – 1.
Необходимость следует из того, что при нулевой последовательнос-
ти А все элементы последовательности В будут либо нулями, либо еди-
ницами, и в этом случае В не может быть произвольной последователь-
ностью.
Для доказательства достаточности построим часть таблицы истин-
ности функции F, в которой функция определена:
1
Åðîø È. Ë., Èãíàòüåâ Ì. Á., Ìîñêàëåâ Ý. Ñ. Àäàïòèâíûå ñèñòåìû óïðàâëå-
íèÿ ïðîìûøëåííûìè ðîáîòàìè: Ó÷åá. ïîñîáèå äëÿ âòóçîâ / ËÈÀÏ. Ë., 1985. 144 ñ.
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
