Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
II. Операция удаления множителя. Переход от д. н. ф. Й к д. н. ф. й' V К' — преобразование, осу-
°г тг
ществляемое путем удаления множителя . Данное преобразование определено тогда и только тогда, когда
й' V К' = й.
Определение. Д. н. ф. й, которую нельзя упростить при помощи преобразований I и II (их применить нельзя), называется тупиковой д. н. ф. {т. д. н. ф.) (относительно преобразований I и II).
Пример 2. Очевидно, д. н. ф. Й = я, \/с?2х, будет тупиковой относительно данных преобразований.
На основе этих двух преобразований можно сформулировать алгоритм упрощения д. н. ф. (Этот алгоритм легко усматривается, и в силу того, что ?(й')^1/(й) п Ь(й' УК') ?(Й), он является разновидностью алгоритма наискорейшего спуска. Легко видеть также, что среди тупиковых д. и. ф. функции 1{х1, ..., хп\ всегда содержатся и минимальные, может быть, правда, не все.)
1. Выбирается какая-нибудь д. н. ф. для функции f{xu а:п) в качестве исходной. Таковой можно взять, например, совершенную д. н. ф., так как существует простой способ ее построения.
Таблица 1
Х1 /(*3. Х8) *1 Х2 *а Цхи х,)
0 0 0 1 1 1 1 0 0 1
0 0 1 I 1 0 1 0
0 1 0 0 i 1 0 1
0 1 1 1 1 1 1 1
2. Осуществляется упорядочивание в исходной д. н, ф. слагаемых и в каждом слагаемом — множителей. Это упорядочение можно задать записью д. н. ф.
Пример 3. Рассмотрим функцию 1{хи х2, а*3) (см. табл. 1). В качестве исходной д. н. ф. для нее возьмем
совершенную д. н. ф. и выберем два упорядочения: одно естественное и второе специальное:
$}' = X 1Х2Х& V Х&гХг V X 1X2X3 V ХлХгХл V ХхХ&г V Х1Х2ХЛ7 91" — Х&ъХг V ХаХ1Х2 V Х2Х1ХЛ V Х^Хз V ХВХ1Х2 V Х1Х2Х3.
3. Затем производится просмотр записи д. н. ф. (слева направо); дли очередного члена К{ {I = 1, ..., з) сначала пробуют применить операцию удаления элементарной конъюнкции К если это невозможно, то п роема три па ют
члены конъюнкции К{ слева направо (V ~ 1, ,.г)
_ <Т т Оу
= х1к & • - • & Х1Г
и применяют операцию удаления множителя До тех пор, пока это удается.
После этого переходят к следующей элементарной конъюнкции.
Закончив обработку последней элементарной конъюнкции, еще раз просматривают полученную д. н. ф. слева направо и пробуют применять операцию удаления элементарной конъюнкции *).
В результате этого мы получаем искомую д. п. ф. Очевидно (с учетом того, что будет изложено в § 4), имеет место следующий факт.
Теорема 1. Д. н. фполученная в результате применения алгоритма упрощения, является тупиковой д. н. ф. (относительно преобразований I и II).
Пример 4. Для фупкции 1(хи х2, хв), задаппой табл. 1, возьмем в качестве исходной д. н. ф. совершенную д. н. ф. Рассмотрим ее упорядочение, задаваемое записью 2Г, и проследим работу алгоритма.
1. Конъюнкция ОС ^ 2^-’ 3}
очевидно, не может быть удалена. Однако можно удалить множитель ад, так как
X %Х з —ХхХзХа V Х1Х2ХЯ.
В результате мы получаем конъюнкцию хгх3, из которой уже нельая выбросить ни одного множителя.
2. Конъюнкцию х^х2х9 удалить также нельзя. Легко видеть, что из нее множитель х1 удалить невозможно, в то время как операция удаления множителя х2 применима.
*) Необходимость вторичного просмотра можно проиллюстрировать примером (см. табл. 3).
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 303
Мы получаем КОНЪЮНКЦИЮ Я^з, которую упростить путем удаления множителей невозможно.
3. Конъюнкция может быть удалена, так как
X i^s = XiX2X3 V XiXzXs.
4. Конъюнкция XiXzXs также может быть удалена (см. п. 1).
5. Конъюнкцию х&гХз удалить нельзя. Однако, возможно выбросить множитель xi. Б результате мы получим конъюнкцию XtXi, из которой уже нельзя выбросить ни одного множителя.
0. Конъюнкция XiX2xs, очевидно, удалена не может быть. Из нее можно удалить множитель Xi. Мы получаем конъюнкцию хгхг, которую упростить путем удаления множителей невозможно. Мы получаем д. н. ф. жйЯ8 V 5ца:8 V V X,XS V Х2Ха. Вторичный просмотр этой д. н. ф. с целью удаления конъюнкций упрощений не дает. Следовательно, д. н. ф. %, где
SI, = X2XS V XiXs V XiXa V Х2Хг,
является результатом применения алгорима упрощения. Приведенные расчеты можно сделать так, как указано в табл. 2.
Для той же функции возьмем другую упорядоченность ее совершенной д. н. ф.:
91" = XiX2Xs V XiXiX2 V X?XtXa V XiXiXa V XsXiXa V X$$t.
В табл. 3 приводятся основные этапы работы алгоритма для этого случая. Следовательно, в этом случае в качестве результата применения алгоритма упрощения получаем д. н. ф.
91а ™ Х2хг v XiXa V Х^Хг.
Из данного примера вытекает, что результат применения алгоритма упрощения зависит от выбора упорядочения исходной д. и. ф.; так, например,
MSti) = 8, ?B(9?a)=6, или
Тупиковые д. н. ф. могут иметь различную сложность и, в частности, отличаться от минимальных. В связи с этим возникает вопрос, возможно ли для любой функции f(xu ..,, xn)t исходя из некоторого упорядочивания, получать, применяя алгоритм упрощения, минимальную д. н. ф. Ответ на это дает следующая теорема,
Зи4 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Таблица 2
л« шага Д.н.ф. и рассматриваемый порядок Иге лед 70-мая коыъ-донг; нк л Рид операции
