Студопедия

КАТЕГОРИИ:

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


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




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

 

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

 

Для построения приведённой системы простых импликант используют импликантную матрицу. В ней количество столбцов – |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; просмотров: 134; Мы поможем в написании вашей работы!; Нарушение авторских прав





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