Минимизация логических функций. Карты Карно

1.

4. Минимизация логических функций. Карты Карно.
Задача минимизации логической функции заключается в
том, чтобы найти наиболее компактное её представление в
виде нормальной формы минимальной сложности –
минимальной дизъюнктивной нормальной формы
(МДНФ) или минимальной конъюнктивной нормальной
формы (МКНФ).
• Минимальной сложности ДНФ = МДНФ.
• Минимальной сложности КНФ = МКНФ.
Минимальная нормальная форма логической функции –
это из всех возможных нормальных форм такая нормальная
форма, которая содержит наименьшее число компонентов
вида Xi или Xi .

2.

Логическая функция может иметь несколько различных
минимальных нормальных форм МДНФ или МКНФ равной
сложности.
4.1 Минимизация логических функций путем
преобразований
Алгоритм:
1. шаг: найти ДНФ или КНФ
2. шаг: выполнить все возможные поглощения и склеивания по
формулам 10 и 11:
10. Законы склеивания:
a) (A & B) (A & B) A
b) (A B) & (A B) A
11. Законы поглощения:
a) A & (A B) A
b) A (A & B) A

3.

Пример: для данной логической функции
f(X1, X2, X3) = (X1 ( X2 X3 )) ( X1 X2)
найти а) ДНФ и МДНФ; b) КНФ и МКНФ.
Решение:
9.a)
8.a)
( X1 ( X2 X3)) ( X1 X2) = ( X1 ( X2 X3)) & ( X1 X2)
8.a)
7.b)
( X1 ( X2 X3)) & ( X1 X2) = ( X1 X2 X3) & ( X1 X2)
7.b) дважды
( X1 ( X2 X3)) & X1 & X2 = ( X1 X2 X3) & ( X1 X2)
4.a)
X1 & X2 & X3 & X1 & X2 = ( X1 X2 X3) & ( X1 X2) =
КНФ
0
5.а)
6.f)
= X1& X1 X1&X2 X2& X1 X2&X2 X3& X1 X3&X2 =
0
= X1 X1&X2 X1& X2 X1&X3 X2&X3
ДНФ

4.

Найдем МДНФ:
11.b )
X1 X1&X2 X1& X2 X1&X3 X2&X3 = X1 X2&X3
МДНФ
Найдем МКНФ:
11.а ) добавим Х3
( X1 X2 X3) & ( X1 X2) =
КНФ
10.b)
= ( X1 X2 X3) & ( X1 X2) & ( X1 X2 X3) =
= ( X1 X3) & ( X1 X2)
МКНФ

5.

4.2 Минимизация логических функций с помощью карты
Карно
Карта Карно – топологическое представление таблицы
истинности логической функции на плоскости или в
пространстве.
Каждой строке таблицы истинности логической функции
соответствует одна клетка карты Карно.
Карта Карно логической функции 2-х переменных –
это таблица размера 2 x 2:
X2
X1
0
1
0
0
1
2
3
1

6.

Пример 4.2.1 пусть логическая функция задана своей
областью единиц
f (X1 , X2 ) = (0,1,3)1
Таблица истинности:
X1 , X2
f (X1 , X2 )
0 0
1
X2
X1
0
1
1
0
1
1
0
0 1
Карта Карно:
1
1 0
0
1
0
1
2
1 1
1
3
0
1
2
3

7.

Карта Карно логической функции 3-х переменных –
это таблица размера 2 x 4:
X2 X3
X1
00
01
11
10
0
0
1
3
2
4
5
7
6
1

8.

Пример 4.2.2 пусть задана логическая функция
f (X1 , X2 , X3 ) = (1,3,6,7)1
Таблица истинности:
X1, X2, X3
f (X1, X2, X3)
0 0 0
0
1
X2 X3
X1
00
01
11
10
0
0
0
1
1
0
0
0 0 1
1
0 1 0
Карта Карно:
0
2
1
0 1 1
3
0
1 0 0
4
0
1 0 1
5
1
1 1 0
6
1
1 1 1
7
1
0
1
0
4
3
1
5
2
1
7
6

