3
Автоматизация задачи определения сложности булевой функции
Так получают вектор
p
= (
p
1
,
p
2
, …,
p
i
, …,
p
n
) повторяемости пере-
менных
1
, ..., , ...,
j
n
X x x x
из множества в формуле
F
(
n
)
, т. е. пере-
менная ,
1,
j
x j
n
повторяется в формуле
F
(
n
)
p
i
раз.
В ячейку (
m
+ 1,
n
+ 1) записывают
1
m
B
i
i
L r
— число букв в фор-
муле
F
(
n
)
(это вспомогательный параметр).
Для решения задачи применяют функциональное уравнение (ФУ)
1
1
1
2
,
n
n
n
i
F x F F
(1)
где индексы 1 и 2 — номера соответствующих остаточных функций,
рассматриваемых на одном множестве
X
′ =
X
\
x
i
. Запишем их в алго-
ритме соответственно как
F
′ =
F
(
n
–1),1
и
F
′′ =
F
(
n
–1),2
.
При записи алгоритма будем использовать дополнительные пара-
метры:
t
1
= 1, 2, … — начало и продолжение записи функций
F
′ и
F
′′,
а также номер последней функции, записанной в табл. 1;
t
2
= 1, 2, …—
начало и продолжение чтения табл. 1, а также номер последней прочи-
танной функции;
j
max — номер-индекс переменной
x
j
max
с
p
j
max
.
Таблица 1
n
′ или
n
′′
m
′ или
m
′′
F
′ или
F
′′
L
F
n
′ =
n
– 1
m
′ =
p
j
max
F
′
L
F
=
L
F
+ 1
n
′′ =
n
′
m
′′ =
m
=
m
′
F
′′
L
F
=
L
F
+ 1
...
…
…
…
2. Алгоритм.
Построим алгоритм определения значения верхней
оценки показателя сложности. Для некоторых классов функций такая
оценка является минимальной.
Дано:
n
,
m
,
F
(
n
)
— правильность формулы, при вводе проверяется.
Шаг 1. Подготовка начальных данных.
Для исходной формулы
F
(
n
)
нужно заполнить матрицу
K
i
,
j
, получая
векторы
r
и
p
, т. е. правый столбец
1, ,
1 ,
i
m n
и нижнюю строку
1,
1, .
m j
n
Теперь выполним инициализацию:
L
F
= 0,
t
1
= 0,
t
2
= 0.
Шаг 2. Если
m
= 1, то увеличиваем значение
L
F
:
L
F
=
L
F
+
r
1
– 1. За-
тем переходим к шагу 6.
Шаг 3. Если
r
1
= 1, то увеличиваем значение
L
F
:
L
F
=
L
F
+
m
– 1. За-
тем переходим к шагу 6.
Шаг 4. Найдем
max
1 2
max , , ..., , ...,
,
j
j
n
p
p p p p
где
1, ,
j
n
и соот-
ветствующее
x
j
max
, равное
j
max
. Отметим, что в общем случае
p
j
max
≠
j
max
.
