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

Метод Квайна и импликантные матрицы

Читайте также:
  1. I. Определение и проблемы метода
  2. I. ОПРЕДЕЛЕНИЕ И ПРОБЛЕМЫ МЕТОДА
  3. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  4. I. Экспертные оценочные методы
  5. II МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ПОДГОТОВКЕ К ПРАКТИЧЕСКОМУ ЗАНЯТИЮ
  6. II. Категории и методы политологии.
  7. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

 

Метод получения сокращенной дизъюнктивной нормальной формы логической функции называется методом Квайна. При минимизации по методу Квайна в базисе 1 предполагается, что исходная функция задана в СНДФ [2].

Задача минимизации по методу Квайна состоит в попарном сравнении всех импликант, входящих в СНДФ, с целью выявления возможности поглощения какой-то переменной в соответствии с правилом неполного склеивания и поглощения: Операция неполного дизъюнктивного склеивания позволяет сократить число рассматриваемых термов СДНФ. Исключение термов, которые склеились, выполняется с помощью операции поглощения.

Эта процедура склеивания проводится до тех пор, пока не останется ни одного члена, допускающего поглощение с каким-либо другим термом. Термы, подвергшиеся поглощению, отмечаются. Неотмеченные термы представляют собой первичные импликанты.

Полученное логическое выражение не всегда оказывается минимальным, поэтому исследуется возможность дальнейшего упрощения. Для этого составляется таблица, в строках которой записываются найденные первичные импликанты, а в столбцах указываются термы исходного уравнения. Клетки этой таблицы отмечаются в случае, если первичная импликанта входит в состав какого-либо терма. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы.

Теорема Квайна. Если в совершенной дизъюнктивной нормальной форме логической функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получается сокращенная дизъюнктивная нормальная форма этой функции, т.е. дизъюнкция всех ее простых импликант.

Метод Квайна выполняется в несколько этапов.

Пример 1.3. Задана совершенная дизъюнктивная нормальная форма булевой функции в виде . Найти минимальную ДНФ используя метод Квайна.

Операцию неполного дизъюнктивного склеивания можно применить к первому и второму, первому и третьему термам, а также к третьему и пятому, четвертому и пятому термам. В результате получаем .

Заметим, что дальнейшее использование операций неполного дизъюнктивного склеивания и элементарного поглощения невозможно, из чего следует, что функция записана в виде ДНФ. Тогда в соответствии с теоремой Квайна следует, что - сокращенная ДНФ.

Следует отметить, что первым этапом при поиске минимальной ДНФ является метод получения сокращенной ДНФ. Метод поиска минимальной ДНФ всегда связан с большим объемом переборов решений, при этом, чем больше переменных булевой функции, тем большее количество переборов.

Пример 1.4. Пусть булева функция задана таблицей истинности (табл. 1.2)

Таблица 1.2

Таблица истинности

                   
                   
                   
                   
                   
                   
                   
                   

Найти минимальную ДНФ методом Квайна.

СДНФ рассматриваемой булевой функцией, имеет вид

.

Каждый минтерм из СДНФ обозначим каким-либо десятичным номером (произвольно). Выполняем склеивание. Так минтерм 1 склеивается только с минтермом 2 и с минтермом 3, а минтерм 2 с минтермом 4 и т.д. В результате запишем

1-2: ; 1-3: ; 2-4: ; 3-4: ;

4-6: ; 5-6: .

Заметим, что результатом склеивания всегда является элементарная конъюнкция, представляющая собой общую часть складываемых минтермов. Далее выполняем склеивание полученных элементарных конъюнкций. Склеиваются только те конъюнкции, которые содержат одинаковые переменные. Имеем два варианта неполного склеивания:

в результате чего получена одна и та же элементарная конъюнкция . Дальнейшее склеивание невозможно. Выполняем поглощения (из полученной дизъюнктивной формы вычеркиваем все поглощаемые элементарные конъюнкции). В итоге получаем сокращенную ДНФ;

.

Переходим ко второму этапу. Для получения минимальной ДНФ необходимо исключить из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью импликантной таблицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т.е. членами сокращенной ДНФ, а столбцы – минтермами, т.е. членами СДНФ булевой функции.

Таблица 1.3

Импликантная таблицы функции

 
 

 


Как уже отмечалось, простая импликанта поглощает, некоторый минтерм, если является его собственной частью. Клетка импликантной таблицы, на пересечении строки соответствующей рассматриваемой простой импликанте и столбцам соответствующим минтермам помечается крестиком (табл. 1.3). Алгоритм построения минимальной ДНФ по импликантной таблице заключается в следующем:

- ищутся столбцы импликантной таблицы, содержащие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными, и они составляют ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.

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

В рассматриваемом примере ядром булевой функции является импликанты и . Импликанта - лишняя, поскольку ядро накрывает все столбцы импликантной матрицы. Поэтому булева функция имеет единственную ДНФ, которая является тупиковой и минимальной ДНФ:

.

 


Дата добавления: 2015-07-08; просмотров: 376 | Нарушение авторских прав


Читайте в этой же книге: Минимизация конъюнктивных нормальных форм | Минимизация неполностью определенных булевых функций | Метод неопределенных коэффициентов | Логические операторы электронных схем или цепей | Канонический метод синтеза комбинационных схем. | Минимизация логических схем со многими выходами | Характеристики комбинационных схем | Анализ КС методом асинхронного моделирования | Определение абстрактного цифрового автомата | Табличное задание автоматов Мили и Мура |
<== предыдущая страница | следующая страница ==>
Метод минимизирующих карт.| Минимизация функций алгебры логики по методу Квайна - Мак-Класки

mybiblioteka.su - 2015-2024 год. (0.01 сек.)