Недоопределенных БФ методом проб.

 

Будем полагать, что БФ задана таблично кодами конъюнкций D ₁ и D ₀.

Любая конъюнкция К из D ₁ такова, что:

1) M ₁ (К) Ç M ₁ (F) ¹ Æ -конъюнкция К из множества М1 входит в множество М₁(F).

2) M ₁ (К) Ç M ₀ (F) = Æ -конъюнкция К из множества М1 не входит в множество М₀(F). Нет такого набора значений переменных, на котором БФ одновременно определяется равной и 1 и 0.

Если максимально укоротить конъюнкцию К так, чтобы условия 1) и 2) попрежнему выполнялись, то мы получим простую импликанту.

Выполнимость условия 1) вытекает из того, что если К* получена из К вычеркиванием букв, то M ₁ (К*) É M ₁ (К).

Доказательство.

Если переменная в конъюнкции К вызывает вхождение в M ₁ (К) наборов со значением Х равным b, то вычеркивая Х, мы увеличим M ₁ (К) за счет наборов с противоположным значением (1 - b).

 

Рассмотрим пример.

Пусть F = (X,Y,Z,W). K = K* =

Тогда M ₁ (К) = (0101,0111).

M ₁ (K*) содержит наборы M ₁ (К) и кроме того наборы (1101,1111).

 

Процедура построения ДНФ эквивалентной D ₁, но состоящей из простых импликант может быть такой:

1. Берем любую К конъюнкцию из D ₁.

2. Максимально укорачивая К, строим простую импликанту и выписываем ее.

3. Удаляем из D ₁ конъюнкции поглощаемые К.

4. Если D ₁ пусто кончаем, иначе идем к пункту 1.

 

Примечание.

Конъюнкция А поглощает конъюнкцию В, если константные значения кода А, тоесть все значения кроме «-», входят составной частью в код В.

 

Рассмотрим пример.

А = (- 0 0 -);

В = (- 0 0 1);

Удаляя из К одну за другой буквы, мы должны проверять не нарушается ли условие 2).

Если нарушается, то букву восстанавливаем, если нет, то оставляем удаленной.

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

Проверка 2) выполняется так.

После вычеркивания буквы, берется код К и поочередно сравнивается со всеми кодами конъюнкций D ₀. Если для любой пары сравниваемых кодов хотя бы в одном разряде значения противоположны (0 и 1), то нет набора, на котором К и D ₀ одновременно равны «1», а значит можно вычеркивать данную переменную.

В противном случае, вычеркнутая (пробно!) буква должна быть восстановлена, так как ее удаление приводит к нарушению условия 2).

 

Процедуру построения ДНФ из простых импликант проиллюстрируем примером.

 

X	Y	Z	W	F
			-
		-
	-
-
-	-
		-

D ₁ =

D ₀ =

Берем из D ₁ первую конъюнкцию: (можно было бы взять и другую) и начинаем пробные вычеркивания букв.

(000 -)

?

(- 00 -)

Если конъюнкция (код - 00 -) такова, что М ₁ () Ç М ₀ (F_~) ¹Æ, то тогда есть набор, который можно получить по коду (- 00 -) и одновременно по коду хотя бы одной конъюнкции из D ₀.

Так как код (- 00 -) ортогонален каждому коду из D ₀, то набора принадлежащего и М ₁ () и М ₀ (F_~) не существует.

Ортогональность - наличие противоположных значений 0/1 хотя бы в одном разряде кодов.

Действительно:

 

(	-			-	)
(	-	-			)
(	-			-	)
(			-		)
(	-			-	)
(				-	)

 

Отсюда имеем первое укорачивание и переход к следующему пробному вычеркиванию.

(000 -)

(- 00 -)

?

(-- 0 -)

 

