Ф-ція 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)

Відмітимо, що якщо провести такий же розклад по всіх змінних, получиться ДДНФ.

Мінімізація булевих функцій

При проектуванні цифрових машин широко використовуються методи мінімізації булевих функцій, які дозволяють отримати рекомендації для побудови економічних схем цифрових машин. Загальна задача мінімізації булевих функцій формулюється так: знайти аналітичне вираження булевої функції в формі, що містить мінімально можливе число букв. Слід відмітити, що в загальній постановці дана задача поки що не розв'язана, але достатньо добре досліджена в класі диз'юнктивно-кон'юктивних нормаьних форм.

Визначення: Елементарною кон'юнкцією називається кон'юнкція кінцевого числа різних між собою булевих змінних, кожна з яких може мати, або не мати заперечення.

Визначення: Диз'юнктивною нормальною формою (ДНФ) називається диз'юнкція елементарних кон'юнкцій.

Визначення: Мінімальною диз'юнктивною нормальною формою булевої функції називається ДНФ, що містить найменше число букв.

Визначення: Булева функція g (x1,x2,…,xn) називається імплікантою булевої функції f (x1,…,xn), якщо для будь-якого набору змінних, на якому g=1, справедливе f=1.

Визначення: Імпліканта g булевої ф-ції f, що є елементарною кон'юнкцією, називається простою, якщо ніяка частина імпліканти g не є імплікантою функції f.

Приведемо без доведень два твердження, корисні при отриманні мінімальної ДНФ.

Дизьюнкція будь-якої кількості імплікант булевої ф-ції f також є імплікантою цієї функції.

Будь-яка булева функція f еквівалентна диз'юнкції всіх своїх простих імплікант. Така форма представлення булевої ф-ції називається скороченою ДНФ.

Отримання скорочених ДНФ є першим етапом відшукання мінімальних форм булевих функцій. В скорочену ДНФ входять всі прості імпліканти булевої функції. Іноді з скороченої ДНФ можна забрати одну, або декілька простих імплікант, не порушуючи еквівалентності початкової функції. Такі прості імпліканти називаються лишніми. Виключення лишніх простих імплікант з скорочених ДНФ - другий етап мінімізації.

Визначення: Скорочена ДНФ булевої ф-ції називається тупіковою, якщо в ній відсутні лишні прості імпліканти.

Виключення лишніх простих імплікант в скорочених ДНФ булевої функції не є однозначним поцесом, тобто булева функція може мати декілька тупікових ДНФ.

Твердження. Тупікові ДНФ булевої функції f, що містять мінімальну кількість букв, являються мінімальними. Мінімальних ДНФ також може бути декілька.

Розглянемо декілька методів мінімізації. Всі вони практично відрізняються тільки на першому етапі - етапі отримання скорочених ДНФ. Слід відмітити, що, на жаль, пошук мінімальної ДНФ завжди зв'язаний з деяким перебором рішень. Існують методи зменшення цього перебору, проте він завжди залишається.

Метод квайна оснований на використанні двох основних співвідношень:

Співвідношення склеювання:

AxA=A,

де А - любе елементарне походження.

Співвідношення поглинання:

АА=А, {x, }.

Справедливість обидвох співвідношень легко перевіряється. Суть методу в послідовному виконанні всіх можливих склеювань і потім всіх поглинань, що приводять до скороченої ДНФ.

Приклад. Нехай є булева ф-ція, задана таблицею істиності (табл.1).

Таблиця 1

Її ДДНФ має вигляд

f=

Для зручності помітимо кожну конституєнту одиниці з ДДНФ ф-ції f яким-небудь десятковим номером (довільно). Виконаємо склеювання. Конституєнта 1 склеюється тільки з конституєнтою2 (по змінній х3) і з конституєнтою 3 (по змінній х2), конституєнта 2 з конституєнтою 4. В результаті отримуємо

1-2: ; 3-4: ;

1-3: ; 4-6: ;

2-4: ; 5-6: .

Далі проводимо склеювання отриманих елементарних перетворень. Склеюються тільки ті перетворення, які містять одинакові змінні. Має місце два випадки склеювання:

=;

=,

з появою одного і того ж .

Подальші склеювання неможливі. Провівши поглинання, отримаємо скорочену ДНФ

.

Переходимо до наступного етапу. Для отримання мінімальної ДНФ необхідно забрати з скороченої ДНФ всі лишні прості імпліканти. Це робиться за допомогою спеціальної імплікантної матриці Квайна. Рядки такої матриці відмічаються простими імплікантами булевої ф-ції, тобто членами скороченої ДНФ, а стовбці - конституєнтами одиниці, тобто членами ДДНФ булевої ф-ції. Приклад (продовження). Імплікантна маириця має вигляд (табл.2)

Таблиця 2.

Відповідна клітка імплікантної матриці на перетині рядка (з розглядуваною простою імплікантою) і стовбця (з конституєнт одиниці) відмічається хрестиком (табл.2). Мінімальні ДНФ будуються по імплікантній матриці наступним чином:

