Логические выражения
Логическое выражение может включать в себя логические переменные и константы, знаки логических операций, скобки, определяющие порядок выполнения логических операций.
Любое логическое высказывание можно записать в виде логического выражения (логической формулы). Например,
(x ⇒ y) ∧ z.
Простейшим вариантом логической формулы является одна логическая константа или одна логическая переменная.
Для формализации логических высказываний будем учитывать следующие положения:
Определение. Логической переменной называется переменная, значением которой может быть любое высказывание.
Логические переменные обозначаются латинскими буквами, которые могут снабжаться индексами, например: х, у, хk, yk, и т. п..
Существует две логические константы: 0 (ложь) и 1 (истина).
В логических выражениях операции имеют следующий приоритет:
- действия в скобках;
- инверсия;
- конъюнкция;
- дизъюнкция и строгая дизъюнкция;
- импликация;
- эквивалентность.
Построение таблицы истинности логического выражения
Для любого логического выражения можно построить таблицу истинности, в которой определяется его истинность или ложность при всех наборах исходных значений логических переменных.
Пример. Построить таблицу истинности для логического выражения: ¬ x ∧ ( y ⇒ z )
При построении таблиц истинности будем использовать следующий алгоритм:
- Определим количество строк в таблице истинности: = 2n (для нашего случая = 23),
где n - число логических переменных, входящих в логическое выражение. - Определим количество столбцов в таблице истинности: = n + p (для нашего случая 3 + 3),
где p - количество логических операций в логическом выражении. - Заполним все возможные наборы значений логических переменных
(будем рассматривать набор значений логических переменных как двоичное число и расположим такие двоичные числа в порядке возрастания). - Выполним логические операции в необходимой последовательности.
x | y | z | ¬ x | y ⇒ z | ¬ x ∧ ( y ⇒ z ) |
---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 1 | 0 |
Равносильные логические выражения.
Определение. Формулы А и В, зависящие от одного и того же набора переменных х1 х2, х3, …, хn, называют равносильными или эквивалентными, если на любом наборе значений переменных х1 х2, х3, …, хn они имеют одинаковые значения.
Для обозначения равносильности формул используется знак равенства, например А = В.
Любую формулу можно преобразовать к равносильной ей, в которой используются только базовые логические операции ∧, ∨ и ¬.
Представим через базовый набор эквивалентность:
x ⇔ y = ¬ x ∧ ¬ y ∨ x ∧ y
Докажем равносильность логических формул с помощью построения таблицы истинности.
x | y | x ⇔ y | ¬ x | ¬ y | ¬ x ∧ ¬ y | x ∧ y | ¬ x ∧ ¬ y ∨ x ∧ y |
---|---|---|---|---|---|---|---|
0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
Заметим, что результирующие столбцы в таблице истинности для левой и правой формулы совпали. Таким образом, формулы равносильные.