Эквивалентность высказываний. Основные теоремы об эквивалентности

Введем новое отношение между формулами. Для его определения удобно интерпретировать формулы как истинностные функции; заметим, что формулу, простыми компонентами которой являются можно рассматривать как функцию с расширенным составом переменных: .

входит в качестве простого компонента по меньшей мере в одну из формул А и В.

Теорема 1. является тавтологией тогда и только тогда, когда A eq B.

Следствие: Пусть есть формула, в которой выделено некоторое вхождение формулы А, и пусть есть результат замены этого вхождения формулы А формулой В. Тогда, если является тавтологией, то и является тавтологией ; если и являются тавтологиями, то и является тавтологией.

Теорема 2. Если А и являются тавтологиями, то и B является тавтологией.