Нормальные формы
Основной из задач алгебры высказываний является проблема разрешения, т.е. является ли данная формула тавтологией или противоречием или выполнимой формулой. Эта проблема легко решается с помощью нормальных форм.
Элементарной конъюнкцией $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) удаляем элементарные дизъюнкции, в которых содержатся высказывания вместе с их отрицанием.
Для тождественно истинных формул СКНФ не существует.
Для любой формулы алгебры высказываний существует только одна СДНФ и только одна СКНФ, кроме противоречий и тавтологий, т.е. для противоречий будет существовать СКНФ, а для тавтологий – только СДНФ.
Далее:
Критерий полноты {формулировка}. Лемма о несамодвойственной функции
Вычисление двойного интеграла. Двукратный интеграл
Полином Жегалкина. Пример.
Несобственные интегралы от неограниченной функции
Криволинейный интеграл первого рода
Функции k-значной логики. Элементарные функции. Лемма об аналоге правила де Моргана
Механические приложения тройного интеграла
Вычисление площадей плоских областей
Выражение площади плоской области через криволинейный интеграл
Логические операции над высказываниями
Определение тройного интеграла. Теорема существования тройного интеграла
Свойства тройного интеграла
Инвариантное определение дивергенции
Поверхностный интеграл второго рода и его свойства
Несобственные интегралы по неограниченной области
Огравление $\Rightarrow $
Комментарии ()