2015-06-28
300
Крім склеювання й поглинання, використаних дотепер для наборів векторного інтервального представлення, є ряд операцій, пов'язаних з інтерпретацією інтервалів, як сукупностей елементів булева простору.
Об'єднання інтервалів полягає в спільному розгляді інтервалів, у складанні списку інтервалів.
Визначення. Операція об'єднання інтервалів, що являють собою булеву функцію, інтерпретується як множина наборів, що покриті у цій сукупності інтервалів.
32.2.1. Дослідження ортогональності інтервалів
Визначення. Інтервали ортогональні, якщо вони не мають загальних елементів.
Набори ортогональних інтервалів розташовані в різних частинах булева простору, тобто повинна існувати хоча б одна зовнішня змінна цих інтервалів, загальна для них обох, що приймає значення нуль на елементах одного й одиницю - на елементах іншого.
Приклад
0 ~ 1 ~ 1
1 ~ 0 0 1
0 ~ 1 ~ 1
1 1 ~ ~ 1
Якщо інтервали не мають загальних зовнішніх змінних або якщо кожна з зовнішніх змінних приймає однакові значення для обох інтервалів, то ці інтервали перетинаються й не є ортогональними.
|
|
|
Приклад
1 ~ 0 0 1
1 1 ~ ~ 1
1 ~ 00 1
1 1 00 ~
Таблиця 32.1
| 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| | 
| · |  ·
| · | · | · |
32.2.2. Перетин інтервалів
Якщо інтервали не ортогональні, то їхні загальні елементи обов'язково утворюють інтервал.
Визначення. Операція перетинання неортогональних інтервалів, що являють собою булеву функцію, - це виділення інтервалу, утвореного всіма загальними елементами цих інтервалів.
У векторному представленні відбувається об'єднання множини зовнішніх змінних неортогональних інтервалів, що перетинаються.
Приклад
1 1 0 0 ~
1 1 ~ ~ 1
1 1 0 0 1
0 ~ 1 ~ 1
~ ~ 1 1 ~
0 ~ 1 1 1
32.2.3. Симетрування інтервалів
В алгоритмі побудови максимальних інтервалів для заданого елемента матричної форми використовувалася операція симетрування інтервалу по осі зовняшної змінної. У векторному представленні симетрування інтервалу по осі зовнішній змінної зводиться до інвертування значення цієї змінної.
Приклад
0 1 ~ ~ по х2 0 0 ~ ~
0 ~ 1 0 по х4 0 ~ 1 1
32.2.4. Склеювання й поглинання інтервалів
Обидві ці операції розглядалися у методі Квайна, нагадаємо їх.
Приклад
Склеювання:
0 ~ 1 0 ~
0 ~ 1 1 ~
0 ~ 1 ~ ~
Поглинання:
0 ~ 1 0 ~
0 1 1 0 ~
0 ~ 1 0 ~
32.2.5. Поглинання інтервалу об'єднанням інтервалу
Якщо всі набори інтервалу покриваються інтервалами заданого об'єднання інтервалів, то цей інтервал поглинається цим об'єднанням. У векторному інтервальному представленні це не очевидно й може бути отримане за рахунок розкладання інтервалу по внутрішніх змінних з перевіркою поглинання отриманих наборів інтервалами об'єднання.
|
|
|
Приклад. Шуканий інтервал 1 ~ 1 ~ і його:
розкладання об'єднання
1 0 1 0 1 0 ~ 0
1 0 1 1 ~ 1 1 0
1 1 1 0 1 1 ~ 1
1 1 1 1 ~ 1 1
Таблиця 32.2
| x 2 | x 2 | ||||
| x 1 | x 1 | |||
| · | ||||
| x3| |   ·
| · | · | ||
| x4| |  x3|
| · | · | · | |
| x4| | · |
Показано поглинання наборів об'єднанням, таким чином вихідний інтервал поглинається заданим об'єднанням.
Операція розкладання при великому числі внутрішніх змінних може привести до громіздкої множини наборів, цю операцію зручніше виконувати вирахуванням кубів.
32.2.6. Розширення інтервалу
Якщо при симетруванні по деякій зовнішньої змінної інтервалу результат поглинається іншими інтервалами об'єднання, то на заданому об'єднанні вихідний інтервал може бути розширений переводом розглянутої зовнішньої змінної у внутрішні. Правомірність розширення інтервалу в заданому об'єднанні перевіряється таким алгоритмом:
1. Вихідний інтервал симетрується по обраній зовнішній змінній.
2. Перевіряється, чи поглинається отриманий симетрований інтервал сукупністю інших інтервалів об'єднання.
3. Якщо результат перевірки позитивний, то інтервал розширюється, якщо ні, то розширення не відбувається.
Приклад. Розширення інтервалу 101~ по змінній х2:
Вихідне об'єднання Симетрований інтервал
1 0 1 ~ 101~ по змінної х2
1 1 ~ 0 1 1 1 ~
~ 1 ~ 1
Розкладання симетрованого інтервалу
1 1 1 0 1 1 ~ 0
1 1 1 1 ~ 1 ~ 1
Результат розширення
1 ~ 1 ~
1 1 ~ 0
~ 1 ~ 1
Таблиця 32.3
| x 2 | X 2 | ||||
 x 1
