Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Для функционала ?(91) потребуем выполнения следующих аксиом.
I. Аксиома неотрицательности. Для любой д. н. ф. ?(9*)> 0.
II. Акси ома монотонности (относительно умножения). Пусть 5{ = 9*'’V Х\гКг. Тогда
?(9*)>?(91' УК').
III. Аксиома выпуклости (относительно сложения). Пусть д. н. ф. 91 разбита в прямую сумму д. н.ф. 91] и %, т. е. 9*1 = 9$! V 9$а и 9?, 9*2 не имеют общих членов. Тогда
? (Я) >?(«!) + ? (91,).
IV. Аксиома инвариантности (относительно изоморфизма). Пусть д. н. ф. 9*' получена из д. и. ф. 9* путем переименования переменных (без отождествлений). Тогда
?(Г)-?( Э1)\
Приведем примеры встречающихся индексов простоты для д. н. ф.
1. ?в (9*) — число букв переменных, встречающихся в записи д. н. ф. 91. Если взять д. н. ф. % и 9*2 из примера 1, то ?в (9*,)= 15 и ?в (912) = 3, т. е. в смысле этого индекса д. н. ф. 912 проще, чем д. н. ф. 91,.
2. ?к(9*)—число элементарных конъюнкций, входящих в 91. Для д.н.ф. 9*, и й2, очевидно, ?к(9*1)=5 и ?к(9*2) = 2, т. е. в смысле этого индекса д. н. ф. 9*2 проще, чем д. н. ф. 9ц.
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 299
3. Lc(9?)—число символов“, встречающихся в записи д. п. ф. 9?. Для д. н. ф. Эй и $2, очевидно, L0(5?t)=7 и L0(9?2) = 2, т. е. в смысле этого индекса д.н. ф. S?2 опять проще, чем д. н. ф. 9ii.
Нетрудно проверить, что каждый из указанных индексов удовлетворяет приведенным выше аксиомам.
Замечание. Пусть SI == Si' V К. Тогда в силу аксиом III и I
?(Эг)^1(ЭГ).
Очевидно, что над алфавитом переменных {xL, «.xj можно построить 3” различных элементарных конъюнкций («пустой» конъюнкции сопоставлена константа 1). Отсюда следует, что число д. н. ф. над этим же алфавитом из п букв равно 2зП* Опираясь на этот подсчет, введем следующее определение.
Определение. Д.н.ф. реализующая функцию }(хи ..., хп) и имеющая минимальный индекс ?($), называется минимальной относительно L (ж д. н. ф. относительно L).
Поскольку дальнейшее изложение связано главным образом с индексом простоты Ьь, то минимальную д. н. ф. относительно этого индекса будем называть минимальной д. н. ф. {м. д. и. ф.). Д. н. ф., минимальную относительно индекса Le, будем называть кратчайшей.
Вернемся теперь к примеру 1.
1. Д. н. ф. == я2.т3 V является минимальной. В самом деле, функция }(хи хг, ?3), реализуемая этой д. н. ф,, существенно зависит от переменных хи хг и .га и потому не может быть представлена д. н. ф., содержащей менее трех букв.
2. Д. н. ф. S?2 — Хг%з V Хх является кратчайшей, так как функция }[xi, х2, х3), реализуемая этой д. н. ф., отлична от любой элементарной конъюнкции.
3. Д. и. ф. S?a = х-2%з V минимальна относительно Л-о, так как функция f(xх2, xs), реализуемая этой д. н. ф., по перемеипым х% и хэ не возрастает и они обе существенны, а поэтому не может быть представлена д. н. ф., содержащей менее двух отрицаний.
Основной вопрос, который пас будет интересовать в этой главе, это как для произвольной функции алгебры логики f(xu хп) построить ее минимальную д. н. ф. относительно L. Эта задача называется проблемой минимизации булевых функций. Мы покажем сейчас, что дан-
300 ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
ная задача допускает тривиальное решение. Сначала в каком-либо порядке строят все д. н. ф. (их 2®п) над переменными #1, ,.х,п
Затем отбирают из этого списка те д. н. ф., которые реализуют функцию /(х1, ..хп). Наконец, Для выбранных д. н. ф. вычисляют величину индекса простоты и путем сопоставлений находят минимальную (относительно Ь). Сформулированный алгоритм весьма трудоемок с точки зрения его реализации, так как он основан на «переборе» всех д. н. ф., т. е. требует, вообще говоря, не менее 2®п более мелких операций. Им нельзя воспользоваться практически уже начиная с п = 3, а для п ~ 1 и п *=* 2 проблема тривиальна. Таким образом, следует считать, что алгоритмы «полного перебора», т. е. алгоритмы, подобные по трудоемкости тривиальному алгоритму, перебирающему все д. н. ф., являются запрещенным средством в решении проблемы минимизации.
Мы обращаем внимание, что развиваемая далее теория справедлива для любого индекса простоты и потому начальный этап минимизации одинаков для всех индексов простоты. С другой стороны, для удобства можно считать, что в этих построениях речь идет об индексе ?в, т. е. о построении м. д. н. ф. Поскольку минимальная д. н. ф. относительно одного индекса может не быть минимальной д. н. ф. относительно другого индекса (см. [2, 4, раздел 3]), то теория, построенная для одного индекса, вообще говоря, не годится для другого. Однако то обстоятельство, что эти теории имеют и много общего, оправдывает рассмотрение минимизации для конкретного индекса.
§ 2. Упрощение д.н. ф. и-тупиковые д. в. ф.
(относительно упрощения)
Пусть 91—произвольная д. н. ф. и
й «= Г V Я, 91 = Г Ух?'К\
где К — некоторая элементарная конъюнкция из 31, —
д. н. ф., образованная из остальных конъюнкций, входящих в 91, — некоторый множитель из К, К' — произ-
ведение остальных множителей из К. Рассмотрим два типа преобразований д. н, ф.
Ои1
I. Операция удаления элементарной конъюнкции. Переход от д. н. ф. й к д. н. ф. й' — преобразование, осуществляемое путем удаления элементарной конъюнкции К. Данное преобразование определено тогда и только тогда, когда й' =* й.
