9. Удаление и восстановление скобок в ПФ

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

При удалении скобок придерживаются следующих правил:

1.У формул опускается внешняя пара скобок, то есть ((AVB)&(ךC)) превращается в

(AVB)&(ךC)

2.Если формула содержит вхождение только одной бинарной связки (→,V,&,≡), то для каждого вхождения этой связки опускаются внешние скобки у той из двух формул, соединяемых этим вхождением, которая стоит слева. Например, формула (((A

→ B) → C) → D) может быть записана в виде A → B → C → D.

3. Связки считают упорядоченными следующим образом: ≡,ѐ→,V,&,ך и опускают все те пары скобок, без которых невозможно восстановление формулы на основе следующего правила. Каждое вхождение знака ך относится к наименьшей подформуле, следующей за ним; после расстановки всех скобок, относящихся ко всем вхождениям знака ך , каждое вхождение знака & связывает наименьшие формулы, окружающие это вхождение; затем, каждое вхождение знака V связывает наименьшие формулы, окружающие это вхождение; и, подобным образом для → и ≡. При применении этого правила к одной и той же связке мы продвигаемся слева направо.

Рассмотрим примеры.

В формуле A V ךB → C ≡ A скобки восстанавливаются в следующей последовательности:

1.A V (ךB) → C → A

2.(A V (ךB)) → C → A

3.((A V (ךB)) →C) → A

4.(((A V (ךB)) → C) → A)

Для формулы D →C →A&D&B V ךD → B последовательность восстановления скобок будет следующая:

1.D → C →A&D&B V(ךD) →B

2.D →C → (A&D)&B V(ךD) → B

3.D → C → ((A&D)&B)V(ךD) → B

4.D →C → (((A&D)&B)V(ךD)) → B

5.D →C → ((((A&D)&B)V(ךD)) → B)

6.(D → C) → ((((A&D)&B)V(ךD)) → B)

7.((D → C) → ((((A&D)&B)V(ךD)) → B))

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

Равносильности формул логики высказываний часто называют законами логики. Знание законов логики позволяет проверять правильность рассуждений и доказательств.

Закон тождества. Он сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. (A = A)

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. (A&(ךA)) = ‖Это яблоко спелое‖ и ‖Это яблоко не спелое‖.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. ‖Сегодня я получу 5 либо не получу‖. Истинно либо суждение, либо его отрицание. (AV(ךA)) =

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. ‖Неверно, что 2x2 не равно 4‖ . (ך(ךA)) = A

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых ‖сомножителей‖ равносильна одному из них. (A&A) = A, (AVA) = A

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.

o Коммутативность: (A&B) = (B&A), (AVB) = (B VA)

o Ассоциативность: (A&B)&C = A&(B&C) (AVB)VC = AV(B VC)

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

o A&(B VC) = (A&B)V(A&C); o AV(B&C) = (AVB)&(AVC)

Законы де Моргана: (ך(A&B)) = ((ךA)V(ךB)) - отрицание логического произведения эквивалентно логической сумме отрицаний множителей; (ך(AVB)) = ((ךA)&(ךB)) - отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

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

oA&(A V B) = A;

oAV(A&B) = A

Законы склеивания

o(AVB)&((ךA)VB) = B;

o (A&B)V((ךA)&B) = B