Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Пусть
Л1 Лй Лт
— список всех максимальных граней множества Л^. Нетрудно видеть, что
= илг * и ... и Ял«
так как N 0еЛг/(1 = 1, ..т) и каждая точка из Nf
К1
принадлежит некоторой максимальной грани. Последнее равенство эквивалентно следующему:
1-к\ ук\ V ... уЛ*
Определение. Д. н. ф., являющаяся дизъюнкцией всех простых импликант функции /, называется сокращенной д. п. ф.
Итак,
= К\ V *2 V >.. V Й
есть сокращенная д. н. ф. функции /. Как это вытекает
из предыдущих рассмотрений, она однозначно определяется по функции / и реализует функцию /.
Пример 9. Для функции /, заданной табл. 4, имеем следующее покрытие, состоящее из всех максимальных граней (см. пример 6)
N / “ N кк 11 Л**
Ему соответствует сокращенная д. н. ф.
йс = Да & Хг V XI.
Геометрический подход вместе с тем дает и способ построения сокращенной д. н. ф. Однако желательно иметь также и аналитическое решение.
Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Алгоритм построения сокращенной д. н. ф. Возьмем для функции 1{хи ..., хп) любую конъюнктивную нормальную форму (например, совершенную к. н. ф.). Затем Ёроизводим раскрытие скобок, т. е. преобразование типа
& V V &.
После этого в полученном выражении удаляем нулевые члены и ликвидируем поглощаемые и дублирующие члены, т. е. совершаем преобразования вида
КхКг\/Кх = Ки Я, V
В результате этого мы придем к сокращенной д. н. ф. Действительно, из любой простой импликанты ж. . ..
аг
,.. & х функции / в каждую дизъюнкцию исходной конъюнктивной нормальной формы должен входить хотя бы один из членов Ж*), ..., х% (иначе, положив
Ж^ = Оь . . . , Хгг = аг,мы обратили бы в нуль все члены
°1 аГ Л
видаж^, . затем смогли бы подооратъ значения
остальных переменных так, чтобы некоторая дизъюнк-
ция, не содержащая ж| , ..ж.^»тоже ооратилась бы в
нуль; но тогда на этом наборе значений переменных #1, . ? функция / обратилась бы в нуль, а простая
°1 °г ^ ,
импликанта ж.^ & .. . & ж^ обратилась оы в единицу, что
невозможно). Поэтому после раскрытия скобок будут получены все простые имплпканты (конъюнкции, не содержащие части сомножителей, получиться не могут, так как соответствующие им грани уже не содержатся в /V/, т. е. каждая такая конъюнкция хотя бы в одном случае равна единице, когда функция / равна нулю). Очевидно, что все остальные конъюнкции, которые будут при этом пблутены,' соответствуют не максимальным граням и, следовательно, поглощаются простыми импликантами.
Пример 10. Возьмем функцию 1(хи ж2; ж3), заданную табл. 1. Для нее имеем совершенную к. н. ф.
/(жи ж3) = V ж? V Хз) (ж, V хг V хг).
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 315
Производим раскрытие скобок и упрощения!
(#! V х2 V х3) (х1 V хг V х3) == х,х! Уад V хух3 V V хух2 V х2х2 V х2х3 V х^3 V х2х3 V х3х 3 =
V х {х3 V V х2ха V д^Хз V х2х 3. Сокращенная д. и, ф. имеет вид
% = ?1X2 V X !Х3 V Х2Хз V ДДД"2 V Х1Ха V х2х3.
Она легко усматривается и из геометрических соображении и соответствует циклу из
ребер (см. рис. (>). ш ^ггхъ $
Пример 11. Рассмотрим Щх3
функцию /(хь х2, х3, ж4, х5): /
СС0) =
11 при 1 ах + .. . + а- ^ 3, Мщхг
[О в остальных случаях.
Ее совершенная д. п. ф. есть, очевидпо,
31= V х/&...&х55
1^сг-^^ , +(Тй<8
3*? (Г
Рис. 6
и имеет сложность Ьц (Я) = 25. Каждой грани, содержащейся в Лг/, соответствует элементарная конъюнкция, имеющая не менее двух множителей с отрицаниями и не менее одного множителя без отрицаний. В то же время каждой копъюнкции вида хгхр:к, где г Ф /, 1Ф- к и / к, соответствует грань, принадлежащая множеству Л7/. Отсюда вытекает, что все конъюнкции вида х^,хк (г Ф /, г' #= к, / ?= А;-) являются простыми имиликантами функции / и
= \/ (едх,Ч \/ гр/й V
(г-
— сокращенная д. н. ф. для /. Очевидно,Ьк(51с)=3*^||= 30.
Данный пример показывает, что сокращенная д. п. ф. для функции / может иметь большее число членов, чем совершенная д. н. ф.
В1б Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ Н КИБЕРНЕТИКИ
§ 5. Тупиковость на основе
геометрических представлений.
Методы построения тупиковых д. н. ф.
Определение. Покрытие множества А//, состоящее из максимальных (относительно Л7/) граней, называется неприводимым, если совокупность граней, получающаяся из исходной путем выбрасывания любой грани, пе будет покрытием N1.
Определение. Д. н. ф., соответствующая неприводимому покрытию мпожества Л-т/, называется тупиковой (в геометрическом смысле).
Пример 12. Для функции /(#„ ?2, а:3), заданной табл. 1, как видно из рис. (5,
Н} „ дг__ у дг_ у $
1 К2л-а и *]*3 и
является неприводимым покрытием, а $ = х2х* V X1ХЪ V Х&г
— тупиковой д. н. ф. (в геометрическом смысле) .
Теорема 3. Понятия тупиковой д. н.ф. относительно преобразований 1 и II и тупиковой д. п. ф. в геометрическом смысле эквивалентны.
В дальнейшем мы будем говорить просто о тупиковых д. н. ф., не указывая определения, из которого мы исходим.
Заметим, что определенные нами д. н. ф.— сокращенная, тупиковая и минимальная находятся в следующем соотношении.
Тупиковая д. н. ф. получается из сокращенной путем отбрасывания (удаления) некоторых членов.
