Конъюнктивная нормальная форма

Формула считается приведенной к конъюнктивной нормальной форме (КНФ), если она представлена в виде конъюнкции элементарных сумм.

Пример:

()(qr)(рr) (снимаем импликацию) (q)(r)r r (по законам де Моргана) ()()r

()()r (снимаем двойные отрицания) рqr ( по второму закону дистрибутивности для второй конъюнкции) (рqr)(рr) (по второму закону дистрибутивности для первых конъюнкций)

(рqr)(qr)(рr)(r)

– это КНФ ..

<== предыдущая лекция	\|	следующая лекция ==>
Дизъюнктивная нормальная форма формулы	\|	Методы доказательства тавтологии

Поделиться с друзьями:

Дата добавления: 2014-01-06; Просмотров: 421; Нарушение авторских прав?; Мы поможем в написании вашей работы!

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

studopedia.su - Студопедия (2013 - 2025) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление

Генерация страницы за: 0.008 сек.