Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2017-09-26 | 1182 |
5.00
из
|
Заказать работу |
|
|
Это наиболее удобный метод минимизации булевых функций при небольшом числе переменных.
Карта Вейча для двух переменных (а), для трех (б), для четырех (в), для пяти (г), представляет собой таблицу с определенным порядком следования наборов (в клетках таблицы – номера минтермов соответствующего числа переменных) (рис.1.3).
Рис.1.3.
Для удобства пользования картами на полях проставляют значения переменных.
Таблица функции записывается в карту обычным способом 1(0) – в квадратах, соответствующих наборам, где f(x1 x2 … xn)=1(0).
Следует иметь виду, что порядок расположения наборов таков, что при переходе между соседними квадратами по строке или столбцу меняется форма лишь одной переменной в наборе. В этом смысле первая строка карты является соседней с последней, а первый столбец – соседний с последним.
Отсюда возникают возможности проведения операции склеивания, исходя из расположения единиц в карте Вейча.
Правила склеивания с помощью карт Вейча.
Два минтерма склеиваются (рис.1.4), если они расположены:
1) по соседству – в одной строке или одном столбце (рис.1.4,а);
2) в противоположных концах одной строки или одного столбца (рис.1.4,б);
3) в одинаковых местах двух карт (рис.1.4,в), последнее – для n>4.
рис.1.4.
Алгоритм метода минимизации с помощью карт Вейча.
1) Нанести функцию на карту.
2) Каждый квадрат, содержащий «1», проанализировать с точки зрения «склеивания» с другими во всех возможных комбинациях.
3) Выбираются те комбинации, которые объединяют наибольшее количество единиц и при этом накрывают все единицы карты функции. Они являются простыми импликантами функции.
4) Если только одна импликанта покрывает какую-либо единицу на карте, то эта импликанта является существенной (обязательной).
|
5) Из совокупности простых импликант выбираются минимальные формы функции.
Метод позволяет получить все возможные МДНФ:
Метод Блека-Порецкого.
Используется для получения сокращенной ДНФ из любой произвольной функции представления [5].
Идея построения сокращенной ДНФ по произвольной ДНФ вытекает из следующего определения: если в ДНФ для данной функции f(x1 … xn) входит две конъюнкции вида Axi и Bxi, то имеет место равенство D=D\/AB, где D – ДНФ, эквивалентная функция f.
Алгоритм метода Блека-Порецкого.
1. Провести все возможные склеивания любых двух смежных термов, представляющих соответствующие элементарные конъюнкции, получить L-разрядный троичный набор и построить матрицу ранга n.
2. Над полученными элементарными конъюнкциями ранга (n-1) провести операции склеивания и поглощения, образовать элементарные конъюнкции нижнего ранга и т.д.
3. Процесс закончить, когда после операции склеивания и поглощения окажется, что в ДНФ отсутствуют члены, дальнейшее поглощение которых невозможно, т.е. когда будет получена сокращенная ДНФ.
4. Строится импликантная матрица и определяется максимальное покрытие.
Метод удобен при машинных способах минимизации.
Пример. Найти минимальную форму для заданной функции:
1. Матрица исходных данных 3. Матрица ранга (n-2)
0 0 0 1 2 0 2 1
0 0 1 0 2 0 2 1
0 0 1 1 2 0 1 2
1 0 0 1 2 0 1 2
1 0 1 0
1 0 1 1
2. Матрица ранга (n-1)*
0 0 2 1
2 0 0 1
0 0 1 2
2 0 1 0
2 0 1 1
1 0 2 1
1 0 1 2
4. Вычеркиваем одинаковые строки матрицы ранга (n-2) и получаем
A B C D
2 0 2 1
2 0 1 2
5.
где 0 – инверсия переменной, 1 – переменная, 2 – отсутствует переменная.
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!