Використання операцій інтервального представлення

33.1.1. Покриття інтервалу об'єднанням інтервалів операцієй віднімання

Для використання операції «#» здійснюється віднімання з вихідного інтервалу елементів об'єднання інтервалів. Якщо після всіх віднімань є порожня множина, вихідний інтервал покривається об'єднанням інтервалів.

Приклад

Вихідний інтервал Задане об'єднання інтервалів

1 ~ 1 ~ 1 0 ~ 0

~ 1 1 0

1 1 ~ 1

~ 0 1 1

Послідовна процедура перевірки поглинання дає

1~1~ # 10~0 = 111~

1011

Таблиця 33.1

				X 2	x 2
			x 1	x 1
			·
	x3|		·	·
x4|	x3|		·	·
x4|

111~ # ~110 = 1111
1011 1011

Таблиця 33.2

				x 2	x 2
			x 1	x 1
	x3|			·	·
x4|	x3|		·	·
x4|

1111 # 11~1 = 1011

1011

Таблиця 33.3

				x 2	x 2
			x 1	x 1
	x3|
x4|	x3|		·	·
x4|				·

1011 # ~011 = Æ

Таблиця 33.4

				x 2	x 2
			x 1	x 1
	x3|
x4|	x3|	·	·
x4|

Інтервал 1~1~ поглинається заданим об'єднанням інтервалів.

33.1.2. Розширення інтервалу в заданому об'єднанні інтервалів до максимального

Ця процедура в загальному випадку неоднозначна й залежить від обраної послідовності розгляду зовнішніх змінних інтервалу:

1. Вибирається чергова зовнішня змінна розширюваного інтервалу.

2. Проводиться симетрування розширюваного інтервалу по обраної зовнішній змінній і перевірка поглинання симетрованого інтервалу заданим об'єднанням інтервалів.

3. Якщо симетрований інтервал поглинається, то в розширюваному інтервалі обрана змінна переводиться із зовнішніх у внутрішні, інакше не переводиться. Якщо ще не всі зовнішні змінні розглянуті, то перетворення виконується спочатку, інакше побудований розширюваний інтервал - максимальний.

Приклад

Вихідний інтервал Вихідне об'єднання інтервалів

1 0 1 ~ 1 0 1 ~

1 1 ~ 0

1 1 ~ 1

~ 1 ~ 1

Перевірка можливості розширення по змінній х₁:

001~ # 11~0 = 001~

001~ # ~1~1 = 001~ ¹ Æ

Таблиця 33.5

				x 2	x 2
			x 1	x 1
				·
	x3|		·	·
x4|	x3|		·	·	·
x4|				·	·

Перевірка можливості розширення по змінній х₂:

111~ # 11~0 = 1111

1111 # ~1~1 = Æ

Таблиця 33.6

				x 2	x 2
			x 1	x 1
				·
	x3|		·	·
x4|	x3|		·	·	·
x4|				·	·

Вихідний інтервал розширюється 1~1~.

Перевірка можливості розширення по змінній х₃:

1~0~ # 11~0 = 100~

1101

100~ # ~1~1 = 100~ ¹ Æ

Таблиця 33.7

				x 2	x 2
			x 1	x 1
				·
	x3|		·	·
x4|	x3|		·	·	·
x4|				·	·

Побудовано максимальний інтервал 1~1~.

Можлива неоднозначність розширення вихідного інтервалу до максимального.

Приклад. Вихідний інтервал Задане об'єднання інтервалів

1 0 0 1 ~ 1 0 0 1 0

1 ~ 0 0 0

0 0 0 ~ 0

~ 0 1 ~ 0

1 0 1 ~ 1

1 ~ 0 1 1

Таблиця 33.8

						x 3	x 3	x 3	x 3
				x 2	x 2	x 2	x 2
			x 1	x 1			x 1	x 1
		·	·	·				·	·
	x4|	·	·					·	·
x5|	x4|		·	·				·
x5|								·

Перша послідовність розгляду змінних х₁х₂х₃х₄х₅, друга – х₅х₄х₃х₂х₁. Нижче показані тільки ті перетворення, які приводять до розширень:

по х₁: 00010 # 000~0 = Æ, розширення ~0010;

по х₃: ~0110 # ~01~0 = Æ, розширення ~0~10;

по х₄: ~0~00 # 1~000 = 00~00

10100;

00~00 # 000~0 = 10100;

10100

10100 # ~01~0 = Æ, розширення ~0~~0.

Заміна інтервалу 10010 в об'єднанні інтервалів на розширений максимальний інтервал скорочує об'єднання інтервалів, забираючи поглинені інтервали.

Скорочене об'єднання інтервалів

~ 0 ~ ~ 0

1 ~ 0 0 0

1 0 1 ~ 1

1 ~ 0 1 1

Таблиця 33.9

						x 3	x 3	x 3	x 3
				x 2	x 2	x 2	x 2
			x 1	x 1			x 1	x 1
		·	·	·				·	·
	x4|	·	·					·	·
x5|	x4|		·	·				·
x5|								·

Для іншого варіанта розширення:

по х₅: 1001~ # 1~011 = Æ, розширення 1001~;

по х₃: 1011~ # ~01~0 = 10111

10111 # 101~1 = Æ, розширення 10~1~.

Заміна інтервалу 10010 в об'єднанні інтервалів на розширений максимальний інтервал 10~1~ до скорочення не приводить.

1 0 ~ 1 ~

1 ~ 0 0 0

