5
Автоматизация задачи определения сложности булевой функции
Таблица 2
x
1
x
2
x
3
x
4
x
5
p
K
1
1
1
1
0
0
3
K
2
1
0
0
1
0
2
K
3
0
0
0
0
1
1
r
2
1
1
1
1
6
Запишем получившуюся матрицу в табл. 1 и поставим начальные
условия:
t
1
= 1 и
t
2
= 1.
Для начального прохода установим счетчик
L
F
= 0.
Найдем переменную с максимальным рангом. Очевидно, что
в табл. 2 максимальный ранг имеет переменная
x
1
.
Разложение функции
F
(3)
будет выглядеть следующим образом:
5
1 2 3
4
5
.
F x x x x x
Итак, возникают две остаточные функции:
1
2 3
4 2
5
.
F x x x F x
Следовательно, необходимо увеличить счетчик подфункций
L
F
=
L
F
+ 2, а также счетчик записи
t
1
:
t
1
=
t
1
+ 2.
Из матрицы выбираем те строки, в которых элемент
x
1
= 1, и копи-
руем их в табл. 3, исключая столбец с элементом
x
1
. Аналогично вы-
бираем сроки с элементом
x
1
= 0 и копируем их в табл. 4. Таблицы 3 и 4
соответствуют функциям
F
1
и
F
2
.
Таблица 3
x
2
x
3
x
4
x
5
p
K
1
1
1
0
0
2
K
2
0
0
1
0
1
r
1
1
1
0
3
Таблица 4
x
2
x
3
x
4
x
5
p
K
3
0
0
0
1
1
r
0
0
0
1
1
В полученных табл. 3 и 4 исключим элементы с рангом
r
i
= 0 и по-
лучим новые таблицы (табл. 5, 6).
