Привести к нормальной форме высказывание
Обновлено: 22.12.2024
Основной из задач алгебры высказываний является проблема разрешения, т.е. является ли данная формула тавтологией или противоречием или выполнимой формулой. Эта проблема легко решается с помощью нормальных форм.
Элементарной конъюнкцией $n$ высказываний называется конъюнкция высказываний или их отрицаний.
Элементарной дизъюнкцией $n$ высказываний называется дизъюнкция высказываний или их отрицаний.
Чтобы элементарная дизъюнкция была тождественно истинной, необходимо и достаточно, чтобы в ней содержалось два высказывания, из которых одно является отрицанием другого.
Чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы в ней присутствовала пара высказываний, из которых одно является отрицанием другого
Дизъюнктивная нормальная форма
Формула равносильная данной и представляющая собой дизъюнкцию элементарных конъюнкций называется дизъюнктивной нормальной формой данной формулы. < ДНФ >.
Конъюнктивная нормальная форма
Формула равносильная данной и представляющая собой конъюнкцию элементарных дизъюнкций называется конъюнктивной нормальной формой данной формулы. < КНФ >.
Обобщим существование ДНФ или КНФ для каждой формулы:
Все логические операции можно заменить тремя: конъюнкцией, дизъюнкцией и отрицанием.
Знак отрицания с помощью законов де Моргана можно отнести к пропозициональным переменным.
С помощью дистрибутивных законов формула преобразовывается в конъюнкцию элементарных дизъюнкций или дизъюнкцию элементарных конъюнкций.
Для каждой формулы может быть составлено несколько ДНФ и КНФ. Но все ДНФ < или КНФ >данной формулы равносильны между собой.
Совершенная дизъюнктивная нормальная форма
Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:
а > в ней нет одинаковых дизъюнктивных элементов;
б > ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;
в > ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;
г > в каждой элементарной конъюнкции содержится либо $X_i$, либо $\overline < X >_i$, где $i = 1, n$.
Условие а > – г > являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:
1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $B\wedge (X_i\vee \overline < X >_i) \equiv (B\wedge X_i)\vee (B\wedge \overline < X >_i)$;
2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;
3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;
4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.
Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.
Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма – это ее КНФ обладающая свойствами:
а > в ней нет двух одинаковых конъюнктивных элементов;
б > ни одна элементарная дизъюнкция не содержит двух одинаковых высказываний;
в > ни одна элементарная дизъюнкция не содержит какой-нибудь переменной с ее отрицанием;
г > каждая элементарная дизъюнкция содержит либо $X_i$, либо $\overline < X >_i$, где $i = 1, n$.
В свою очередь эти условия дают возможность составить алгоритм получения СКНФ из КНФ:
1) если какая-нибудь элементарная дизъюнкция не содержит высказывание $X_i$, то заменим выражением $B\vee (X_i\wedge \overline < X >_i)\equiv (B\vee X_i)\wedge (B\vee \overline < X >_i)$;
2) если в полученном выражении окажутся одинаковые элементарные дизъюнкции, то лишние опускаются;
3) если в некоторых элементарных дизъюнкциях окажутся одинаковые высказывания, то лишние опускаются;
4) удаляем элементарные дизъюнкции, в которых содержатся высказывания вместе с их отрицанием.
Для тождественно истинных формул СКНФ не существует.
Для любой формулы алгебры высказываний существует только одна СДНФ и только одна СКНФ, кроме противоречий и тавтологий, т.е. для противоречий будет существовать СКНФ, а для тавтологий – только СДНФ.
Далее:
Вычисление площадей плоских областей
Полином Жегалкина. Пример.
Вычисление двойного интеграла. Двукратный интеграл
Свойства потока векторного поля
Замена переменных в тройном интеграле
Вычисление площади поверхности
Соленоидальное векторное поле
Теорема Остроградского
Векторное поле
Формула Грина
Класс $L$. Теорема о замкнyтости класса $L$
Механические приложения криволинейного интеграла 1-го рода
Критерий полноты
Решение задач с помощью алгебры высказываний
Односторонние и двусторонние поверхности. Ориентация поверхности
Читайте также: