Введем новое отношение между формулами. Для его определения удобно интерпретировать формулы как истинностные функции; заметим, что формулу, простыми компонентами которой являются можно рассматривать как функцию с расширенным составом переменных:
. Условимся теперь называть формулу А эквивалентной (равносильной) формуле В (A eq B), если они равны как истинностные функции для перечня переменных
, где каждое
входит в качестве простого компонента по меньшей мере в одну из формул А и В.
Теорема 1. является тавтологией тогда и только тогда, когда A eq B.
Следствие: Пусть есть формула, в которой выделено некоторое вхождение формулы А, и пусть
есть результат замены этого вхождения формулы А формулой В. Тогда, если
является тавтологией, то и
является тавтологией ; если
и
являются тавтологиями, то и
является тавтологией.
Теорема 2. Если А и являются тавтологиями, то и B является тавтологией.