Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД МИНИМИЗИРУЮЩИХ КАРТ: КАРТЫ КАРНО ЛЕКЦИЯ 14 С.В.ЧУМАЧЕНКО Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ ДИСКРЕТНАЯ МАТЕМАТИКА БУЛЕВА АЛГЕБРА

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 2 Цель лекции – изучить метод карт Карно для минимизации булевых функций, описывающих комбинационные подсхемы цифровых проектов Содержание: Карты Карно двух, трех, четырех переменных Свойства карт Карно Упрощенный стандарт карт Карно Правила минимизации Р-подкубы. Покрытия Выводы Тема: Минимизация булевых функций. Метод карт Карно

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 3 Литература Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк., с. Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовкого ун-та, с. Хаханов В.И. Техническая диагностика элементов и узлов персональных компьюторов. К.: ИСМО, с. Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу Дискретна математика. Харків, ХНУРЕ С

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 4 Базовые понятия: Булева переменная Булева функция Двоичная система счисления Числовое представление ФАЛ Кубическое представление ФАЛ СДНФ и СКНФ Законы склеивания и поглощения Термины Ключевые слова: Минимизация Соседние клетки р-подкуб Одномерный р-подкуб Двумерный р-подкуб Минимальное покрытие

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 5 Представление ФАЛ на картах Карно Карта Карно является графическим способом представления булевых функций нескольких переменных Таблицы истинности функции от 2, 3, 4-х переменных может быть перестроена в карты Карно Пример: карта Карно для двух переменных набора x1x1 x2x x1x2x1x

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 6 Карты Карно для трех и четырех переменных x2x3x2x x1x x3x4x3x x1x2x1x2 Для представления функции на карте достаточно в те клетки, где функция равна единице, поместить единицы Считается, что в остальных клетках содержатся нули

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 7 Свойства карт Карно Карты организованы таким образом, что соседние по строке или по столбцу клетки отличаются значением только одной переменной Если две комбинации значений переменных отличаются только по одной координате, то клетки являются соседними В карте Карно двух переменных клетки на противоположных концах карты тоже являются соседними Это свойство сохраняется для карт Карно трех и четырех переменных: противоположные концы каждой строки или столбца являются соседними

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 8 Упрощенный стандарт карт Карно x1x1 x1x1 x2x2 x2x2 x3x3 x3x3 x4x4 x1x1 x2x2 Для упрощения обозначений строки и и столбцы, содержащие переменную, равную 1, обозначают фигурной скобкой. При этом значение ноль эта переменная имеет в неотмеченных местах

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 9 Правила минимизации Две соседние клетки образуют 1-куб Несущественная координата для двух кубов обозначается символами X: =1Õ1 Четыре клетки объединяются, образуя 2-куб: =1ÕÕ В общем случае могут объединяться соседние клетки, число которых равно 2 n, где n=1,2,3... (2,4,8,16,32,...) с образованием 2-кубов, где k=n

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 10 Примеры представления функций на картах Карно x1x x1x x2x2 x2x2 x3x3 x3x3 x4x4 x1x1 x2x2

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 11 Примеры x3x3 x4x4 x1x1 x2x x3x3 x4x4 x1x1 x2x2

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 12 Time-Out

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 13 Р-подкубы. Покрытия Р-клетки – клетки с единицами Две соседние единицы образуют одномерный р-подкуб Одномерный р-подкуб соответствует произведению, в котором всегда отсутствует один первичный терм Переменная, отсутствующая в произведении, определяется по карте – она имеет различные значения для двух единиц соответствующего подкуба x1x1 11 x2x2 11 x3x3 x4x4 x1x1 x2x2

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 14 Р-подкубы. Покрытия Четыре соседние единицы образуют двумерный р-подкуб Двумерный р-подкуб соответствует произведению без двух первичных термов Опущены те переменные, которые не сохраняют постоянное значение на этом подкубе x3x3 x4x4 x1x1 x2x x3x3 x4x4 x1x1 x2x2

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , x3x3 x4x4 x1x1 x2x x3x3 x4x4 x1x1 x2x2 Трехмерные р-подкубы содержат по 8 единиц Одномерный р-подкуб соответствует ребру, имеющему две соседние вершины Двумерный р-подкуб соответствует двумерному подкубу n-мерного куба Чтобы представить функцию, следует покрыть все единицы карты р-подкубами Р-подкубы. Покрытия

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 16 Представления функций р-подкубами x3x3 x4x4 x1x1 x2x x3x3 x1x1 x2x2 x4x4

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 17 Выводы n Карты Карно есть технологичная форма представления Таблицы истинности для минимизации булевых функций от небольшого числа переменных n На практике используются для минимизации аппаратурных затрат, реализующих функции возбуждения триггеров при синтезе цифровых автоматов n Используются при анализе рисков сбоев, гонок и состязаний, возникающих в цифровых устройствах, соответствующих функциям, которые представлены картами Карно

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 18 Тест-вопросы x1x x1x x2x2 x2x2 x3x3 x3x3 x4x4 x1x1 x2x2 Обозначить на картах Карно минимизирующие контуры Указать результаты склеивания x1x1 111 x2x2 А Б В Г

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 19 Связь булевой алгебры с другими разделами

Минимизация булевых функций. Метод карт Карно Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 20 Выводы к разделу «Булева алгебра» Булева алгебра может выступать в качестве модели для схем из логических элементов Она имеет связь с такими разделами математики как теория множеств, теория групп, логика, теория структур, теория переключательных схем Теория булевых алгебр положена в основу построения модели, описывающей поведение переключательных схем Она является эффективным математическим аппаратом для их исследования