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

При решении задачи минимизации булевых функций часто используют алгоритмы, основанные на геометрическом представлении функций алгебры логики. Пусть Eⁿ – обозначает множество всех вершин n – мерного единичного куба. Каждой булевой функции f(x₁, x₂,…, x_n) взаимно-однозначно соответствует подмножество N_f  Eⁿ таких вершин  Eⁿ , что f()=1, где =(₁, ₂,…,_n) и _i  {0, 1}.

Пример:

x	y	z	f(x,y,z)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0
Таблица 24

П усть функция трех переменных f(x, y, z) задана таблицей 24.

Изобразим трёхмерный единичный куб и отметим на нем те вершины, на которых функция принимает единичные значения. Множество единичных вершин составляет: N_f ={(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0)}

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

Пусть K_i = x_i1^s1 & x_i2^s2 &…& x_ir^sr – элементарная конъюнкция ранга r, тогда множество N_ki Í Eⁿ, составленное из таких вершин a=(s₁,…,s_r, a_r+1,…,a_n), что K_i(a)=1, называется интервалом ранга r или (n-r)–мерной гранью единичного куба Eⁿ.

Пример:

Рассмотрим E³– трехмерный единичный куб.

а) K =. Тогда N_К = {(0,0,0)} – интервал 3-го ранга или 0-мерная грань (вершина куба);

б) K =. Тогда N_К = {(0,0,0),(1,0,0)} – интервал 2-го ранга или одномерная грань (ребро трехмерного единичного куба);

в) K =. Тогда N_К = {(0,0,0),(0,0,1),(0,1,0),(0,1,1)} – интервал 1-го ранга или двумерная грань (сторона трехмерного единичного куба);

Очевидно, что для каждого интервала N_К всегда можно написать соответствующую конъюнкцию K, причем единственным образом.

Говорят, что система интервалов {N_К1, N_К2,…, N_Кm} образует покрытие множества N Í Eⁿ, если N = N_К1 N_К2… N_Кm. Так как равенства f = K₁ Ú K₂ Ú…Ú K_m и N_f = N_К1 N_К2… N_Кm эквивалентны, то задача минимизации булевой функции f равносильна отысканию покрытий, сумма рангов интервалов которых минимальна. Такие покрытия называются минимальными.

Пример:

Для функции, заданной таблицей 24, составим следующие покрытия:

а) N_f = {(0,0,1)}  {(0,1,0)}  {(0,1,1)}  {(1,0,0)}  {(1,0,1)}  {(1,1,0)} – из интервалов 3-го ранга. Ранг покрытия составляет 3·6=18. Этому покрытию соответствует СДНФ данной функции:

б) N_f = {(0,0,1),(0,1,1)}  {(0,1,0),(0,1,1)}  {(0,1,0),(1,1,0)}    {(1,1,0),(1,0,0)}  {(1,0,0),(1,0,1)}  {(1,0,1),(0,0,1)} – из интервалов второго ранга. Ранг этого покрытия равен 2·6=12. ДНФ, соответствующая этому покрытию, равна . Как нетрудно заметить, для записи конъюнкции по интервалу используются не изменяющиеся на этом интервале координаты.

в) N_f = {(0,1,0),(0,1,1)}{(0,0,1),(0,1,1)}{(1,0,0),(1,0,1)}{(1,1,0),(1,0,0)} – из интервалов второго ранга. Ранг покрытия равен 2·4=8. Соответствующая ДНФ: .

г) N_f = {(0,0,1),(0,1,1)}{(0,1,0),(1,1,0)}{(1,0,0),(1,0,1)} – из интервалов 2‑го ранга. Ранг покрытия равен 2·3=6. И соответствующая ДНФ равна .

В рассматриваемом примере можно указать и другие покрытия N_f, составленные из интервалов 3–го ранга (вершин куба) и интервалов 2–го ранга (ребер), или состоящие только из интервалов 2–го ранга, но отличные от покрытий, приведенных в пунктах в) и г). Среди всех покрытий N_f – покрытия 6–го ранга являются минимальными.

Интервал N_К называется максимальным для функции f, если N_К  N_f и не существует интервала N_К1 такого, что N_К  N_К1 N_f. Конъюнкция K, соответствующая максимальному интервалу N_К функции f, называется простой импликантой для f. Удаление любого множителя из простой импликанты приводит к конъюнкции K¹ такой, что интервал N_К1 не содержится в покрытии N_f.

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

Для функции f(x,y,z) из предыдущего примера максимальными будут все интервалы 2–го ранга (ребра куба), т.к. ни в одно покрытие N_f не входят интервалы 1–го ранга (грани куба), которые могли бы содержать в себе какие–нибудь из этих ребер. Понятно также, что ни один из интервалов 3–го ранга (вершины куба) не будет максимальным для этой функции, т.к. для любого из них можно указать интервал 2–го ранга (ребро) из N_f, включающий в себя данную вершину. Поэтому покрытие, приведенное в пункте б) является сокращенным, а соответствующая ему ДНФ – является СокрДНФ.

Тупиковым ДНФ соответствуют так называемые неприводимые покрытия, которые получаются из сокращенного покрытия путем удаления некоторых максимальных интервалов. При этом никакое собственное подмножество интервалов из неприводимого покрытия уже не будет являться покрытием для функции f.

П окрытия в) и г) из предыдущего примера являются неприводимыми для функции, заданной таблицей 24, а соответствующие им ДНФ – тупиковыми. Графическое изображение покрытий в) и г) представлено на рис. 3 и 4 соответственно.

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

На рис. 5 представлено неприводимое покрытие:

N_f={(0,1,0),(0,1,1)}{(0,1,0),(1,1,0)}{(0,0,1),(1,0,1)}

{(1,0,0),(1,0,1)}. Соответствующая ТДНФ равна

На рис. 6 представлено неприводимое покрытие:

N_f={(0,1,0),(1,1,0)}{(1,0,0),(1,1,0)}{(0,0,1),(0,1,1)}

{(0,0,1),(1,0,1)}. Соответствующая ТДНФ равна

На рис. 7 представлено неприводимое покрытие:

N_f={(0,1,0),(0,1,1)}{(1,0,0),(1,1,0)}{(0,0,1),(1,0,1)}

Соответствующая ТДНФ равна . Эта ДНФ является также и минимальной.

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