Розглянемо ознаку рівносильності формул

Теорема 3.1. Дві формули F і Н алгебри висловлень рівносильні тоді й тільки тоді, коли формула є тавтологією, тобто ╞ .

Доведення даної теореми безпосередньо випливає із означення рівносильності формул та означення тавтології.

Зазначимо, що рівносильність формул не є формулою. Це відношення між формулами F і Н логіки висловлень.

Наслідок. Відношення рівносильності між формулами алгебри висловлень

а) рефлексивне: ;

б) симетричне: якщо , то ;

в) транзитивне: якщо і , то ,

тобто відношення рівносильності між формулами алгебри висловлень є відношенням еквівалентності.

Отже, відношення рівносильності розбиває множину всіх формул алгебри висловлень на класи еквівалентності, які попарно не перетинаються. Один клас, наприклад, утворюють усі тавтології, інший - усі тотожно хибні формули і т. д.

Приклади рівносильних формул. Наведені нижче рівносильності випливають із тавтологій, розглянутих у попередній лекції, на основі ознаки рівносильності.

Теорема 3.2. Мають місце наступні рівносильності:

а) ;

б) ;

в) ;

г) ;

д) ;

ж) ;

з) ;

і) ;

й) ;

к) ;

л) ;

м) ;

н) ;

о) ;

п) (1-й закон де Моргана);

р) (2-й закон де Моргана);

с) ;

т) ;

у) ;

ф) ;

х) ;

ц) ;

ч) ;

ш) ;

щ) .