Інтервальне представлення в матричній формі

Інтервал у булевому просторі визначається як упорядкована сукупність наборів, задана мінімальним «Мін» і максимальним «Макс» наборами. [«Мін», «Макс»] – безліч наборів К, для яких «Мін»£К£«Макс». Тут £ - відношення порядку на безлічі векторів, для якого «Мін» £ «Макс», якщо для кожного компонента «Мін»_i £ «Макс»_i.

Приклад. Інтервал [0010, 0110] - це два набори 0010 й 0110, інтервал [0010, 1011] - це чотири набори 0010, 0011, 1010, 1011.

Змінні, що приймають однакові значення в «Мін», «Макс» наборах, мають однакове значення у всіх наборах до інтервалу, їх називають зовнішніми змінними. Інші змінні називають внутрішніми змінними, вони в кожному наборі інтервалу мають свій набір значень, що приймає в наборах інтервалу всі 2^k значень, де k – число внутрішніх змінних.

Визначення. Інтервал – це сукупність 2^k наборів, в яких n-k зовнішніх змінних приймають однакові для всіх наборів значення, k внутрішніх змінних – всі можливі набори значень змінних.

Приклад. x1 x2 x3 x4
0 0 1 0 Всі змінні зовнішні.
0 0 1 0 Змінна x2 – внутрішня
0 1 1 0 інші зовнішні.
0 0 1 0 Змінні х1 і х4 – внутрішні,
0 0 1 1 змінні х2 і х3 – зовнішні,
1 0 1 0 вони приймають на всіх чотирьох
1 0 1 1 наборах х2=0, х3=1.

Аналогічно операції склеювання кон’юнкцій можна проводити операцію склеювання наборів - склеюються два набори, якщо множини їх змінних збігаються, і значення тільки однієї змінної розрізняються. Результат склеювання двох наборів зображується у вигляді набору, у якого замість значення змінної, що розрізняє, проставлена тильда.

Приклад. 0010 й 0011 дають 001~, 0~10 й 0~11 дають 0~1~.

Набори інтервалу склеюються, після всіх склеювань виходить один набір, де зовнішні змінні приймають задані вихідні значення, а внутрішні змінні задані тильдою або рискою.

Приклад. 0010
0011 дають 001~

усе разом дають ~01~

1010
1011 дають 101~.

Тильда означає, що змінна може приймати значення 0 або 1, конкретний набір значень k-внутрішніх змінних визначає один з 2^k внутрішніх наборів інтервалу. Для ДНФ у мінтермі інтервалу відповідає кон’юнкція зовнішніх змінних, зовнішня змінна входить у кон’юнкцію без інверсії, якщо в інтервалі їй відповідає 1, з інверсією, якщо в інтервалі їй відповідає 0. Інтервальне представлення використається й для КНФ, різниця лише у відомому по главі 2 відповідності змінних й їхніх інверсій 0 й 1 у макстермах.

Приклад. Функції f(x1, x2, x3, x4) = x1`x2 Ú x1x3 Ú x2x4 Ú`x3x4 відповідає сукупність чотирьох інтервалів:

х1 х2 х3 х4
1 0 ~ ~
1 ~ 1 ~
~ 1 ~ 1
~ ~ 0 1

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

Приклад.

Для функції від чотирьох змінних ДНФ і матриця виглядають у такий спосіб: f(x₁, x₂, x₃, x₄) = x₁`x<sub>2</sub> Ú x<sub>1</sub>x<sub>3</sub> Ú x<sub>2</sub>x<sub>4</sub> Ú`x₃x₄

x₁ x₂ x₃ x₄

x₁`x₂ ~ 1 0 ~ ~

Таблиця 29.3

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

Приклад.

Для функції п'яти змінних ДНФ і матриця виглядають так:
f(x₁, x₂, x₃, x₄, x₅) = `x<sub>1</sub>`x₂x₄ Ú x₂`x<sub>5</sub> Ú`x₃x₄x₅ Ú`x₁x₄x₅

Таблиця 29.4

						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|		·			·	·			·