Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. I. Решение логических задач средствами алгебры логики
  2. II. Модусы эволюции функций.
  3. III. Задача
  4. III. Задача
  5. III. Перейдем к доказательству теоремы о промежуточном значении
  6. IV. Работа над задачами.
  7. IV. Работа над задачами.
  8. IV. Работа над задачами.
  9. IV. Работа над задачами.
  10. IV. Работа над задачами.

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

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

 

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

 

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

 

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

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; просмотров: 12; Нарушение авторских прав







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