Совершенные нормальные формы. Формулы х и будем называть литералами, т.е

Формулы х и будем называть литералами, т.е. литерал – это или х, или.

Если в ДНФ каждое элементарное произведение содержит все элементарные высказывания, но только в виде единственного литерала, то ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).

Например:

=pqrr является ДНФ, но не является СДНФ, т.к. во второе элементарное произведение не входит ни р, ни.

Формула = pqr r – СДНФ.

Формула = pqr rq – не СДНФ, т.к. во втором элементарном произведении содержится два литерала.

Теорема.Любая формула, отличная от 0, представима в виде СДНФ.

Доказательство:

Пусть Ф – формула, содержащая n литералов. Пусть ДНФ содержит элементарное произведение без литерала . =, - литералы. Введем дизъюнкцию , которая равна 1. Получим =() = (по первому закону дистрибутивности) = .

Теперь элементарные произведения содержат все литералы. Поступая аналогично с другими элементарными произведениями, и, заменяя р нулем, получим СДНФ.

Что и требовалось доказать.

Пример 2.

Пусть = pqr q – ДНФ.

Приведем к СДНФ.

Добавим 1 в виде дизъюнкции r .

Получим = pqrq (r )pqrqrq ─ СДНФ.

Если каждая элементарная сумма КНФ формулы содержит все литералы по одному разу, то такая форма называется совершенной конъюнктивной нормальной формой (СКНФ).

Дата добавления: 2014-01-06