Курсовая работа: Логическое проектирование и минимизация
fсднф = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 ( 1.5)
1-й этап - производим все возможные склеивания членов заданной функции. В общем случае эта процедура осуществляется за несколько шагов, в результате каждого из которых происходит понижение ранга склеиваемых членов на единицу. На первом шаге склеиваются конституенты:
fпр = x1 x3 + x2 x3 + x1 x2 (1.6)
Затем производится второй шаг испытания на склеивание всех членов функции в промежуточной форме. Рассматривая соотношение (1.6), убеждаемся, что все его члены изолированы. Следовательно, полученная промежуточная форма является сокращенной ДНФ исходной функции (сДНФ). Отметим, что все конституенты функции (1.5) участвовали хотя бы в одном склеивании, поэтому ни в сокращенной, ни тем более в тупиковой форме членов максимального ранга не будет:
fсднф = x1 x3 + x2 x3 + x1 x2 (1.7)
2-й этап - осуществляется проверка каждой простой импликанты в сДНФ с целью выявления и удаления лишних членов. Проверка состоит в следующим. На значение истинности функции влияет только та импликанта, которая сама равна 1. любая импликанта становится равной 1 лишь на одном, вполне определенном наборе значений истинности своих аргументов. Но если именно на этом наборе суммы остальных членов тоже обращается в 1, то рассматриваемая импликанта не влияет на значение истинности функции даже в этом единственном случае, т.е. является лишней. Применим это правило к проверке членов функции в сДНФ (1.7):
1) x1 x3 = 1 при x1 = 0, x3 = 1; сумма остальных членов на этом же наборе равна x2 1 + 1x2 = 1; следовательно, проверяемый член - лишний;
2) x2 x3 = 1 при x2 = 0, x3 = 1; сумма остальных членов на этом же наборе равна x1 1 + x1 0 = x1 ; следовательно, проверяемый член не является лишним;
3) x1 x2 = 1 при x1 = 0, x2 = 1; сумма остальных членов на этом же наборе равна 1x3 + 0x3 = x3 ; следовательно, проверяемый член не является лишним.
Таким образом, отбросив лишний член, получим тупиковую дизъюнктивную нормальную форму (ТДНФ) исходной функции:
fтднф = x1 x2 + x2 x3 (1.8)
Более подробно остановимся на случае, когда лишних членов оказывается больше, например два. Это не означает, что оба лишних члена можно отбросить, так как каждый из них проверялся при вхождении другого в оставшуюся сумму. Следовательно, отбросить наверняка можно только один из них, а затем нужно снова произвести проверку возможности отбросить и второй член.
Следует также остановится подробнее и на случае, когда исходной формой является СКНФ. Методика проведения первого этапа при этом практически не изменяется, но реализация второго этапа имеет свою специфику. На значение истинности функции в конъюнктивной нормальной форме влияет только та имплицента, которая сама равна 0. Но любая имплицента становится нулем только при одном наборе своих аргументов. Следовательно, правило проверки сокращенной КНФ на лишние члены нужно сформулировать таким образом: для каждого члена сокращенной КНФ находится такой набор значений истинности его переменных, который обращает данный член в 0. Далее определяется значение истинности произведения остальных членов на этом же наборе. Если произведение также равно 0, то проверяемый член - лишний.
3-й этап - упрощаем ТДНФ или ТКНФ функции. Применив закон инверсии к первому члену функции в ТКНФ, получим минимальную форму (МФ):
fмф = x1 x2 (x2 + x3 )
для аппаратурной реализации которой нужной всего семь условий транзисторов. Интересно, что преобразование в минимальную форму ТДНФ функции получается более сложным путем:
fтднф = x1 x2 + x2 x3 = (x1 + x2 )(x2 + x2 )(x1 + x3 )(x2 + x3 ) = (x1 + x2 )(x1 + +x3 )(x2 + x3 ) = fскнф
Переход от сКНФ к МФ нетрудно осуществить через ТКНФ, как это было сделано выше.
1.4. Расчётно-табличный метод минимизации
Минимизация этим способом отличается от расчётной минимизации только методикой выявления лишних членов в сокращённой Д(К)НФ. Данный метод предложен американским ученым У.Квайном. Первый и третий этапы минимизации в этом случае будут идентичны соответствующим этапам при расчетном методе. Нахождение тупиковой формы (второй этап) производится с помощью специальной таблицы (отсюда название метода), значительно упрощающей обнаружение лишних членов. рассмотрим методику расчетно-табличной минимизации на том же примере, который разбирался нами при расчетном способе, что дает возможность более четко показать как общие черты обоих методов, так и их различия.
Итак, пусть требуется минимизировать функцию (1.5), заданную в СДНФ:
fсднф = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3
1-й этап - не отличается по содержанию от 1-го этапа при расчетном методе. Поэтому сразу же запишем исходную функцию в сДНФ:
fcднф = x1 x3 + x2 x3 + x1 x2
2-й этап - для выявления возможных лишних членов в сД(К)НФ функции построим таблицу, входными величинами в которой будут конституенты - члены СД(К)НФ и импликанты (имплиценты) - члены сокращенной Д(К)НФ. Поэтому чаще всего такую таблицу называют конституентно-импликантной (имплицентной) матрицей; применяются также названия: таблица Квайна и таблица покрытий. Она имеет число строк, равное количеству импликант (имплицент) в сокращенной Д(К)НФ. Строки делятся на столбцы, число которых берется равным количеству конституент в СД(К)НФ. Поэтому в горизонтальные (строчные) входы таблицы записываются все простые импликанты(имплиценты), а в вертикальные входы - все члены совершенной нормальной формы (см. табл. 1.3).
Таблица 1.3
Таблица Квайна.
| Импли- | Конституенты | |||
| канты | x1 x2 x3 | x1 x2 x3 | x1 x2 x3 | x1 x2 x3 |
| x1 x3 | X | X | ||
| x2 x3 | X | X | ||
| x1 x2 | X | X | ||
Процесс минимизации начинается с последовательного составления каждой импликанты со всеми конституентами. Если какая-либо импликанта является собственной частью некоторой конституенты, то в табличной клетке, соответствующей обоим членам, проставляется любой условный значок (так, в табл.1.3 клетка перечеркивается крест-накрест). Таким образом, значки в каждой строке заполненной таблицы показывают, какие члены совершенной формы функции появятся при развертывании данной импликанты в семейство конституент. В идеальном случае каждая импликанта развертывалась бы только в “свои” конституенты, и в каждом столбце тогда находился бы только один условный значок. Практически этого не происходит, и очень часто одна и та же конституента покрывается в таблице несколькими импликантами. Задача состоит в том, чтобы вычеркиванием некоторых (лишних!) импликантов попытаться оставить в каждой колонке только значок или по крайней мере минимальное число импликант, покрывающих все конституенты. Практически обычно по таблице вначале находится так называемое ядро функции, состоящее из трех импликант (имплицент), каждая из которых осуществляет единственное покрытие некоторой конституенты и поэтому никоим образом не может оказаться в числе лишних.
Возвращаясь к рассматриваемому примеру (см.табл.1.3), констатирует. что в ядро функции входят импликанты x1 x2 и x2 x3 . Следовательно, остается только проверить возможность вычеркивания импликанты x1 x3. Ее вычеркивание не нарушает условия о наличии хотя бы одного покрытия каждой конституенты любой импликантой. Следовательно, импликанта x1 x3 является лишней. Тупиковая дизъюнктивная нормальная форма исходной функции