Cтраница 2
После того как в ДНФ D1 будут включены все конъюнкции - простые импликанты функции /, - преобразование 2) удаляет из D1 конъюнкции, не являющиеся простыми импликантами. [16]
В общем случае сокращенная ДНФ не является минимальной, так как некоторые простые импликанты могут накрываться дизъюнкцией других членов и их можно исключить. [17]
Значит, для получения сокращенной ДНФ достаточно применять поглощение, т.е. все простые импликанты содержатся в остаточных ДНФ. При этом / hi, f - g h и для элементарной конъюнкции, входящей в hi и в 2 ( 2) имеют пересечения по одной переменной, и для / gi V hi, f h элементарные конъюнкции удовлетворяют этому свойству. В итоге получаем, что / и / - недиффузные функции. [18]
Затем надо из множества всех сечений выбрать только те, инверсии которых образуют такие простые импликанты функции /, которые покрывают хотя бы один ее рабочий консти-туент. [19]
Аналогичная ситуация будет иметь, очевидно, место и в том случае, когда все переменные входят в простые импликанты непременно с отрицаниями. Более общо: будем говорить, что в системе простых импликант все переменные разделены, если любая переменная xt не может входить в одну из импликант системы с отрицанием, а в другую - без отрицания. Как и выше, мы легко установим, что полная система простых импликант с разделенными переменными является непременно приведенной системой. [20]
На втором этапе минимизации сокращение перебора достигается за счет того, что проверке на избыточность подлежат не все простые импликанты, а только те, которым соответствуют основные состояния, использованные при упрощении функции не менее двух раз. [21]
Для функции ( 12) сокращенная ДНФ: х-у V J / z ибо х-у и y - z - все простые импликанты этой, функции. [22]
Лш, /) своим простым импликантом, в то время, как поступающие на его входы функции не имеют таких простых импликантов. Получается противоречие, ибо на элементах V новые простые импли-канты не возникают. [23]
Мы можем получить из этой сокращенной таблицы набор тестов, обнаруживающих неисправности, либо выбирая по одному представителю от каждой строки, либо применяя к сокращенной таблице метод простых импликантов. [24]
Применяя процесс подобного исключения многократно, приведем форму go к какой-нибудь тупиковой дизъюнктивной нормальной форме gv Действительно, в силу приведенного выше результата Блейка, с помощью соотношения ( 30) из формы gi все еще можно получить все простые импликанты, входящие в go - Дальнейшее же исключение членов формы g оказывается невозможным. [25]
В предыдущем параграфе были обсуждены проблема минимизации булевых выражений и способы такой минимизации. Метод перечисления и отбора простых импликантов поддается дальнейшим усовершенствованиям, часть которых обсуждается в настоящем параграфе, а другая часть - в упражнениях. [26]
Может оказаться, что останутся простые импликанты, которые не покрывают ни один из одночленов в Ф, не покрываемых элементами ядра. Эти импликанты влекут сумму элементов ядра и являются совершенно лишними: они не войдут ни в одно минимальное выражение. [27]
Импликативные связи могут быть связаны друг с другом не только попарно, но и более сложным образом. К примеру, данная матрица содержит только простые импликанты, а они по определению не могут имплицировать друг друга. Однако может оказаться, что какая-то из них имплицирует дизъюнкцию нескольких из остальных, например двух. [28]
Основное состояние, соответствующее данному импликанту, нужно проверять на покрытие только последующими импликан-тами. Это следует из анализа процесса получения простых импликантов: основное состояние не могло быть покрыто ни одним из предыдущих импликантов, так как в противном случае оно было бы ранее переведено в условные и его нельзя было бы принять за основное. [29]
Здесь видны пределы метода подстановки констант и исключения элементов. Значимость этого метода убывает с ростом длины простых импликантов. Кроме того, в общем случае трудно надеяться, что один элемент Л участвует в вычислении лишь одного простого импликанта. [30]