Основные законы алгебры логики и формы логических функций

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

· Переместительный (коммутативности) закон для дизъюнкции:

· Переместительный (коммутативности) закон для конъюнкции:

· Сочетательный (ассоциативности) закон для дизъюнкции:

· Сочетательный (ассоциативности) закон для конъюнкции:

· Первый распределительный (дистрибутивный) закон:

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

Итак

Операция	Значения переменной

Из таблицы видно, что если одновременно. В остальных случаях Те­перь рассмотрим таблицу для функ­ции

Операция

Значения переменной

Отсюда следует, что и утверждение доказано.

· Закон инверсии для дизъюнкции: отрицание дизъюнкции двух логиче­ских переменных равносильно конъюнкции их отрицаний

Рассмотрим таблицу истинности для функции

Операция	Значения переменной

Пусть Тогда

Операция	Значения переменной

что и требовалось доказать. Закон справедлив и для произвольного числа логических пере­менных, т.е.

· Закон инверсии для конъюнкции: отрицание конъюнкции двух логиче­ских переменных равносильно дизъюнкции их отрицаний

В этом случае таблица истинности имеет вид:

Операция	Значения переменной

Функция только в том случае, когда обе переменные равны 1. В остальных случаях он принимает значения равные единице. Имеет место обобщение закона для произвольного числа логи­че­ских пе­ременных, т.е.

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

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

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

Элементарной конъюнкцией Q называется логическое произве­дение пе­ременных и их отрицаний, например, Для того чтобы конъюнкция была элементар­ной, необходимо выполнение условия: каждая переменная в про­изведении должна встречаться только один раз.

Число переменных, составляющих элементарную конъюнкцию, называ­ется ее рангом, т.е. если конъюнкция имеет ранг равный , то она составля­ется из логических переменных. Конъюнкции, тождественно эквивалентные единице, считаются элементарными конъюнкциями нуле­вого ранга.

Аналогично понятию элементарной конъюнкции вводится понятие эле­ментарной дизъюнкции.Элементарной дизъюнкцией называется логи­ческая сумма инверсиро­ванных или не инверсированных переменных, причем каждая переменная встречается в сумме только один раз. К эле­ментарным относится, например, дизъюнкция Теперь

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

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

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

Совершенной дизъюнктивной нормальной формой логической функ­ции от различных двоичных переменных на­зывается д. н. ф., обладающая следующими свойствами [2]:

A. в ней нет двух одинаковых конъюнкций;

B. ни одна конъюнкция не содержит двух одинаковых двоич­ных пере­менных;

C. никакая конъюнкция не содержит двоичной переменной вме­сте с ее отрицанием;

D. все конъюнкции имеют ранг , причем каждая из них со­держит либо переменную либо ее отрицание

Данные свойства можно использовать для при­ведения любой не тожде­ственно ложной функции к совершенной дизъюнктивной нормальной форме. Произвольная логическая функ­ция приводится к совер­шенной д. н. ф. в такой по­следовательности :

— функция приводится к какой-либо дизъюнктивной нор­мальной форме; выполняется условие D — конъюнкции, не содержащие всех переменных, дополняются до их полного числа с получением конъ­юнкций только ранга для чего используются соотношения типа

— из полученной д. н. ф. с конъюнкциями ранга удаляются конъюнкции тождественно ложные и лишние, т. е. повторяю­щие другие конъюнкции.

Рассмотрим следующий пример [2]:

Привести функцию к совершенной д. н. ф.