| x 1 | ||||
| 
| · | |||
| x3| |  ·
| · | |||
| x4| | x3| | · | · | ·ё | |
| x4| | · | · |
Інтервал 11~0 також допускає розширення по змінній х4.
32.2.7. Скорочення інтервалу
Якщо в кожнім об'єднанні при формуванні значення (0 або 1) обраної внутрішньої змінної для деякого вихідного інтервалу сукупність наборів, покритих інтервалами об'єднання, не змінюється, то таке фіксування припустиме й називається операцією скорочення інтервалу.
Приклад
Вихідне об'єднання Симетрований інтервал
1 0 1 ~ 101~ по змінної х2
1 1 ~ 0 1 1 1 ~
~ 1 ~ 1
Досліджуваний інтервал 1~1~, обрана змінна х2, обране значення 0, що скорочує інтервал 111~.
Результуюче об'єднання
1 0 1 ~
1 1 ~ ~
~ 1 ~ 1
Розкладання результуючого об'єднання
1 1 1 ~ 1 1 ~ ~
1 1 1 1
Таблиця 32.4
| x 2 | x 2 | ||||
| x 1
| x 1 | ||||
|
| 
| · | |||
| x3| | ·
| · | |||
| x4| | x3| | · | · | · | |
| x4| | · | · |
У вихідному інтервалі фіксується значення обраної змінної, інверсне заданому. Якщо отриманий інтервал поглинається сукупністю інших інтервалів об'єднання, то скорочення можна.
32.2.8. Віднімання інтервалу
Операція полягає в представленні покриття наборів зменшуваного інтервалу, не покритих інтервалом, що віднімають. Віднімання ортогонального інтервалу не приводить до зміни зменшуваного, віднімання поглинаючого інтервалу приводить до одержання порожньої різниці. У загальному випадку різниця не може бути покрита одним інтервалом.
Приклад
Таблиця 32.5
| x 2 | x 2 | ||||
| x 1 | x 1 | ||||
| · | · | |||
| x3| |  ·
| · | · | ||
| X4| | x3| | · | · | ||
| X4| | · | · |
При побудові різниці пересічних інтервалів розглядаються два варіанти операції віднімання:
- покриття різниці об'єднанням максимальних інтервалів „\”;
- покриття різниці об'єднання ортогональних інтервалів „#”.
Віднімання з одержанням покриття максимальними інтервалами
Якщо інтервали не ортогональні й від’ємник не поглинає зменшуваного, то виходить такий алгоритм:
|
|
|
1. Виділяється множина Хвнеш зовнішніх змінних інтервалу, що віднімається і не є зовнішніми змінними зменшуваного інтервалу, нехай таких змінних буде k.
2. Різниця представляється об'єднанням k інтервалів, кожний з яких виходить скороченням зменшуваного інтервалу по одній зі змінних множини Хвнеш зі значенням, інверсним її значенню в інтервалі, що віднімається.
Приклад. Об'єднання різниці
1~~~ \ ~110 = 1 0 ~ ~
1 ~ 0 ~
1 ~ ~ 1
Таблиця 32.6
| x 2 | x 2 | ||||
| x 1 | x 1 | ||||
 · 
