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

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

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

Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 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.

 

2.1.2. Логическое следствие в алгебре высказываний

 

Говорят, что формула ψ(х₁,...,х_п) АВ является логическим следствием формул φ₁(х₁,...,х_п),…,φ_m(х₁,...,х_п) АВ (обозначается ), если для любых из соотношений следует . Формулы называются гипотезами.

Пример 3. Доказать, что φ, φ→ψ, ψ→χ

Построим таблицы истинности для каждой формулы:

 

φ	ψ	χ	φ→ψ	ψ→χ

 

Из таблицы истинности видно, что когда все гипотезы принимают значение равное 1, формула χ тоже принимает значение 1, значит, χ является логическим следствием, что и требовалось доказать.

Формула φ(x₁,x₂,…,x_n) называется выполнимой (опровержимой), если существует такой набор значений переменных, на котором формула принимает значение 1 (соответственно 0) .

Пример 4. Формула х∧ у является одновременно выполнимой и опровержимой, поскольку 0∧0=0, а 1∧1=1.

Формула φ(x₁,…,x_n) называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) на всех наборах значений переменных.

Пример 5. Формула x∨¬x является тождественно истинной, а формула x∧¬x — тождественно ложной:

 

 

x	x∨¬x	x∧¬x

 

Множество формул φ₁,…,φ_n АВ называется противоречивым или несовместным, если формула φ₁∧…∧φ_n тождественно ложна.

Пример 6.Множество формулx∨y, ¬x, ¬y противоречиво.

Теорема 1.Пусть φ₁,..,φ_m,ψ – формулы АВ. Следующие условия эквивалентны:

1) ;

2)

3) {φ₁,..,φ_m,¬ψ} – противоречивое множество формул;

4) – тождественно истинная формула;

5) φ₁∧..∧φ_m∧¬ψ – тождественно ложная формула.