Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

Склеивание х у + х`у = х (под х можно понимать любое выражение) позволяет заменить два минтерма, отличающихся вхождением только одной переменной (с отрицанием и без него), одним минтермом более низкого ранга. Пусть, например, функция задана в виде канонической суммы минтермов: у=`х1 х23 + `х1 х2 х3 + х123 + х12 х3 + х1х2х3. Группируя члены и применяя операцию склеивания, имеем у= (`х1 х23 +`х1х2х3 )+ (х123 + х12 х3)+ х1х2х3=`х1 х2 + х12 + х1х2х3. При другом варианте группирования получим у=`х1 х23 + (х1х2х3 + х1х2х3 )+ (х123 + х12 х3)= `х1 х23 + х1 х212.

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

 

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 = х + у.

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

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

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.