П. 2.2. Дизъюнктивная и конъюнктивная нормальная форма. ?????

Определение 2.2. Формула, в которую входят только операции конъюнкции, дизъюнкции и отрицания, причем операция отрицания относится непосредственно к высказывательным переменным, называется приведенной.

Пример:

1) - является приведенной;

2) - не является приведенной, так как содержит операцию импликации;

3) - не является приведенной, так как операция отрицания отнесена к формуле , а не к высказывательной переменной.

Для любой формулы алгебры высказываний путем равносильных преобразований можно получить приведенную формулу, например, .

Пусть задана система высказывательных переменных (1).

Определение 2.3. Элементарной дизъюнкцией высказывательных переменных из системы (1) называется дизъюнкция некоторых переменных этой системы или их отрицаний.

Определение 2.4. Элементарной конъюнкцией называется конъюнкция некоторых переменных этой системы или их отрицаний.

Например:

1) Пусть задана система . Формулы являются элементарными дизъюнкциями; первые две из них – одночленными.

2) – элементарными конъюнкциями.

Теорема 2.1. Элементарная дизъюнкция (элементарная конъюнкция) является тождественно истинной (тождественно явной) тогда и только тогда, когда она наряду с некоторой высказывательной переменной содержит отрицание этой переменной .

Доказательство. (э. стр. 37).

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

ДНФ можно записать в виде , где каждое - элементарная дизъюнкция.

Например: ; – являются ДНФ.

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

Например: – является КНФ.

Теорема 2.2. КНФ (ДНФ) является тождественно истинной (тождественно ложной) тогда и только тогда, когда каждая составляющая её элементарная дизъюнкция (элементарная конъюнкция) содержит некоторую высказывательную переменную вместе с ее отрицанием .

Доказательство вытекает из Т. 2.1.

Теорема 2.3. Для любой формулы алгебры высказываний существует эквивалентная ей КНФ (ДНФ).

Доказательство проведем для случая КНФ. Пусть задана формула А. Вначале получим для данной формулы А эквивалентную ей приведенную формулу В. Применяя к В дистрибутивный закон, получим КНФ.

Схема приведения формулы к КНФ и ДНФ:

Для облегчения процедуры раскрытия скобок (дистрибутивный закон) можно воспользоваться формальной заменой логических операций на арифметические. Если формула приводится к КНФ, то меняется на , а на , к ДНФ – – , и – . На последнем шаге нужно совершить обратную замену.

Например:

1) Приведите к конъюнктивной нормальной форме (КНФ) .

Решение:

. Заменим в приве-денной формуле на , на и раскроем скобки: .

Сделав обратную замену, получим КНФ формулы А:

.

2) Привести к ДНФ формулу .

Решение:

– приведенная формула.

Заменим в приведенной формуле на , на и раскроем скобки:

.

Сделав обратную замену, получим ДНФ формулы А: .

Определение 2.7. Элементарная конъюнкция (дизъюнкция) называется полной, если каждая переменная входит в нее один и только один раз.

Например:

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

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

Определение 2.9. Совершенной дизъюнктивной нормальной формой (СДНФ) называется дизъюнкция различных полных элементарных конъюнкций.

Например:

Пусть задана система переменных .

Формула – СКНФ, а – СДНФ.

Теорема 2.4. Для любой не тождественно истинной (тождественно ложной) формулы алгебры высказываний существует эквивалентная ей СКНФ (СДНФ).

Доказательство: (э. стр.40).

Алгоритм получения СДНФ:

1. Для формулы А получаем любую ДНФ.

2. Если в ДНФ есть слагаемое, не содержащее , то заменяем .

3. Если в ДНФ два одинаковых слагаемых В, то лишнее можно отбросить, так как .

4. Если в некоторое слагаемое В ДНФ А входит дважды, то лишнюю можно отбросить, так как .

5. Если слагаемое В в ДНФ А содержит конъюнкцию , то и , и это слагаемое можно отбросить.

Например: привести к СДНФ формулу .

Решение:

Алгоритм получения СКНФ путем равносильных преобразований похож на алгоритм получения СДНФ:

1. Для формулы А получаем любую КНФ.

2. Если элементарная дизъюнкция В, входящая в КНФ, не содержит , то .

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

4. Если КНФ содержит два одинаковых сомножителя В, то лишнюю элементарную дизъюнкцию можно отбросить, так как .

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

Например: привести к СКНФ .

Если же будет задана таблица истинности формулы, то алгоритм построения СДНФ следующий:

1. В таблице истинности отмечаем наборы переменных, для которых значение формулы равно 1.

2. Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если , то конъюнкция включает саму переменную, а противном случае – ее отрицание.

3. Все полученные конъюнкции связываем операциями дизъюнкции. Получив СДНФ можно восстановить формулы алгебры высказываний.

Например: Задана таблица истинности функции .

x	y	z

Эту формулу можно упростить. Для удобства обозначим – .

Алгоритм получения СКНФ по таблице истинности:

1. В таблице истинности отмечаем наборы переменных, для которых значение формулы равно 0.

2. Записываем для каждого отмеченного набора дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в дизъюнкцию включаем саму переменную, а противном случае – ее отрицание.

3. Все полученные дизъюнкции связываем операциями конъюнкции.

Например: Построить формулу по данной таблице истинности

x	y	z	А

.

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