МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД МИНИМИЗИРУЮЩИХ КАРТ: КАРТЫ КАРНО ЛЕКЦИЯ 16

ХАХАНОВ
Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ
ДИСКРЕТНАЯ МАТЕМАТИКА
БУЛЕВА АЛГЕБРА

функций, описывающих комбинационные подсхемы цифровых проектов
Содержание:
Карты Карно

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

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

1987. 222-240 с.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко

С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.35-43.
Дискретная математика: Гипертекстовые учебные материалы (электронный учебник) / В.И. Хаханов, С.В. Чумаченко. 2004. http/…/10.13.20.100/nserv/library/education/Чумаченко/Дискретная математика/Дистанционный_учебник/index.htm.
Арифметические и логические основы цифровых автоматов. Гипертекстовые учебные материалы (электрон. учебник) / А.С. Шкиль. 2004. http/…/10.13.20.100/nserv/library/education/Шкиль/ ЛМ/Лк_лб/st_text/index.htm.

ФАЛ
СДНФ и СКНФ
Законы склеивания и поглощения


Термины
Ключевые слова:
Минимизация
Соседние клетки

р-подкуб
Одномерный
р-подкуб
Двумерный
р-подкуб
Минимальное покрытие

булевых функций от нескольких переменных
Таблицы истинности функции от 2,

3, 4-х переменных могут быть перестроены в карты Карно
Пример: карта Карно для двух переменных

x1x2

00 01 11 10

10
x1
0
1

10
00
01
11
10
x1x2

достаточно в те клетки, где функция равна единице, поместить единицы

Считается, что в остальных клетках содержатся нули
Примеры

x2x3

00 01 11 10

x1

0
1

x1x2

00 01 11 10

строке или по столбцу клетки отличаются значением только одной переменной

Если две комбинации значений переменных отличаются только по одной координате, то клетки являются соседними
В карте Карно двух переменных клетки на противоположных концах карты тоже являются соседними
Это свойство сохраняется для карт Карно трех и четырех переменных: противоположные концы каждой строки или столбца являются соседними

переменная хi равна 1, обозначают фигурной скобкой. При этом значение

ноль эта переменная имеет в неотмеченных местах

одномерный р-подкуб
Одномерный р-подкуб соответствует произведению, в котором всегда отсутствует один

первичный терм
Переменная, отсутствующая в произведении, определяется по карте – она имеет различные значения для двух единиц соответствующего подкуба

x1

x2

x3

x4

x1

x2

без двух первичных термов
Опущены те переменные, которые не сохраняют постоянное

значение на этом подкубе

x3

x4

x1

x2

x3

x4

x1

x2

две соседние вершины
Двумерный р-подкуб соответствует двумерному подкубу n-мерного куба
Чтобы представить

функцию, следует покрыть все единицы карты р-подкубами

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

обозначается символами X: 101111=1Õ1
Четыре клетки объединяются, образуя 2-куб:

100 

101  110  111=1ÕÕ

В общем случае могут объединяться соседние клетки, число которых равно 2k, где k=1,2,3... (2,4,8,16,32,...) с образованием k-кубов


5 и 7 
8 

Итак, результирующая ДНФ имеет вид:

Например: требуется получить минимальную ДНФ для функции Y=1 на наборах

{0,1,2,5,6,11,13,15}

x3

x4

x1

x2

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

булевых функций от небольшого числа переменных
На практике используются для минимизации

аппаратурных затрат, реализующих функции возбуждения триггеров при синтезе цифровых автоматов
Используются при анализе рисков сбоев, гонок и состязаний, возникающих в цифровых устройствах, соответствующих функциям, которые представлены картами Карно