1 of 20

МІНІМІЗАЦІЯ булевих функцій. МЕТОД КАРТИ Карно� �Лекція 6

1

ДИСКРЕТНА МАТЕМАТИКА

Булева алгебра

Харьковский национальный университет радиоэлектроники,

кафедра АПВТ, тел. 7021 326, е-mail: ri@kture.kharkov.ua

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

2 of 20

мета лекції - вивчити метод карт Карно для мінімізації булевих функцій, що описують комбінаційні підсхеми цифрових проектів

2

зміст:

  • Карти Карно двох, трьох, чотирьох змінних
  • Властивості карт Карно
  • Спрощений стандарт карт Карно
  • Р-підкуби, покриття
  • Правила мінімізації
  • Висновки

Тема: Мінімізація булевих функцій. � Метод карт Карно

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

3 of 20

Базові поняття:

    • булева змінна
    • булева функція
    • Двійкова система числення
    • Числове уявлення ФАЛ
    • Кубічне уявлення ФАЛ
    • ДДНФ і ДКНФ
    • Закони склеювання і поглинання

​

​

3

терміни

Ключові слова:

    • мінімізація
    • сусідні клітини
    • р-подкуб
    • Одновимірна

р-подкуб

    • двовимірний

р-подкуб

    • мінімальне покриття

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

4 of 20

4

Подання ФАЛ на картах Карно

  • Карта Карно є графічним способом представлення булевих функцій від декількох змінних
  • Таблиці істинності функції від 2, 3, 4-х змінних можуть бути перебудовані в карти Карно
  • приклад: карта Карно для двох змінних

№ набору

x1

x2

f (x1, x2)

0

0

0

​

1

0

1

​

2

1

0

​

3

1

1

​

x1x2

0

1

3

2

00 01 11 10

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

5 of 20

5

Карта Карно для трьох змінних

x2x3

00 01 11 10

0

1

3

2

4

5

7

6

x1

0

1

№

х1

х2

х3

f (x1, x2, x3)

0

0

0

0

​

1

0

0

1

​

2

0

1

0

​

3

0

1

1

​

4

1

0

0

​

5

1

0

1

​

6

1

1

0

​

7

1

1

1

​

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

6 of 20

6

Карта Карно для чотирьох змінних

x3x4

00 01 11 10

0

1

3

2

4

5

7

6

12

13

15

14

8

9

11

10

00

01

11

10

x1x2

№

х1

х2

х3

х4

f (x1, x2, x3, х4)

0

0

0

0

0

​

1

0

0

0

1

​

2

0

0

1

0

​

3

0

0

1

1

​

4

0

1

0

0

​

5

0

1

0

1

​

6

0

1

1

0

​

7

0

1

1

1

​

8

1

0

0

0

​

9

1

0

0

1

​

10

1

0

1

0

​

11

1

0

1

1

​

12

1

1

0

0

​

13

1

1

0

1

​

14

1

1

1

0

​

15

1

1

1

1

​

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

7 of 20

7

Подання ФАЛ на картах Карно

  • Для представлення функції на карті досить в ті клітини, де функція дорівнює одиниці, помістити одиниці
  • Вважається, що в інших клітинах містяться нулі
  • приклади

x2x3

00 01 11 10

1

​

1

​

​

1

​

1

x1

0

1

x1x2

​

1

​

1

00 01 11 10

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

8 of 20

8

Властивості карт Карно

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

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

9 of 20

9

Спрощений стандарт карт Карно

x1

​

​

​

​

​

​

​

​

​

​

​

​

x1

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

x2

x2

x3

x3

x4

x1

x2

  • Для спрощення рядки і стовпці, де змінна хi дорівнює 1, позначають фігурною дужкою. При цьому значення нуль ця змінна має в невідмічених місцях

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

10 of 20

10

Приклади представлення функцій на картах Карно з використанням спрощеного стандарту

x1

1

​

1

​

​

1

​

1

1

​

1

​

x1

​

​

1

​

​

1

1

​

​

​

​

​

1

​

​

​

x2

x2

x3

x3

x4

x1

x2

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

11 of 20

11

