Восстановление формул

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

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

Если элементарная сумма не содержит литерал , то можно в нее ввести конъюнкцию и воспользоваться вторым законом дистрибутивности.

Пример 3. Пусть = (pqr) (q) – КНФ.

Приведем к СКНФ. Добавим 0 в виде r . Получим

= (pqr) (qr) (pqr) (qr) (q)

– это СКНФ.

Каждой формуле соответствует таблица истинности, следовательно, каждой таблице истинности соответствует некоторая формула. Возникает задача ─ для заданной таблицы истинности восстановить формулу, которой она соответствует. Этого можно достичь двумя способами:

С помощью СКНФ или с помощью СДНФ.

1. СКНФ.

В таблице истинности выделяются строки, в которых формула ложна. Каждой такой строке будет соответствовать единственная элементарная сумма СКНФ. В эту сумму высказывание истинное будет входить с отрицанием, а высказывание, которое ложно - без отрицания. Это объясняется тем, что элементарная сумма должна быть ложной, а если в нее будут входить истинное высказывание, то она ложной не будет. Составляя СКНФ из этих строк, мы получим исходную формулу.

Пример:

Дана таблица

	р	q	r	Ф

Так как во 2-ой строке функция ложна, то должна быть ложна элементарная сумма. А элементарная сумма ложна тогда, когда каждый ее член равен 0.

Т. к. р =1, то =0; и в дизъюнкцию должно входить .

Т. к. q =1, то =0; и в дизъюнкцию должно входить.

r = 0- без отрицания.

Получим: r.

Аналогично

Для 4-ой строки: р

Для 7-ой строки: pq. Тогда

Ф= (r)(p)(pq.).

2. СДНФ.

В таблице истинности выделяются строки, в которых формула истинна. Каждой такой строке поставим в соответствие элементарное произведение, которое должно быть истинно. В это произведение истинные высказывания входят без отрицания, а ложные - с отрицанием. Затем составляется дизъюнкция элементарных произведений.

Для нашего примера:

Ф = рqrрrрq

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