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

Минимизация конъюнктивных нормальных форм

Читайте также:
  1. БАЛЬЗАМ-ополаскиватель для нормальных волос, 450мл. 100 руб.
  2. Вычисление площади сечения растянутой арматуры второстепенной балки из условия прочности нормальных сечений
  3. Вычисление площади сечения растянутой арматуры главной балки из условия прочности нормальных сечений.
  4. Минимизация булевых функций с помощью карт Карно
  5. Минимизация булевых функций с помощью матрицы Квайна
  6. Минимизация логических схем со многими выходами

Теория минимизации КНФ аналогична теории минимизации ДНФ за исключением некоторых определений, которые будут ниже приведены.

Булева функция называется имплицентой БФ , если на каком-либо наборе переменных где функция равна нулю или не определена, функция также равна нулю.

Простой имплицентой БФ называется элементарная дизъюнкция, которая является имплицентой булевой функции и никакая ее часть не может быть имплицентой функции .

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

- конъюнкция конечного числа имплицент булевой функции также является имплицентой данной БФ;

- конъюнкция всех имплицент булевых функции является полной системой;

- конъюнкция всех простых имплицент БФ называется сокращенной конъюнктивной нормальной формой.

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

Пример 1.5. СКНФ задана в числовом виде: . С помощью алгоритма Квайна - Мак-Класки найти МКНФ. Запишем эти макстермы в двоичном коде и разделим их на группы (см. табл. 1.8).

Согласно с алгоритмом Квайна - Мак-Класки сравниваем между собой соседние группы и выполняем операцию неполного конъюнктивного склеивания (см. табл. 1.9).

Продолжаем выполнять операцию неполного конъюнктивного склеивания до тех пор, пока имеется возможность.

Таблица 1.8 Имплицентная таблица функции
 
 

 

Таблица 1.9 Таблица склеиваний макстермов  
 
 

 


В нашем примере после еще одного цикла склеивания имеем три простые имплиценты: . Строим имплицентную таблицу 1.10.

Таблица 1.10

Таблица простых имплицент

 
 

 

 


Таким образом, получили минимальную КНФ:

 


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


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

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