Доказательство.

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

Достаточность: Пусть формула в условии теоремы есть тавтология, тогда для любого набора значений пропозиционных переменных, например, , ,..., её значение будет «истина», т.е. эквивалентность есть истинное высказывание. Следовательно, высказывания и либо оба истинны, либо оба ложны. Таким образом, для любых значений пропозиционных переменных формулы и принимают одинаковые истинностные значения, поэтому они равносильны. Теорема доказана.