15. Утворення дднф

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

Правила утворення ДДНФ функції n аргументів такі:

За кожним набором двійкових змінних, за яких функція добуває значення 1, скласти елементарні кон'юнкції (мінтерми).

В елементарну кон'юнкцію записати неінвертованими змінні, що задані одиницею в таблиці істинності, а інвертовани­ми — ті змінні, які в таблиці істинності задані нулем. Здобу­тий результат називають коyституентами одиниці.

Елементарні кон'юнкції об'єднати знаком диз'юнкції.

16. Перехід від ДНФ до ДДНФ

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

1. в нести відсутні змінні в кожну кон'юнкцію множен­ням її на

2. рівнозначність вигляду a + =1, де а — відсутня змінна;

3. розкрити дужки, застосувавши комутативний закон (ab = bа);

4. позбутися кон'юнкцій, що повторюються, на основі закону ідемпотентності (а + а = а).

17. П обудова комбінаційних схем

При записі логічних виразів і, отже, побудові логічних схем можна скористатися тільки двома типами операцій, наприклад операціями І та НЕ чи АБО та НЕ.

Сукупність ЛЕ, що дає змогу реалізувати логічну схему довільної складності, називають функціонально повною системою. Отже, системи двох елементів І та НЕ, а також АБО та НЕ нарівні з системою з трьох елементів І, АБО, НЕ є функ­ционально повними.

18. Мінімізація перемикальних функцій

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

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

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

Мінімальною диз‘юнктивною нормальною формою булевої функції називається ДНФ, що містить найменшу кількість букв (відносно інших ДНФ, що представляють задану булеву функцію).

19. Метод мінімізації Квайна.

Метод Квайна базується на двох основних співвідношеннях.

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

де А – будь-який елементарний добуток.

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

Справедливість обох співвідношень легко перевірити. Метод полягає в послідовному виконанні всіх можливих склеювань, а потім всіх поглинань, що приводить до скороченої ДНФ. Метод застосовують для довершеної ДНФ. Зі співвідношення поглинання випливає, що довільний елементарний добуток поглинається будь-якою його частиною. Справді, застосовуючи до p операцію розгортки (обернену до операції склеювання):

по всім змінним, яких не вистачає, вихідній функції f, отримаємо сукупність S конституєнт одиниці. При склеюванні всіх конституєнт з S отримаємо імпліканту р. Останнє очевидно, оскільки операція склеювання є оберненою до операції розгортки. Множина S конституєнт обов‘язково присутня в довершеній ДНФ функції f , оскільки р — її імпліканта.