1. Шукаються стовбці матриці, які мають тільки один хрестик. Відповідні цим хрестикам прості імпліканти називаються базисами і складають так зване ядро булевої ф-ції. Ядро обов'язково входить в мінімальну ДНФ.

2. Розглядаються різні варіанти вибору сукупності простих імплікант, які накриють хрестиками решту стовбців матриці, і вибираються варіанти з мінімальним сумарним числом букв в такій сукупності імплікант.

Ядром нашої ф-ції є імпліканти x1x2x3. Імпліканта x2x3x4 -лишня. Тому ф-ція має єдину тупікову і мінімальну ДНФ:

Метод квайна-мак-класкі

Метод представляє собою формалізований на етапі знаходження простих імплікант метод Квайна. Формалізація проводиться таким чином:

Всі конституанти одиниці з ДДНФ булевої функцію f записуються їх двійковими номерами.

Всі номери розбиваються на групи, що не перетинаються. Ознака утворення і-ї групи: і одиниць в кожному двійковому номері конституєнти одиниці.

Склеювання проводять тільки між номерами сусідніх груп. Склеювані номери відмічається будь-яким знаком (закреслюванням).

Склеювання проводять всеможливі, як і в методі Квайна.

Невідмічені після склеювання номера є простими імплікантами.

Знаходження мінімальних ДНФ дальше проводяться на імплікантній матриці, як і в методі Квайна.

Метод дозволяє швидко отримати мінімальні ДНФ булевої функції f невеликого числа змінних. В основі методу лежить задання булевих функцій діаграмами деякого спеціального виду, які дістали назву діаграм Вейча. Для булевої ф-ції двох змінних діаграма Вейча має вигляд (табл.3) Кожна клітка діаграми відповідає набору змінних булевої функції в її таблиці істиності. В клітці діаграми ставиться одиниця, якщо булева функція приймає одиничне значення на відповідному наборі. Нульові значення булевої функції в діаграмі не ставляться. Для булевої функції трьох змінних діаграма Вейча має такий вигляд (табл.4)

Додаванням до неї ще такої ж таблиці ми отримаємо діаграму для функції 4-х змінних (табл.5). Таким же чином можна отримати діаграму 5-ти змінних і т.д.

Таблиця 5

Для приведених діаграм характерне наступне:

Кожній клітці діаграми відповідає свій набір.

Сусідні набори розміщені поряд в рядку або в стовбці.

Сусідніми наборами називають набори, які відрізняються однією компонентою.

Ще одне важливе зауваження: стовбці, розміщені по краях діаграми, також вважають сусідніми.

Загальне правило склеювання на діаграмі Вейча можна сформолювати таким чином: склеюванню підлягають прямокутні конфігурації, заповнені одиницями і які містять число кліток, що являються степінню 2. Отримане повне елементарне перетворення визначається як перетворення змінних, які не змінюють свого значення на всіх склеюваних наборах. Число m змінних, які залишились в елементарному перетворенні визначається легко:

m = n - log2M,

де n - число змінних функції; М - число склеюваних наборів. Метод широко використовується на практиці, завдяки простоті і зручності.

Мінімізація булевої ф-ції полягає в знаходженні мінімального накриття всіх одиниць діаграми Вейча блоками з одиниць (вказаної конфігурації), розміщених в сусідніх клітках діаграми. При цьому завжди вважають, що лівий край діаграми Вейча 4-х змінних прилягає до її правого краю, а верхній край діаграми - до її нижнього краю. Після отримання максимального покриття всіх одиниць діаграми Вейча, мінімальна ДНФ булевої функції записується як диз'юнкція елементарних кон'юнкцій, які відповідають виділеним блокам одиниць в діаграмі.

Приклад. Булева функція f має наступну ДДНФ:

Знайти мінімальну ДНФ з допомогою діаграми Вейча. Діаграма Вейча, що відповідає функції f, представлена в табл.18. Мінімальне накриття всіх одиниць діаграми можливе тільки блокамипо дві одиниці. Кожному такому блоку відповідає своя кон'юнкція, як показано в табл.22. Отже, мінімальна ДНФ ф-ції має вигляд:

.

Таблиця 18

Висновок

Отже, ключовими математичними поняттями теорії цифрових автоматів являється т. зв. булева алгебра та її під-дисципліни, які і визначають її математичний базис.

Література

1. А.Я. Савельев. Арифметические и логические основы цифровых автоматов. М.: Высшая школа. 1999.

2. А.Я. Савельев. Прикладная теория цифровых автоматов. М.: Высшая школа. 2007.

3. Е.Н. Вавилов, Г.П. Портной. Синтез схем электронных цифровых машин. М.: Советское радио. 2003.

4. Г.Н. Соловьев. Арифметические устройства ЭВМ. М.: Энергия. 2008.

Страницы: 1, 2, 3