0 0 0 ~ 0

~ 0 0 ~ 0

1 0 1 ~ 1

1 ~ 0 1 1

Таблиця 33.10

						x 3	x 3	x 3	х 3
				x 2	x 2	x 2	x 2
			x 1	x 1			x 1	x 1
		·	·	·				·	·
	x4|	·	·					·	·
x5|	x4|		·	·				·
x5|								·

33.1.3. Перевірка інтервалу на ядерність

Пошук ядерних інтервалів (екстремалей) дозволяє одержати більше компактне об'єднання інтервалів для булевої функції й навіть скоротити сам процес спрощення об'єднання інтервалів (спрощення ДНФ). При пошуку ядерного інтервалу за матричною формою використана така властивість: ядерний інтервал повинен містити хоча б один набір, всі сусіди якого перебувають теж у цьому інтервалі. За матричною формою, користуючись симетрією, досить перевірити сусідів точки, що розглядається.

Для векторного інтервального представлення змінюють правило перевірки: повинен бути в інтервалі хоча б один набір, для якого немає сусідів поза даним інтервалом.

Алгоритм перевірки інтервалу на ядерність такий:

1. Вибирається черговий інтервал і розширюється до максимального I (по будь-якого послідовності змінних), якщо максимальний інтервал буде ядерним, то він буде єдиним (об'єднання інтервалів дорівнює I).

2. Інтервал I симетруеться по черговій зовнішньої змінній й отриманий I^с Перерізається з кожним інтервалом об'єднання. Якщо перетин не порожньо, то результат перетин I^с_i = I^с Ç I_i симетруеться по розглянутій змінній і віднімається із симетрованого інтервалу. Така процедура виконується для всіх I_i, що належать об'єднанню інтервалів по всіх зовнішніх змінних інтервалу I. Якщо після виконання всіх перетворень I^с_i ¹ Æ, то інтервал I – ядерний, у ньому найшлися набори, що належать симетрованому інтервалу, які не мають сусідів поза інтервалом I.

Приклад. Нехай I = ~01~0. I розширюється до максимального:

по х₂ розширення неможна;

по х₃: ~00~0 # 000~0 =100~0

100~0 # 1~000 =10010

10010 # 10~1~ =(, розширення ~0~~0;

по х₅ розширення неможна.

I = ~0~~0 - це максимальний інтервал.

Скорочене об'єднання інтервалів

1 0 ~ 1 ~ I₁

1 ~ 0 0 0 I₂

~ 0 ~ ~ 0 I

1 0 1 ~ 1 I₃

1 ~ 0 1 1 I₄

Таблиця 33.11

						x 3	x 3	x 3	X 3
				x 2	x 2	x 2	x 2
			x 1	x 1			x 1	x 1
		·	·	·				·	·
	x4|	·	·					·	·
x5|	x4|		·	·				·
x5|								·

Зовнішні змінні інтервалу I = ~0~~0 – це х₂ і х₅.

Симетрований інтервал ~0~~0.

Вибирається змінна х₂: I^с = ~1~~0

I^с Ç I₂ = ~ 1 ~ ~ 0

1 ~ 0 0 0

1 1 0 0 0

Симетрований інтервал дорівнює

~0~~0 # 10000 = 0 0 ~ ~ 0

1 0 1 ~ 0

1 0 0 1 0

З іншими інтервалами I₁, I₃, I₄ перетини порожні.

Вибирається змінна х₅: I^с = ~0~~1

I^с Ç I₁ = ~ 0 ~ ~ 1

1 0 ~ 1 ~

1 0 ~ 1 1

Симетрований інтервал дорівнює

~0~~0 # 10~10 = 0 0 ~ ~ 0

101~0 1 0 1 0 0

10010

I^с Ç I₃ = ~ 0 ~ ~ 1

1 0 1 ~ 1

1 0 1 ~ 0

Симетрований інтервал дорівнює:

00~~0 # 101~0 = 0 0 ~ ~ 0

10100

I^с Ç I₄ = ~ 0 ~ ~ 1

1 ~ 0 1 1

1 0 0 1 1

Симетрований інтервал дорівнює:

00~~0 # 10010 = 0 0 ~ ~ 0

Набори інтервалу 00~~0 не мають сусідів поза інтервалом
I = ~0~~00, отже, інтервал I - ядерний.

33.1.4. Перевірка надмірності інтервалу в об'єднанні інтервалів

Якщо всі набори деякого інтервалу I, що входить в об'єднання інтервалів, покриваються сукупністю інших елементів об'єднання інтервалів, то інтервал I надлишковий і може бути вилучений. Перевірка надмірності зводиться до віднімання з I інших інтервалів й якщо різниця виявилася порожньою, то інтервал I - надлишковий.

Приклад. Нехай I =10~1~ в об'єднанні інтервалів надлишковий:

Для симетрованого інтервалу:

10~1~ # ~0~~0 = 1 0 ~ 1 1

10~11 # 101~1 = 1 0 0 1 1

10011 # 1~011 = Æ,

що доводить надмірність інтервалу I.

Скорочене об'єднання інтервалів

1 ~ 0 0 0

~ 0 ~ ~ 0

1 0 1 ~ 1

1 ~ 0 1 1

Таблиця 33.12

						x 3	x 3	x 3	X 3
				x 2	x 2	x 2	x 2
			x 1	x 1			x 1	x 1
		·	·	·				·	·
	x4|	·	·					·	·
x5|	x4|		·	·				·
x5|								·