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

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

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

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

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

F = K₁Ú K₂Ú K₃Ú . . ., где K_i = ( A&B&C& . . .).

В элементарной коньюнкции нет двух одинаковых пропозициональных переменных, т.к. по закону идемпотентности F&F=F. В ДНФ нет двух одинаковых элементарных коньюнкций, т.к. по закону идемпотентности FÚF=F. Если одна из элементарных коньюнкций содержит F и ù F, то элементарную коньюнкцию следует удалить, т.к. F&ù F=л.

Пример: F=F₁&(F₁ÚF₂) ÚF₂&(F₁Úù F₂).

1) по закону дистрибутивности:

F=F₁&F₁ÚF₁&F₂ÚF₁&F₂ÚF₂&ù F₂;

2) по законам идемпотентности и противоречия:

F=F₁ÚF₁&F₂;

3) по закону поглощения:

F=F₁.

F = D₁& D₂& D₃& . . . , где D_i = ( AÚBÚCÚ . . . ).

В элементарной дизьюнкции нет двух одинаковых пропозициональных переменных, т.к. по закону идемпотентности FÚF=F. В КНФ нет двух одинаковых элементарных дизьюнкций, т.к. по закону идемпотентности F&F=F. Если одна из элементарных дизьюнкций содержит F и ù F, то её следует удалить,

т.к. FÚù F = и.

Наибольшее распространение в логике высказываний по­лучили формулы вида КНФ, элементарные дизъюнкции которых D_i принято называть дизъюнктами, а члены каждого дизъюнкта A, B, C –атомами.

Шаг 1. Устранить логические связки “«” и “®” всюду по правилам:

F₁ « F₂ =(F₁®F₂)&(F₂®F₁)=(ù F₁Ú F₂)&(ù F₂Ú F₁)=

=(ù F₁&ù F₂)Ú( F₁& F₂);

F₁ ® F₂ =ù F₁ÚF₂ =ù (F₁ &(ù F₂)).

Шаг 2. Продвинуть отрицание до элементарной формулы (пропозициональной переменной) по правилам:

ù (ù F) = F ;

ù (F₁Ú F₂ ) = (ù F₁) &(ù F₂);

ù (F₁&F₂) = (ù F₁)Ú(ù F₂).

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

a) для КНФ: F₁Ú(F₂ &F₃) = (F₁Ú F₂)&(F₁ÚF₃);

b) для ДНФ: F₁&(F₂Ú F₃) = (F₁&F₂)Ú(F₁&F₃).

Пример: Дана формула F=((F₁®(F₂ÚùF₃))®F₄).

Привести формулу к виду КНФ:

1) F=(ùF₁Ú(F₂Úù F₃))®F₄ ;

2) F=ù(ùF₁Ú(F₂ÚùF₃))ÚF₄ ;

3) F=(F₁&(ù F₂)& F₃)ÚF₄ ;

4) F=(F₄ÚF₁)&(F₄Ú(ù F₂)&F₃);

5) F=(F₄ÚF₁)&(F₄Úù F₂)&(F₄ÚF₃).