Студопедия

КАТЕГОРИИ:

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



Приведенная система простых ипликант и конъюнктивная форма импликантной матрицы.




Читайте также:
  1. Amp; 3. Управління, прийняття рішень та інформаційна підтримка в умовах надзвичайних ситуацій.
  2. CASE-технология создания информационных систем
  3. CASE-технология создания информационных систем.
  4. E) деформациялар мен сызаттарды болғызбау
  5. E. создания инструментальных программных средств информационных технологий
  6. ERP система
  7. GIF (Graphics Interchange format – формат графічного обміну).
  8. GPSS World – общецелевая система имитационного моделирования
  9. I. Информационная безопасность Российской Федерации
  10. I. Информационная карта

Система простых импликант некоторой булевской функции, не содержащая избыточных простых импликант, называется приведенной системой простых импликант.

 

Избыточная простая импликанта – та, мн-во истинности которой покрывается другими ипликантами.

 

Для построения приведённой системы простых импликант используют импликантную матрицу. В ней количество столбцов – |Tf| – мощность множества истинности исходной функции; количество строк – мощность системы простых импликант.

Элемент матрицы aij = 1, если i-ая простая импликанта покрывает j-ую конституэнту единицы, иначе aij = 0.

 

Конъюнктивная форма импликантной матрицы строится в виде конъюнкции по столбцам дизъюнкций ненулевых элементов каждого столбца. Затем конъюнктивная форма преобразуется в дизъюнктивную (дизъюнкция конъюнкций), в которой каждой конъюнкции соответствует неизбыточная система простых импликант.


21. Теоремы Квайна и Мак-Класски и минимизация булевских функций на n-мерных гиперкубах – доказательство.

Что такое ваще склеивание (т.н. правила склейки):

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

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

2) slp = 2k , kÎZ+

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

 

Примерное док-во теоремы Квайна:

1) Возьмём 2 склеивающиеся конституэнты единицы. Представим их как кортежи единичек и ноликов. У них все разряды кроме одного одинаковые. Сложим их по модулю 2 (эта операция эквивалентна операции взятия разности их модулей). Получаем что их сумма по модулю (она же разность модулей) 2 равна целой степени двойки:
x1xn
Å
x1xn
=
0 …0 1 0 … 0 = 2 j-1
.
Т.о. доказали теорему в одну сторону.

2) В обратную сторону – х.з., как. =( Но в общем-то аналогично. ;)

 

 

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

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

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

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

 


Дата добавления: 2015-04-05; просмотров: 8; Нарушение авторских прав







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