Полные системы булевых функций

курсовая работа

4. Геометрическое представление логических функций

Обозначим через Еn множество всех наборов (б1,..., бз), состоящих из чисел ноль и единица. Множество Еn называется n-мерным кубом, а набор (б1, ..., бз) - вершинами куба.

Пусть у1, ..., уr- фиксированный набор чисел из 0 и 1. Множество всех вершин (б1,..., бз) куба Еn таких, что бi1 = у1, бi2 = у2, ... , бir = уr, 1 < i1 < i2 < ...< ir, называется (n - r) - мерной гранью. Очевидно, что (n - r)-мерная грань является (n - r) - подкубом куба Еn.

Например, в трехмерном кубе Е3 наборы (0,0,1) и (0,0,0) образуют одномерную ( n = 3, r = 2) грань (ребро), а наборы (1,0,0), (1,0,1), (1,1,0), (1,1,1) - двухмерную грань.

Пусть f(X1,X2,…,Xn) - произвольная булева функция. Ей сопоставляется в соответствие подмножество Нf вершин куба Еn, таких что (б1, ..., бз) Nf тогда и только тогда, когда f(б1, ..., бз) = l Очевидно, что по подмножеству Nf исходная функция f(X1, X2., ... , Чn) восстанавливается однозначно. Таким образом геометрический способ задания булевой функции заключается в задании множества вершин n-мерного куба Еn, в которых данная функция истинна.

Пример 8. Пусть функция f(X1, X2, Х3) задана табл. 4. Составить для нее множество Nf.

Таблица 4

X1

X2

X3

f(X1, X2, Х3)

0

0

0

1

0

0

1

0

0

1

0

0

1

0

0

1

0

1

1

0

1

0

1

1

1

1

0

1

1

1

1

1

Решение. Очевидно, что Nf = {(0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}. Множество Nf изображено на рис. 3.

Напомним [1], что для любой булевой функции существует ее представление в СДНФ. Причём в алгоритме построения СДНФ используется только те наборы значений, при которых функция равна единице [3]. Это позволяет проинтерпретировать геометрическое представление функции следующим образом. Рассмотрим трёхмерный куб и занумеруем вершины так, как показано на рис. 4.

2

Тогда его грани (двумерные подкубы) можно рассматривать как

Ребрами данного куба ( одномерными подкубами) будут, например, , и т.д.

Пример 9. Построить модель куба, соответствующего функции:

.

Решение. Первому слагаемому соответствует вершина 2, второму - вершина 6, третьему - вершина 3, четвертому - вершина 8, пятому - вершина 4 (рис. 5).

Пример 10. Дана модель куба с помеченными вершинами (рис. 6). Составить СДНФ для данной булевой функции

Решение. Вершине 1 соответствует конъюнкция , вершинам 3 и 4 конъюнкция и соответственно; вершинам 5 и 6 - конъюнкции и . Следовательно, искомая СДНФ имеет вид

.

Заметим, что для функций, зависящих от четырёх и более переменных, геометрическое представление применяется очень редко, т.к. трудно построить наглядную модель n-мерного куба при n > 3. Поэтому в этом и следующих параграфах мы будем рассматривать только булевы функции трех аргументов, хотя все изложенное справедливо для других функций, зависящих от большого числа аргументов.

Перейдем теперь к геометрической постановке задачи минимизации булевых функций.

5. Геометрический метод минимизации булевой функции

Рассмотрим элементарную конъюнкцию ранга r (т.е. содержащую r пропозициональных переменных)

где е = 0,1; . Очевидно, что множество Nk, соответствующее конъюнкции К, есть (3 - r)-мерная грань. Число r называется рангом этой грани.

Пример 11. Конъюнкциям

,

,

соответствуют грани (рис. 7 а, б, в) , Nk1={7,8}, Nk2={8,6}, Nk3={6,2,4,8}, имеющие ранги 2, 2, и 1. Первые две грани являются одномерной гранью (ребром), а третья - двумерной гранью.

Отметим очевидные свойства введенного соответствия между булевой функцией f и подмножеством Nf.

Если , то

.

В частности, если f(X1, Ч2, X3) обладает ДНФ, т. е. , то и т.е. ДНФ функции f соответствует покрытие множества Н, гранями .

Пример 12. Рассмотрим представленную в СДНФ функцию

.

модель куба, для которой построена на рис. 3. С помощью таблицы истинности может быть показано, что данная функция представима также ДНФ

.

Этим ДНФ соответствуют два покрытия множества Nf :

,

,

где Nk1={2}, Nk2={6}, Nk3={3}, Nk4={8}, Nk5={4}, Nk10={2,6,8,4}, Nk20={4,3}. Одно из этих покрытий - точечное, второе состоит из ребра и двумерной грани.

Пусть ri - ранг гpани Нki (он равен рангу конъюнкции ki). Число r, определенное формулой

,

называется рангом покрытия. Тoгда задача о минимизации булевой функции принимает следующую геометрическую постановку: для данного множества Nf, найти такое покрытие гранями, принадлежащими Nf,, чтобы его ранг был наименьшим.

Приведем также определения сокращенной и тупиковой ДНФ c геометрической точки зрения.

Грань Nk, содержащаяся в Nf, называется максимальной относительно Nf, если не существует грани , такой, что

1)

