Логика

Электронное учебное пособие

 

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

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

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

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, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.

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

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

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

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

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

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

 

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

Сайт создан по технологии «Конструктор сайтов e-Publish»