Лекції з Дискретної математики - Лекція 5
Носій елементарної кон'юнкції рангу R називатимемо інтервалом рангу R. Інтервал рангу R містить 2N-R векторів. N – кількість аналізованих векторів. Інтервал – носій елементарної кон'юнкції.
Теорема Носій диз'юнкції двох функцій дорівнює об'єднанню носіїв цих функцій. Доказ. f V g f() V g() = 1 f() = 1 АБО g() = 1 f АБО g ч.т.д. Носій ДНФ є об'єднанням інтервалів. Допустимим інтервалом для цієї функції називається інтервал, який цілком міститься в носії цієї функції. Nf = I1 V I2 V … V Ik Інтервал для даної функції є максимальним, якщо він не міститься в жодному іншому допустимому інтервалі. Елементарна кон'юнкція, носієм якої є допустимий інтервал, називається імплікантою. ЕК, N – максимальний інтервал – проста імпліканта. Подання носія у вигляді поєднання максимальних інтервалів називатимемо покриттям носія максимальними інтервалами. Диз'юнкція всіх можливих простих імплікантів називається скороченою ДНФ функції. Покриття носія інтервалами називатимемо непривідним, якщо жоден не можна відкинути з правої частини рівності, не порушивши цієї рівності. ДНФ, яка відповідає неприводимому покриттю, називається тупиковою ДНФ. Твердження. Мінімальна ДНФ міститься серед тупикових ДНФ. Визначення Максимальний інтервал називається ядровим, якщо він містить хоча б одну вершину з носія функції, яка не належить більше жодному іншому максимальному інтервалу. Елементарна кон'юнкція, що відповідає ядровому інтервалу - ядерна імпліканта. Об'єднання всіх ядрових інтервалів – ядро функції. Диз'юнкція всіх ядерних імплікантів - ядерна ДНФ. Ядро функціїобов'язково входить у будь-яке покриття.
Алгоритм отримання мінімальної ДНФ. 1. Виділяємо носій функції. 2. Виділяємо усі можливі інтервали. 3. Виписуємо усі прості імпліканти. 4. Виділяємо ядровий інтервал. 5. Використовуючи ядро функції та комбінацію неядрових інтервалів, отримуємо всі ненаведені покриття, для кожного з яких виписуємо тупикову ДНФ. 6. Серед тупикових ДНФ вибираємо мінімальну.
Виділення всіх можливих інтервалів. 1. Для булева куба розмірності 3 інтервалом рангу 1 можуть бути 4 вершини, що лежать в одній грані. 2. Ранга 2 – будь-які 2 вершини, з'єднані рубом. 3. Ранг 3 – будь-яка окрема вершина.
1. Ні _ 2. I1 = < 001011>П1 = x1x3 - ядровий I2 = < 011 111>П2 = x2x3 Якщо координата вектора змінює значення, то змінна не входить I3 = < 111110>П3 = x1x2 _ I4 = < 110 100 П4 = x1x3
Dскор. = П1 V П2 V П3 V П4
Nf = I1 U I4 U I2 (U – об'єднання) Отримали непривідне покриття, додавши до ядра відсутні інтервали так, щоб усі одиничні вершини були задіяні. D1= П1 V П4 V П2 Nf = I1 U I4 U I3 D2= П1 V П4 V П3 Порахуємо ранги тупикових ДНФ R1 = 6 R2 = 6
Метод карт Карно для знаходження мінімальної ДНФ n = 4 Карта Карно – площинна інтерпретація 4-мірного булева куба.
Вважаємо, що лівий край склеєний із правим, а верхній – із нижнім. Якщо таблицю Карно згорнути таким чином, то вийде тор (torus - геометрична фігура, що нагадує бублик).
Правила пошуку інтервалів. 1. Інтервалом рангу 1 можуть бути 2 сусідні рядки (2 сусідні стовпці) 2. Інтервалом рангу 2 може бути весь рядок, весь стовпець або квадрат 2х2. 3. Інтервалом рангу 3 – будь-які 2сусідні по горизонталі та вертикалі клітини. 4. Одна окремо взята вершина буде інтервалом рангу 4. Алгоритм – той самий.