9.

Карта Карно логической функции 4-х переменных –
это таблица размера 4 x 4:
X3 X4
X1 X2
00
01
11
10
00
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
01
11
10

10.

Пример 4.2.3 пусть задана логическая функция
f (X1 , X2 , X3 , Х4 ) = (0,1,6,8,9,12,14)1
Карта Карно:
X3 X4
X1 X2
00
01
11
10
00
1
1
0
0
0
01
0
1
0
4
11
1
0
5
0
12
10
1
7
13
6
1
15
0
9
2
1
0
1
8
3
14
0
11
10

11.

Карта Карно логической функции 5-ти переменных –
это 2 таблицы размера 4 x 4:
X3 X4
X1 X2
00
01
11
X3 X4
X1 X2
10
00
00
01
11
10
00
0
1
3
2
4
5
7
6
01
16
17
19
18
20
21
23
22
28
29
31
30
24
25
27
26
01
11
11
12
13
15
14
10
10
8
9
Х5 = 0
11
10
Х5 = 1

12.

Пример 4.2.4 пусть задана логическая функция
f (X1 , X2 , X3 , Х4 , Х5) =
(2,3,5,6,7,11,15,16,17,18,19,21,22,23,26,27,30,31)1
X3 X4
X1 X2
00
01
11
00
0
0
1
0
01
0
1
1
4
11
0
5
12
10
0
8
01
11
10
1
00
1
1
1
1
2
1
7
1
13
0
00
3
1
0
10
X3 X4
X1 X2
Х5 = 0
1
0
14
1
0
0
23
29
Х5 = 1
22
1
31
1
25
18
1
1
0
24
19
21
28
10
10
17
20
11
0
11
0
6
15
9
01
0
1
16
30
1
27
26

13.

Карты Карно логических функций 2-х, 3-х и 4-х переменных
– 2-мерные, т.е. представимы на плоскости.
Карты Карно логических функций 5-ти и 6-ти переменных 3-х мерные или пространственные.

14.

Свойства карт Карно:
1. Каждой клетке карты Карно соответствует один
аргумент-вектор логической функции.
2. Число соседних клеток к каждой клетке карты Карно
равно числу переменных карты.
3. Аргумент-векторы любых двух соседних клеток карты
Карно являются ближайшими друг к другу аргументвекторами (отличаются друг от друга только в одной
координате).

15.

Соседние клетки карты Карно = клетки, имеющие общую
сторону, учитывая также возможность свернуть карту Карно в
пространстве.
X2 X3
X1
00
01
11
10
0
0
1
3
2
4
5
7
6
1
Соседними клетками к клетке 3 (011) являются клетки 1 (001),
2 (010) и 7 (111).
Соседними клетками к клетке 4 (100) являются клетки 0 (000),
5 (101) и 6 (110).

16.

X3 X4
X1 X2
00
01
11
10
00
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
01
11
10
Соседними клетками к клетке 5 (0101) являются клетки 1 (0001),
4 (0100), 7 (0111) и 13 (1101).
Соседними клетками к клетке 8 (1000) являются клетки 0 (0000),
9 (1001), 12 (1100) и 10 (1001).
Соседними клетками к клетке 12 (1100) являются клетки 4
(0100), 8 (1000), 13 (1101) и 14 (1110).

17.

Вспомогательные понятия:
n-мерное Булево пространство {0,1}n: множество всех
возможных двоичных векторов (X1 , X2 ,...,Xn ) длины n .
Ближайшие векторы: двоичные векторы равной длины,
которые отличаются друг от друга только в одной координате.
Интервал длины 2m: множество таких двоичных векторов
(X1, X2 ,...,Xn ), среди которых для каждого вектора найдется
точно m ближайших к нему векторов.
Например, {000, 001, 010, 011} или {0100, 0110}.
Компактное представление интервала: представление через
постоянные координаты, изменяющиеся координаты заменяют
символом ” - ” .
{000, 001, 010, 011} = {0 - -}
{0100, 0110} = {0 1 - 0}

18.

