 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Використання операцій інтервального представлення
|
|
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
Перевірка можливості розширення по змінній х1:
001~ # 11~0 = 001~
001~ # ~1~1 = 001~ ¹ Æ
Таблиця 33.5
| x 2 | x 2 | ||||
 x 1
| x 1 | ||||
| · | |||||
 x3|
| ·
| · | |||
| x4| | x3| | · | ·
| · | |
| x4| | · | · |
Перевірка можливості розширення по змінній х2:
111~ # 11~0 = 1111
1111 # ~1~1 = Æ
Таблиця 33.6
| x 2 | x 2 | ||||
| x 1
| x 1 | ||||
|
| · | ||||
| x3| |  ·
| · | |||
| x4| | x3| | · | · | · | |
| x4| | · | · |
Вихідний інтервал розширюється 1~1~.
Перевірка можливості розширення по змінній х3:
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| | · |
Перша послідовність розгляду змінних х1х2х3х4х5, друга – х5х4х3х2х1. Нижче показані тільки ті перетворення, які приводять до розширень:
по х1: 00010 # 000~0 = Æ, розширення ~0010;
по х3: ~0110 # ~01~0 = Æ, розширення ~0~10;
по х4: ~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| | · |
Для іншого варіанта розширення:
по х5: 1001~ # 1~011 = Æ, розширення 1001~;
по х3: 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с Ç Ii симетруеться по розглянутій змінній і віднімається із симетрованого інтервалу. Така процедура виконується для всіх Ii, що належать об'єднанню інтервалів по всіх зовнішніх змінних інтервалу I. Якщо після виконання всіх перетворень Iсi ¹ Æ, то інтервал I – ядерний, у ньому найшлися набори, що належать симетрованому інтервалу, які не мають сусідів поза інтервалом I.
Приклад. Нехай I = ~01~0. I розширюється до максимального:
по х2 розширення неможна;
по х3: ~00~0 # 000~0 =100~0
100~0 # 1~000 =10010
10010 # 10~1~ =(, розширення ~0~~0;
по х5 розширення неможна.
I = ~0~~0 - це максимальний інтервал.
Скорочене об'єднання інтервалів
1 0 ~ 1 ~ I1
1 ~ 0 0 0 I2
~ 0 ~ ~ 0 I
1 0 1 ~ 1 I3
1 ~ 0 1 1 I4
Таблиця 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 – це х2 і х5.
Симетрований інтервал ~0~~0.
Вибирається змінна х2: Iс = ~1~~0
Iс Ç I2 = ~ 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
З іншими інтервалами I1, I3, I4 перетини порожні.
Вибирається змінна х5: Iс = ~0~~1
Iс Ç I1 = ~ 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с Ç I3 = ~ 0 ~ ~ 1
1 0 1 ~ 1
1 0 1 ~ 0
Симетрований інтервал дорівнює:
00~~0 # 101~0 = 0 0 ~ ~ 0
10100
Iс Ç I4 = ~ 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| | · |
Дата публикования: 2014-11-18; Прочитано: 399 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
