Законы логики

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

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

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

a + b = b + a, a∙b = b ∙a. (4)

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

(a + b) + c = a + (b + c), (5)

(a∙ b)∙ c = a∙ (b∙ c). (6)

Закон исключения констант (нуля и единицы):

a +0 = a, A∙1=A. (7)

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

(a + b)∙ c = a∙ c + b∙c, (8)

(a + c)∙ (b + c) = a∙b + c, (9)

(a b)∙ c = a∙ c b∙c. (10)

Закон противоречия:

(11)

Закон равносильности (идемпотентности):

. (12)

Закон двойного отрицания: (13)

Закон инверсии (формулы де Моргана):

(14)

(15)

Закон поглощения:

(16)

(17)

Закон склеивания (закон исключения):

(18)

(19)

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

Докажем первый закон де Моргана (14) с использова­нием таблиц истинности. Построим таблицы истинности для левой и правой частей закона.

a	b	a+b

Так как результирующие столбцы ( и ) совпали, то формулы, стоящие в левой и правой частях закона, равносильны.

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

Докажем ещё один закон поглощения путем логических рассуждений. Для этого достаточно показать, что если правая часть истинна, то и левая часть истинна, и что если левая часть истинна, то и пра­вая часть истинна.

Пусть истинна правая часть, т. е. A = 1, тогда в левой части дизъюнкция истинна по определению дизъюнкции. Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула A, или формула , или обе эти формулы одновременно. Если A ложна, тогда ложна. Следовательно, A может быть только истинной.

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

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