2
А.А. Гурченков, Е.К. Егорова
необходимость в информационных и вычислительных ресурсах для
образования, науки и техники сохраняется. Следовательно, теория
алгоритмов и их минимизация, а также методы декомпозиции, клас-
сификации, структуризации и другие, позволяющие сводить решение
трудно формализуемых задач к решению системы взаимосвязанных
упрощенных задач, будут востребованы. При этом повышаются тре-
бования к разработке программного обеспечения, включая и такое, ко-
торое способствует облегчению общения пользователя с компьютером
[2, 5–7].
Актуально решение задачи оптимальности синтеза дискретных
управляющих систем на основе модели формул. Алгоритм логиче-
ского управления для синтеза задается системой булевых функций.
В качестве базиса применяют булевы формулы из определенных
классов.
1. Используемые понятия.
Пусть
1 2
, , ..., , ...,
j
n
X x x x x
— мно-
жество булевых переменных. Произвольная булева функция
f
(
n
)
(
X
) за-
дается полиномом Жегалкина
1
2
...
...
n
i
m
F K K K K
в базисе
3
&, , 0, 1 ,
G
где
n
— число переменных;
m
— длина по-
линома Жегалкина;
K
i
— монотонная элементарная конъюнкция (ЭК)
ранга ,
1, ;
i
r i
m
r
= (
r
1
,
r
2
, …,
r
m
) — вектор рангов полинома Жегал-
кина;
K
i
′ — монотонная ЭК ранга ,
1, ;
i
r i
m
r
′ — строение полинома
Жегалкина
F
′ уже упорядоченного вектора.
Полином Жегалкина
F
(
n
)
задают с помощью матрицы
K
i
,
j
размером
[
m
×
n
], представляемой в виде таблицы с числом строк (
m
+ 1) и числом
столбцов (
n
+ 1). Матрицу и таблицу определяют следующим образом:
в ячейку
K
i
,
j
пишут 1, если
,
j
i
x K
иначе
,
0 1,
,
1, ,
i j
K i
m j
n
где под
i
K
понимают множество переменных, образующих ЭК
K
i
.
В столбец
1,
,
1
i
m n
записывают ранг элементарной конъ-
юнкции
K
i
, вычисляемый следующим образом:
, 1
,
1
.
n
i
i n
i j
j
r r
K
В строку
1,
1,
n j
n
пишут
p
j
— число повторений переменной
,
1, ,
j
x j
n
в формуле
F
(
n
)
:
1,
,
1
.
m
j
m j
i j
i
p p
K
