bulevy-funktsii-i-postr.-log.-skhem (1016573), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

 xi i11  xk  xi i11  ...  xn n ,тогдаК1  К 2  x11  x2 2  ...  xi i11  xi  xi i11  ...  xn n  x11  x2 2  ...  xi i11  xi  xi i11  ...  xn n  x11  x2 2  ...  xi i11  xi i11  ...  xn n  xi  xi   x11  x2 2  ...  xi i11  xi i11  ...  xn n .Элементарной конъюнкции x1 1  x2 2  ...

 xi i11  xi i11  ...  xn n ,полученной в результате склеивания, соответствует троичныйвектор степеней1, 2 ,..., i1, , i1,..., n1, n  ,где символ "−" заменяет i -ю компоненту, значение которой утроичных векторов степеней  1 и  2 разное.96В данном случае говорят, что элементарные конъюнкции K1и K 2 склеиваются по переменной xi , или к соседним троичнымвекторам степеней  1 и  2 применяется операция склеивания поi -ой компоненте.Например, для соседних троичных векторов степеней1  1001 и  2  1101 в результате операции склеивания получим:10011101    1  01 .1  01Применить операцию склеивания к троичным векторам степеней  3  1011 и  4  1101 нельзя, так как они различаютсядвумя компонентами и соседними не являются.Пример.

18.2.1. Упростить выражениеx1x2 x3  x1x2 x3  x1x2 x3  x1x2 x3 ,выписав все элементарные конъюнкции в формализованном видеи применяя операцию склеивания троичных векторов степеней.Решение. Запишем элементарные конъюнкции в формализованном виде:Элементарная конъюнкция Троичный вектор степеней 001x1x2 x3  x10 x20 x31 000100110x1x2 x3  x10 x20 x30x1x2 x3  x11x20 x30x1x2 x3  x11x12 x30Применяя операцию склеивания к парам соседних троичныхвекторов степеней, получим001100и000110 .00 1 097Полученные вектора  00   и 1  0  дальше склеивать нельзя.

Имсоответствуют конъюнкции x1 x2 и x1 x3 , поэтомуx1x2 x3  x1x2 x3  x1x2 x3  x1x2 x3  x1x2  x2 x3 .18.3. Сокращённая ДНФОпределение 18.3.1. Элементарная конъюнкция K называется импликантой функции f , если на произвольном наборе аргументов выполняется равенство: K  f  f .Из определения вытекает:- если существует набор аргументов  , на котором функцияf    0 , то на этом наборе и импликанта K    0 ;- если существует набор аргументов  , на котором импли-  канта K   1 , то на этом наборе и функция f   1 .Утверждение 18.3.1 (свойство импликант).

Если K1 иK 2 - импликанты функции f , то их дизъюнкция  K1  K2  такжеявляется импликантой функции f .Доказательство. Пусть K1 и K 2 - импликанты функции f ,тогда на произвольном наборе аргументов выполняются равенK2  f  f .K1  f  fстваиТаккак K1  K2   f  K1   K2  f   K1  f  f , то  K1  K2  такжеявляется импликантой функции f . Утверждение доказано.□Определение 18.3.2. Импликанта K функции f называетсяпростой, если элементарная конъюнкция, получающаяся из Kвыбрасыванием любой переменной, не является импликантойфункции f .Теорема 18.3.2.

Всякая функция реализуется дизъюнкциейвсех своих простых импликант.Доказательство. Пусть D  K1  K 2  ...  K m – дизъюнкциявсех простых импликант функции f  x  и  – произвольныйнабор аргументов.98D    1 , то найдётся дизъюнктивное слагаемоеKi    1, что влечёт f    1, так как Ki - простая импликанта.Если f    1, то в СДНФ для функции f найдётся элементарная конъюнкция K    1. Одна из простых импликант K jфункции f получается из K выбрасыванием некоторых множителей, поэтому K j    1 . Так как K j является одним из слагаеЕслимых выражения D , то D    1 .Получили, что для произвольного набора аргументов  выполняется равенство f    D   .

Следовательно, всякая функция реализуется дизъюнкцией всех своих простых импликант, итеорема доказана.□Определение 18.3.3. Сокращённой ДНФ называется дизъюнкция всех простых импликант функции f .Рассмотрим алгоритм построения сокращённой ДНФ изСДНФ (метод Квайна-МакКласки).Этот метод нахождения множества всех простых импликантбыл предложен первоначально Квайном и усовершенствованМакКласки. Метод предполагает, что функция f задана первоначально в виде СДНФ.1. Для нахождения простых импликант, выписываем все элементарные конъюнкции из СДНФ функции f в формализованном виде. Выписываем троичные вектора степеней в столбец,располагая по порядку возрастания числа единиц в их компонентах.

В результате множество троичных векторов степеней разбивается на соседние классы, между которыми определена операция склеивания.2. Между троичными векторами степеней из соседних классов проводим всевозможные склеивания. Результаты записываемв новый столбец справа, а вектора, участвовавшие в склеивании,помечаем «+».3. К полученному столбцу ещё раз применяем шаг 2.4. В результате операций склеивания остаются троичные вектора степеней, которые дальше склеивать нельзя, выписываем их.995. Добавляем к выписанным троичным векторам степенейвектора, не участвовавшие в склеиваниях (они не помечены знаком «+»). Получаем множество троичных векторов степеней, которым соответствуют все простые импликанты функции f .6. Дизъюнкция всех простых импликант даёт сокращённуюДНФ.Пример 18.3.1. Для функции, заданной СДНФf  x, y, z, w  x yzw  x yzw  x yzw  xyzw  xyzw  x yzw  x yzw  x yzw  xyzw  xyzw ,методом Квайна-МакКласки найти сокращённую ДНФ.Решение.Для нахождения простых импликант выписываем элементарные конъюнкции в формализованном виде.1.2.3.4.5.6.7.8.9.10.0000000101001000001101101001110010111101I столбец++++++++++1.2.3.4.5.6.7.8.9.10.11.12.13.0000-00-00000-101-0-001100-1001-00-01110-11-01110-1-21-31-42-53-62-74-73-84-85-97-97-108-10II столбец++++1.2.3.4.Таблица 18.3.1.-00- 1-7,--00 2-9, 3-8-0-1 4-11, 6-101-0- 9-12++++++++III столбецТроичные вектора степеней располагаем в первом столбцетаблицы 18.3.1 в порядке возрастания числа единиц в их компонентах.

Множество векторов разбивается на четыре класса. Между соседними классами проводим операцию склеивания, а ре100зультаты записываем во второй столбец таблицы справа. Во втором столбце получается три соседних класса, между которымипроводим операцию склеивания. Результаты записываем в третийстолбец таблицы. В третьем столбце получаются троичные вектора степеней, которые дальше склеивать нельзя.Множество троичных векторов степеней, которым соответствуют все простые импликанты функции f , включает:- вектора, полученные в результате операций склеивания втретьем столбце таблицы, которые дальше склеивать нельзя;- вектора, не участвовавшие в склеиваниях (они не помеченызнаком «+»).В таблице 18.3.2 показано соответствий между полученнымитроичными векторами степеней и простыми импликантами:Таблица 18.3.2.1.2.3.4.5.Троичные вектораПростые импликантыстепеней-00yz--00zw-0-1yw1-0xz01-0xywСокращённая ДНФ данной булевой функции имеет вид:f  x, y, z, w   xyw  yz  zw  yw  xz .18.4.

Минимальная ДНФПроблема минимизации булевых функций состоит в том,чтобы построить ДНФ, у которой число вхождений элементарных конъюнкций минимально, по сравнению со всеми другимиДНФ, реализующими булеву функцию.Ранг элементарной конъюнкции K обозначим r  K  .Определение 18.4.1. Рассмотрим ДНФ функции f101D f  K1  K 2  ...  K S ,у которой Ki i  1, S – элементарная конъюнкция ранга r  Ki  .    r  K  называется сложностью ДНФ.Число r DSfi 1iОпределение. 18.4.2.

Минимальной ДНФ (МДНФ) функцииf) называется такая ДНФ, которая имеетf (обозначают Dminнаименьшую сложность среди всех ДНФ, равных функции f , т.е. fr Dmin min r Di f .iПример 18.4.1. Построить несколько ДНФ для функцииf  1110 1100  , и среди них указать минимальную ДНФ.Решение.D1f  x y z  x y z  x y z  x y z  x y z , r D1f  15 ;  D2f  x y  x y z  x y z  x y z , r D2f  11 ; D4f  x y  x z  x y , r  D   6 ;D5f  y  x z , r  D   3 .D5f - минимальная ДНФ, т.к. r  D5f   min r  Di f   3 .1i 5D3f  x y  x y z  x y , r D3f  7 ;f4f5Теорема 18.4.1. Если МДНФ функцииfимеет видD f  K1  K 2  ...

 K S , то все элементарные конъюнкции Ki i  1, S  являются простыми импликантами.Доказательство. Докажем от противного. Предположим, чтоМДНФ функции f имеет вид: D f  K1  K 2  ...  K S и какая-токонъюнкция Ki не является простой импликантой, тогда её можно представить в виде произведения Ki  Ki1  Ki2 , где K i1 - простая импликанта.В этом случае можно получить ДНФ функции f вида:102D1f  K1  ...

 Ki 1  Ki1  Ki 1  ...  K S .Так как для рангов конъюнкций выполняется неравенство    fr  Ki   r Ki1 , то для сложностей ДНФ имеем r D f  r D1 .Таким образом, D f не является минимальной ДНФ функции f .Получили противоречие. Следовательно, предположение, чтоМДНФ содержит конъюнкцию не являющуюся простой импликантой, неверное. Теорема доказана.□Следствие 18.4.2.

МДНФ булевой функции f либо совпадает с сокращённой ДНФ, либо получается из неё путём вычёркивания некоторых простых импликант.18.5. Тупиковая ДНФДля решения вопроса о том, какие простые импликанты входят в МДНФ введём понятие тупиковой ДНФ.Определение 18.5.1. Тупиковой ДНФ (ТДНФ) булевой функции f называется такая дизъюнкция простых импликант (т.е.часть сокращённой ДНФ), которая представляет данную функцию f , но не сохраняет этого свойства после отбрасывания любой простой импликанты.Отметим, что устранение лишних простых импликант из сокращённой ДНФ булевой функции не является однозначнымпроцессом, т. е. булева функция может иметь несколько различных тупиковых ДНФ.

Поэтому для получения МДНФ функции fнеобходимо построить все тупиковые ДНФ функции f , а затемвыбрать из них те, которые имеют наименьшую сложность.При нахождении ТДНФ нужно учитывать, что не все простыеимпликанты из сокращённой ДНФ равноправны. Наиболее важную роль играют ядровые импликанты.Определение 18.5.2. Простая импликанта Ki булевой функции f называется ядровой, если существует набор  , на которомKi    1, а все остальные простые импликанты на этом набореравны нулю.103Определение 18.5.3. Дизъюнкция всех ядровых импликантназывается ядром булевой функции. Обозначают Я  x  .Теорема 18.5.2.

Характеристики

Список файлов учебной работы