Нормальные формы формул

В алгебре высказываний используют две нормальные формы: дизъюнктивную (ДНФ) и конъюнктивную (КНФ):

• Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция элементарных конъюнкций:

Ф=К₁ÚК₂ÚК₃ÚК₃…, где К_i=(А&В&С&…);

• Конъюнктивная нормальная форма (КНФ) – конъюнкция элементарных дизъюнкций:

Ф=D₁&D₂&D₃&D₃…, где D_i=(АÚВÚСÚ…).

Алгоритм приведения к нормальной форме:

1. Устранить всюду связки ® и «по законам для импликации и для эквивалентности:

• (A®B) º (ØAÚB) º Ø(A&ØB)

• (A«B) º (A ®B)&(B ®A)

2. Используя законы дополнения и де Моргана, продвинуть отрицание до ПП:

• Ø(ØA) º A,

• Ø(AÚB) º (ØA&ØB)

• Ø(A&B) º (ØAÚØB)

3. Применить закон дистрибутивности:

• для КНФ AÚ(B&C) º (AÚB)&(AÚC)

• для ДНФ A&(BÚС) º (A&B)Ú(A&C)

Кроме нормальных форм существуют совершенные нормальные формы - в них в каждой элементарной конъюнкции или дизъюнкции присутствуют все ПП.

Алгоритм преобразования ДНФ к виду СДНФ:

1. Если в элементарную конъюнкцию Ф не входит подформула Ф_i или ØФ_i, то шаг2. Иначе – конец.

2. Дополнить элементарную конъюнкцию формулой (Ф_iÚØФ_i) и выполнить преобразование формулы по закону дистрибутивности Ф&(Ф_iÚØФ_i)ºФ&Ф_iÚФ&ØФ_i

3. Повторить шаг 1.

Алгоритм преобразования КНФ к виду СКНФ:

1. Если в элементарную дизъюнкцию Ф не входит подформула Ф_i или ØФ_i, то шаг2. Иначе – конец.

2. Дополнить элементарную дизъюнкцию формулой (Ф_i&ØФ_i) и выполнить преобразование формулы по закону дистрибутивности ФÚ(Ф_i&ØФ_i)º(ФÚФ_i)&(ФÚØФ_i)

3. Повторить шаг 1.

Элементарные конъюнкции СДНФ формируются для значений формулы, равных “и”, т.е. число элементарных конъюнкций СДНФ равно числу истинных значений формулы. Пропозициональные переменные элементарной конъюнкции записываются без изменений, если их значение равно “и” и с логической связкой “¬”, если их значение равно “л”.

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

Можно сформировать логические формулы в форматах СДНФ и СКНФ по таблицам истинности, а не по приведенным выше правилам.

Пусть дана таблица истинности для некоторого сложного высказывания:

№ п/п	B	С	D	В&С&D	А	Ф
	л	л	л	л	л	и
	л	л	и	л	л	и
	л	и	л	л	л	и
	л	и	и	л	л	и
	и	л	л	л	л	и
	и	л	и	л	л	и
	и	и	л	л	л	и
	и	и	и	и	л	л
	л	л	л	л	и	и
	л	л	и	л	и	и
	л	и	л	л	и	и
	л	и	и	л	и	и
	и	л	л	л	и	и
	и	л	и	л	и	и
	и	и	л	л	и	и
	и	и	и	и	и	и

Необходимо:

1) Сформировать формальную запись этого высказывания в форматах СДНФ и СКНФ,

2) Упростить формулу в формате СКНФ.

Решение:

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

(ØА&ØВ&ØС&ØD)₁Ú(ØА&ØВ&ØС&D)₂Ú(ØА&ØВ&С&ØD)₃Ú(ØА&ØВ&С&D)₄Ú (ØА&В&ØС&ØD)₅Ú(ØА&В&ØС&D)₆Ú(ØА&В&С&ØD)₇Ú(А&ØВ&ØС&ØD)₉Ú (А&ØВ&ØС&D)₁₀Ú(А&ØВ&С&ØD)₁₁Ú(А&ØВ&С&D)₁₂Ú(А&В&ØС&ØD)₁₃Ú (А&В&ØС&D)₁₄Ú(А&В&С&ØD)₁₅Ú(А&В&С&D)₁₆

2) Для формирования СКНФ используем в заданной таблице строки, для которых Ф=л. Видно, что в этом случае число элементарных конъюнкций равно 1. СКНФ показана ниже (индекс элементарной дизъюнкции соответствует номеру строки таблицы истинности): (АÚØВÚØСÚØD)₈

3) Выполним эквивалентные преобразования полученной СКНФ:

(АÚØВÚØСÚØD)= (АÚØ(В&С&D))=(В&С&D)®А

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

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