Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 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) удаляем элементарные дизъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Для тождественно истинных формул СКНФ не существует.

Для любой формулы алгебры высказываний существует только одна СДНФ и только одна СКНФ, кроме противоречий и тавтологий, т.е. для противоречий будет существовать СКНФ, а для тавтологий – только СДНФ.

 






Date: 2015-07-25; view: 330; Нарушение авторских прав

mydocx.ru - 2015-2019 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию