1 - Булевы функции. Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ (1059972), страница 5
Текст из файла (страница 5)
Они интересны тем, что каждый определяется свойством, сохраняющимся при конструировании формул. Точнее говоря, если функцииf , g1 , . . . , gk принадлежат одному из указанных классов, то и их композиция f (g1 , g2 , . . . , gk )принадлежит этому же классу. Это означает, что каждый из названных классов есть замкнутое множество. Отметим также, что классы Поста замкнуты относительно операций введенияили удаления фиктивных аргументов.Рассмотрение классов Поста приводит к следующему необходимому условию полноты рассматриваемого базиса: базис, целиком попадающий в один из классов Поста, не может бытьполным.
Действительно, если базис включен в один из классов Поста, то замыкание базисатакже оказывается в этом классе. Но ни один из классов Поста не совпадает со всем множеством булевых функций. Следовательно, замыкание базиса не будет совпадать с множествомвсех булевых функций. Менее очевидным является то, что это условие и достаточно.ÔÍ-12ÔÍ-12Пять классов Поста T0 , T1 , S. M , L. Их замкнутость.
Критерий Поста: множество полно,если оно не содержится ни в одном из классов Поста. Примеры.ÌÃÒÓÌÃÒÓ1.4. Критерий ПостаÌÃÒÓÔÍ-12ÌÃÒÓ11ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ12ÔÍ-12компоненты этих векторов. Тогда формула f (α1 , α2 , . . . , αi−1 , x, αi+1 , . .
. , αn ) представляет собойоперацию отрицания.Предположим, например, что функция g1 (x) является отрицанием. Тогда мы можем составлять формулы вида f (x ⊕ σ 1 , . . . , x ⊕ σn ), где x ⊕ σ есть переменная x при σ = 0 и ееотрицание при σ = 1. Выберем функцию f ∈ F , не являющуюся самодвойственной. Тогдаможно указать такой булев вектор p ∈ Bn , что f (p) 6= f (p), откуда f (p) = f (p). Пусть σ1 , . . . ,σn — компоненты вектора p.
Рассмотрим функцию g(x) = f (x ⊕ σ 1 , . . . , x ⊕ σn ), определяемуювыбранной несамодвойственной функцией f и вектором p. Так как 0 ⊕ σi = σi , 1 ⊕ σi = σ i ,то g(0) = f (p) = f (p) = g(x). Следовательно, функция g(x) является константой. Пусть,например, g(x) = 1. Тогда g(x) = 0 — другая константа.Итак, мы показали, что множество F , не являющееся подмножеством классов T0 , T1 , S, M ,позволяет получить в виде формул отрицание и обе константы.
Для построения формулы дляпроизведения выберем функцию f ∈ F , не являющуюся линейной. Составляя формулы видаf (X1 , X2 , . . . , Xn ), где Xi — это либо переменная x, либо переменная y, мы получим функциидвух аргументов. Покажем, что среди таких функций есть нелинейные. В полиноме Жегалкина, представляющем функцию f , выберем нелинейное (степени два или выше) слагаемоенаименьшей степени. Пусть это слагаемое имеет вид xi1 xi2 .
. . xik . В формуле f (X1 , X2 , . . . , Xn )положим Xi1 = x, Xij = y, j = 2, k, а для остальных переменных, не вошедших в выбранное слагаемое выберем значение 0. Тогда выбранное слагаемое преобразуется в xy, остальныенелинейные слагаемые обнулятся, и мы получим функцию вида g(x, y) = xy ⊕ αx ⊕ βy ⊕ γ.Так какÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИМинимальная ДНФ — наименьшее число литералов (вхождений переменных). КратчайшаяДНФ — наименьшее число элементарных конъюнкций. Геометрия булева куба. Импликантыи простые импликанты.
Сокращенная ДНФ. Избыточные импликанты и тупиковые ДНФ.Методы построения сокращенной ДНФ. Алгоритм Квайна — Мак-Клоски. Склейка. ТаблицыКвайна и простые импликанты. Ядровые импликанты. Тупиковые ДНФ и функция Патрика.Выбор кратчайших и минимальных ДНФ.ÔÍ-12Каждая функция может быть представлена дизъюнктивной нормальной формой различнымиспособами. например, изменить ДНФ можно, если в одно из ее слагаемых ввести фиктивнуюпеременную с помощью сомножителя x + x. Возникает задача из всех ДНФ найти наиболеепростую в том или ином смысле.Возможны по крайней мере два подхода к оценке сложности ДНФ: по количеству элементарных конъюнкций в ней (это количество называют длиной ДНФ) и по общему количествулитералов, т.е.
по сумме длин элементарных конъюнкций, входящих в ДНФ (эту сумму называют сложностью ДНФ). ДНФ называют минимальной, если она имеет наименьшуюсложность, и кратчайшей, если она имеет наименьшую длину.В приведенной терминологии задача состоит в выборе среди всех ДНФ, представляющихданную функцию, наименьших и кратчайших. Решение такой задачи сводится к отбору некоторого ограниченного круга ДНФ, подозрительных на минимум“, и последующему пере”бору отобранных ДНФ.
Здесь возможны различные приемы. Чтобы описать и объяснить этиÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-121.5. Минимизация ДНФÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12заключаем, что g(x ⊕ β, y ⊕ α) ⊕ γ 0 = xy. Но x ⊕ σ — это переменная x при σ = 0 и ееотрицание x при σ = 1. Поэтому, если g(x, y) принадлежит замыканию F , то и функцияg(x ⊕ β, y ⊕ α) ⊕ γ 0 = xy, т.е. конъюнкция, принадлежит замыканию F .Итак, мы показали, что если множество F не является подмножеством никакого классаПоста, то формулами над F можно представить отрицание и конъюнкцию, а значит, и дизъюнкцию. В этом случае, согласно теореме 1.3, множество F полное. IÌÃÒÓÌÃÒÓg(x, y) = xy ⊕ αx ⊕ βy ⊕ γ = (x ⊕ β)(y ⊕ α) ⊕ αβ ⊕ γ = (x ⊕ β)(y ⊕ α) ⊕ γ 0 ,ÌÃÒÓkX(n − ni ) = kn − r,i=1ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓi=1di =ÔÍ-12kXÌÃÒÓs=ÔÍ-12Чтобы получить кратчайшую ДНФ заданной функции, надо выбрать минимальное количество импликант (граней булева куба, содержащихся в уровне единицы функции), в совокупностинакрывающих уровень 1. Для минимальной ДНФ минимума достигает сумма длин импликант,а для этого надо стремиться увеличить сумму размерностей граней куба, соответствующихэлементарным конъюнкциям ДНФ.
В самом деле, пусть di и ni , i = 1, k, — длины конъюнкций,составляющих ДНФ, и размерности соответствующих граней булева куба; s — сложность ДНФ;r — сумма размерностей граней, соответствующих конъюнкциям ДНФ. ТогдаÌÃÒÓЗамечание. Далее будем предполагать, что исследуемая функция от n аргументов не меняется, так что можно заранее каждый аргумент функции связать с некоторой переменной, аточнее, с i-м аргументом связывается переменная xi . Это позволяет не различать булевы функции и формулы, составленные из переменных x1 , . .
. , xn . Именно в этом контексте элементарнаяконъюнкция трактуется как функция от n аргументов.ÔÍ-12приемы, перейдем к геометрической интерпретации области определения булевой функции —булева куба.Отдельные элементы, составляющие булев куб Bn , т.е. булевы векторы принято называтьвершинами куба. Множество булевых векторов, у которых компоненты заданного набора,например с номерами i1 , . . . , ik , имеют определенные значения образуют подалгебру булевойалгебры, называемую гранью булева куба. Грань представляет собой булев куб, но меньшейразмерности, равной n − k, где n — размерность булева куба, k — количество фиксированныхномеров. Грань размерности 1 называется ребром булева куба.
Кортеж номеров фиксированных компонент, определяющий грань куба называют направлением грани. Грани, имеющие одинаковое направление, не пересекаются. Они называются параллельными. Средипаралельных граней выделим соседние, у которых совпадают значения всех фиксированныхкомпонент, кроме одной.Грани булева куба удобно обозначать, как слово из трех символов 0, 1 и ∗, где 0 и 1 обозначают фиксированные значения компонент, а ∗ указывает меняющиеся компоненты.
Например,слово 00 ∗ 1, обозначает ребро четырехмерного булева куба, определяемое условиями x1 = 0,x2 = 0, x4 = 0. Третья компонента, отмеченная звездочкой, варьируется. При таком способезаписи размерность грани совпадает с количеством звездочек, грани параллельны, если у нихсовпадает положение звездочек (например 10 ∗ 0 и 01 ∗ 1). Грани соседние, если их записи различаются только в одной позиции, в которой для одной грани указано значение 0, а для другой1 (например 01 ∗ 0 ∗ 1 и 11 ∗ 0 ∗ 1).Будем говорить, что булева функция f , определенная на Bn , подчиняется булевой функцииg, определенной на том же кубе (или f меньше g), если f (x) 6 g(x) для любого x ∈ Bn . В этомслучае будем писать f 6 g. Множество вершин куба, в которых функция f принимает значение1, будем называть уровнем единицы функции, сами эти вершины называют конституентами единицы.
Если f 6 g, то уровень единицы функции f является подмножеством уровняединицы функции g.Элементарная конъюнкция принимает значение 1 в том и только в том случае, когда каждый литерал в ней принимает значение 1. Часть переменных может не входить в конъюнкцию,т.е. эти переменные будут фиктивными. Варьируя значения фиктивных переменных, получимгрань n-мерного булева куба. Таким образом, уровень единицы любой элементарной конъюнкции есть некоторая грань булева куба.Любую ДНФ данной функции f можно интерпретировать как набор граней булева куба,объединение которых совпадает с уровнем единицы функции f .
При этом каждая элементарная конъюнкция рассматриваемой ДНФ будет подчинена функции f . Любую элементарнуюконъюнкцию, подчиненную функции f , будем называть импликантой.ÌÃÒÓÔÍ-12ÌÃÒÓ13ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12Склейка. Дизъюнктивная нормальная форма данной функции может содержать пару импликант, соответствующих соседним граням булева куба. Но две соседние грани булева кубавместе составляют грань большей размерности. Например, две двумерные грани 01∗∗10 и01∗∗11 пятимерного куба в совокупности составляют трехмерную грань 01∗∗1∗. Замена в ДНФдвух таких импликант одной более короткой приводит к0*0*уменьшению и длины, и сложности ДНФ.
Такую заменуx3 x4называютсклейкой. Импликанты, соответствующие со00 01 11 10x1x2седним граням, имеют один и тот же набор переменных,*0*011100причем они различаются только по одной переменной: водной импликанте стоит сама переменная, а в другой —01*111101ее отрицание. Например, грани 01∗∗10 и 01∗∗11 соответ11ствуют элементарным конъюнкциям x1 x2 x4 x5 и x1 x2 x4 x5 .Изменение ДНФ выполняется в данном случае в соответ1110ствии с тождеством x1 x2 x4 x5 + x1 x2 x4 x5 = x1 x2 x4 . Примеры возможных склеек показаны с помощью карты КарноРис. 1.3на рис.
1.3.Отталкиваясь от совершенной ДНФ, мы можем сперва склеивать различные пары соседнихнульмерных граней (вершин) в ребра, затем в соседние ребра в двумерные грани и т.д. Процессподобной склейки приведет к выявлению граней максимальной размерности, содержащихся вÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓи мы видим, что увеличение суммы размерностей граней ведет к уменьшению сложности ДНФ.При небольших размерностях булева куба (до 4) его геометрию можно представить на плоскости с помощью так называемых карт Карно. Представим куб Bn как декартово произведение двух кубов Bk × Bl , где k, l 6 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
