Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Алгоритм на основе логического перманента.

Пусть — логические функции от  переменных и , где .

Определение. Логическим перманентом матрицы  называется следующая Д.Н.Ф.:

где  и — симметрическая группа порядка .

Таким образом, Д.Н.Ф.  содержит  конъюнкций. Как обычно,  — это множество единиц логической функции .

Пример. Пусть , , , . Тогда

и

Далее

Пусть, как и ранее,  — класс эквивалентности, построенный по характеристическому множеству  и содержащий слово .

Конструкция  описывается следующими шагами.

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*. Доказать, что число классов эквивалентности для характеристического множества  равно .

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...