2015-06-28
216
Властивість симетрії дозволяє дати нове визначення інтервалу.
Визначення. Інтервал – це сукупність 2k елементів матричної форми, симетрично розташованих по k осях внутрішніх змінних у зоні їхньої дії.
Інтервал належить функції, якщо на всіх його елементах функція дорівнює одиниці для ДНФ (нулю для КНФ) або не визначена (для часткових функцій). Інтервал називається максимальним, якщо він належить функції, але при симетруванні його по кожній з осей зовнішніх змінних відбувається поглинання елементів, на яких функція дорівнює нулю для ДНФ (одиниці для КНФ).
Приклад. Максимальні інтервали з виділенням осей внутрішніх змінних, по яких елементи інтервалів становлять симетричну фігуру (табл. 29.6).
Таблиця 29.6
| x 3 | x 3 | ||||||||
| x 2 | x 2 | x 2 | x 2 | 
| |||||
| x 1 | x 1 | x 1 | x 1 | x 1 | x 1 | x 1 | x 1 | ||
| x4| |   ·
|  ·
|  ·
| · | |||||
| x5| | x4| |   ·
| · |  ·
| · | ||||
| x5| | x4| | 
| |||||||
| x4| |  ·
| · |  ·
| · |
Сукупність 22 елементів (табл. 29.7) не є інтервалом, тому що ця фігура не симетрична щодо осей симетрії елементів у зоні їхньої дії. Елементи, позначені «а», симетричні по осі х3, тому інші елементи, позначені «в», щоб формувати інтервал, повинні бути симетричні по цій же осі, але це не так. Елементи, позначені «в», симетричні по осі х2, тому елементи, позначені «а», повинні мати в інтервалі симетричні елементи по осі х2, але це також не так.
Таблиця 29.7
| x 3 | x 3 | ||||||||
| x 2 | x 2 | x 2 | x 2 |
| |||||
| x 1 | x 1 | x 1 | x 1 | x 1 | x 1 | x 1 | x 1 | ||
| x4| | 
| ||||||||
| x5| | x4| | 
| а·
|  а·
|  в·
| в· | |||
| x5| | x4| | ||||||||
| x4| |
На другому кроці виконується побудова максимальних інтервалів. Визначаються безлічі Xmпвп потенційно внутрішніх змінних для виділеного елемента m з безлічі М – змінних, по осях симетрії яких для вихідної точки симетрично розташовані сусідні точки або невизначені елементи (~). Потенційно внутрішні змінні так називаються, тому що вихідна точка може склеїтися, утворивши інтервал з кожним зі своїх сусідів, і тоді відповідна змінна стане внутрішньої. Не завжди все потенційно внутрішні змінні можуть одночасно бути внутрішніми в одному інтервалі.
Приклад.
У клітках матриці показане число сусідів для всіх точок. Безлічі Хпвп для: 11000 – х1, х3, х4, х5, 00010 – х1, х2, х3, 10110 – х1, х3, 10001 – х2, х3, 11001 – х1, х2, х3, х4, х5. Для точки 11000 чотири змінних потенційно внутрішні, але максимальні інтервали покриваючі цю точку, мають кожний внутрішніми тільки деяку підмножину цих змінних: для інтервалу ~1~0~ - x1, x3, x5,для інтервалу ~10~0 – х1, х4, для інтервалу 110~~ - х4, х5.
Таблиця 29.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 | ||||||
| 4· | 4· | 3· | 3· | ||||||
| x4| | 3· | 3· | 4· | 3· | 2· | 2· | |||
| x5| | x4| | 3· | 2· | ||||||
| x5| | 2· | 5· | 3· | 3· | 5· | 2· |
Для визначення максимальних інтервалів, що містять задану точку, знаходять максимально сумісні підмножини змінних множин Хпвп цієї точки.
У цьому пошуку використовується алгоритм граничного перебору на опуклій безлічі трансформуванням процедури перевірки сумісності змінних: змінні сумісні, якщо симетричний для них інтервал належить функції.
Контрольні запитання
1. Що таке послідовний позиційний код і код Грея?
2. Як будується матрична двовимірна форма?
3. Що розуміється під інтервалом?
4. Що називають зовнішніми й внутрішніми змінними?
5. Як являють інтервал у матричній формі?
6. Як визначаються осі й скільки їх може бути?
7. Які кроки є в спрощенні ДНФ за матричною формою Закревського?
8. Що називають максимальним інтервалом?
