Ф-ція f1 нам відома як сума за модулем 2 трьох змінних х1х2х3. Ф-ція f2 називається мажорантною (вона приймає значення, яке приймає більшість змінних) і позначається знаком М (х1, х2, х3)
Друга відома форма носить назву “досконалої кон'юктивної нормальної форми" (ДКНФ). Вона будується аналогічно ДДНФ.
Визначення: Конституєнтою нуля називається функція, яка приймає значення 0 на єдиному наборі.
Конституєнта нуля записується у вигляді елементарної диз'юнкції всіх змінних. Кожному набору відповідає своя конституєнта 0.
Приклад Для розглянутих вище ф-цій х1х2х3 і М (х1, х2, х3) (табл.7) побудуємо ДКНФ:
;
.
Легко побачити, що в ДДНФ можна замінити операцію диз'юнкції операцією суми за модулем 2, причому рівність збережеться. Ця форма називається “досконалою поліноміальною нормальною формою” (ДПНФ). Для нашого прикладу
Якщо в ДПНФ замінити всі змінні з запереченням у відповідності з співвідношенням =1х, то отримається канонічний поліном Жегалкіна вигляду
f (x1, x2, …, xn)
=a0a1x1a2x2…anxna12x1x2a13x13…a12…nx1x2…xn,
де аi {0,1}.
Приклад: Для тих же функцій f1 і f2 знайдемо канонічний поліном Жегалкіна:
f1= (x11) (x21) x3 (x11) x2 (x31) x1 (x21) (x31) x1x2x3= x1x2x3x3x1x3x2x3x1x2x3x1x2x2x3x1x2x3x1x2x2x3x2x1x2x3x1x2x1x3x1x1x2x3=x1x2x3
Аналогічно для f2= x1x2x2x3x1x3.
В булевій алгебрі широко використовується розклад Шеннона- формула, яка дозволяє перейти від представлення функції від n-змінних до представлення функції від (n-1) - змінних:
f (x1, x2, …, xn) =x1f (1, x2, …, xn) f (0, x2, …, xn)
Співвідношення легко узагальнюється для будь-якої кількості змінних, якщо функції правої частини піддати такому ж розкладу по інших змінних. Наприклад:
f (x1, x2, …, xn) =x1 [x2f (1,1, x3, …, xn) f (1,0, x3, …, xn)] [x2f (0,1, x3…xn) f (0,0,x3,…xn)] =x1,x2f (1,1,x3,…xn) x1f (1,0,x3,…,xn) x2f (0,1,x3,. .,xn) f (0,0,x3,…,xn)
Відмітимо, що якщо провести такий же розклад по всіх змінних, получиться ДДНФ.
x1 x2 x3 x4
F
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
1
0
Її ДДНФ має вигляд
f=
Для зручності помітимо кожну конституєнту одиниці з ДДНФ ф-ції f яким-небудь десятковим номером (довільно). Виконаємо склеювання. Конституєнта 1 склеюється тільки з конституєнтою2 (по змінній х3) і з конституєнтою 3 (по змінній х2), конституєнта 2 з конституєнтою 4. В результаті отримуємо
1-2: ; 3-4: ;
1-3: ; 4-6: ;
2-4: ; 5-6: .
Далі проводимо склеювання отриманих елементарних перетворень. Склеюються тільки ті перетворення, які містять одинакові змінні. Має місце два випадки склеювання:
=;
=,
з появою одного і того ж .
Подальші склеювання неможливі. Провівши поглинання, отримаємо скорочену ДНФ
Переходимо до наступного етапу. Для отримання мінімальної ДНФ необхідно забрати з скороченої ДНФ всі лишні прості імпліканти. Це робиться за допомогою спеціальної імплікантної матриці Квайна. Рядки такої матриці відмічаються простими імплікантами булевої ф-ції, тобто членами скороченої ДНФ, а стовбці - конституєнтами одиниці, тобто членами ДДНФ булевої ф-ції. Приклад (продовження). Імплікантна маириця має вигляд (табл.2)
Таблиця 2.
Прості імпліканти
Конституенти одиниці
x2 x3 x4
x1 x2 x3
Відповідна клітка імплікантної матриці на перетині рядка (з розглядуваною простою імплікантою) і стовбця (з конституєнт одиниці) відмічається хрестиком (табл.2). Мінімальні ДНФ будуються по імплікантній матриці наступним чином:
1. Шукаються стовбці матриці, які мають тільки один хрестик. Відповідні цим хрестикам прості імпліканти називаються базисами і складають так зване ядро булевої ф-ції. Ядро обов'язково входить в мінімальну ДНФ.
2. Розглядаються різні варіанти вибору сукупності простих імплікант, які накриють хрестиками решту стовбців матриці, і вибираються варіанти з мінімальним сумарним числом букв в такій сукупності імплікант.
Ядром нашої ф-ції є імпліканти x1x2x3. Імпліканта x2x3x4 -лишня. Тому ф-ція має єдину тупікову і мінімальну ДНФ:
1100
1101
1001
1000
1110
1111
1011
1010
0110
0111
0011
0010
0100
0101
0001
0000
Для приведених діаграм характерне наступне:
Кожній клітці діаграми відповідає свій набір.
Сусідні набори розміщені поряд в рядку або в стовбці.
Сусідніми наборами називають набори, які відрізняються однією компонентою.
Ще одне важливе зауваження: стовбці, розміщені по краях діаграми, також вважають сусідніми.
Загальне правило склеювання на діаграмі Вейча можна сформолювати таким чином: склеюванню підлягають прямокутні конфігурації, заповнені одиницями і які містять число кліток, що являються степінню 2. Отримане повне елементарне перетворення визначається як перетворення змінних, які не змінюють свого значення на всіх склеюваних наборах. Число m змінних, які залишились в елементарному перетворенні визначається легко:
m = n - log2M,
де n - число змінних функції; М - число склеюваних наборів. Метод широко використовується на практиці, завдяки простоті і зручності.
Мінімізація булевої ф-ції полягає в знаходженні мінімального накриття всіх одиниць діаграми Вейча блоками з одиниць (вказаної конфігурації), розміщених в сусідніх клітках діаграми. При цьому завжди вважають, що лівий край діаграми Вейча 4-х змінних прилягає до її правого краю, а верхній край діаграми - до її нижнього краю. Після отримання максимального покриття всіх одиниць діаграми Вейча, мінімальна ДНФ булевої функції записується як диз'юнкція елементарних кон'юнкцій, які відповідають виділеним блокам одиниць в діаграмі.
Приклад. Булева функція f має наступну ДДНФ:
Знайти мінімальну ДНФ з допомогою діаграми Вейча. Діаграма Вейча, що відповідає функції f, представлена в табл.18. Мінімальне накриття всіх одиниць діаграми можливе тільки блокамипо дві одиниці. Кожному такому блоку відповідає своя кон'юнкція, як показано в табл.22. Отже, мінімальна ДНФ ф-ції має вигляд:
Таблиця 18
Страницы: 1, 2, 3