Материал: Дискретная математика. учебное пособие. Собенина О.В

_{СДНФ примет вид}

2. Произведем с СДНФ все возможные склеивания, а затем и поглощения:

Получили сокращенную СДНФ:

3. Перейдем от сокращенной СДНФ к минимальной, используя импликантную матрицу:

Достаточно оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один «+», поэтому вторую или четвертую строку в импликантной матрице можно отбросить. Данная булева функция имеет две различные минимизированные формы

_и .

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

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

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

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

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

Пусть f( ) — произвольная булева функция. Ей сопоставляется в соответствие подмножество вершин куба Е , таких что  тогда и только тогда, когда f =l. Очевидно, что по подмножеству исходная функция f( ) восстанавливается однозначно. Таким образом, геометрический способ задания булевой функции заключается в задании множества вершин п-мерного куба Е , в которых данная функция истинна.

Пример. Пусть функция f( ) задана таблицей истинности. Составить для нее множество .

Очевидно, что

N_f={(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0)(1,1,1)}. Множество можно изобразить следующим образом. Рассмотреть вершины трехмерного куба (или просто куба), каждой вершине поставить в соответствие набор из нулей и единиц. Для этого одну из вершин поместить в начало декартовой системы координат, при этом три вершины должны оказаться на координатных осях. Считая, что ребро куба равно единице, каждой вершине поставим в соответствие набор из нулей и единиц, соответствующий координатам вершины в декартовой системе. Для наглядного изображения геометрического представления булевой функции выделяют вершины куба, в которой функция принимает значение 1. На рис. 5.1 изображено геометрическое представление рассмотренной булевой функции.

Z

(0,0,1)

(0,1,1)

(1,0,1)

(1,1,1)

(0,0,0)

(1,0,0) (0,1,0 )

Y

X (1,1,0)

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

Для любой булевой функции существует ее представление в СДНФ. Причем в алгоритме построения СДНФ используются только те наборы значений, при которых функция равна единице. Это позволяет проинтерпретировать геометрическое представление функции следующим образом. Рассмотрим, например, ребро куба, представленное вершинами (1,0,0) и (1,0,1), им соответствуют элементарные конъюнкции и . Ребру (одномерному подкубу) соответствует формула .

Аналогично можно получить формулы, описывающие грани (двумерные подкубы). Например, описанию грани куба, представленной вершинами (1,0,0), (1,0,1), (1,1,0) и (1,1,1), соответствует формула . Описанию грани куба, представленной вершинами (0,0,0), (0,0,1), (0,1,0) и (0,1,1), соответствует формула .

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

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

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

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

K(X ,...,X_r)=X ... Х ,

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

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

K ( )=

К ( )=

К ( )= ,

соответствуют грани, имеющие ранги 2, 2, и 1. Первые две грани являются одномерной гранью (ребром), а третья - двумерной гранью.

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

Если f( ) = g( )  h( ), то

1) , ;

2)N_f = N_g N_h.

В частности, если f( ) обладает ДНФ, т. е.

f( )= , то и , т.е. ДНФ функции f соответствует покрытие множества N гранями N_k , ., N_ks