Логические выражения

Логическое выражение может включать в себя логические переменные и константы, знаки логических операций, скобки, определяющие порядок выполнения логических операций.

Любое логическое высказывание можно записать в виде логического выражения (логической формулы). Например,
(x ⇒ y) ∧ z.
Простейшим вариантом логической формулы является одна логическая константа или одна логическая переменная.

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

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

Логические переменные обозначаются латинскими буквами, которые могут снабжаться индексами, например: х, у, х_k, y_k, и т. п..

Существует две логические константы: 0 (ложь) и 1 (истина).

В логических выражениях операции имеют следующий приоритет:

1. действия в скобках;
2. инверсия;
3. конъюнкция;
4. дизъюнкция и строгая дизъюнкция;
5. импликация;
6. эквивалентность.

Построение таблицы истинности логического выражения

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

Пример. Построить таблицу истинности для логического выражения: ¬ x ∧ ( y ⇒ z )

При построении таблиц истинности будем использовать следующий алгоритм:

1. Определим количество строк в таблице истинности: = 2ⁿ (для нашего случая = 2³),
   где n - число логических переменных, входящих в логическое выражение.
2. Определим количество столбцов в таблице истинности: = n + p (для нашего случая 3 + 3),
   где p - количество логических операций в логическом выражении.
3. Заполним все возможные наборы значений логических переменных
   (будем рассматривать набор значений логических переменных как двоичное число и расположим такие двоичные числа в порядке возрастания).
4. Выполним логические операции в необходимой последовательности.

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

Равносильные логические выражения.

Определение. Формулы А и В, зависящие от одного и того же набора переменных х₁ х₂, х₃, …, х_n, называют равносильными или эквивалентными, если на любом наборе значений переменных х₁ х₂, х₃, …, х_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

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