Р-підкуби. покриття 1

  • Р- клітини - клітини з одиницями
  • Дві сусідні одиниці утворюють одновимірний р-підкуб
  • Одновимірна р-підкуб відповідає твору, в якому завжди відсутній один первинний терм
  • Змінна, відсутня в творі, визначається по карті - вона має різні значення для двох одиниць відповідного підкуба

x1

​

​

1

1

x2

​

​

​

​

​

1

1

​

​

​

​

​

​

​

​

​

x3

x4

x1

x2

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

12 of 20

12

Р-підкуби. покриття 2

  • Чотири сусідні одиниці утворюють двовимірний р-підкуб
  • Двовимірний р-підкуб відповідає твору без двох первинних термів
  • Опущені ті змінні, що не зберігають постійне значення на цьому підкубі

1

​

​

1

​

​

​

​

​

​

​

​

1

​

​

1

x3

x4

x1

x2

​

​

​

​

​

​

​

​

1

​

​

1

1

​

​

1

x3

x4

x1

x2

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

13 of 20

13

1

1

1

1

1

1

1

1

​

​

​

​

​

​

​

​

x3

x4

x1

x2

​

1

1

​

​

1

1

​

​

1

1

​

​

1

1

​

x3

x4

x1

x2

  • Тривимірні р-підкуби містять по 8 одиниць
  • Одновимірний р-підкуб відповідає ребру, що має дві сусідні вершини
  • Двовимірний р-підкуб відповідає двовимірному підкубу nмірного куба
  • Щоб уявити функцію, слід покрити всі одиниці карти р-підкубами

Р-підкуби. покриття 3

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

14 of 20

14

Уявлення функцій р-підкубами

​

​

1

1

1

1

​

​

1

1

1

​

​

​

1

​

x3

x4

x1

x2

​

​

1

​

1

1

1

1

1

​

1

​

​

​

​

​

x3

x1

x2

x4

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

15 of 20

15

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

  • Дві сусідні клітини утворюють 1-куб
  • Несуттєва координата для двох кубів позначається символами X: 101∨111 = 1Õ1
  • Чотири клітини об'єднуються, утворюючи 2-куб:

100 ∨ 101 ∨ 110 ∨ 111 = 1ÕÕ

​

  • У загальному випадку можуть об'єднуватися сусідні клітини, число яких дорівнює 2k, де k= 1,2,3 ... (2,4,8,16,32, ...) з утворенням k-куб

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

16 of 20

16

Приклади мінімізації по картах Карно 1

​

​

​

​

​

1

1

​

​

1

1

​

​

​

​

​

x3

x4

x1

x2

1

​

​

​

1

​

​

​

1

​

​

​

1

​

​

​

x3

x4

x1

x2

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

17 of 20

17

Приклади мінімізації по картах Карно 2

​

​

1

​

​

1

1

​

​

​

​

​

1

​

​

​

x3

x4

x1

x2

Склеювання сусідніх осередків дає:

​

3 і 7 ⇒

5 і 7 ⇒

8 ⇒

​

Отже, результуюча ДНФ має вигляд:

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

18 of 20

18

Приклади мінімізації по картах Карно 3

1

1

​

1

​

1

​

1

​

1

1

​

​

​

1

​

x3

x4

x1

x2

Не завжди вибране покриття виявляється мінімальним. Наприклад: потрібно отримати мінімальну ДНФ для функціїY = 1 на наборах {0,1,2,5,6,11,13,15}

1

1

​

1

​

1

​

1

​

1

1

​

​

​

1

​

x3

x4

x1

x2

Всі можливі попарні склеювання НЕ дадуть мінімальну форму функції!

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

19 of 20

висновки

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

​

19

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

20 of 20

Тест-питання

20

x1

1

1

1

​

1

​

1

​

​

1

​

1

x1

1

1

​

​

1

1

​

​

​

1

1

​

​

​

1

​

x2

x2

x3

x3

x4

x1

x2

  • Позначити на картах Карно мінімізують контури
  • Вказати результати склеювання

x1

1

​

1

1

x2

А

Б

В

Г

Минимизация булевых функций. Метод карт Карно 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua