Используя равносильности I, II, III групп можно часть формулы или формулу заменить равносильной ей формулой. такие преобразования формул называются равносильными.
Равносильные преобразования используются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.
Формула \(A\) считается проще равносильной ей формулы \(В\), если она содержит меньше букв, меньше логических операций. При этом обычно операции эквивалентности и импликации заменяются операциями дизъюнкции и конъюнкции, а отрицание относятся к элементарным высказываниям. Рассмотрим ряд примеров.
Пример 1. Доказать равносильность \(x \leftrightarrow y \equiv \bar{x} \wedge \bar{y} \vee x \wedge y\).
Решение. Используя равносильности I, II, III групп запишем цепочку равносильных формул:
$$x \leftrightarrow y \equiv ( x \rightarrow y) \wedge (y \rightarrow x) \equiv (\bar{x} \vee y) \wedge ( \bar{y} \vee x) \equiv$$
$$\equiv \bar{x} \wedge \bar{y} \vee \bar{x} \wedge x \vee y \wedge \bar{y} \vee y \wedge x \equiv$$
$$\equiv \bar{x} \wedge \bar{y} \vee 0 \vee 0 \vee y \wedge x \equiv \bar{x} \wedge \bar{y} \vee y \wedge x \equiv \bar{x} \wedge \bar{y} \vee x \wedge y.$$
Пример 2. Упростить формулу \(( \overline{( x \vee y ) }\rightarrow x \vee y) \wedge y\).
Решение. Запишем цепочку равносильных формул:
$$(\overline{\overline{( x \vee y )}} \vee x \vee y) \wedge y \equiv ( x \vee y \vee x \vee y) \wedge y \equiv ( x \vee y ) \wedge y \equiv y.$$
Пример 3. Доказать тождественную истинность формулы:
$$( x \rightarrow y) \rightarrow ((y \rightarrow z) \rightarrow ( x \vee y \rightarrow z)).$$
Решение. Запишем цепочку равносильных формул, используя равносильности:
$$( x \rightarrow y) \rightarrow ((y \rightarrow z) \rightarrow ( x \vee y \rightarrow z)) \equiv$$
$$\equiv \overline{( \bar{x} \vee y)} \vee (\overline{ \bar{y} \vee z } \vee \overline{ x \vee y} \vee z) \equiv \bar{\bar{x}} \wedge \bar{y} \vee \bar{\bar{y}} \wedge \bar{z} \vee \bar{x} \wedge \bar{y} \vee z \equiv$$
$$\equiv x \wedge \bar{y} \vee y \wedge \bar{z} \vee \bar{x} \wedge \bar{y} \vee z \equiv ( x \wedge \bar{y} \vee \bar{x} \wedge \bar{y} ) \vee ( y \wedge \bar{z} \vee z) \equiv$$
$$\equiv \bar{y} \wedge ( x \vee \bar{x} ) \vee ( y \vee z) \wedge ( \bar{z} \vee z ) \equiv \bar{y} \wedge 1 \vee ( y \vee z) \wedge 1 \equiv$$
$$\equiv \bar{y} \vee y \vee z \equiv ( \bar{y} \vee y ) \vee z \equiv 1 \vee z\equiv 1.$$
