А.А. Гурченков, Е.К. Егорова
6
5
1
2
3
4
5
.
F
x x
x x
x
Пример 3.
Пусть
2
1
1 2
.
F x x x
(3)
Если вынести переменную с максимальным рангом за скобки,
получим
2
1
2
1 .
F x
x
(4)
Формулы (3) и (4) содержат одно и то же число операций. Следо-
вательно, формулу (3) можно оставить в исходном виде, но при этом
учесть число подформул.
Рассмотрим еще два случая, когда при разложении отсутствует
одна из подформул.
Пример 4.
Пусть
1 , 2
max
.
n
n
j
F x
F
Очевидно, что переменная
max
j
x
имеет число повторений
max
1,
j
p
иначе существовала бы подформула
1 ,1
n
F
. Но в таком
случае и остальные переменные повторяются всего один раз.
Можно привести аналогичный пример:
4
1
2 3 4
.
F x x x x
(5)
Для того чтобы избежать подобной ситуации, в алгоритме выполня-
ется первоначальное упорядочивание по числу переменных в конъюнк-
циях. Таким образом, пример (5) приобретет следующий вид:
4
2 3 4
1
,
F x x x x
где максимальный ранг будет иметь переменная
2
x
. Следовательно,
единственный возможный вид формулы в таком случае
4
1
2
3
4
.
F x x x x
Данный вид формулы разбирается в примере 2.
Пример 5.
Рассмотрим последний случай, когда
1 ,1
max
.
n
n
j
F x F
