Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення.

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

1. Побудова таблиці істинності для заданого виразу.

2. Побудова за таблицею істинності так званої досконалої диз’юнктивної (або кон’юнктивної) нормальної форми.

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

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

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

Диз’юнктивна нормальна форма від n змінних називається досконалою(ДДНФ), якщо кожна елементарна кон’юнкція включає всі змінні, можливо із запереченням.

Зазначимо, що крім диз’юнктивних нормальних форм, широко застосовуються нормальні форми іншого типу – кон’юнктивні.

Кон’юнктивною нормальною формою (КНФ) називається логічний добуток елементарних диз’юнкцій, в кожну з яких аргумент або його заперечення входять один раз. КНФ може бути отримана з таблиці істинності: для кожного набору аргументів на якому функція рівна «0» складають елементарну суму, причому змінні, значення яких рівне «1», записуються із запереченням. Отримані суми, які носять назву констітуент нуля, або макстермів, об’єднують операцією логічного множення. КНФ також називається досконалою(ДКНФ), якщо кожна елементарна сума містить всі змінні з інверсією або без.

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

Нехай заданий деякий набір значень: змінні x1, …, xn приймають значення відповідно s1, …, sn. Елементарна кон’юнкція, яка залежить від змінних x1, …, xn, при даних значеннях аргументів може дорівнювати 1 в одному і тільки одному випадку: якщо аргументи, що дорівнюють 0, входять до неї під знаком заперечення, а ті, що дорівнюють 1 – без знака заперечення. Іншими словами, єдина елементарна кон’юнкція, яка при x1 = s1, … , xn = sn дорівнює 1, має вид y1…yn, де yi =`xi при si = 1 і yi = xi при si = 0. Далі, оскільки таблиця істинності дорівнює 1 при декількох наборах значень аргументів, вона повинна являти собою диз’юнкцію усіх відповідних елементарних кон’юнкцій.

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

Ще один приклад. Побудуємо ДДНФ для наведеної таблиці істинності.

x y z F(x, y, z)

До ДДНФ повинно увійти чотири елементарні кон’юнкції, які відповідають наборам, при яких функція F(x, y, z) приймає значення 1 (вони в таблиці істинності виділені заливкою). Відповідно до цього ДДНФ матиме вид:

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru .

Оскільки побудова ДДНФ дуже важливий етап у синтезі електронних схем реалізації конкретних вузлів МП-систем, наведемо ще кілька прикладів.

Розглянемо побудову ДДНФ для створення методом синтезу логічного пристрою перетворювача кодів, призначеного для керування семисегментним індикатором, який повинен висвітлювати одну із десяткових цифр (0, 1, 2, …, 9) в залежності від поданого на вхід коду цифри. Індикатор складається із семи сегментів, кожний з яких керується окремою логічною схемою. Схема керування кожним сегментом реалізує логічну функцію уі1, х2, х3, х4), де х1, х2, х3, х4 – розряди вхідного слова, яке є кодом символу, що відтворюється індикатором. Сукупність логічних схем керування сегментами і уявляє собою шифратор або перетворювач кодів.

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

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Складемо таблицю істинності для комбінацій вхідних – х4 ¸ х1 і комбінацій вихідних – у1¸ у7 сигналів. При подачі коду десяткової цифри 0 (двійковий код – 0000) повинні світитись сегменти, що керуються функціями у1, у2, у3, у4, у5, у6, тобто значення цих функцій – 1 («істина»); при подачі коду десяткової цифри 1 (двійковий код – 0001) повинні світитись сегменти, що керуються функціями у2, у3; при подачі коду цифри 2 (двійковий код – 0010) повинні світитись сегменти, що керуються функціями у1, у2, у4, у5, у7 і т.д.

Таблиця.

Таблиця відповідності символу, його коду та значень логічних функцій уі.

Символ (цифра) Двійковий код (вхідні сигнали) Значення сигналів, що керують сегментами (вихідні сигнали)
х4 х3 х2 х1 у1 у2 у3 у4 у5 у6 у7

Тепер треба дати відповідь на питання: коли повинен світитись сегмент, що керується функцією у1? Відповідь: коли буде поданий код 0000, або 0010, або 0011, або 0101, або 0110, або 0111, або 1000, або 1001 (в таблиці виділено курсивом). Цю відповідь треба записати у вигляді логічного виразу, тобто у вигляді ДДНФ:

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Аналогічно будуються ДДНФ для інших функцій – у2, у3, …, у7:

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Вхідні сигнали Вихідні сигнали
Ai Bi Pi–1 Si Pi

Ще один приклад побудови ДДНФ для однорозрядного суматора, з яких складається багаторозрядний суматор, і який реалізує в арифметичному пристрої процесора комп’ютера арифметичну операцію додавання двох бітів в однойменних розрядах. На вхід такого пристрою подаються три сигнали – два доданка (Аі, Ві), і третій сигнал – значення переносу із суматора попереднього молодшого розряду (Рі–1). На виході повинні утворюватись два сигнали – значення суми в розряді (Si) і значення переносу в наступний старший розряд (Рі). Таблиця істинності для зазначених сигналів матиме вид, наведений в таблиці.

Так наприклад, у випадку, коли Аі = 1, Ві = 1, Рі–1 = 0, тобто значення і-тих розрядів доданків дорівнюють 1, і відсутній перенос одиниці із попереднього молодшого розряду, будемо мати 1 + 1 = 10, тобто значення суми саме в цьому розряді дорівнює 0 (Si = 0), і є перенос одиниці в сусідній старший розряд (Рі = 1). Ці обставини відображені у сьомому рядку таблиці. З аналогічних міркувань заповнюються інші рядки.

ДДНФ для вихідних сигналів Si і Рі матимуть вид:

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

Вираження довільного логічного виразу через кон’юнкцію, диз’юнкцію та заперечення. - student2.ru

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

Наши рекомендации