Материал: Дискретная математика. учебное пособие. Собенина О.В

Пусть r, - ранг грани N_ki (он равен рангу конъюнкции k ) Число r, определенное формулой

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

Приведем также определения сокращенной и тупиковой ДНФ с геометрической точки зрения.

Грань , содержащаяс в , называется максимальной относительно , если не существует грани , такой, что

1) ;

2) размерность грани больше размерности грани N_{k .}

Конъюнкция К, соответствующая максимальной грани , называется простой импликантой функции f.

ДНФ, являющаяся дизъюнкцией всех простых импликант функции f, называется сокращенной ДНФ.

Покрытие множества , состоящее из максимальных относительно

граней, называется неприводимым, если совокупность граней, получающаяся из исходной путем выбрасывания любой грани, не будет покрытием .

ДНФ, соответствующая неприводимому покрытию множества , называется тупиковой в геометрическом смысле.

Теорема 5.7.1. Понятия тупиковой ДНФ и тупиковой ДНФ в геометрическом смысле эквивалентны.

Алгоритм минимизации функций, зависящих от трех переменных, состоит в следующих четырех шагах:

1. Нанести множество N , на трехмерный куб. Использовать или табличное задание функции, отметив вершины, в которых f( ) = 1, или СДНФ функции и тогда каждому слагаемому СДНФ поставить в соответствие вершину.

2. Если отмеченными окажутся все вершины куба, то данная функция тождественно истинна.

3. . Если отмечены все вершины какой-либо грани, то для построения минимальной формы заменить все четыре вершины одной переменной - названием грани.

4. . Если отменены вершины какого-либо ребра то в минимизированной форме им соответствует конъюнкция - название ребра.

Чтобы получить минимизированную форму, надо выбирать ребра, покрывающие вершины так, чтобы меньшим числом ребер покрыть все отмеченные вершины.

5. Если существует вершина, которая не образует ребро ни с какой другой вершиной, то в минимизированной форме ей соответствует конъюнкция - название вершины.

Пример. Минимизировать булеву функцию f(0,1,1)=f(1,0,0)=f(1,0,1)=0 геометрическим методом.

Так как функция задана перечислением наборов, на которых функция принимает значение 0, то на остальных она принимает эначение 1, т.е.

f(0,0,0)=f(0,0,1)=f(0,1,0)=f(1,1,0)= f(1,1,1)=1.

На рис. 5.2 изображено геометрическое представление данной булевой функции с указанием наборов и соответствующих им элементарных конъюнкций.

; ; ;

_.

_{Из геометрического представления булевой функции следует, что осуществить покрытие вершин можно не единственным образом, поэтому существует для данной булевой функции две различные минимизированные формы} и _.

Замечание. При n=3 геометрический метод минимизации булевых функций аналогичен минимизации с помощью прямоугольной таблицы, называемой минимизирующей картой (картой Карно) [4].

Задачи и упражнения

1. Упростить следующие ПФ, используя равносильные преобразования:

а) ,

б) ,

в) ,

г) ,

д) ,

е) .

2. Составить таблицы истинности следующих ПФ и определить их тип:

а) ,

б) ,

в) ,

г) ,

д) .

3. Доказать равносильность

а) ,

б) ,

в)

4. Определить конъюнктивное разложение по переменной следующих ПФ:

а) ,

б) ,

в) .

5. Определить дизъюнктивное разложение по переменной следующих ПФ:

а) ,

б) ,

в) .

6. Привести к нормальным и совершенным нормальным формам следующие ПФ:

а) ,

б) ,

в) .

7. Запишите символически следующие суждения:

а) «вертолет является средством передвижения по воздуху, имеет двигатель, пилотскую кабину, систему управления, несущий винт, по­мещение для пассажиров или грузов»;

б) «подготовка специалистов высокой квалификации возможна лишь на базе всемерного развития вузовской науки, усиления связи вузов­ской, академической и отраслевой науки, обеспечения единства науч­ной и учебной работы, широкого привлечения студентов к научным ис­следованиям»;

в) «если я поеду автобусом и автобус опоздает, то я опоздаю на работу; если я опоздаю на работу и стану огорчаться, то я не попадусь на глаза моему начальнику; если я не сделаю в срок важную работу, то я начну огорчаться и попадусь на глаза моему начальнику. Следовательно, если я поеду автобусом, а автобус опоздает, то я сделаю в срок важную работу».

8. Минимизировать булевы функции методом Квайна и геометрическим методом

а)

б)

в) г)

6. Разрешимые и неразрешимые проблемы

Общепринятой является точка зрения, согласно которой алгоритм считается эффективным, если он имеет полиномиальную сложность. Дело в том, что несмотря на усилия многих специалистов, для решения таких задач, как задачи отыскания в графе наибольшего независимого множества, гамильтонова цикла, k-раскраски и ряда других, до сих пор не найдено полиномиальных алгоритмов. Более того, имеются веские доводы, позволяющие предположить, что таких алгоритмов не существует. Обсуждению этих доводов и посвящен данный раздел.

