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

Мы уже достаточно много говорили и приводили примеры эквивалентности формул логики высказываний. Наиболее важные эквивалентности называются законами логики. Законы выражают сущность корректных рассуждений.

Приведу основные законы логики высказываний.

1. Коммутативность дизъюнкции и конъюнкции:

$$X | Y \equiv Y | X$$

$$X Y \equiv Y X$$

2. Дистрибутивный закон относительно дизъюнкции и конъюнкции:

$$X | (Y Z) \equiv (X | Y) (X | Z)$$

$$X (Y | Z) \equiv (X Y) | (X Z)$$

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

$$x + y = y + x$$

$$x * y = y * x$$

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

$$x * (y + z) = (x * y) + (x * z)$$

Однако для арифметики неверно, что:

$$x + (y * z) = (x + y) * (x + z)$$

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

3. Поглощение:

$$X (X | Y) \equiv X$$

$$X | (X Y) \equiv X$$

Законы Отрицание отрицания, Непротиворечивости и Исключающего третьего – это законы, исследуемые еще Аристотелем, являющиеся частью Аристотелевой логики.

4. Отрицание отрицания:

$$\neg (\neg X) \equiv X$$

5. Непротиворечивость:

$$X \neg X \equiv false$$

6. Исключающее третье:

$$X | \neg X \equiv true$$

7. Законы де-Моргана:

$$\neg (X | Y) \equiv \neg X \neg Y$$

$$\neg (X Y) \equiv \negX | \neg Y$$

8. Упрощение:

$$X X \equiv X$$

$$X | X \equiv X$$

$$X true \equiv X$$

$$X false \equiv false$$

$$X | true \equiv true $$

$$X | false \equiv X$$

9. Замена импликации

$$X \to Y \equiv \neg X | Y$$

10. Замена тождества

$$(X \equiv Y) \equiv (X Y) | (\neg X \neg Y)$$

Проверить истинность всех законов можно стандартным способом, построив таблицы истинности.

Вычисление формул

Логические формулы, называемые также логическими выражениями, строятся как уже говорилось, из констант и логических переменных, соединяемыми знаками логических операций и скобками. В качестве логических операций используются базисные операции – отрицание, конъюнкция, дизъюнкция, Исключающее Или, импликация и эквивалентность. Из определения этих операций ясно, каков будет результат операции над двумя операндами. Чтобы корректно вычислить значение всей формулы, нужно понимать, каков порядок выполнения операций, поскольку они имеют разный приоритет. Как всегда управлять порядком можно, используя расстановку скобок, поскольку выражение в скобках имеет наивысший приоритет. Приоритеты логических операций напоминают приоритет арифметических операций, где унарные знаки + и – имеют наиболее высокий приоритет, следующим приоритетом обладают операции умножения и деления, затем сложения и вычитания.

Для логических операций приоритеты следующие:

Пример: Вычислить значение формулы $$F$$ на кортеже $$<А =1, B =1, C = 1, D = 0>$$:

$$F: A \to B C \to D$$

В соответствии с приоритетами первой необходимо выполнить конъюнкцию $$B$$ и $$С$$, что дает 1, затем слева направо выполнить две операции следования. Результатом первой импликации будет 1 (истина), второй – ложь. Окончательный результат: $$F = 0$$.

Расстановка скобок может изменить порядок выполнения операций. Вычислим выражение:

$$(A \to B) (C \to D)$$

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