Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Нормальные формы
Основной из задач алгебры высказываний является проблема разрешения, т.е. является ли данная формула тавтологией или противоречием или выполнимой формулой. Эта проблема легко решается с помощью нормальных форм. Определение 1. Элементарной конъюнкцией п высказываний называется конъюнкция высказываний или их отрицаний. Определение 2. Элементарной дизъюнкцией п высказываний называется дизъюнкция высказываний илиих отрицаний. Теорема 1. Чтобы элементарная дизъюнкция была тождественно истинной, необходимо и достаточно, чтобы в ней содержалось два высказывания, из которых одно является отрицанием другого. Теорема 2. Чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы в ней присутствовала пара высказываний, из которых одно является отрицанием другого. Определение 3. Формула равносильная данной и представляющая собой дизъюнкцию элементарных конъюнкций называется дизъюнктивной нормальной формой данной формулы.(ДНФ). Определение 4. Формула равносильная данной и представляющая собой конъюнкцию элементарных дизъюнкций называется конъюнктивной нормальной формой данной формулы.(КНФ). Обобщим существование ДНФ или КНФ для каждой формулы: 1. Все логические операции можно заменить тремя: конъюнкцией, дизъюнкцией и отрицанием. 2. Знак отрицания с помощью законов де Моргана можно отнести к пропозициональным переменным. 3. С помощью дистрибутивных законов формула преобразовывается в конъюнкцию элементарных дизъюнкций или дизъюнкцию элементарных конъюнкций. Для каждой формулы может быть составлено несколько ДНФ и КНФ. Но все ДНФ (или КНФ) данной формулы равносильны между собой. Определение 5. Совершенной дизъюнктивной нормальной формой формулы А(x1,x2,…,xn) называется ДНФ, обладающая следующими свойствами: а) в ней нет одинаковых дизъюнктивных элементов; б) ни одна элементарная конъюнкция не содержит двух одинаковых высказываний; в) ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием; г) в каждой элементарной конъюнкции содержится либо Xi, либо , где i= . Условие а) – г) являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ: 1) если какая-нибудь элементарная конъюнкция не содержит высказывание Xi, то заменим выражением ; 2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются; 3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются; 4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием. Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ. Определение 6. Совершенная конъюнктивная нормальная форма – это ее КНФ обладающая свойствами: а) в ней нет двух одинаковых конъюнктивных элементов; б) ни одна элементарная дизъюнкция не содержит двух одинаковых высказываний; в) ни одна элементарная дизъюнкция не содержит какой-нибудь переменной с ее отрицанием; г) каждая элементарная дизъюнкция содержит либо Xi, либо , где i= . В свою очередь эти условия дают возможность составить алгоритм получения СКНФ из КНФ: 1) если какая-нибудь элементарная дизъюнкция не содержит высказывание Xi, то заменим выражением ; 2) если в полученном выражении окажутся одинаковые элементарные дизъюнкции, то лишние опускаются; 3) если в некоторых элементарных дизъюнкциях окажутся одинаковые высказывания, то лишние опускаются; 4) удаляем элементарные дизъюнкции, в которых содержатся высказывания вместе с их отрицанием. Для тождественно истинных формул СКНФ не существует. Для любой формулы алгебры высказываний существует только одна СДНФ и только одна СКНФ, кроме противоречий и тавтологий, т.е. для противоречий будет существовать СКНФ, а для тавтологий – только СДНФ.
|