Элементы логики


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

Рассмотрим согласования, которые позволяют сокращать запись формул. Пропозицийни связки упорядочиваются за "силой притяжения к формулам" подобно знакам арифметических операций. Все понимают, что выражение 1+23 помечает сумму 1 и 23, а не произведение 1+2 и 3, то есть знак умножения "притягивается" сильнее знака добавления. Связка  считается сильнейшей, то есть AB является сокращением от (A)B, а не от (AB). Дальше за спадением "силы притяжения" двухместные связки идут в таком порядке: &, , , . Следовательно, формулу ABC можно рассматривать, как сокращенная запись формулы A(BC)а формулу ABCA - как A(B(CA)).

Все двухместные связки имеют свойство левостороннего связывания. Это значит, что если справа и влево от подформулы записаны без скобок знаки двухместных связок, "сила притяжения" которых одинакова, то первой к подформуле применяется левая из них. Например, ABC является сокращенной записью формулы (AB)C.

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

Например, нетрудно убедиться, что при произвольных формулах A, B, C следующие ривносильности являются законами (справа указаны названия некоторых из них) :

(1)AB  BA, AB  BA - законы коммутативности

(2)A(BC)  (AB)C, A(BC)  (AB)C - законы ассоциативности

(3)A(BC)  (AB)(AC)A(BC)  (AB)(AC) - законы дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции

(4)AA  A, AA  A - законы идемпотентности

(5)A(AB)  A, A(AB)  A

(6)(AB)  AB, (AB)  AB - законы Где Моргана

(7)A  A - закон двойного отрицания

(8)A0  0, A1  A, A0  A, A1  1 - законы поглощения

(9)AA  1 - закон исключенного третьего

(10)AA  0 - закон противоречия

(11)AB  BA - закон контрапозиций

Полезно также помнить еще два закона:

(12) AB  AB

(13) AB  (AB)(BA).

На законах основываются так называемые равносильные превращения формул, когда формула или ее подформула замещается на равносильную ей. В результате получается формула, равносильная начальной. Такие превращения бывают нужные для упрощения формул. Например, формула A(AB) имеет равносильные формулы A(AB)A(AB)61658;B, AB, что получаются последовательным применением законов (12) (7) (2) (4).





Вернуться назад