Новиков Ф.А. Дискретная математика для программистов (860615), страница 24
Текст из файла (страница 24)
Расщепление переменных. По правилу расщепления в каждую конъюнкцию,которая содержит не все переменные, добавляются недостающие. В результатешестого шага формула становится «совершенной», то есть в каждой конъюнкции содержатся все переменные.7. Сортировка. С помощью коммутативности переменные в каждой конъюнкции, а затем конъюнкции в дизъюнкции сортируются в установленном порядке (см. 3.1.1 и 3.6.2). В результате седьмого шага формула приобретает видСДНФ.Заметим, что все указанные преобразования обратимы.Если теперь даны две формулы, преобразуем их в СДНФ указанным алгоритмом.Если результаты не совпали, значит, формулы не равносильны и эквивалентноепреобразование одной в другую невозможно.
Если же результаты совпали, то,применяя обратные преобразования в обратном порядке, преобразуем полученную СДНФ во вторую формулу. Объединяя последовательность преобразований первой формулы в СДНФ и обратных преобразований СДНФ во вторуюформулу, имеем искомую последовательность преобразований.•3.4.4. Минимальные дизъюнктивные формыБулева функция может быть задана бесконечным числом различных, но равносильных формул. Возникает естественная задача: для данной булевой функциинайти реализующую формулу, обладающую теми или иными свойствами.Практически наиболее востребованной оказалась задача минимизации: найти минимальную формулу, реализующую функцию.
Но и в этой постановке задачаимеет множество вариантов:1. Найти реализующую формулу, содержащую наименьшее количество переменных.2. Найти реализующую формулу, содержащую наименьшее количество определённых операций.3. Найти реализующую формулу, содержащую наименьшее количество подформул определённого вида.Кроме того, могут быть наложены ограничения на синтаксический вид искомойформулы, набор операций, которые разрешается использовать в формуле, и т. д.Из всего этого разнообразия наиболее детально, по-видимому, изучена задачаотыскания дизъюнктивных форм, минимальных по числу вхождений переменных.
Эту задачу мы бегло рассматриваем в заключительных подразделах данногораздела.3.4. Нормальные формы125Дизъюнктивной формой называется формула видаkrrii\f Кг, где кг=/\i=1р=1Формула Кг называется элементарной конъюнкцией, переменные в элементарную конъюнкцию входят в установленном порядке (хотя и не обязательно всеп). Количество переменных в конъюнкции называется её рангом (обозначение\Кг\УТЕОРЕМАЧисло различных дизъюнктивных форм п переменных равно 2 3 ".Переменная либо не входит в элементарную конъюнкцию, либовходит с отрицанием, либо входит без отрицания. Таким образом, существует З пэлементарных конъюнкций, а каждое подмножество множества элементарныхконъюнкций даёт дизъюнктивную форму.•ДОКАЗАТЕЛЬСТВОИз этой теоремы можно извлечь два практических вывода, важных для рассматриваемой задачи минимизации дизъюнктивной формы:1.
Существует тривиальный алгоритм решения задачи: перебрать все формы,а их конечное число, и выбрать минимальную.2. Количество дизъюнктивных форм с ростом п растёт очень быстро, и уже присравнительно небольших п полный перебор практически неосуществим.3.4.5. Геометрическая интерпретацияПри обсуждении задач, связанных с булевыми функциями, очень полезна следующая геометрическая интерпретация. Двоичным наборам из п элементов можновзаимно-однозначно сопоставить вершины n-мерного единичного гиперкуба Еп.Пример На рис.
3.1 представлен гиперкуб для п = 3. При этом булева функция f(xi,...,xn)задается подмножеством N вершин гиперкуба, на которых еёзначение равно 1: TV = f { ( a i , . . . , a n ) | / ( a i , . . . , a n ) = 1}.Пример На рис. 3.1 выделены вершины, соответствующие функции g(x, y,z),имеющей следующую таблицу истинности:X00001111У00110011г g(x,y,z)1011101000101010126Глава 3. Булевы функцииДля функции д имеем N = {{О, О, О), (0,0,1), (0,1,0), (1,1,0)}.illОС.101110010//ООО100XРис. 3.1. Представление булевой функции в виде гиперкубаКаждой элементарной конъюнкции К = х^1 А ...
Асоответствует множество вершин гиперкуба, у которых х^ = <ti, . . . , x*fc — сгь а значения остальныхкоординат произвольны. Другими словами, элементарной конъюнкции К сопоставляется множество { ( a i , . . . , ап) € Еп | К (ai,..., ап) = 1} вершин (кортежей),на которых конъюнкция имеет значение 1. Мы будем обозначать одной и той жебуквой и элементарную конъюнкцию, и то множество вершин, на котором онапринимает значение 1.Легко видеть, что элементарная конъюнкция к переменных образуетную грань гиперкуба Еп.(п-к)-мер-Примеры1.
Элементарной конъюнкции -нх А у соответствует ребро ((0,0,0), (0,0,1)): нарис. 3.1 это ребро выделено.2. Элементарной конъюнкции z соответствует верхняя грань куба на рис. 3.1.Теперь ясен геометрический смысл задачи минимизации дизъюнктивной формы.Дано подмножество N вершин гиперкуба Еп. Требуется найти такой набор гиперграпей Ri, чтобы они в совокупности образовывали покрытие N (N = Ui=iи сумма рангов\Ki\ была минимальна.3.4.6. Сокращённые дизъюнктивные формыИзвестно несколько различных методов решения задачи минимизации дизъюнктивной формы. Все они используют одну и ту же идею: уменьшить по возможности множество рассматриваемых элементарных конъюнкций и затем найти минимальную дизъюнктивную форму, перебирая оставшиеся конъюнкции.Рассмотрим один из самых простых методов этого типа.Пусть функция / задана множеством N вершин единичного гиперкуба Еп.3.4.
Нормальные формы127Если К с N, то конъюнкция К называется допустимой для функции / . Ясно, чтов минимальную (да и любую другую) дизъюнктивную форму функции / могутвходить только допустимые конъюнкции. Если К П ( Е п \ N) Ф 0 , то К — недопустимая конъюнкция. Поэтому для каждого набора ( a i , . . . , a n ) из множестваЕп \ N следует удалить из множества всех З п конъюнкций те 2П конъюнкций,которые можно построить из сомножителей { х , .
. . , а^™}.ПримерДля функции g имеем:f(x,y,z)= 0Недопустимые конъюнкции-IXz ->х А у ->х А 2у Az-ix А у А 2УX-12 X А -1 у X А -12 ->у А -12 х А ->у A -i2X ^У2 х А -|ух А2—>у A z х A -iy А 2X2хАухAzу А2хАуА2У1(0,1,1)(1,0,0)1(1,0,1)11(1.1,1)Удаляя из множества всех 27 конъюнкций те, которые не являются допустимыми,получаем следующий список допустимых конъюнкций:у Л->2,->хЛ -iy,-ixA->z,хАуА-«2,~*хАу A~*z,~*хА^у Az,-^xA^yA~>z.Конъюнкция К называется максимальной для функции / , еслиKcNk(К С К' CN =>• К' = К).Очевидно, что всякая допустимая конъюнкция содержится в некоторой максимальной. Поэтому совокупность всех максимальных конъюнкций образует покрытие множества N, то есть дизъюнктивную форму, которая называется сокращённой дизъюнктивной нормальной формой.
Сокращённая дизъюнктивная нормальная форма определена для функции / однозначно (с учётом установленногопорядка переменных).Примерет видДля функции g сокращённая дизъюнктивная нормальная форма име-(-IX Л -Iу) V (-IX Л -Iz) V (у А -«г),что существенно короче, чем С Д Н Ф этой функции:(-IX Л у А -| z) V (-ix Л у A z) V (-ix Ay A -<z) V (х Л у А -> z).На рис.
3.1 выделены рёбра (000-001, 000-010, 010-110), соответствующие сокращённой дизъюнктивной нормальной форме.Минимальная дизъюнктивная форма является подформулой сокращённой дизъюнктивной нормальной формы.ТЕОРЕМАО Т противного. Пусть минимальная форма содержит не максимальную конъюнкцию. Тогда эту конъюнкцию можно заменить соответствующеймаксимальной, при этом покрытие сохранится, а сумма рангов уменьшится, чтопротиворечит минимальности формы.•ДОКАЗАТЕЛЬСТВО128Глава 3. Булевы функцииПримерДля функции д минимальная дизъюнктивная форма имеет вид->х Л ~iy V у Л -iz.Действительно, на рис.
3.1 видно, что рёбра 000-001 и 010-110 являются максимальными конъюнкциями и в совокупности покрывают множество N.3.5. ПолнотаВ типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевыфункции. Выше показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужныйпроцессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Этот раздел посвящён ответу на вопрос: существуют ли(и если существуют, то какие) иные системы булевых функций, обладающих темсвойством, что с их помощью можно выразить все другие функции.3.5.1.
Замкнутые классыПусть F = { / i , . . . , fm}, Vi е l..m ( f i G Pn)- Замыканием F (обозначается [F])называется множество всех булевых функций, реализуемых формулами над F:[F] = f { / e P n | / = func?[F]}.Свойства замыкания (см. 2.1.2):1. Fс [F],2. [{F}\ = [F].3. Fi С F 2 = > [FJ С [Fa].4.([Fi]U[F2])С [FI UF2].Класс (множество) функций F называется замкнутым, если [F] = F.Рассмотрим следующие классы функций.Def1. Класс функций, сохраняющих 0: То = {/ | / ( 0 , . . . ,0) = 0} .Def2. Класс функций, сохраняющих 1: Т\ = {/ | / ( 1 , .
. . , 1) = 1} .Def3. Класс самодвойственных функций: Т* = {/ | / = /*} •4. Класс монотонных функций: Т^ = f {/ | а < /5 = > f ( a ) ^ /(/5)} , гдеа = ( а ь . . . ,а„),(3 = (&i,..., 6П), а*, Ы G F 2 ,Defа ^ /3 = Vi (а< ^ 6»).5. Класс линейных функций: Tl = f {/ | / = cq + c\Xi -\-I- с п х п } , где + обозначает сложение по модулю 2, а знак конъюнкции опущен.3.5. Полнота129Примеры1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
