 |
Алгоритм на основе логического перманента.
|
|
|
|
Пусть 
— логические функции от 
переменных и 
, где 
.
Определение. Логическим перманентом матрицы называется следующая Д.Н.Ф.:
где 
и 
— симметрическая группа порядка 
.
Таким образом, Д.Н.Ф. 
содержит 
конъюнкций. Как обычно, 
— это множество единиц логической функции .
Пример. Пусть 
, 
, 
, 
. Тогда
и
Далее
Пусть, как и ранее, 
— класс эквивалентности, построенный по характеристическому множеству 
и содержащий слово 
.
Конструкция описывается следующими шагами.
1) При заданном 
и находим слова
2) Строим конъюнкции
При этом, если 
, то соответствующая конъюнкция — это тождественный нуль.
3) Строим матрицу 
.
4) 
Обоснование пункта 
довольно просто и состоит в следующем. Любое слово 
обладает следующим характеристическим свойством. Всё мультимножество фраментов 
совпадает с мультимножеством 
. Другими словами, для некоторой перестановки справедливы соотношения
Решению системы соответствует решение уравнения
(9.4)
что соответствует элементу логического перманента матрицы 
.
Пример. Пусть 
, 
, 
.
Применим к этому случаю алгоритм построения класса эквивалентности .
1) 
, 
.
2) 
, 
, 
, 
.
3) 
,
и 
В общем виде матрица имеет следующие параметры. Если 
, то порядок равен ; при 
ранг конъюнкции 
равен 
. Далее: 
-я строка матрицы имеет вид: 
, а -ый столбец
Пример. Если 
, 
и 
,
то 
, 
, 
. Отсюда следует
Разлагая по первой строке, получаем выражение:
и, таким образом, 
.
В общем виде Д.Н.Ф. имеет 
конъюнкций, максимальный ранг которых не превосходит 
с учётом кратности вхождения букв и не превосходит 
при классическом определении. Следует отметить также, что мы имеем дело не с «элементарными» конъюнкциями, а с некоторым их обобщением, представляющим специальный класс булевых функций, включающий в себя элементарные конъюнкции.
|
|
|
Следствие. 
, где под нормой 
, понимается число единиц логической функции .
Следующий частный случай служит хорошей иллюстрацией для всех приведённых выше абстрактных построений.
Пусть 
— характеристическое множество, которое соответствует всем парам букв 
неизвестного слова 
. Если 
, то класс эквивалентности выглядит следующим образом — это логический перманент матрицы :
В частности, для , 
матрица имеет вид
и
Конъюнкция 
соответствует главной диагонали матрицы , а конъюнкция 
— второй главной диагонали этой матрицы. Ясно, что 
.
9.3 Пример на основе 
-го слоя 
.
Одним из самых простых и естественных характеристических множеств является -ый слой 
или множество 
В содержательном смысле условие 
означает, что информацией о неизвестном слове 
являются все его фрагменты длины .
1) Пусть 
.
В этом случае
и каждый класс эквивалентности представляет собой слой куба . Таким образом, имеется ровно 
класс эквивалентности.
2) 
.
В этом случае 
и критерий эквивалентности двух слов и 
состоит в выполнении двух условий:
Условия (9.5) означают, что эквивалентные слова имеют одинаковый вес Хэмминга и одинаковую сумму номеров единичных координат. Для нахождения числа классов эквивалентности используем следующее утверждение.
Теперь заметим, что
Предложение. Число классов эквивалентности для характеристического множества равно 
.
С учётом предыдущих замечаний доказательство этого предложения состоит в нахождении разности 
. Доказательство этого утверждения выносится в качестве упражнения. Это задача из задания.
Пример. Для разбиение на кассы эквивалентности имеет следующий вид:
Общее число классов эквивалентности равно 15.
Пример. Для 
:
Общее число классов эквивалентности 26. Классы эквивалентности следующие: 
. 
, 
, 
, 
, 
. 
, 
, 
, 
, 
, 
, 
. 
, 
, 
, 
, 
, 
, 
. 
, 
, 
, 
, 
. 
.
|
|
|
Для 
биномиальные коэффициенты 
вычисляются следующим образом.
По определению
Так как
то приведённых выше формул достаточно для нахождения всех остальных биномиальных коэффициентов: 
, 
, 
.
Далее
Подробные рутинные выкладки приводят к следующим полиномам, устанавливающим эквивалентность слов по характеристическому множеству 
.
Пусть
Если перейти в другую систему координат 
, где 
— это номер 
-й единичной координаты в слове 
, то приведённые выше функции перейдут в следующие:
Предложение. Справедливо соотношение
Таким образом, полиномы 
, 
, 
, 
представляют собой полную систему инвариантов любого класса эквивалентности по характеристическому множеству . Если при этом учесть число значений, которое принимает каждая из функций 
, а это, по порядку величины не превосходящие 
, 
, 
, , то можно получить оценку сверху для числа классов эквивалентности: 
.
В общем виде система инвариантов строится следующим образом.
В соответствии со значениями биномиальных коэффициентов
выписываются следующие полиномы:
и так далее вплоть до
Всего полиномов вида (9.7) существует ровно 
штук.
Упражнения.
1. Найти Va, если n=4, a=0101, V= {v1=(123), v2=(234)}.
2. Найти Va, если n=4, a=1101, V= {v1=(124), v2=(134)}.
3*. Доказать, что число классов эквивалентности для характеристического множества равно .
|
|
|