Вычеркивание недопустимо, так как (-- 0 -) не ортогонально с (11 - 1). Отсюда следует, что набор 1101 принадлежит и М ₁ и М ₀, а этого быть не может. Следовательно, вычеркивание невозможно и нужно новое пробное вычеркивание. Восстанавливаем вычеркнутую букву.

Пробуем вычеркнуть

(- 00 -)

?

(- 0 --)

Вычеркивание недопустимо, так как (- 0 --) не ортогонально с (--11). Отсюда следует, что набор 0011 принадлежит и М ₁ и М ₀, а этого быть не может. Следовательно, вычеркивание невозможно.

В итоге мы получили .

Константные значения кода (- 00 -), то есть все значения кроме «-», входят составной частью в коды (000 -) и (- 000). Следовательно, эта конъюнкция поглощает конъюнкции .

После выполнения поглощения, мы получим следующую таблицу:

X	Y	Z	W	F
		-
	-
-	-
		-
			-

 

Берем код 00-0 и выполняем пробное вычеркивание -0-0. Теперь выполним проверку на ортогональность с наборами из М₀.

 

-

-

-

-

-

-

-

-

-

-

Так как код (- 0-0) ортогонален каждому коду из D ₀, то набора принадлежащего и М ₁ () и М ₀ (F_~) не существует. Вычеркивание возможно.

Далее, попытаемся вычеркнуть следующую букву в коде -0-0. Выполним проверку на ортогональность с наборами из М₀ кода ---0.

 

-

-

-

-

-

-

-

-

-

-

-

-

-

 

Вычеркивание недопустимо, так как (---0) не ортогонально с (111-). Отсюда следует, что набор 1110 принадлежит и М ₁ и М ₀, а этого быть не может. Следовательно, вычеркивание невозможно и буква восстанавливается.

Теперь, попытаемся вычеркнуть другую букву в коде -0-0. Выполним проверку на ортогональность с наборами из М₀ кода -0---.

 

-

-

-

-

-

 

Вычеркивание недопустимо, так как (-0--) не ортогонально с (0011). Отсюда следует, что набор 0011 принадлежит и М ₁ и М ₀, а этого быть не может. Следовательно, вычеркивание невозможно.

Таким образом, получаем уще одну простую импликанту , которая поглощает конъюнкцию .

В результате, у нас остается ода конъюнкция из М₁.

 

X	Y	Z	W	F
	-
-	-
		-
			-

Берем оставшийся код 0-00 и выполняем пробное вычеркивание --00. Теперь выполним проверку на ортогональность с наборами из М₀.

-

-

-

-

-

-

-

-

-

-

Так как код (- 0-0) ортогонален каждому коду из D ₀, то набора принадлежащего и М ₁ () и М ₀ (F_~) не существует. Вычеркивание возможно.

Дальнейшие пробные вычеркивания выполняются аналогично.

В итоге получаем F_~= .

 

Рассмотрим еще один пример.

X	Y	Z	W	F~

Берем из D ₁ первую конъюнкцию: и начинам ее укорачивать. Будем работать не с конъюнкциями, а с их кодами.

0 0 0 1
- 0 0 1	Все коды из D0 ортогональны
- - 0 1	Нельзя, так как в как в D0 есть код 0101
- 0 0 1	Восстанавливаем вычеркнутую переменную
- 0 - 1	Нельзя, так как в как в D0 есть код 0011
- 0 0 1	Восстанавливаем вычеркнутую переменную
- 0 0 -	Все коды из D0 ортогональны	Эта конъюнкция поглощает 0001 и 1001 из D1

Берем из D ₁ следующую конъюнкцию: и начинам ее укорачивать. Будем работать не с конъюнкциями, а с их кодами.

 

0 0 1 0
- 0 1 0	Все коды из D0 ортогональны
- - 1 0	Все коды из D0 ортогональны
- - - 0	Все коды из D0 ортогональны	Эта конъюнкция поглощает 0010 и 0110 из D1

 

Множество D ₁ = Æ.

В результате получается F_~=