О трудностях решения специальных систем булевых уравнений

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

ГЛАВА I. СИСТЕМЫ ТЕСТОВЫХ УРАВНЕНИЙ

§ 1.1. Основные обозначения и определения

§ 1.2. Труднорешаемо сть систем тестовых

уравнений

§ 1.3. Сложность произведения левых частей

тестовых уравнений

§ 1.4. Полиномиальный алгоритм для решения

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

двух уравнений

§ 1.5. Труднорешаемость задачи декомпозиции систем тестовых уравнений на блоки минимальной сложности, состоящие из

трех уравнений

ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ СИСТЕМЫ БУЛЕВЫХ УРАВНЕНИЙ
§ 2.1. Конечнозначные системы уравнений. Труд-норешаемость задачи о декомпозиции двухзначных систем на оптимальные
блоки из трех уравнений
§ 2.2. Примеры двухзначных систем уравнений, на которых задача декомпозиции на оптимальные 3 -блоки является трудноре-шаедай
- 3 -

§ 2.3. Общий случай конечнозначных систем
ГЛАВА 3. ИССЛЕДОВАНИЕ СИСТЕМ ИЗ СИММЕТРИЧЕСКИХ И МОНОТОННЫХ ФУНКЦИЙ. СИСТЕМЫ НЕЛЬСОНОВСКИХ УРАВНЕНИЙ
§ 3.1. Системы из монотонных функций
§ 3.2. Системы из симметрических функций
§ 3.3. О сложности произведения левых частей
нельсоновских уравнений
§ 3.4. Исследование задачи о декомпозиции нельсоновских систем на оптимальные
3 -блоки
ЛИТЕРАТУРА

В диссертации исследуются сложности алгоритмов решения систем булевых уравнений вида
^ С'Э'Ч,ос.*') = 1 , 1-1^
Универсальным методом решения таких систем является приведение левых частей к дизъюнктивным нормальным формам (д.н.ф.) ? = ,2^ и сведение системы к одному уравнению

(1 я1-1* 1 1*1
Левая часть построенного уравнения снова приводится к д.н.ф., после чего нахождение множества всех решений не представляет труда.
Наиболее сложным в данном процессе является этап перехода от формулы „П к д.н.ф. Даже при простейших системах булевых
и* 1.
уравнений этот этап требует большой памяти и выполнения большого числа операций на ЭВМ, Это делает практически невозможным решение даже при т = 50-40* Существующие эффективные алгоритмы решения нелинейных булевых систем узко специализированы и существенно используют свойства функций £ Сзса.*... ,ос„У Попытки построения более общих алгоритмов связаны, в основном, с разбиением системы на блоки таким образом, чтобы умножение левых частей уравнений, входящих в один блок, приводило бы к д.н.ф. минимальной или достаточно близкой к минимальной. Это позволяет, в некоторой степени, гуменьшать требуемую память и трудоемкость алгоритма, но тогда трудной оказывается сама задача разбиения на блоки. Для решения этой проблемы в работе ставятся и изучаются следующие задачи.
Пусть задана функция алгебры логики ?(.-эсос. Д.н.ф., реализующая эту функцию, называется кратчайшей (минимальной),

Теорема 2.1.2, Задача (РАЗБИЕНИЕ НА КРАТЧАЙШЕ 3-БЛОКИ> А?-полна для систем из Пк(Ь4і).
Доказательство этой теоремы полностью совпадает с доказательством предыдущей. Система уравнений, построенная в доказательстве теоремы 2.1 Л, является также (ъ,2) -значной и по кратчайшей д.н.ф. Очевидно, что для функций, входящих в эту систему, имеет место соотношение
СЖШЬ
а»-= 1-, Сі.і.кЧвХУі
Йа. “ л 4 ХУї. .
§ 2.2. Примеры (*,д) -значных систем уравнений, на которых задача декомпозиции на оптимальные 2 -блоки является труднорешаемой
В данном параграфе будет продолжаться исследование задачи декомпозиций на оптимальные блоки для систем вида

х*4) ^ 1, иі^ (2.2.1)
Все нижеописанные системы уравнений принадлежат классу Гм Д.2.) (ПкСз.аЛ^ . Но они представляют и самостоятельный интерес, так как будут ставиться естественные ограничения на функции ^ , составляющие данную систему уравнений.
Определение 2.2.1. Два множества і и 6 вершин п -мерного единичного куба назовем изолированными друг от друга, если выполнены следующие два условия:
а)(ие>4*
N. П л- г*— г—
б) Для любых о(£ Н и В, вершины ОІ и ^ не являются соседними.
Определение 2.2.2. Поясом ширины к + 1 п -мерного единич-