Начнем с внесения изменений в вычислительную модель. Будем считать, что каждая ячейка абстрактной вычислительной машины может содержать только 0 или 1, и целые числа рассматриваются в двоичной системе счисления. В соответствии с этим всякое целое число  ≠ 0, 1 займет ]log ||[ ячеек машинной памяти (]x[ – наименьшее целое, не меньшее чем x). Рациональное число, не являющееся целым, будем рассматривать в виде несократимой дроби и представлять в машине как упорядоченную пару целых чисел – числитель и знаменатель этой дроби. Время выполнения каждой элементарной операции примем равным сумме длин записей ее операндов в двоичной системе счисления.

Далее будем рассматривать каждую задачу в так называемом распознавательном варианте, когда решение задачи заключается в получении ответа «да» или «нет». Всякий алгоритм решения такой задачи, будучи примененным к соответствующему входу, работает какое-то время и затем, сообщив ответ «да» или «нет», останавливается. Для некоторых задач их «естественные» постановки уже являются распознавательными. Таковы, например, задачи распознавания изоморфизма, гамильтоновости, планарности, эйлеровости графов. Однако чаще (а на практике – как правило) исходная постановка задачи является оптимизационной. В оптимизационной задаче требуется выбрать из множества допустимых решений X такое решение x, вес (или стоимость) которого w(x) минимален. В рассмотренных вами оптимизационных задачах в качестве X фигурировали множества остовов, путей с заданной начальной вершиной или паросочетаний данного графа. Каждой оптимизационной задаче сопоставим ее распознавательный вариант, который выглядит следующим образом. По данным множеству X, весовой функции w и числу k требуется определить, существует ли элемент xX такой, что w(x)k. Очевидно, что имея полиномиальный алгоритм решения оптимизационной задачи, легко получить полиномиальный алгоритм решения соответствующей ей распознавательной задачи. Можно показать. Что при довольно необременительных предположениях относительно функции w верно и обратное. Мы не будем на этом останавливаться, поскольку для дальнейшего нам достаточно только знать, что оптимизационная задача «не проще» соответствующей распознавательной.

Итак, далее рассматриваются только распознавательные задачи. Определим P как класс распознавательных задач, каждая из которых может быть решена некоторым алгоритмом за полиномиальное время. Мы уже знаем, что в этот класс входят задачи о минимальных остовах, кратчайших путях и наибольших паросочетаниях (имеются в виду распознавательные постановки этих задач, как было установлено). В то же время было названо несколько задач, принадлежность которых к классу P не установлена и считается сомнительной.

Теперь сделаем следующее важное наблюдение. Все задачи, с которыми мы сталкивались до сих пор, независимо от того, установлена их принадлежность классу P или нет, обладают одним общим свойством: если вход задачи таков, что имеет место ответ «да», то существует полиномиальный алгоритм, доказывающий этот факт. Поясним сказанное на примере. Пусть задача состоит в выяснении, является ли граф гамильтоновым, и пусть поступающий на вход граф G гамильтонов, т. е. в графе G имеется гамильтонов цикл C. Тогда доказательство гамильтоновости графа G заключалось бы в проверке включения CG. Если, например, граф G задан матрицей смежности, то эту проверку можно выполнить с помощью очевидного алгоритма, затратив O(n) операций. Подчеркнем, что речь идет лишь о существовании полиномиального доказательства – чтобы иметь это доказательство в своем распоряжении, надо знать цикл C. Положение иное, если граф G не является гамильтоновым. В этом случае нельзя утверждать даже, что полиномиальное доказательство этого факта существует. Можно, конечно, перебрать все (|G|-1)! простых циклов длины |G| полного графа, проверяя каждый раз, содержится ли цикл в графе G. Однако подобное доказательство требует времени по крайней мере O((|G|-1)!), и, следовательно, не является полиномиальным.

Теперь мы хотим определить еще один класс распознавательных задач, включив в него все задачи, обладающие тем свойством, что если вход задачи имеет ответ «да», то существует полиномиальный алгоритм, проверяющий (доказывающий) этот факт. С этой целью дополним множество обычных операторов, из которых мы составляли алгоритмы, одним особым. Пусть A=A₁, A₂,…, A_m – последовательность, элементами которой служат обычные операторы и один особый, запись которого имеет вид B(l₁, l₂), l₁, l₂{1, 2, …, m}. Пусть, далее, Q=q₁, q₂, …, q_p – такой список, что q_i=l₁ либо q_i=l₂ (i=1, p). После того, как A и Q заданы, действие особого оператора B(l₁, l₂) определим так: в результате k-го (kp) выполнения этого оператора управление передается оператору А_l , если q_k=l₁, и A_l , если q_k=l₂, а при k>p вычисления прекращаются. Итак, последовательности операторов A и списку Q ставится в соответствии обычный (детерминированный) алгоритм. Этот алгоритм будем обозначать через A_Q, чтобы подчеркнуть наличие двух компонент A и Q. Список Q будем при этом называть угадывающей последовательностью, а последовательность A – недетерминированным алгоритмом. Подчеркнем особо, что недетерминированный алгоритм не является алгоритмом, а представляет собой чисто абстрактную конструкцию.

Будем говорить, что недетерминированный алгоритм А решает распознавательную задачу за полиномиальное время, если найдется такой полином р(п), что выпол­няется следующее условие: каждый вход длины п этой задачи имеет ответ «да» тогда и только тогда, когда для него существует такая угадывающая последовательность Q, что алгоритм A_Q, будучи примененным к этому вхо­ду, останавливается, сообщив ответ «да», и время его работы не превосходит р{п). Заметим, что согласно это­му определению каждому входу с ответом «да» должен ставиться в соответствие свой алгоритм A_Q. От этого ал­горитма не требуется ничего иного, кроме правильной реакции на свой вход. Поведение алгоритма на всех дру­гих входах для нас безразлично.