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

Логическая функция может иметь несколько различных минимальных нормальных форм МДНФ или МКНФ равной сложности. 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

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

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

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

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

Карта Карно логической функции 3-х переменных – это таблица размера 2 x 4: X 2 X 3 X

Пример пусть задана логическая функция f (X 1, X 2, X 3 ) = (1,3,6,7) 1 Таблица истинности: X 1, X 2, X 3 f (X 1, X 2, X 3 ) Карта Карно: X2 X3X1X2 X3X

Карта Карно логической функции 4-х переменных – это таблица размера 4 x 4: X3 X4X1 X2X3 X4X1 X

Пример пусть задана логическая функция f (X 1, X 2, X 3, Х 4 ) = (0,1,6,8,9,12,14) 1 Карта Карно: X3 X4X1 X2X3 X4X1 X

Карта Карно логической функции 5-ти переменных – это 2 таблицы размера 4 x 4: X3 X4X1 X2X3 X4X1 X X3 X4X1 X2X3 X4X1 X Х 5 = 0Х 5 = 1

Пример пусть задана логическая функция f (X 1, X 2, X 3, Х 4, Х 5 ) = (2,3,5,6,7,11,15,16,17,18,19,21,22,23,26,27,30,31) 1 X3 X4X1 X2X3 X4X1 X X3 X4X1 X2X3 X4X1 X Х 5 = 0Х 5 = 1

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

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

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

X3 X4X1 X2X3 X4X1 X Соседними клетками к клетке 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).

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

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

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

Контуры: X3 X4X1 X2X3 X4X1 X

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

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

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

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

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

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

X2 X3X1X2 X3X Все максимальные интервалы нулей: {0-0}={000, 010} {-00}={000, 100} {10-}={100, 101} Сокращенная КНФ: (X 1 X 3 ) & (X 2 X 3 ) & ( X 1 X 2 )