2) размерность грани больше размерности грани Nk.

Пример 13. Пусть f(X1, Х2, X3) - функция, заданная табл. 4 и Тогда грани Нk1 и Nk3 являются максимальными, a Nk2 не максимальна для Nf, т. к. и размерность Nk3 больше размерности Nk2.

Конъюнкция К, соответствующая максимальной грани Nk, называется простой импликантой функции f.

ДНФ, являющаяся дизъюнкцией всех простых импликант функции f, называется сокращенной ДНФ.

Покрытие множества Nf, состоящее из максимальных относительно Nf граней, называется неприводимым, если совокупность граней, получающаяся из исходной путем выбрасывания любой грани, не будет покрытием Nf.

ДНФ, соответствующая неприводимому покрытию множества Nf называется тупиковой в геометрическом смысле.

Теорема. Понятия тупиковой ДНФ и тупиковой ДНФ в геометрическом смысле эквивалентны.

Алгоритм минимизации функций, зависящих от трех переменных, состоит в следующих четырех шагах:

Нанести множество Nf, на трехмерный куб. Использовать или табличное задание функции, отметив вершины, в которых f(X1, Ч2, Ч3) = 1, или СДНФ функции и тогда каждому слагаемому СДНФ поставить в соответствие вершину (см. раздел 5).

Если отмеченными окажутся все вершины куба, то данная функция тождественно истинна

Если отмечены все вершины какой-либо грани, то для построения минимальной формы заменить все четыре вершины одной переменной - названием грани.

Если отмечены вершины какого-либо ребра, то в минимизированной форме им соответствует конъюнкция - название ребра.

Чтобы получить минимизированную форму, надо выбирать ребра, покрывающие вершины, так, чтобы меньшим числом ребер покрыть все отмеченные вершины.

Пример 14. Минимизировать функцию f(X1, X2, Х3), заданную табл. 4.

Решение. Множество Nf для указанной функции изображено на рис. 3. Так как вершины 2, 4, 6, 8 принадлежат одной грани Ч1, вершины 7 и 8 принадлежат ребру, то минимизированная форма функции f имеет вид

.

Пример 15. Минимизировать записанную в СДНФ функцию

.

Решение. Отметим на модели куба элементарные конъюнкции: первой конъюнкции соответствует вершина 6, второй - вершина 5, третьей - вершина 8, четвертой - вершина 2 (рис 8). Таким образом, множество Nf -построено. Ни одна грань не отмечена полностью, поэтому переходим к шагу 4 алгоритма.

Рис. 8

Вершины 5 и 6 принадлежат одному ребру , вершины 6 и 8 - ребру , следовательно, минимизированная форма имеет вид:

.

Пример 16. Минимизировать функцию f(X1,X2,X3), заданную табл. 5.

Таблица 5

Х1

1

1

1

0

1

0

0

0

Х2

1

1

0

1

0

1

0

0

Х3

1

0

1

1

0

0

1

0

f(X1,X2,X3)

1

1

1

1

1

1

0

0

Решение. Построим модель куба, соответствующего этой функции (рис.9).

Рис. 9

Грани (1, 2, 3, 4) соответствует X2, грани (2, 4, 6, 8) - Х1, следовательно, минимизированная форма имеет вид

.

Отметим, что при n = 3 геометрический метод минимизации булевых функций аналогичен минимизации с помощью прямоугольной таблицы, называемой, минимизирующей картой (картой Карно).

Делись добром ;)