Лекція №8 Метод карт Карно

Лекція №7 Методи мінімізації

Тема 2.3 Мінімізація функцій алгебри логіки

1. Алгебраїчний метод.

2. Метод Квайна.

1. Метод карт Карно.

2. Правила мінімізації.

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

І. Алгебраїчний:

При мінімізації цим методом використовуються основні закони і тотожності алгебри логіки.

f = x3•x2•1Ú3•x2•1 = x2•1•(x3Ú3) = x2•1

 

ІІ. Метод Квайна.

Використовується для мінімізації функції заданої у ДДНФ.

Імпліканта функції – деяка логічна функція, яка рівна = 0 на наборі змінних, на яких функція рівна 0.

Нехай необхідно мінімізувати логічну функцію, яка задана у вигляді:

f 1 (x1, x2, x3) = (3, 4, 5, 7) = 1·x2·x3 + x1·2·3 + x1·2·x3 + x1·x2·x3

 

1. Складаємо таблицю та знаходимо імпліканти на ранг нижче ніж члени які входять у ДДНФ.

 

Терми
1 x2 x3     x2 x3
x1 2 3   x1 2  
x1 2 x3   x1 2 x1 x3
x1 x2 x3 x2 x3   x1 x3 ¯

Первинні імпліканти 2 рангу

 

2. Виконуємо операцію поглинання, тобто Х+Х = Х

3. Розставляємо мітки. У рядок записуємо первинні імпліканти, а у стовпчики мінтерми ДДНФ. Якщо у мінтерм входить первинна імпліканта та ставимо мітку.

 

імпліканти
x2 x3 V     V
x1 2   V V  
x1 x3     V V

Не є суттєві

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

5. Вибираємо мінімальне покриття, тобто записуємо декілька імплікантів, щоб всі вони разом мали по одній мітці в кожному стовпчику. Тоді мінімальна форма заданої функції складається з суми цих імплікант:

f (x1, x2, x3) = x2 x3 + x1 2

 

ІІІ. Метод карт Карно:

При мінімізації цим методом функція представляється на карті розміри якої 2n, де n – кількість аргументів, розміри карти – кількість кліток на карті. Далі для одержання мінімальної ДНФ (МДНФ) необхідно зробити об’єднання, в які будуть входити сусідні одиниці по дві або чотири, або вісім. Для кожного об’єднання виписуються прості імпліканти, диз’юнкція яких і буде МДНФ. Необхідно перевірити чи всі об’єднання є суттєвими.

Кожній комірці карти співставляємо певний мінтерм.

А В    
А
В АВ

 

 

Правило нумерації комірок: номер сусідніх комірок повинен відрізнятись на 1 в любому розряді.

F = x1 x2 x3 + 1 x2 x3 + x1 x2 3 + x1 2 3

х2х3 х1         х2х3 х1
       
   

 

Карта Карно утворює циліндр як вертикально так і горизонтально.

 

А В    
   

І. F = AB + B =B(A+) = B

Мінімізуємо сусідні одиниці та випадає змінна, яка входить в прямому та інверсному вигляді тобто А.

 

А В    
 

II. F = AB + B + = AB + B +B += B(A + ) +(B +)=B +

 

х2х1 х3         х2х1 х3
       
   

III. F = x2 x1 +x3 1

 

х2х1 х3         х2х1 х3
     
     

IV. При об’єднанні 4 мінтермів випадають ті змінні, які попарно входять у прямому та інверсному вигляді.

F = 2

 

Приклад 1:

f1 (х1, х2, х3) = (0, 4, 5, 7) – функція представлена в так званій числовій формі по якій запишемо таблицю істинності (в дужках записана позиція де записуємо 1):

  х3 х2 х1 f
  22 21 20  

 

х2х1 х3   00       х2х1 х3
 
 

 

 

Не суттєве об’єднання

МДНФ

f = 1•2Úх3•х1

 

 

Для одержання МКНФ в об’єднання необхідно включити нулі, і застосувати прийоми, протилежні тим, які були використані для запису МДНФ.

Запис у МКНФ f = (х1 + 3)( 1 + х2)

 

Приклад 2.

х2х1 х3         х2х1 х3
 
 

 

f = х2•1Ú3•1

 

 

Приклад 3.

х2х1 х3         х2х1 х3
 
 

 

f = x2•3Ú1

 

 

Приклад 4.

х2х1 х4 х3   00        
 
 
 
 

 

 

F0 (х4, х3, х2 х1) = (2, 3 )

0 01 10 01 0

х4х3 х2х1 х4х3 х2х1

 

f = 2Úx3Úx4

 

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