Студопедия

КАТЕГОРИИ:

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


Задача минимизации функций алгебры логики. Теоремы Квайна и Мак-Класски.




Минимальной формой булевской функции называется такая форма, которая содержит количество символов, не превышающее количество символов в любой другой форме.

В общем случае минимальных форм может быть несколько.

 

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

 

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

 

Вспомогательные характеристики конституэнт единицы, используемые в теоремах Квайна и Мак-Класски:

1) | xe | = – десятичное представление двоичного набора.

2) index( xe ) =

3) slp = abs ( | xl | – | xp | ) – разность

 

Теорема Квайна: Для того чтобы 2 конституэнты единицы склеивались необходимо и достаточно, чтобы:

1) | index (xl ) - index (xp )|=1

2) slp = 2k , kÎZ+

3) | xl | > | xp | Þ index (xl ) > index (xp )

 

Теорема Мак-Класски:

Необходимыми и достаточными условиями склеивания импликант произвольного уровня являются:

1) Равенство последовательностей разностей

2) Возможность склеивания младших конституэнт единицы в склеиваемых импликантах.



Поделиться:

Дата добавления: 2015-04-05; просмотров: 110; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты