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

 

Говорят, что формула ψ (х₁,..., х_п) АВ является логическим следствием формул φ ₁(х₁,..., х_п), …, φ _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∧ ψ – тождественно ложная формула.