Форми представлення ФАЛ

Для аналізу і синтезу дискретних пристроїв часто зручно представляти ФАЛ в кон’юнктивній та диз’юнктивній нормальних формах.

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

Прикладом завдання ФАЛ у формі ДНФ і КНФ, відповідно можуть служити функції:

, (3)

. (4)

Елементарні диз’юнкції є конституентами одиниці (відповідно конституентами нуля) для даної множини змінних, якщо вони в прямому або інверсному вигляді містять всі змінні алфавіту даної множини. ДНФ (відповідно КНФ) називається довершеною, якщо всі елементарні кон’юнкції (відповідно елементарні диз’юнкції), які входять до її складу, є конституентами одиниці (нуля) для однієї і тієї ж множини змінних. Прикладом завдання ФАЛ у формі ДДНФ і КДНФ можуть відповідно служити функції:

, (5)

. (6)

Будь-яка ФАЛ має одну ДДНФ і КДНФ. Для отримання довершених нормальних форм існують різні способи, основними з яких є аналітичний і табличний. Аналітичний спосіб ґрунтується на використанні теореми розкладання, яка у разі розкладання ФАЛ по одній змінній (наприклад ) записується таким чином:

, (7)

. (8)

Для отримання довершених нормальних форм необхідно здійснити розкладання ФАЛ за кожною зі змінних.

Табличний спосіб отримання довершених нормальних форм ґрунтується на використанні таблиці істинності або карти Карно. Для отримання ДДНФ виписують всі елементарні вирази, відповідні наборам змінних, на яких ФАЛ приймає одиничне значення. Для отримання КДНФ виписуються всі елементарні диз’юнкції, відповідні наборам змінних, на яких функція приймає нульове значення, причому кожна зі змінних, що входить в елементарні диз'юнкції, інвертується. Нижче наведений приклад запису у формі ДДНФ і КДНФ функції двох змінних , заданої таблицею істинності, наведеною на рис. 1.1:

, (9)

. (10)

1.2.4. Основні закони і тотожності алгебри логіки

Для перетворення функцій в АЛ використовується ряд законів і тотожностей, основні з яких без доказу наведені нижче.

Комутативні переміщувальні закони для диз’юнкції і кон’юнкції:

, (11)

. (12)

Дистрибутивні (розподільні) закони:

, (15)

. (16)

Закон інверсії:

. (17)

Закони повторення:

, (18)

. (19)

Закони заперечення:

, (20)

. (21)

Закон подвійного заперечення

. (22)

Закони поглинання:

, (23)

. (24)

Правила для операцій з константами:

, (25)

, (26)

, (27)

, (28)

, (29)

. (30)

Закон склеювання

. (31)

Додаткові тотожності:

або , (32)

. (33)

1.2.5. Реалізація ФАЛ на контактах реле та інтегральних
логічних елементах

Використання контактних схем для реалізації основних логічних функцій і побудова цих функцій на безконтактних елементах наведені в табл. 1.3.

Таблиця 1.3

Реалізація і позначення основних логічних операцій

Реалізуюча ФАЛ і логічна операція	Позначення для реалізації
на контактах реле	на безконтактних елементах
Інверсія «НІ»,
Кон’юнкція «І»,
Диз’юнкція «АБО»,
Заперечення кон’юнкції «І-НІ»,
Заперечення диз’юнкції «АБО-НІ»,

Застосування АЛ для аналізу і синтезу комбінаційних схем пояснює рис. 1.2.

Рис. 1.2. Комбінаційні схеми: а – контактна схема, що мінімізується;
б, в – контактна і безконтактна схеми, отримані після мінімізації

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

. (34)

Застосовуючи до даної функції закони і тотожності АЛ здійснюємо її мінімізацію:

(35)

Дата добавления: 2017-01-13