Cтраница 1
Элементарное поглощение во всех этих теоремах понимается в конъюнктивном смысле; именно, при использовании тождественного соотношения A ( A v В) А говорят, что множитель А осуществляет элементарное поглощение множителя A v В. Доказательства сформулированных теорем мы не будем приводить, поскольку они являются перефразировками доказательств теорем Квайна, Блейка и Нельсона, приведенных в § § 2 и 3 настоящей главы. [1]
Операция элементарного поглощения соответствует тождеству А vABA булевой алгебры. Если использовать дизъюнктивное представление импликантной таблицы лишь для нахождения приведенных систем простых импликант, то наряду с этим тождеством можно, разумеется, употреблять для упрощения выражения также и другие тождества булевой алгебры, не содержащие отрицаний и констант. [2]
Выполняя в дизъюнктивном представлении импликантной таблицы все элементарные поглощения и устраняя все повторения в соответствии с тождествами ААА и АуАА, мы приходим к так называемому приведенному дизъюнктивному представлению импликантной таблицы. Термам этого представления соответствуют все приведенные системы простых импликант рассматриваемой булевой функции. [3]
Заметим, что в этом примере мы произвели часть элементарных поглощений еще до того, как были закончены все операции обобщенного склеивания. Ясно, что таким, упрощающим выкладки приемом можно пользоваться всякий раз, когда исключаемые члены не могут дать ( в результате обобщенного склеивания) никаких новых членов. [4]
Необходимо подчеркнуть при этом, что исключить с помощью операции элементарного поглощения можно лишь те члены, к которым были применены все возможные для них склеивания. Нарушение этого условия может привести к ошибкам. [5]
Применял к совершенной к.н.ф. булевой функции все возможные операции неполного конъюнктивного склеивания и устраняя элементарные поглощения, мы получаем сокращенную к.н.ф. этой функции. [6]
Элементарное поглощение во всех этих теоремах понимается в конъюнктивном смысле; именно, при использовании тождественного соотношения A ( A v В) А говорят, что множитель А осуществляет элементарное поглощение множителя A v В. Доказательства сформулированных теорем мы не будем приводить, поскольку они являются перефразировками доказательств теорем Квайна, Блейка и Нельсона, приведенных в § § 2 и 3 настоящей главы. [7]
После получения дизъюнктивной нормальной формы g, содержащей все свои простые импликанты, ее нетрудно освободить от всех членов, не являющихся простыми импликантами. Подобное исключение называют обычно операцией элементарного поглощения. [8]
Для получения одних лишь приведенных систем простых импликант в дизъюнктивном представлении импликантной таблицы нужно, очевидно, произвести исключение тех термов, которые содержат в своем составе другие термы того же представления. Операция исключения более сложных термов при наличии более простых называется обычно операцией элементарного поглощения термов. [9]
Точно так же, как и в § 1, строится конъюнктивное представление имплицентной таблицы. Превращая это представление в дизъюнктивное ( с помощью раскрытия скобок) и осуществляя упрощения в соответствии с правилами булевой алгебры ( элементарные поглощения), мы получаем дизъюнкцию произведений простых имплицент. Каждое из таких произведений является тупиковой к.н.ф. исходной булевой функции, причем таким способом получаются все тупиковые ( а, значит, и все минимальные) конъюнктивные нормальные формы. [10]
Если исходная функция задана в конъюнктивной нормальной форме, то построение минимальной формы методом непосредственного упрощения осуществляется так. Вначале, пользуясь законом распределительности конъюнкции относительно дизъюнкции, раскрывают в конъюнктивной нормальной форме скобки. После этого приводят подобные члены и устраняют элементарные поглощения. Таким образом получается дизъюнктивная нормальная форма, минимизацию которой проводят указанным алгоритмом. [11]
Рассмотрим один из наиболее распространенных методов нахождения сокращенных ДНФ - метод Квайна. Для этого метода исходная булева функция должна быть представлена в СДНФ. Если эта функция представлена в произвольной ДНФ, то ее с помощью операции развертывания, заключающейся в умножении некоторых членов на выражение вида х / х1, приводят к СДНФ. Метод Квайна основан на последовательном применении к парам дизъюнктивных членов операций склеивания и элементарного поглощения. [12]
Для этой цели необходимо перебрать все возможные комбинации ветвей, удаление которых обрывает все пути, и выбрать из них комбинацию, обладающую минимальной суммарной емкостью. Однако такой метод неалгоритмичен и поэтому трудно поддается механизации. Более эффективным является метод определения минимальных сечений [62], аналогичный методу получения приведенных систем простых импликант булевых функций. Можно показать, что в этом случае остаются справедливыми равносильности тождества и элементарного поглощения, способ выделения ядра и другие приемы, используемые для получения приведенных систем простых импликант. [13]