2015-06-28
308
Інтервал у булевому просторі визначається як упорядкована сукупність наборів, задана мінімальним «Мін» і максимальним «Макс» наборами. [«Мін», «Макс»] – безліч наборів К, для яких «Мін»£К£«Макс». Тут £ - відношення порядку на безлічі векторів, для якого «Мін» £ «Макс», якщо для кожного компонента «Мін»i £ «Макс»i.
Приклад. Інтервал [0010, 0110] - це два набори 0010 й 0110, інтервал [0010, 1011] - це чотири набори 0010, 0011, 1010, 1011.
Змінні, що приймають однакові значення в «Мін», «Макс» наборах, мають однакове значення у всіх наборах до інтервалу, їх називають зовнішніми змінними. Інші змінні називають внутрішніми змінними, вони в кожному наборі інтервалу мають свій набір значень, що приймає в наборах інтервалу всі 2k значень, де k – число внутрішніх змінних.
Визначення. Інтервал – це сукупність 2k наборів, в яких 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-внутрішніх змінних визначає один з 2k внутрішніх наборів інтервалу. Для ДНФ у мінтермі інтервалу відповідає кон’юнкція зовнішніх змінних, зовнішня змінна входить у кон’юнкцію без інверсії, якщо в інтервалі їй відповідає 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(x1, x2, x3, x4) = x1`x2 Ú x1x3 Ú x2x4 Ú`x3x4
x1 x2 x3 x4
x1`x2 ~ 1 0 ~ ~
Таблиця 29.3
| x 2 | x 2 | ||||
| x 1 | x 1 | ||||
| · | |||||
| x3| | · | · | |||
| x4| | x3| | · | · | · | |
| x4| | · | · | · | · |
Приклад.
Для функції п'яти змінних ДНФ і матриця виглядають так:
f(x1, x2, x3, x4, x5) = `x1`x2x4 Ú x2`x5 Ú`x3x4x5 Ú`x1x4x5
Таблиця 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| | · | · | · | · |
