Тавтологией (╞ ) или общезначимой называется тождественно истинная формула, то есть такая формула, которая принимает значение И при любых значениях ее компонент.
Наряду с тавтологиями первостепенную роль в логике высказываний играют тождественно ложные формулы (противоречия или невыполнимые формулы), которые на всех наборах компонент принимают значение Л.
Существуют различные способы доказательства тавтологий:
Формула В логически следует из формулы А (пишут A => B), если В истинно на всех наборах переменных, для которых А истинно.
A => B тогда и только тогда, когда ╞ A → B.
Логическое следствие означает, что из истинности А следует истинность В, но если А ложно, то относительно В ничего утверждать нельзя.
Это определение можно обобщить на совокупность высказываний.
Формула В логически следует из множества формул Г: A1, A2, ..., Am, если из истинности всех Ai (i = 1, ..., m), следует истинность В.
Из определения конъюнкции можно заключить, что это сводится к соотношению:
A1 & A2 & ... & Am => B,
необходимым и достаточным условием которого является тавтология:
╞ A1 & A2 & ... & Am → B.
Установить, является ли формула логическим следствием, можно разными способами:
Задачи для самоcтоятельного решения