Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Метод минимизирующих карт Карно

Читайте также:
  1. Amp; Методичні вказівки
  2. Amp; Методичні вказівки
  3. Amp; Методичні вказівки
  4. Amp; Методичні вказівки
  5. Amp; Методичні вказівки
  6. Amp; Методичні вказівки
  7. Amp; Методичні вказівки
  8. B. Искусственная вентиляция легких. Методики проведения искусственной вентиляции легких
  9. Cтруктуры внешней памяти, методы организации индексов
  10. FDDI. Архитектура сети, метод доступа, стек протоколов.

 

При построении сокращенных ДНФ для функций, зависящих от небольшого числа (не более 4) переменных, используется метод карт Карно. Построение карт Карно основано на свойствах булева куба.

Множество всех двоичных наборов длины n образует n-мерный булев или двоичный куб, который называют также единичным n-мерным кубом и обычно обозначают . Применяя геометрическую терминологию, наборы называют вершинами куба .

Расстоянием Хэмминга между вершинами и куба называется число оно равно числу координат, в которых наборы и отличаются друг от друга. Расстояние Хемминга является метрикой, а куб – метрическим пространством.

Наборы и из называются соседними если и противоположными если, т.е. соседние наборы различаются только в одной координате, а противоположные во всех координатах.

Символом обозначают множество т.е. множество всех наборов из , на которых функция обращается в 1.

Гранью единичного n-мерного куба называется множество Множество называется направлением, число k - рангом, а число nk – размерностью грани . Кодом грани G= называется вектор длины n, в котором , а остальные координаты есть «–». Например =

(0–1–). Одномерные грани называются ребрами куба.

Обозначим множество векторов длины n с координатами из множества {0, 1, –} через Gn. На множестве Gn зададим частичный порядок, полагая если вектор может быть получен из путем замены некоторых (быть может, ни одной) координат набора , равных 0 и 1, на «–». Отношение между кодами граней G и H соответствует отношению между гранями. Положим равным числу прочерков в наборе и Тогда соответствует множеству ребер куба , – множеству граней куба , имеющих размерность k. Интервалом куба называется множество вида , где , – вершины из такие, что . Число называется размерностью интервала.

Если элементарная конъюнкция k является импликантой функции , то множество Nk всех наборов и из таких, что образует грань, содержащуюся в множестве Nf. Эта грань называется интервалом функции f, соответствующем импликанте k. Интервал функции f, не содержащийся ни в каком другом интервале функции f, называется максимальным интервалом. Максимальные интервалы функции f соответствуют ее простым импликантам.



В методе минимизирующих карт Карно функция задается прямоугольной таблицей, в которой наборы значений переменных на каждой из сторон прямоугольника расположены в коде Грея. Нахождение простых импликант сводится к выделению максимальных по включению прямоугольников, состоящих из единиц. Из прямоугольников, соответствующих граням максимальной размерности, находим коды максимальных интервалов. Считается, что каждая клетка таблицы является соседней к клетке, примыкающей к противоположной стороне и расположенной на той же горизонтали или вертикали. Метод применим также и для не всюду определенных функций. В этом случае выделяются максимальные прямоугольники, содержащие хотя бы одну единицу и не содержащие нулей.

Пример 2. Таблица 3.12 представляет собой минимизирующую карту для функции с вектором значений Коды максимальных интервалов имеют вид (00-0), (000-), (--01), (-1-1), (110-). Сокращенная ДНФ имеет вид

Таблица 3.12 Таблица 3.13

Пример 3. Таблица 3.13 представляет собой минимизирующую карту для частичной функции f, зависящей от трех переменных. Сокращенная ДНФ имеет вид

 


Дата добавления: 2014-11-13; просмотров: 102; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
В классе КНФ | Задачи по минимизации и доопределению булевых функций
lektsii.com - Лекции.Ком - 2014-2019 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты