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

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

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

Каждая тупиковая ДНФ функции f содержит ядро этой функции.Доказательство. Докажем от противного. Если Ki - ядроваяимпликанта функции f , то существует набор  , на которомKi    1. Тогда значения всех остальных простых импликантфункции f на наборе  равны нулю.

Предположим, что Ki невходит в какую-нибудь ТДНФ функции f . В этом случае значение этой ТДНФ на  равно нулю, в то время как f    1, т.е.ТДНФ не реализует функцию f . Получаем противоречие. Следовательно, предположение, что ядровая импликанта не входит вТДНФ неверное. Теорема доказана.□Определение 18.5.4. Простая импликанта K называется несущественной, если она обращается в единицу только на технаборах, где ядро равно единице.Теорема 18.5.3.

Тупиковая ДНФ функции f не содержит несущественных импликант.Доказательство. Докажем от противного. Любую ТДНФможно записать в видеDТ  Я  K1  K 2  ...  K S ,где Я - ядро функции f , Ki ( i  1, S ) – некоторые неядровые простые импликанты. Предположим, что среди неядровых простыхимпликант имеется несущественная, например, K1 .Покажем, что Я  K1  Я . Пусть  - произвольный наборпеременных.Если K1    0 , то равенство выполняется, так какЯ    K1    Я    0  Я   .Если K1    1, то по определению несущественной импликанты имеем Я    1.

Равенство выполняется, так какЯ    K1    1  1  1  Я   .104Применяем равенство Я  K1  Я к выражению для тупиковой ДНФ: DТ  Я  K1  K2  ...  K S  Я  K 2  ...  K S . Получили, что из тупиковой ДНФ можно удалить импликанту K1 , а этопротиворечит определению ТДНФ. Следовательно, наше предположение, что ТДНФ функции f содержит несущественную импликанту неверное. Теорема доказана.□Таким образом, при построении тупиковых ДНФ несущественные импликанты можно удалять из сокращённой ДНФ, безпотери равносильности полученной ДНФ исходной функции.Алгоритм построения ТДНФ и МДНФ из сокращённой ДНФ:1. Выписываем все простые импликанты из сокращённойДНФ функции f . Присвоим каждой простой импликанте некоторое имя, т.е.

обозначим их, например, как K1 , K 2 , …, K m .2. Для получения минимальной ДНФ необходимо убрать изсокращенной ДНФ все несущественные импликанты. Это делается с помощью специальной импликантной матрицы Квайна, которая строится по следующему правилу:- каждому столбцу ставим в соответствие простую импликанту K j ;- каждой строке ставим в соответствие двоичный набор  i , накотором f i   1.На пересечении строки и столбца ставим значение простойимпликанты K j i  .Формируя из импликант функции f , соответствующихстолбцам матрицы Квайна, некоторую тупиковую ДНФ, надо побеспокоится о том, чтобы для каждой строки матрицы Квайна вТДНФ нашлась импликанта, принимающий значение 1 на наборе,соответствующем этой строке.3. Ищем ядровые импликанты (все столбцы, в которых содержится 1, являющаяся единственной в некоторой строке), покоторым выписываем ядро Я  x  функции f  x  .4.

Строим сокращённую матрицу Квайна:105- вычёркиваем из матрицы Квайна столбцы, соответствующие ядровым импликантам, а также строки, соответствующиедвоичным наборам  i , на которых f i   1 и Я i   1 ;- среди оставшихся столбцов матрицы Квайна ищем столбцысоответствующие несущественным импликантам (столбцы, у которых все единицы оказались вычеркнутыми на предыдущемэтапе) и вычёркиваем их.Получаем сокращённую матрицу Квайна состоящую из строксоответствующих двоичным наборам  i , для которых f i   1 иЯ i   0 , и столбцов не содержащих ядровых и несущественных импликант.5. Составляем вспомогательную функцию Петрика, котораяявляется конъюнктивным представлением сокращённой матрицыКвайна:- для каждой i -ой строки сокращённой матрицы Квайнастроим элементарную дизъюнкцию из имён простых импликант,обозначающих столбцы матрицы, на пересечении с которыми в i-ой строке находятся единицы;- из построенных для всех строк матрицы дизъюнкций составляем КНФ, которая называется вспомогательной функциейПетрика.6.

Преобразуем функцию Петрика в ДНФ. Для этого в полученной КНФ в соответствии с законами дистрибутивности раскрываем скобки, производим всевозможные элементарные поглощения и устраняем все повторения. Получим ДНФ, в которойкаждая элементарная конъюнкция соответствует некоторой тупиковой ДНФ и, наоборот, каждой тупиковой ДНФ может быть сопоставлена одна из этих конъюнкций.Обоснованием данного факта служит то, что функция Петрика принимает значение 1 тогда и только тогда, когда каждая элементарная дизъюнкция равна 1. В свою очередь, элементарнаядизъюнкция равна 1, когда хотя бы одна из её переменных равна1.

