Элементы логики
Таблицы, в которых представлена зависимость значений формул от пропозицийних переменных, называются таблицами истинности.
Рассмотрим согласования, которые позволяют сокращать запись формул. Пропозицийни связки упорядочиваются за "силой притяжения к формулам" подобно знакам арифметических операций. Все понимают, что выражение 1+23 помечает сумму 1 и 23, а не произведение 1+2 и 3, то есть знак умножения "притягивается" сильнее знака добавления. Связка считается сильнейшей, то есть AB является сокращением от (A)B, а не от (AB). Дальше за спадением "силы притяжения" двухместные связки идут в таком порядке: &, , , . Следовательно, формулу ABC можно рассматривать, как сокращенная запись формулы A(BC)а формулу ABCA - как A(B(CA)).
Все двухместные связки имеют свойство левостороннего связывания. Это значит, что если справа и влево от подформулы записаны без скобок знаки двухместных связок, "сила притяжения" которых одинакова, то первой к подформуле применяется левая из них. Например, ABC является сокращенной записью формулы (AB)C.
Определение. Две формулы называются эквивалентными, или равносильными, если принимают одинаковые значения при всех возможных значениях пропозицийних переменных. Ривносильнисть формул обозначается знаком и в логике называется законом.
Например, нетрудно убедиться, что при произвольных формулах A, B, C следующие ривносильности являются законами (справа указаны названия некоторых из них) :
(1)AB BA, AB BA - законы коммутативности
(2)A(BC) (AB)C, A(BC) (AB)C - законы ассоциативности
(3)A(BC) (AB)(AC)A(BC) (AB)(AC) - законы дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции
(4)AA A, AA A - законы идемпотентности
(5)A(AB) A, A(AB) A
(6)(AB) AB, (AB) AB - законы Где Моргана
(7)A A - закон двойного отрицания
(8)A0 0, A1 A, A0 A, A1 1 - законы поглощения
(9)AA 1 - закон исключенного третьего
(10)AA 0 - закон противоречия
(11)AB BA - закон контрапозиций
Полезно также помнить еще два закона:
(12) AB AB
(13) AB (AB)(BA).
На законах основываются так называемые равносильные превращения формул, когда формула или ее подформула замещается на равносильную ей. В результате получается формула, равносильная начальной. Такие превращения бывают нужные для упрощения формул. Например, формула A(AB) имеет равносильные формулы A(AB)A(AB)61658;B, AB, что получаются последовательным применением законов (12) (7) (2) (4).
Вернуться назад