Равносильные логические выражения

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

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

1)	¬0=1 ¬1=0 X&1=X X&0=0 Xv0=X Xv1=1	Правила выполнения операций над константами (свойства операций отрицания, конъюнкции и дизъюнкции)
2)	¬(¬A)=A	Закон двойного отрицания Двойное отрицание исключает отрицание.
3)	X&Y=Y&X XvY=YvX	Законы коммутативности (переместительный закон) Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания. В обычной алгебре: а+b=b+а,  а*b = b*а.
4)	X&Y&Z=(X&Y)&Z=X&(Y&Z) XvYvZ =(XvY)vZ =Xv(YvZ)	Законы ассоциативности (сочетательный закон) Переменные  можно группировать в любом порядке, как для операции конъюнкции, так и для операции дизъюнкции. При одинаковых знаках скобки можно ставить произвольно или вообще опускать. В обычной алгебре:   (а+b)+с=а+(b+с)=а+b+с,  (а*b)*с =а*(b*с)=а*b*с.
5)	Xv(Y&Z)=(XvY)&(XvZ) X&(YvZ)=(X&Y)v(X&Z)	Распределительные (дистрибутивный) законы В  алгебре логики допускается вынесение общего высказывания за скобки. В обычной алгебре справедлив распределительный закон только для сложения: (а+b)*с=а*с+b*с.
6)	¬(XvY)=¬X&¬Y ¬(X&Y)=¬Xv¬Y   (X=>Y)=¬XvY ¬(X=>Y)=X&¬Y	Законы общей инверсии (законы де Моргана) Описывает  эффект отрицания переменных, связанных операциями И и ИЛИ. Используя формулы де Моргана, можно всякую сложную формулу записать так, чтобы знак отрицания распространялся только на простые высказывания, входящие в эту формулу.
7)	X&X=X  YvY=Y	Законы идемпотентности Закон означает отсутствие показателей степени.
8)	X&¬X=0	Закон противоречия Невозможно, чтобы противоречащие высказывания были одновременно истинными.
9)	Xv¬X=1	Закон исключения третьего Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.
10)	Xv(X&Y)=X  X&(XvY)=X  Xv(¬X&Y)=XvY  ¬X&(XvY)=¬X&Y	Законы поглощения
11)	(X&Y)v(X&¬Y)=X  (XvY)&(Xv¬Y)=X	Законы исключения (склеивания)
12)	(X<=>Y)=(Y<=>X)	Закон контрапозиции (правило перевертывания)

    

     Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений X и Y, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.

    Поскольку переменные в алгебре логики принимают только два значения, такая процедура оказывается вполне допустимой.

   Таким образом, используя основные свойства операций алгебры логики, можно одну формулу заменить другой, ей равносильной.

    Повторение - мать учения       

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

Импликацию можно выразить через дизъюнкцию и отрицание:

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

 

Докажите самостоятельно справедливость этих утверждений(с помощью построения таблиц истинности).