Переменными в ДНФ, полученной из функции Петрика, являются имена простых импликант. Поэтому каждая конъюнкцияэтой ДНФ описывает некоторое множество простых импликант, в106котором для любого двоичного набора  i такого, что f i   1 иЯ i   0 , найдётся хотя бы одна импликанта, равная на этомнаборе единице. Добавив к полученному множеству ядровые импликанты, получим множество простых импликант, в которомдля любого двоичного набора  i такого, что для f i   1,найдётся импликанта принимающая единичное значение.

Этотфакт гарантирует, что тупиковая ДНФ, составленная из импликант данного множества, будет эквивалентна исходной СДНФфункции f .7. По конъюнкциям ДНФ, полученной из функции Петрика,выписываем все тупиковые ДНФ функции f . Для этого:- по именам импликант, входящих конъюнкции, выписываемсоответствующие множества простых импликант;- к выписанным множествам импликант добавляем ядровыеимпликанты;- по полученным множествам простых импликант формируем тупиковые ДНФ.8. Среди выписанных тупиковых ДНФ выбираем минимальную по сложности ДНФ.Применяя данный алгоритм, найдём все минимальные ДНФдля функции из примера 18.3.1.Так как для данной функции сокращённая ДНФ имеет видDcoкр  xyw  yz  zw  yw  xz , то матрица Квайна (рис. 18.5.1) впервоначальном виде содержит 10 строк (по числу единичныхнаборов функции) и 5 столбцов (по числу простых импликант).На пересечении строки и столбца будем ставить единичные значения простых импликант, а нулевые значения вписывать не будем, им будут соответствовать пустые клетки таблицы(рис.18.5.1).Ищем ядровые импликанты и упрощаем матрицу Квайна.Строка, соответствующая набору (0011), содержит толькоодну единицу в четвёртом столбце.

Следовательно, импликантаК4 – ядровая. Вычёркиваем из матрицы четвёртый столбец, атакже строки, соответствующие наборам (0001), (0011), (1001),107(1011), на которых эта ядровая импликанта принимает единичныезначения.Строка, соответствующая набору (0110), содержит толькоодну единицу в первом столбце. Следовательно, импликанта К1 –ядровая.

Вычёркиваем из матрицы первый столбец и строки, соответствующие наборам (0100), (0110), на которых эта импликанта принимает единичные значения.Строка, соответствующая набору (1101), содержит толькоодну единицу в пятом столбце. Следовательно, импликанта К5 –ядровая. Вычёркиваем из матрицы пятый столбец и строки, соответствующие наборам (1000) , (1001), (1100), (1101), на которыхэта импликанта принимает единичные значения.18.5.1. Первоначальный вид матрицы Квайна.В результате получаем, что ядро состоит из простых импликант K1  xyw, K 4  yw, K5  xz , а упрощённая матрица Квайнаимеет вид, показанный на рис.18.5.2.По упрощённой матрице Квайна выписываем вспомогательную функцию Петрика: K  f   K2  K3 .108В данном случае вспомогательная КНФ и вспомогательнаяДНФ совпадают.18.5.2.

Упрощённая матрица Квайна.По дизъюнктивным слагаемым вспомогательной ДНФ составляем все тупиковые ДНФ функции f . Для этого:- по именам импликант, входящих конъюнкции, выписываемсоответствующие множества простых импликант: y z , zw ;  - к выписанным множествам импликант добавляем ядровыеимпликанты: yz, xyw, yw, xz , zw, xyw, yw, xz ;- по полученным множествам простых импликант формируем тупиковые ДНФ:D1f  yz  xyw  yw  xz , D2f  zw  xyw  yw  xz .ТаккаксложностиполученныхТДНФравны   r D1f  r D2f  9 , то каждая из этих ДНФ является минимальной.Таким образом, получили две минимальные ДНФ:fDmin1 xyw  yz  yw  xz ;fDmin2  xyw  zw  yw  xz .18.6.

Алгоритм минимизации булевой функции в классенормальных формЗадачу минимизации булевой функции f в классе ДНФ можнорассматривать как переход от СДНФ к МДНФ, который включаетряд этапов рис.18.6.1.109СДНФфункции fСокр. ДНФфункции fПо методу Квайна-МакКласкиПо матрице Квайна (с помощью функции Петрика)ТДНФфункции fПо сложности ТДНФМДНФфункции f18.6.1. Этапы минимизации в классе ДНФ.Запишем алгоритм минимизации булевой функции в классеДНФ:1.

Строим СДНФ функции f.2. По методу Квайна-МакКласки находим сокращённуюДНФ функции f.3. С помощью матрицы Квайна и функции Петрика находимвсе ТДНФ функции f.4. Среди построенных ТДНФ выбираем все минимальныеДНФ функции f.Для получения минимальных форм в классе КНФ используют те же методы, только для функции f .Чтобы построить все минимальные КНФ (МКНФ) функции f,следует построить все МДНФ функции  f и взять от каждой изних отрицание. Полученные КНФ для функции f будут минимальными.

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

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