![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Метод минимизирующих карт Карно
При построении сокращенных ДНФ для функций, зависящих от небольшого числа (не более 4) переменных, используется метод карт Карно. Построение карт Карно основано на свойствах булева куба. Множество всех двоичных наборов длины n образует n-мерный булев или двоичный куб, который называют также единичным n-мерным кубом и обычно обозначают Расстоянием Хэмминга между вершинами Наборы Символом Гранью единичного n-мерного куба (0–1–). Одномерные грани называются ребрами куба. Обозначим множество векторов длины n с координатами из множества {0, 1, –} через Gn. На множестве Gn зададим частичный порядок, полагая Если элементарная конъюнкция k является импликантой функции В методе минимизирующих карт Карно функция задается прямоугольной таблицей, в которой наборы значений переменных на каждой из сторон прямоугольника расположены в коде Грея. Нахождение простых импликант сводится к выделению максимальных по включению прямоугольников, состоящих из единиц. Из прямоугольников, соответствующих граням максимальной размерности, находим коды максимальных интервалов. Считается, что каждая клетка таблицы является соседней к клетке, примыкающей к противоположной стороне и расположенной на той же горизонтали или вертикали. Метод применим также и для не всюду определенных функций. В этом случае выделяются максимальные прямоугольники, содержащие хотя бы одну единицу и не содержащие нулей. Пример 2. Таблица 3.12 представляет собой минимизирующую карту для функции Таблица 3.12 Таблица 3.13
Пример 3. Таблица 3.13 представляет собой минимизирующую карту для частичной функции f, зависящей от трех переменных. Сокращенная ДНФ имеет вид
|