Построение простых нормальных форм характеристических функций классов в задачах распознавания с целочисленной и бинарной информацией

• Автор: Дьяконов, Александр Геннадьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 123 с. : ил

ОГЛАВЛЕНИЕ
Введение

Глава 1. Основные определения и обозначения. Обзор предыдущих работ

1.1. Некоторые обозначения

1.2. Обзор методов синтеза ДНФ по перечню нулей

1.3. Обзор: нормальные формы £-значной логики

1.4. Задача распознавания образов

1.5. Задача распознавания с целочисленной (бинарной) информацией. Логические алгоритмы распознавания

* 1.6. Эффективная реализация логических алгоритмов распознавания_

1.7. Основные результаты диссертации
Глава 2. Тестовый подход к задаче ДНФ-реализацин
2.1. ДНФ , построенная по матрице нулей
2.2. Оценка сложности ДНФ
2.3. Построение тупиковой ДНФ [О*]^
т 2.4. Построение ДНФ булевой функции по перечню её нулей с помощью
тестового подхода
2.5. Построение ДНФ характеристических функций классов. Равномерные ДНФ
2.6. Построение явных ДНФ-формул с помощью тестового подхода
2.7. ДНФ-реализация по матрице нулевых интервалов

Глава 3. Построение ДНФ последовательным умножением
3.1. Умножение ДНФ
3.2. Некоторые свойства тестовых ДНФ
3.3. Умножение на скобку совершенной КНФ
3.4. Реализация метода Нельсона на ЭВМ
3.5. Построение ДНФ по формуле С.В. Яблонского
Глава 4. ДНФ-реализация функций А-значной логики. Кодировки
4.1. Тестовый подход для ДНФ-реализации квазибулевских функций
4.2. Определение кодировки. Соответствие конъюнкций ___ „
4.3. Возможность построения произвольной ДНФ с помощью кодировки. Построение сокращённых Н-ДНФ и Т-ДНФ
4.4. Построение А-ДНФ и квазисокращённой А-ДНФ с помощью кодировки
Глава 5. Тестирование алгоритмов распознавания
Список литературы
Приложение

- 4 - »
ВВЕДЕНИЕ
Проблема построения кратчайших, минимальных или достаточно простых ДНФ для булевых функций и функций £-значной логики была одной из основных в исследованиях по дискретному анализу и математической кибернетики, проводимых в СССР в 50х - 70х годах прошлого столетия.
С.В. Яблонским, Ю.И. Журавлёвым, A.A. Сапоженко, Ю.Л. Васильевым, В.В. Глаголевым, У.А. Абдугалиевым, А.Н. Нурлыбаевым и др. были получены фундаментальные результаты, показывающие, что задачи минимизации, как правило, являются весьма трудоёмкими и реально неразрешимыми даже при относительно небольшом числе переменных. Так как прикладное применение ДНФ ограничивалось, в основном, решением систем булевых уравнений, для чего были получены при других подходах более эффективные методы, интерес к задачам минимизации в дальнейшем существенно уменьшился, что отразилось и на числе публикаций.
В последние десятилетия снова появилось значительное число публикаций, имеющих отношение к исследованию задач эффективного представления булевых функций и функций £-значной логики в классе ДНФ и их обобщений. Это вызвано, в первую очередь, использованием ДНФ для синтеза логических распознающих процедур при решении задач распознавания образов. Как известно, большинство применений теории распознавания связано с плохо формализованными областями науки и практики. Для этих областей не удаётся построить адекватную математическую модель, поэтому строится алгоритм, аппроксимирующий нужную зависимость по прецедентам, т.е. примерам корректной работы алгоритма: входные данные (описания объектов распознавания) и результаты работы алгоритма (классы этих объектов). Для построения таких алгоритмов потребовалась разработка специального математического аппарата, поскольку прецедентов, как правило, не очень много и, например, традиционные статистические методы не всегда давали
полученное множество конъюнкций до множества ГУ, обладающего свойством 07 с N(17) и М(1У{К})г&-' *07 для всех К е ГУ. Очевидно, что множество ГУ можно было построить алгоритмом А*в как ТУ и | ГУ |< т + #.
Пусть выполняются предположения второй части леммы и ТУ = ТУ (1) и ТУ (0), где буква ху входит в конъюнкции из ТУ (1), а буква х^ - в
конъюнкции из ТУ(0). Положим /я =|ТУ(1)|, 9=|ТУ(0)|. Каждая конъюнкция

из ТУ(1) имеет вид АГ = х&&х ?, где г'е{1,2,.Поставим

ей в соответствие выражение А(К)=&ая. Тогда очевидно, что

а. = V ДАТ). Аналогично, поставив в соответствие каждой конъюнкции
1 Хе£>у(1)
К = х- & & х*9 из ТДО) выражение ДАГ)=&ар, получаем
1 4 ц^О.
-Iа. = V ДАТ). Из выражений для а. и -па, выписываются значения
7 АГеГДО) 7
чисел (2.5) и множества (2.4). При этом выполняются все требования леммы. Лемма доказана.
Из описания алгоритма А*в видно, что |ТУ |<£ для всех у е{/ + 1,.а, следовательно, | Т)* |<| От +{п - *)& • Как следует из леммы 2.3, эта оценка,
вообще говоря, завышена. Например, если а, = g(aj ,а. ), у.,у, еГ(у), то
./ У| У
можно легко построить множество ТУ: | ТУ |< 4, а если а° = ар V... V ар для каких-то сг,<т,,...,стА б{0,1), ур...,уй еГ(у), то легко строится множество /У: |Т>7 |<£ + 1. Далее получен критерий наиболее эффективного (в смысле длины синтезируемой ДНФ) применения алгоритма