Интервал единиц логической функции: интервал, для всех
векторов которого значение функции f(X1 ,X2 ,...,Xn )=1.
Максимальный интервал единиц логической функции: такой
интервал единиц, который не содержится ни в одном другом
интервале единиц.

19.

Koнтуры карты Карно:
Группы клеток карты Карно определенных размеров
называют контурами.
Для карт Карно, определенных на плоскости, контурами
являются прямоугольники, с допустимыми размерами
сторон 2m x 2n, m, n = 0, 1, 2 …
1x1
1x2
1x4
2x1
2x2
2x4
4x1
4x2
4x4

20.

X3 X4
X1 X2
00
01
11
10
00
Контуры:
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
01
11
10

21.

Связь контуров с интервалами:
Каждый контур карты Карно соответствует определенному
интервалу.
Пример 4.2.5
пусть задана логическая функция
f (X1 , X2 ) = (0,1,2,3,7)1
Карта Карно:
Интервалы:
X2 X3
X1
00
01
11
10
0
1
1
1
1
0
1
0
1
0
4
3
1
5
{0 - -}={000, 001, 010, 011}
{-11}={011, 111}
2
{1-0}={100, 110}
0
7
6
{10-}={100, 101}

22.

Алгоритм минимизации методом карты Карно :
1. Представить логическую функцию картой Карно.
2. Покрыть на карте все 1-цы (для получения МДНФ) или
все 0-ли (для получения МКНФ) возможно меньшим
числом возможно более крупных размеров контурами.
3. Найти для каждого контура соответствующий ему
интервал.
4. По постоянным переменным интервалов записать
элементарные конъюнкции МДНФ или элементарные
дизъюнкций МКНФ по правилу составления СДНФ или
СКНФ по заданной области истинности или ложности.
Каждый контур карты Карно дает одну элементарную
конъюнкцию в МДНФ или одну элементарную
дизъюнкцию в МКНФ .

23.

Пример 4.2.6 пусть задана логическая функция
f (X1 , X2 , X3 ) = (1,3,6,7)1
Найти МДНФ и МКНФ методом Карно.
Решение:
Карта Карно:
X2 X3
X1
00
01
11
10
0
0
1
1
0
Интервалы области
единиц:
{0-1}={001, 011}
{11-}={111, 110}
0
1
0
1
0
4
3
1
5
2
1
7
6
МДНФ: X1&X3 X1& X2.
Интервалы области нулей:
МКНФ:
{0-0}={000, 010} и {10-}={100, 101}
(X1 X3) & ( X1 X2)

24.

Недостатки метода Карно:
1. Метод применим только для логических функций до
7-ми переменных.
2. Выбор контуров происходит визуально и не
существует алгоритма, обеспечивающего наилучшее,
оптимальное решение.

25.

Определения:
Каждый интервал области единиц логической функции
называют импликантой логической функции.
Максимальную импликанту (максимальный интервал единиц)
называют простой импликантой логической функции.
Дизъюнкция всех простых импликант логической функции
образуют сокращенную ДНФ логической функции.
Аналогичным образом определяются максимальный интервал
области нулей логической функции и сокращенная КНФ

26.

Пример 4.2.7 пусть задана логическая функция
f (X1 , X2 , X3 ) = (1,3,6,7)1
Найти сокращенные ДНФ и МКНФ методом Карно.
Решение:
Все простые
импликанты:
Карта Карно:
X2 X3
X1
00
01
11
10
0
0
1
1
0
{0-1}={001, 011}
{-11}={011, 111}
{11-}={111, 110}
Сокращенная ДНФ:
0
1
0
1
0
4
3
1
5
2
1
7
6
X1&X3 X2& X3 X1& X2.

27.

Все
максимальные
интервалы нулей:
X2 X3
X1
00
01
11
10
0
0
1
1
0
0
{0-0}={000, 010}
{-00}={000, 100}
1
0
1
0
4
3
1
5
2
1
7
6
{10-}={100, 101}
Сокращенная КНФ:
(X1 X3) & (X2 X3) & ( X1 X2)