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

В данной работе рассматривается задача минимизации частично определенных булевых функций. Решается вопрос о доопределении функции таким образом, чтобы она удовлетворяла исходным требованиям.

В некоторых прикладных задачах заданная булева функция может быть не определена на некоторых наборах. Если эти наборы в исследуемой задаче не будут играть никакой роли, то можно доопределить функцию на этих наборах таким образом, чтобы получить наиболее минимальную нормальную форму, т. е. форму, имеющую наименьшее число букв [1].

Рассмотрим, например функцию, заданную следующей последовательностью

01x111x011x010x0, где «х» означает, что функция на данном наборе значений не определена.

Доопределим данную функцию нулями [2]. Найдем минимальную дизъюнктивную нормальную форму (ДНФ). Сначала необходимо определить импликанты заданной булевой функции. Функция h = h ( Х р ..., х_п ) является импликантой функции f = f ( X p ..., х_п ) , если h принимает значение единицы лишь в тех точках (не обязательно во всех), в кото

рых значения f равны единице или не определены. Иначе говорят, что h заключает в себе f и записывают: h <  f .

Будем проводить минимизацию с помощью дерева декомпозиций [3]. Метод заключается в построении дерева всех 2к возможных декомпозиций функции f от к переменных и применении оператора л в каждом узле дерева. Нулевой уровень дерева — де композиция Dq = f. Первый уровень дерева будут составлять декомпозиции D4, D2, D3,

D 4 .	04044400	01011100
D 4	:      v 44004000 ; D2 :	v 11001000 ;
	д4 = 04004000 01111110	д2 = 01001000 00101010
D 3	:     v 01000000; D 4	:     v 11101000
	д3 = 01000000	д4 = 00101000

Второй уровень:

0400	0440
D42 :       v 4000 ; D13 :       v	0000 :
g 42   = 0000         g 43 =	0000
0040	0110
D44 :       v 4000 ; D23 :       v	0000
g 44 = 0000        g 23 =	0000
0010	0110
D24 :       V 1000; D 34 :       v	0000
g 24 = 00 00        g 34 =	0000

При последующем разложении все функции д будут равны QQ, поэтому нет необходимости построения третьего уровня. Получим 7 простых импликант: Х ₂ ^Х 3 Х 4 , х ₂ ^х 3 ^х 4 , ^Х 4 ^Х 3 ^Х 4 > ^ 4 X 3 X 4 , Х 4 Х 2 Х 4 , Х 2 Х 3 Х 4 , Х 2 Х 3 Х 4 .

Построим имплицентную таблицу:

	0001	0011	0100	0101	1000	1001	1100
x 2 X 3 X 4	*					*
x 2 X 3 X 4			*				*
Х 4 Х 3 Х 4	*			*
Х 4 Х 3 Х 4					*		*
Х 4 Х 2 Х 4	*	*
X 2 X 3 X 4			*	*
Х 2 Х 3 Х 4					*	*

Если в каком-либо столбце имеется только одна метка, то импликанта, стоящая в соответствующей строке, является существенной — без нее не может быть получено покрытие всего множества импликант данной функции. Она в любом случае войдет в минимальную форму, поэтому из дальнейшего рассмотрения можно исключить соответствующие ей столбцы и строки. После исключения таблица примет вид:

	0100	0101	1000	1001	1100
X 2 X 3 X 4				*
X 2 X 3 X 4	*				*
Х 4 Х 3 Х 4		*
Х 4 Х 3 Х 4			*		*
Х 2 Х 3 Х 4	*	*
Х 2 Х 3 Х 4			*	*

Из таблицы получим систему ограничений:

“ 2 + “ 5 >  ¹

“ 3 + “ 5 >  1.

^ “ 4 + “ g >  1

“ 1 + “ g >  1,

“ 2 + “ 4 >  1>

L — и + и 2 + U ₃ + U 4 + U g + U g .

Решив соответствующую задачу целочисленного программирования, определим, что в минимальную КНФ войдут 4-я, 5-я и g-я им-пликанты. Добавим исключенную ранее существенную импликанту и в итоге минимальная ДНФ будет иметь вид:

^ 1 ^ 3 ^ 4 V 5 2 X 3 X 4 V 5 2 X 3 X 4 V Х 1 Х ₂ Х 4 .

