Равносильные преобразования формул

    Используя равносильности 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.$$


2012-11-03 • Просмотров [ 5123 ]