Отношения логической эквивалентности и логического следствия

Определение. Формулы и называются логически эквивалентными тогда и только тогда, когда формула – тавтология.

Замечание. Формула – тавтология, если таблицы истинности формул и совпадают.

Пример. По законам де Моргана, логически эквивалентны формулы и , а также формулы и .

Теорема. Отношение логической эквивалентности является отношением эквивалентности.

Рефлексивность, симметричность и транзитивность данного отношения следуют из замечания.

Справедливы правило подстановки и правило замены.

Пусть и – формулы, содержащие букву , и – формулы, полученные из формул и соответственно подстановкой вместо буквы формулы .

Правило подстановки. Если формула логически эквивалентна формуле , то формула логически эквивалентна формуле .

Пусть – формула, в которой выделена некоторая подформула , – формула, полученная из формулы заменой на некоторую формулу .

Правило замены. Если формулы и логически эквивалентны, то логически эквивалентны и формулы и .

Доказательства правил подстановки и замены основано на сравнении таблиц истинности соответствующих формул.

Пример. Известна тавтология (проверьте самостоятельно). По правилу подстановки, формула логически эквивалентна формуле . По правилу замены, примененному к закону двойного отрицания, получаем, что формула логически эквивалентна формуле . Следовательно, по свойству транзитивности, формулы и логически эквивалентны.

Определение. Говорят, что формула логически влечет формулу (из формулы логически следует формула ), если формула является тавтологией.

Теорема. Отношение логического следствия является отношением предпорядка, то есть рефлексивным и транзитивным отношением.

Пример. Формула логически влечет формулу . В самом деле, в примере 1 предыдущего пункта было доказано, что формула является тавтологией.

В Содержание.