Логическое следствие в алгебре высказываний
Говорят, что формула ψ (х1,..., хп) АВ является логическим следствием формул φ 1(х1,..., хп), …, φ m(х1,..., хп) АВ (обозначается Пример 3. Доказать, что φ, φ → ψ, ψ → χ
Из таблицы истинности видно, что когда все гипотезы принимают значение равное 1, формула χ тоже принимает значение 1, значит, χ является логическим следствием, что и требовалось доказать. Формула φ (x1, x2, …, xn) называется выполнимой (опровержимой), если существует такой набор значений переменных, на котором формула принимает значение 1 (соответственно 0). Пример 4. Формула х∧ у является одновременно выполнимой и опровержимой, поскольку 0∧ 0=0, а 1∧ 1=1. Формула φ (x1, …, xn) называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) на всех наборах значений переменных. Пример 5. Формула x∨ x является тождественно истинной, а формула x∧ x — тождественно ложной:
Множество формул φ 1, …, φ n АВ называется противоречивым или несовместным, если формула φ 1∧ …∧ φ n тождественно ложна. Пример 6. Множество формул x∨ y, x, y противоречиво. Теорема 1. Пусть – φ 1,.., φ m, ψ – формулы АВ. Следующие условия эквивалентны: 1) 2) 3) { φ 1,.., φ m, ψ } – противоречивое множество формул; 4) 5) φ 1∧..∧ φ m∧ ψ – тождественно ложная формула.
|
), если для любых 
из соотношений 
следует 
. Формулы 
называются гипотезами.
Построим таблицы истинности для каждой формулы:
;
– тождественно истинная формула;