Теперь доопределим исходную функцию единицами [2] и построим дерево декомпозиций. Нулевой уровень дерева — декомпозиция D q = f. Первый уровень дерева будут составлять декомпозиции D \ , D 2 , D 3 , D 4 :

01111110             01111110

D₁ :      v 11101010 ; D₂ : v 11101010 ;

g_v = 01101010       g₂ = 01101010

01111110	01111111
D 3 :     v 11101010; D 4 : v	11101000
g3 = 01101010       g4 =	01101000
Второй уровень:
0110	0110
D 12 :        v 1010 ; D 13 :	v 1010 ;
g 12 = 0010         gV 3	= 0010
0111	0110
D 14 :       v 1000 ; D 23 :	v 1010 ;
g 14 = 0000         g 23	= 0010
0111	0110
D 24 :      v 1000; D 34 :	v 1000 .
g 24 = 0000         g 34	= 0000

Получим следующие простые импликан-ты: Х 2 Х 3 Х 4 , 5 3 X 4 , ^ 2 ^ 4 , 5 1 5 3 5 4 , 5 1 X 4 , 5 1 ^ 2 ^ 4 , 5 1 5 ₂ 5 3 , 5 1 5 2 ^ 3 , 5 1 5 2 ^ 3 .

Имплицентная таблица примет вид:

	0001	0011	0100	0101	1000	1001	1100
5 2 5 3 5 4	*					*
5 3 5 4
5 2 54			*				*
X 1 X 3 X 4	*			*
* 1 * 4					*		*
* 1 * 2 * 4	*	*
5 1 5 2 5 3		*
* 1 5 2 5 3			*	*
5 1 5 2 5 3					*	*

“ 2 + “ 4 + “ g >  1’

“ g + “ у >  1’

<

“ 4 + “ g

“ 5 + “ д

> 1

> 1’

“ 1 + “ д >  1.

“ 3 + “ 5 > ¹

L — М1 + М ₂ + М 3 + М 4 + М 5 + M g + М у + M g + М д .

Решив соответствующую задачу целочисленного программирования, определим, что минимальная ДНФ будет иметь вид:

5 1 5 2 5 4 V 5 1 5 2 5 3 V 5 1 5 3 5 3 V 5 ₂ 5 4 .

Таким образом, более простую минимальную ДНФ можно получить, если доопределить функцию единицами на всех неопределенных наборах. Из полученных данным способом импликант в минимальную форму необходимо включить только импли-

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

Важно отметить, что в некоторых задачах могут требоваться булевы функции определенного подкласса, например, линейные, однородные или симметричные. Поэтому в таких случаях целесообразно производить доопределение таким образом, чтобы исходная функция принадлежала необходимому подклассу. С помощью дерева декомпозиций можно проверить принадлежность функции к некоторым подклассам [2]. Например, симметричные функции могут быть синтезированы с использованием меньшего числа логических элементов, поэтому они играют важную роль в логическом синтезе и используются для построения эффективных электрических цепей. Симметричной называется такая булева функция, которая изменяет свое значение при перестановке любой пары переменных. Симметричные булевы функции и переменных могут быть представлены не таблицей истинности, а вектором с и + 1 значениями, где г-е значение равно значению функции на наборах, содержащих г единиц.

Проверим, является ли частично определенная булева функция 01x111x011x010x0, рассматриваемая выше, симметричной. Как доказано в работе [2], функция будет симметричной, если декомпозиции первого уровня будут одинаковы. Для рассматриваемой выше функции декомпозиции первого уров ня следующие:

01x111x0       01x111x0

D :           ; D :           ;

1 11x010x0    2 11x010x0

D3 :              ;

x1x0x0x0

Oxlxlxlx

Da :

4 11101000

Можно заметить, что декомпозиции будут одинаковыми, а значит, и функция будет симметричной, если ее доопределить следующим образом: 0111111011101000. В виде вектора ее можно представить так: (0, 1, 1, 0, 0). Несмотря на то что ее ДНФ будет содержать большее число букв, чем доопределен ная полностью единицами, запись в виде вектора будет даже меньше, чем в виде последовательности нулей и единиц собственных значений.