Равносильные формулы алгебра логики

Определение. Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.

Равносильность формул будем обозначать знаком =, а запись А = В означает, что формулы А и В равносильны.

Например, равносильны формулы:

Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы

Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных.

Например, тожественно ложна формула

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула тавтология, и обратно, если формула тавтология, то формулы А и В равносильны.