22. Основные законы булевой алгебры ПФ. Формулы равносильных преобразований.
Основные законы булевой алгебры переключательных функций

Формулы ПФ f1 и f2 равносильны, если их эквиваленция f1f2 явля-ется тождественно истинной (тавтологией). Равносильность, как правило, обозначается , но мы будем «нестрого» использовать в дальнейшем и простое равенство =.
Равносильность – это некоторое отношение, которое обладает сле-дующими свойствами:
а) оно рефлексивно, т.е. ff, всякая формула f равносильна самой се-бе;
б) оно симметрично: если f1f2, то f2f1;
в) оно транзитивно: если f1f2 и f2f3, то f1f3.
Равносильности формул алгебры логики часто называют законами. Они подобны законам алгебры множеств. Говорят, что булева алгебра логических (переключательных) функций изоморфна булевой алгебре множеств.
Законы булевой алгебры:
1) хх – закон тождества. Закон тождества означает, что мысль, заключенная в некотором высказывании, соответствующем двоичной переключательной функции остается (считается) неизменной на протяжении всего рассуждения.
2)   – закон противоречия. Закон противоречия гласит, что никакое предложение не может быть истинным одновременно со своим отрицанием.
3)   – закон исключенного третьего. Закон исключенного третьего говорит о том, что для каждого высказывания имеется лишь две возможности: быть либо истинным, либо ложным. Третьего не дано.
4)   – закон двойного отрицания.
5) ххх; ххх – закон идемпотентности (от латинского idem – то же, potentio – сила). Этот закон рассматривается относительно операций конъюнкции и дизъюнкции. В силу закона идемпотентности в алгебре логики, как и в алгебре множеств, нет показателей степеней, коэффициентов. Оказывается, основные законы алгебры логики двойственны (справедливы относительно конъюнкции и дизъюнкции).
6) хyyх; xyyх – закон коммутативности (переместительности).
7) х(yz)(xy)z; x(yz)(xy)z – закон ассоциативности (сочета-тельности).
8) х(yz)xyхz; xyz)(xy)(хz) – закон дистрибутивности (рас-пределительности). Закон дистрибутивности относительно дизъюнкции не имеет аналога в обычной алгебре.
9)  ;   закон Де Моргана. Отрицание конъюнк-ции высказываний равносильно дизъюнкции отрицаний этих высказыва-ний. Отрицание дизъюнкции высказываний равносильно конъюнкции от-рицаний этих высказываний.
10) xхyх; х(xy)х – закон поглощения. Короткий член конъюнкции (дизъюнкции) поглощает длинный член, содержащий короткий в качестве составной части.
11)     – закон склеивания. Здесь склеивание производится по переменной y; она исключается, если входит в члены дизъюнкции (конъюнкции) с разными знаками, а остальные элементы в конъюнкции (дизъюнкции) с ней одинаковы.
12)     – закон обобщенного склеивания, т.е. в дизъюнкции конъюнкций «лишней» является конъюнкция, полученная в результате конъюнкции членов перед инверсной и неинверсной переменной в двух других конъюнкциях. То же можно сказать и о конъюнкции дизъюнкций, в которых имеются дизъюнкции с такими переменными.
Еще раз отметим двойственность законов алгебры логики: они дейст-вуют как относительно дизъюнкции, так и относительно конъюнкции.
Кроме перечисленных законов, которые можно доказать, например, построив соответствующие таблицы истинности (соответствия), большое значение имеют так называемые соотношения 0 и 1, полученные на осно-вании законов алгебры логики:
   
 
   
причем   два последних соотношения – это закон исключенного третьего и закон противоречия. Так, например:
10=1; 10=0;
01=1; 01=0.
Здесь мы стали применять простое равенство (=).
Рассмотренные законы применимы не только к отдельным перемен-ным, но и к группам переменных, объединенных операциями алгебры логики, т.е. х, например, может быть в свою очередь конъюнкцией   а  .
В алгебре переключательных функций установлен порядок выполне-ния действий. При отсутствии в выражении скобок первыми выполняются операции отрицания (инверсии), затем операции конъюнкции и последними – дизъюнкции.
При наличии в выражении скобок в первую очередь выполняются операции внутри скобок.