Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в формулу.
Обозначение: А=В, читается А равносильно В. Примеры: x=xÙx, xÙ0=0, xÚØx=1.
Легко видеть, что если А=В, то ØА=ØВ.
Отношение равносильности обладает следующими свойствами:
1) А=А (рефлексивно)
2) Если А=В, то В=А (симметрично)
3) Если А=В и В=С, то А=С (транзитивно)
Теорема об эквивалентной замене: Если формула A содержит подформулу B, и B = C, то А’=A , где А’ образованна из A заменой B на С.