- •Розділ 1. Математичні основи синтезу логічних схем
- •1.1. Деякі поняття і визначення булевої алгебри
- •1.2. Способи задання булевих функцій
- •1.3. Булеві функції від однієї і двох змінних
- •1.4. Принцип суперпозиції логічних функцій. Пріоритет операцій
- •1.5. Аксіоми та закони булевої алгебри
- •Аксіоми кон’юнкції, диз’юнкції і заперечення:
- •1.7. Аксіоми та закони алгебри Жегалкіна
- •1. Комутативний закон
- •2. Сполучний закон
- •3. Розподільний закон по відношенню до додавання за модулем 2
- •1.8. Аксіоми та закони для функцій Шеффера та Пірса
- •1.9. Аналітичне подання булевих функцій
- •1.10. Класи булевих функцій. Теорема про повноту
- •1.11. Розвинення логічних функцій за змінними
- •1.12. Зв’язок між дднф і дкнф. Канонічні нормальні форми
1.12. Зв’язок між дднф і дкнф. Канонічні нормальні форми
представлення булевих функцій
Нехай маємо булеву функцію, задану у ДДНФ
, (1)
де – усі мінтерми функції .
Побудуємо функцію наступним чином:
Запишемо диз’юнкцію усі мінтермів функції , які не ввійшли формулу (1), тобто, мінтерми функції – інверсної до :
,
де – усі мінтерми функції .
В одержаній формулі замінимо на , на , змінні на , на .
В результаті такого перетворення дістанемо функцію вигляду
, (2)
яка є не що інше як ДКНФ функції .
З формул (1) і (2) випливає рівність
. (3)
Таблиця 18
x
y
f
0
0
0
0
1
1
1
0
0
1
1
1
Розв’язання. 1. Запишемо ДДНФ:
.
2. Запишемо диз’юнкцію усі мінтермів функції , які не ввійшли формулу :
.
3. В одержаній формулі виконаємо заміни згідно з п.2 вищенаведеного правила, одержимо функцію
,
яка є не що інше як ДКНФ для функції .
Зауваження. З одержаних результатів, можна одержати рівності:
, , , , (4)
де і – відповідно мінтерм і макстерм на і-му наборі, а і – деякі елементарні кон’юнкціія і диз’юнкція, які одержані одна з одної шляхом заміни на , на , змінні на , на .
Означення 1. Форму запису логічних функцій у ДДНФ (ДНФ) будемо називати записом логічної функції у канонічній диз’юнктивній нормальній формі або форма І/АБО.
Означення 2. Форму запису логічних функцій у ДКНФ (КНФ) будемо називати записом логічної функції у канонічній кон’юнктивній нормальній формі або форма АБО/І.
Форми І/АБО і АБО/І не є єдними способами задання функції алгебри логіки. Використовуючи закони подвійного заперечення і закони де Моргана , або , можна одержати ще шість канонічних форм. Справді, нехай маємо функцію, задану в ДНФ
– (форма І/АБО).
Використовуючи вищеназвані закони та формули (4), послідовними перетвореннями, одержимо перші чотири канонічні форми:
– (форма І-НЕ/І-НЕ)
– (форма АБО/І-НЕ)
– (форма АБО-НЕ/АБО).
У формі І/АБО можна подати як функцію так і її заперечення , що дасть ще нові чотири канонічні форми:
– (форма І/АБО-НЕ)
– (форма І-НЕ/І)
– (форма АБО/І).
– (форма АБО-НЕ/АБО-НЕ)
К
Таблиця 19
А
В
С
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
Приклад 2. Знайти логічні вирази мажоритарної (порогової) функції від трьох змінних, яка задається таблицею істинності (табл. 2.19).
Розв’язання. Користуючись переходом від табличної форми подання функції алгебри логіки до аналітичної, запишемо її ДДНФ
.
Виконаємо мінімізацію .
Застосувавши закон склеювання до першого і четвертого, другого і четвертого, третього і четвертого доданків , одержимо:
, , .
Таким чином мінімальна форма має вигляд
– форма І/АБО.
Користуючись подвійним запереченням та законом де Моргана, подамо в інших формах:
– форма І-НЕ/І-НЕ;
– форма АБО/І-НЕ;
– форма АБО-НЕ/АБО.
Відповідні логічні схеми та результати моделювання, виконані в системі проектування MAX+PLUS II на базі різних елементів, наведено на рис. 10, 11.
Форма
І/АБО
Форма
І–НЕ/І–НЕ
Форма
АБО/І–НЕ
Форма
АБО–НЕ/АБО
Рис. 10
Рис. 11
Для побудови чотирьох інших форм розглянемо функцію . Користуючись таблицею істинності оберненої функції, знайдемо
.
Застосувавши закон склеювання до першого і другого, першого і третього, першого і четвертого доданків , одержимо .
Оскільки , то маємо:
– форма І/АБО-НЕ;
– форма І-НЕ/І;
– форма АБО/І;
– форма АБО-НЕ/АБО-НЕ.
Відповідні логічні схеми та результати моделювання, виконані в системі проектування MAX+PLUS II на базі різних елементів наведено на рис. 12, 13.
Форма
І/АБО–НЕ
Форма І–НЕ/І
Форма АБО/І
Форма АБО–НЕ/АБО–НЕ
Рис. 12
Рис. 14