|  ·
| ||||
| X3| |  ·
| · | · | ||
| x4| | X3| | · | · | ||
| x4| |  ·
| · |
Віднімання з одержанням покриття ортогональними інтервалами
Якщо аналогічно інтервали не ортогональні й від’ємник не поглинає зменшуваного, то виходить такий алгоритм:
1. Виділяється множина Хвнеш зовнішніх змінних інтервалу, що віднімається і не є зовнішніми змінними зменшуваного інтервалу, k = |Хвнеш|.
2. Різниця представляється об'єднанням k інтервалів, одержуваних у такій послідовності:
а) зменшуваний інтервал розглядається як поточний інтервал;
б) вибирається чергова змінна із множини Хвнеш і поточний інтервал скорочується по ній зі значенням цієї змінної, взятому з інтервалу, що віднімається, той інтервал симетрується по розглянутій змінній й у такий спосіб виходить черговий інтервал результату;
в) якщо ще не всі змінні множини Хвнеш розглянуті, виконується п. б).
Приклад. Об'єднання різниці
1~~~ # ~110 = 1 0 ~ ~
1 1 0 ~
1 1 1 1
Поточний інтервал
1 1 ~ ~
1 1 1 ~
1 1 1 0
Таблиця 32.7
| x 2 | x 2 | ||||
| x 1 | x 1 | ||||
 ·
| ·
| ||||
| X3| | ·
| · | · | ||
| x4| | X3| | · |  ·
| ||
| x4| |  ·
| · |
Таблиця 32.8
| x 2 | x 2 | ||||
| x 1 | x 1 | ||||
 ·
| · | ||||
| x3| | 
|  ·
| · | · | |
| x4| | x3| | · | · | ||
| x4| | · | · |
Різні послідовності розгляду змінних множини Хвнеш приводять і к різним результатам – для послідовності х2х3х4 результат представлений у табл. 32.7, для послідовності х4х3х2 – у табл. 32.8.
32.2.9. Побудова мінімального покриваючого інтервалу для заданого об'єднання інтервалів
|
|
|
Мінімальний покриваючий інтервал містить всі набори заданого об'єднання інтервалів і має можна менше число внутрішніх змінних. Мінімальний покриваючий інтервал може містити набори, що не належать покриваючим інтервалам (табл. 32.9, 32.11). У побудови мінімального покриваючого інтервалу інтервал сукупності поширюють по зовнішніх змінних, що мають інше значення в інших інтервалах.
Приклад
а) 1 ~ 0 1
1 1 ~ ~
1 ~ ~ ~
Таблиця 32.9
| x 2 | x 2 | ||||
| x 1 | x 1 | |||
  ·
| ·
| ||||
| x3| | · | ||||
| x4| | x3| | · | |||
| x4| |  ·
| · |
б) 1 0 ~ 0
1 0 1 ~
1 0 0 1
1 0 ~ ~
Таблиця 32.10
| x 2 | x 2 | ||||
 x 1
| x 1 | ||||
  ·
| |||||
| x3| | · | ||||
| x4| | x3| | · | |||
| x4| |  ·
|
в) 1 0 1 ~
1 0 0 1
0 0 0 1
~ 0 ~ ~
Таблиця 32.11
| x 2 | x 2 | ||||
| x 1 | x 1 | ||||
|
| ||||
| x3| | · | ||||
| x4| | x3| | · | |||
| x4| |  ·
| ·
|
Контрольні запитання
1. Як описують системи булевих функцій?
2. Які алфавіти використовуються для опису систем повністю визначених булевих функцій?
3. Які алфавіти використовуються для опису систем не повністю визначених булевих функцій?
4. Як інтерпретується операція об'єднання інтервалів?
5. Які інтервали називають ортогональними?
6. Що є перетином неортогональних інтервалів?
7. Які особливості симетрування інтервалу у векторному представленні на відміну від матричного представлення?
8. Що розуміється під склеюванням і поглинанням інтервалів?
9. Як виконується поглинання інтервалу об'єднанням інтервалів?
10. Як виконується розширення інтервалу у вихідному об'єднанні?
11. Як перевіряється розширення інтервалу у вихідному об'єднанні?
12. Як виконати скорочення інтервалу?
13. Які варіанти віднімання інтервалу можливі?
14. Як виконується кожний з варіантів вирахування інтервалу?
15. Як побудувати мінімальний покриваючий інтервал для заданого об'єднання інтервалів?
