7. Задача о построении уравнений границ и частичные булевы функции

Предположим, что на плоскости задана система областей определяемых соответственно неравенствами Булевой функции соответствует некоторая область однако это может быть и пустое множество. Например, если области не пересекаются, то пустое множество соответствует конъюнкции если области расположены так, как показано на рис. 14, пустое множество соответствует булевой функции При заданном расположении областей может быть несколько булевых функций, которым

Рис. 14

соответствует на плоскости пустое множество. Пусть есть система таких функций (очевидно, что отрицанию этих функций соответствует вся плоскость Выделим те наборы двоичных переменных которым соответствует единица хотя бы одной из функций Так как двоичные переменные являются предикатами

то, очевидно, что на плоскости нет таких точек, которым соответствовали бы указанные наборы этих двоичных переменных. В противном случае множество, соответствующее какой-то из функций оказалось бы не пустым.

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

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

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

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

Рис. 15.

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

Следовательно, уравнение границы области может быть написано в виде