Преобразование и упрощение формул

Основные свойства булевой алгебры позволяют осуществлять эквивалентные преобразования формул для их упрощения или приведения к требуемому виду, а также для доказательства логических правил и теорем.

Процесс упрощения сводится к последовательному применению тех или иных общих свойств с тем, чтобы уменьшить общее количество вхождений в формулу переменных и символов логических операций. Между тем далеко не очевидно, какое из свойств наиболее целесообразно использовать на каждом шаге, поэтому работа с формулами на интуитивном уровне подобна блужданию в лабиринте. Этому процессу можно придать целенаправленный характер, если воспользоваться свойствами склеивания, поглощения и выявления, представив предварительно исходное выражение в нормальной форме. В дальнейшем преобразования выполняются в дизъюнктивной нормальной форме (сумме минтермов), а соответствующие правила для конъюнктивной нормальной формы (произведения макстермов) можно получить на основе принципа дуальности.

Склеивание х у + х`у = х (под х можно понимать любое выражение) позволяет заменить два минтерма, отличающихся вхождением только одной переменной (с отрицанием и без него), одним минтермом более низкого ранга. Пусть, например, функция задана в виде канонической суммы минтермов: у=`х₁ х₂`х<sub>3</sub> + `х₁ х₂ х₃ + х₁`х<sub>2</sub>`х₃ + х₁`х<sub>2</sub> х<sub>3</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>. Группируя члены и применяя операцию склеивания, имеем у= (`х₁ х₂`х<sub>3</sub> +`х₁х₂х₃ )+ (х₁`х<sub>2</sub>`х₃ + х₁`х<sub>2</sub> х<sub>3</sub>)+ х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>=`х₁ х₂ + х₁`х<sub>2</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>. При другом варианте группирования получим у=`х₁ х₂`х<sub>3</sub> + (х<sub>1</sub>х<sub>2</sub>х<sub>3</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub> )+ (х<sub>1</sub>`х₂`х<sub>3</sub> + х<sub>1</sub>`х₂ х₃)= `х<sub>1</sub> х<sub>2</sub>`х₃ + х₁ х₂+х₁`х₂.

Последующие упрощения основаны на свойствах поглощения и выявления. Поглощение х+ху=х, если под х и у понимать не только переменные, но и любые булевы выражения, позволяет исключить все минтермы, в которые в качестве сомножителя входит некоторый другой минтерм более низкого ранга. Наряду с этим дополнительный член, можно использовать для поглощения и/или замещения других членов (минтермов). Эта операция, называемая обобщенным склеиванием, всегда возможна, если исходная формула наряду с порождающими членами содержит минтермы, в которые в качстве сомножителя входит дополнительный член, например:

xy+xz+yzv=xy+xz+yzv+yz=xy+xz+yz=xy+xz

yz – дополнительный член поглощение выявление

Здесь дополнительный член поглотил yzv, после чего удаляется как не влияющий на значение полученного выражения. В случаях, когда дополнительный член поглощает один из порождающих членов, его удалять нельзя и, следовательно, происходит замещение этого порождающего члена.

Например:

х +`xy + yz = x +`xy + yz + y = x +`xy + y = x + y

у-дополнительный член поглощение замещение

Здесь дополнительный член поглощает минтерм yz и замещает породивший его минтерм `ху. Заметим, что это выражение можно было бы упростить и без введения дополнительного члена с помощью поглощения и замещения: х +`ху + yz = х + у + yz = х + у.

Применяя изложенную процедуру к рассматриваемому примеру для первого варианта группирования `х<sub>1</sub> х<sub>2</sub> + х<sub>1</sub>`х₂ + х₁ х₂ х₃, получаем `х<sub>1</sub> х<sub>2</sub> + х<sub>1</sub>`х₂ + х₂ х₃ или `х<sub>1</sub> х<sub>2</sub> + х<sub>1</sub>`х₂ + х₁ х₃. Аналогично второй вариант `х<sub>1</sub> х<sub>2</sub>`х₃ + х₂ х₃ + х₁`х<sub>2</sub> упрощается к виду `х₁ х₂ + х₂ х₃ + х₁`х<sub>2</sub>, что повторяет уже полученный результат для первого варианта. Таким образом, исходная формула преобразуется к двум формам, которые в данном случае являются и минимальными. К такому же результату можно было бы прийти, применяя только простое склеивание, если в исходном выражении повторить минтерм `х₁х₂х₃ и х₁`х<sub>2</sub> х<sub>3</sub>, о чем, конечно, не так просто догадаться в самом начале преобразования. Следует заметить, что с применением обобщенного склеивания можно упрощать формулы, заданные в любой форме, а не обязательно в канонической. В то же время эта операция не подходит, если порождающие члены содержат различное вхождение (с отрицание и без него) не одной, а двух или больше переменных. Например, х(yz) +`х(`yz), так как при этом дополнительный член (yz) (`yz) обращается в тождественный нуль.

Хотя в рассмотренном примере получены минимальные формы, в общем случае процедура склеивания минтермов не гарантирует этого. Она обеспечивает лишь преобразование к сокращенной форме, минтермы которой называют простыми импликантами. Так как склеиваемые минтермы покрываются минтермом низшего ранга, сокращенная форма не содержит таких импликант, которые целиком покрываются какой-либо одной импликантой. В то же время среди простых импликант могут быть такие, которые покрываются совокупностями других импликант и, следовательно, являются избыточными. После удаления избыточных импликант приходим к тупиковым формам, среди которых находятся и минимальные формы. Следует заметить, что для данной функции существует единственная сокращенная форма, в то время как тупиковых и минимальных формул разработан ряд методов, среди которых наиболее известны алгоритм Квайна – Мак-Класки и графический метод, основанный на картах Карно.