text: Приведем к КНФ формулу F = ( X → Y ) ∧ ( ( ¬ Y → Z ) → ¬ X ) . {\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).} Преобразуем формулу F {\displaystyle F} к формуле, не содержащей → {\displaystyle \rightarrow } : F = ( ¬ X ∨ Y ) ∧ ( ¬ ( ¬ Y → Z ) ∨ ¬ X ) = ( ¬ X ∨ Y ) ∧ ( ¬ ( ¬ ¬ Y ∨ Z ) ∨ ¬ X ) . {\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \neg Y\vee Z)\vee \neg X).} В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания: F = ( ¬ X ∨ Y ) ∧ ( ( ¬ Y ∧ ¬ Z ) ∨ ¬ X ) . {\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).} По закону дистрибутивности получим КНФ: F = ( ¬ X ∨ Y ) ∧ ( ¬ X ∨ ¬ Y ) ∧ ( ¬ X ∨ ¬ Z ) . {\displaystyle F=(\neg X\vee Y)\wedge (\neg X\vee \neg Y)\wedge (\neg X\vee \neg Z).} k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно k литералов.