Формулы алгебры высказываний

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

В качестве примеров высказываний приведем предложения " Владивосток — крупнейший город Приморья" и " Снег зеленый". Первое высказывание является истинным, а второе — ложным.

Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 1, если Р истинно, и 0, если Р ложно.

Если имеется несколько высказываний, то из них можно об­разовать различные новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные — сложными. Соответственно из логических переменных можно составлять различные конструкции, которые образуют формулы алгебры высказываний.

Итак, пусть {х_i│ i I} — некоторое множество логических переменных. Определим по индукции понятие формулы алгебры высказываний (АВ):

1) любая логическая переменная является формулой АВ
(называемой атомарной);

2) если φ и ψ — формулы АВ, то выражения φ, (φ ∧ ψ),
(φ ∨ ψ), (φ → ψ) являются формулами АВ;

3) никаких других формул АВ, кроме построенных по пп. 1 и 2, нет.

Если формула φ АВ построена из логических переменных, принадлежащих множеству {х₁, х₂, …, x_n}, то будем писать φ (x₁, …x_n).

Символы, ∧, ∨ →, использованные в определении, называются логическими операциями или связками и читаются соответственно: отрицание, конъюнкция, дизъюнкция и импликация.

Эти логические операции следующим образом интерпретируются в русском языке: φ — " не φ ", (φ ∧ ψ) — φ и ψ, (φ ψ) — φ или ψ, (φ → ψ) — если φ, то ψ;.

Вместо φ часто пишут , вместо (φ ∧ ψ) — (φ & ψ), (φ • ψ) или (φ ψ).

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

 

φ	φ

 

φ	ψ	(φ ∧ ψ)	(φ ∨ ψ)	(φ → ψ)

Пример 1. Построить таблицу истинности для формулы φ ((x→ y)∧ ((y→ z)→ x)).

Решение. Будем строить таблицу истинности последовательно в соответствии с шагами построения формулы φ:

 

x	y	z	(x→ y)	(y→ z)	((y→ z)→ x)	φ

 

Легко заметить, что таблица истинности для φ совпадает с таб­лицей истинности для x. В дальнейшем выяснится причина этого совпадения.

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

1. Внешние скобки не пишутся. Например, вместо высказывания ((x∨ y)→ z) пишется (x∨ y)→ z.

2. На множестве {, ∧, ∨, → } вводится транзитивное отношение " быть более сильным" следующим образом: наиболее сильная связка –, далее идут ∧ и ∨, самая слабая связка – →.

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

Пример 2. В формуле ((x∨ y)→ z)→ u)) все скобки можно опустить: х∨ y→ z→ u.