Предваренная нормальная форма

Дата добавления: 2013-12-24; просмотров: 1054; Нарушение авторских прав

Основные законы эквивалентных преобразований алгебры предикатов представлены в таблице.

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

Наименование закона и правила	Равносильные формулы F_i=F_j
коммутативности	"_x"_y(F²(x; y))="_y"_x(F²(x; y))^); $_x$_y(F²(x; y))=$_y$_x(F²(x; y))^). *) только для одноименных кванторов.
дистрибутивности	"_x(F₁(x))&"_x(F₂(x))="_x(F₁(x)&F₂(x))⁾; $_x(F₁(x))Ú$_x(F₂(x))=$_x(F₁(x)ÚF₂(x))^*); )для логической связки “&” формул только с кванторами " по одной переменной x. **)для логической связки “Ú” формул только с кванторами $ по одной переменной x.
идемпотентности ÂÎ{";$}	Â_x(F(x))Ú Â_x(F(x))= Â_x(F(x)); Â_x(F(x))&Â_x(F(x))= Â_x(F(x))
исключенного третьего	Â_x(F(x))ÚùÂ_x(F(x))=и, где ÂÎ{";$}
противоречия	Â_x(F(x))&ùÂ_x(F(x))=л, где ÂÎ{";$}
де Моргана	"x(ùF(x))=ù$x(F(x)); $x(ùF(x))=ù"x(F(x))
дополнения	ù (ùÂ_x(F(x)))= Â_x(F(x)), где ÂÎ{";$}
свойства констант	Â_x(F(x))Ú и=и; Â_x(F(x))Úл=Â_x(F(x)); Â_x(F(x))&л=л; Â_x(F(x))&и=Â_x(F(x)), где ÂÎ{";$}.

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

В результате этих алгебраических преобразований может быть получена формула вида: Â_x₁ Â_x₂ ¼Â_xn(M), где ÂÎ{"; $} , а М – матрица формулы. Кванторную часть формулы Â_x₁ Â_x₂ ¼Â_xn иногда называют префиксом ПНФ.

В последующем матрицу формулы преобразуют к виду КНФ, что облегчает механизм по принципу резолюции.

<== предыдущая лекция	\|	следующая лекция ==>
Законы алгебры предикатов	\|	Шаг 1. Представить формулу F в виде ПНФ, т.е.