Примеры приведения формул к СДНФ и СКНФ

    Пример 1. Следующую формулу привести к СДНФ, предварительно приведя ее равносильными преобразованиями к ДНФ: $$A \equiv a ( bc \rightarrow ab) .$$
    Решение. \(A \equiv a ( bc \rightarrow ab) \equiv a ( \bar{b}\bar{c} \vee ab) \equiv a ( \bar{b} \vee \bar{c} \vee ab) \equiv\)
    \(\equiv a \bar{b} \vee a \bar{c} \vee ab \equiv ДНФ A\). $$A \equiv ДНФ A \equiv a\bar{b } ( c \vee \bar{c}) \vee a\bar{c} ( b \vee \bar{b}) \vee ab ( c \vee \bar{c})\equiv$$ $$\equiv a\bar{b} c \vee a \bar{b} \bar{c} \vee ab\bar{c} \vee a \bar{b} \bar{c} \vee abc \vee ab\bar{c} \equiv$$ $$\equiv a\bar{b} c \vee a \bar{b} \bar{c} \vee ab\bar{c} \vee \vee abc \equiv СДНФ A.$$
    Ответ. \(СДНФ A \equiv a\bar{b} c \vee a \bar{b} \bar{c} \vee ab\bar{c} \vee \vee abc .\)

    Пример 2. Для формулы из примера 1 найти СДНФ путем составления таблицы истинности.
    Решение. Составим таблицу истинности для формулы \(A \equiv a ( bc \rightarrow ab).\)

\(a\) \(b\)\(c\)
\(bc\)
\(ab\)
\(bc\rightarrow ab\)
\(A\)
1 11
1
1
1
1
1 10
0
1
1
1
1 01
0
0
1
1
1 00
0
0
1
1
0 11
1
0
0
0
0 10
0
0
1
0
0 01
0
0
1
0
0 00
0
0
1
0

    Ответ. Тогда \(СДНФ A \equiv abc \vee ab \bar{c} \vee a\bar{b}c \vee a\bar{b}\bar{c}.\)

    Пример 3. Для формулы из примера 1 найти СКНФ путем равносильных преобразований, предварительно приведя ее к КНФ.
    Решение. Из примера 1: \(A \equiv a\bar{b} \vee a \bar{c} \vee ab.\) Далее \(A \equiv a ( \bar{b} \vee \bar{c} \vee b) \equiv a \wedge 1\equiv a\equiv КНФ A.\) $$A \equiv КНФ A \equiv a \vee ( b \wedge \bar{b}) \equiv ( a \vee b) \wedge ( a \vee \bar{b}) \equiv$$ $$\equiv (( a \vee b) \vee c \wedge \bar{c}) \wedge (( a \vee \bar{b}) \vee c \wedge \bar{c}) \equiv$$ $$\equiv ( a \vee b \vee c) \wedge(a \vee b \vee \bar{c}) \wedge ( a \vee \bar{b} \vee c) \wedge ( a \vee \bar{b} \vee \bar{c}) \equiv СКНФ A.$$
    Ответ. \(СКНФ A \equiv ( a \vee b \vee c) \wedge(a \vee b \vee \bar{c}) \wedge ( a \vee \bar{b} \vee c) \wedge ( a \vee \bar{b} \vee \bar{c}).\)

    Пример 4. Для формулы из примера 1 найти СКНФ, записав предварительно СДНФ ее отрицания, а потом воспользовавшись формулой двойственности.
    Решение. СКНФ $$\bar{A} \equiv \overline{СДНФ \bar{A}} \equiv \overline{\bar{a}bc \vee \bar{a}b\bar{c} \vee \bar{a}\bar{b}c \vee \bar{a}\bar{b}\bar{c}} \equiv$$ $$\equiv ( a \vee \bar{b} \vee \bar{c} ) \wedge ( a \vee \bar{b} \vee c) \wedge ( a \vee b \vee \bar{c}) \wedge ( a \vee b \vee c) .$$
    Ответ. СКНФ \(A \equiv ( a \vee \bar{b} \vee \bar{c} ) \wedge ( a \vee \bar{b} \vee c) \wedge ( a \vee b \vee \bar{c}) \wedge ( a \vee b \vee c) .\)


2012-11-05 • Просмотров [ 13398 ]