Способи переходу від нормальної до досконалих форм перемикаючої функції

 

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

Аналітичний спосіб. Досконала нормальна форма на відміну від нормальної завжди містить диз'юнкції (ДДНФ) або кон'юнкції (ДКНФ) тільки максимального рангу r. Це дає можливість робити перехід за такими правилами.

Для переходу від довільної ДНФ до ДДНФ r-го порядку необхідно: кон'юнкції, що входять у ДНФ, k-го (k <r) порядку послідовно множити на логічне вираження , де Y_i =А, В, С, … N — одна з змінних, котра не входить у дану кон'юнкцію. Число таких перетворень для кожної кон'юнкції повинно бути (r - k).

Приклад1. Перетворити в ДДНФ перемикаючу функцію, задану в ДНФ:

1. Використовуючи закони і тотожності алгебри логіки, перетворимо кон'юнкції заданої функції в мінтерми 3-го порядку:

;

.

2. У результаті перетворень отримані мінтерми з'єднаємо символом диз'юнкції і, використовуючи тотожність (2.11), одержимо

.

Для переходу від довільної КНФ до ДКНФ r-го порядку необхідно диз'юнкції, що входять у КНФ, k-го (k - r) рангу послідовно підсумовувати з логічним вираженням , де Y_i =А, В, С, … N — одна з змінних, котра не входить у дану диз'юнкцію. Число таких перетворень для кожної диз'юнкції повинне бути (r-k).

Приклад 2. Перетворити в ДКНФ перемикаючу функцію, задану в КНФ:

1. Використовуючи закони і тотожності алгебри логіки, перетворимо диз'юнкції заданої функції в макстерми 3-го порядку:

;

.

2. У результаті перетворень отримані макстерми з'єднаємо символом кон'юнкції і, використовуючи тотожність ідемпотентності, одержимо

.

Графічний спосіб.Найбільш наочним і простим графічним способом перетворення перемикаючої функції із нормальної форми в досконалу являються карти Карно-Вейча.

Карта Карно — графічне представлення всіх мінтермів (2^п) для даного числа змінних (п). Кожний мінтерм зображується у вигляді клітини, розташованої так, що мінтерми, які знаходяться в сусідніх клітках, відрізняють тільки однією змінною. На рис. 1представлені зображення карт Карно для функцій двох, трьох і чотирьох змінних. Змінні написані по дві сторони діагональної смуги в лівому кутку карти. Значення змінних позначаються із зовнішньої сторони карти двійковими цифрами: 0 — відповідає інверсному значенню змінної, а 1 — прямому. Така умовність дає можливість легко представити для кожної клітки карти Карно відповідний їй мінтерм.

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

 

Рис. 1. Зображення карт Карно для двох, трьох і чотирьох змінних.

Алгоритм перетворення перемикаючої функції із ДНФ в ДДНФ за допомогою карти Карно полягає в наступному:

1. Для заданої перемикаючої функції зобразити карту Карно.

2. Поставити в клітках карти Карно 1 для тих мінтермів, в склад яких входять кон’юнкції заданої функції.

3. Позначені 1 мінтерми з’єднати символами диз’юнкції — це й буде ДНДФ заданої перемикаючої функції.

П р и к л а д 2. За допомогою карти Карно перетворити перемикаючу функцію f (A, B, C)=AB / C з ДНФ в ДДНФ.

Розв’язування.1. Для заданої перемикаючої функції будуємо карту Карно (рис. 2), на якій 1 позначає мінтерми, до складу яких входять кон’юнкція АВ і змінна С.

4.
Запишемо значення перемикаючої функції в СНДФ, з’єднуючи позначені мінтерми символами диз’юнкції:

Рис. 2. Карта Карно для перемикаючої функції f (A, B, C)=AB / C.

F_ДНДФ (А, В, С)=С / ВС / AC / A/ ABC.

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

П р и к л а д 3. Перетворити в ДКНФ перемикаючу функцію, задану в КНФ:

f_КНФ (A, B, C, D)=(A / B / C) (A / / D).

Розв’язування.1. Від заданої функції в КНФ отримаємо її інверсне значення:

=/ .

2. Для отриманої перемикаючої функції будуємо карту Карно (рис. 3), на якій і позначаємо мінтерми, які містять в собі логічні змінні і .

Рис. 3. Карти Карно для перемикаючої функції

f_КНФ (A, B, C, D)= / B

3. Використовуючи карту Карно (рис. 3), запишемо інверсне значення перемикаючої функції в ДКНФ:

= / D / B/ BC.

4. На основі закону подвійного заперечення інверсне значення для цієї функції має вигляд:

F_ДКНФ (A, B, C, D)=( A / B / C / D) (A / B / C /) (A / / C / D)*

*( AD)

і буде представляти задану перемикаючу функцію в ДКНФ.