Анықтама Егер формула элементар конъюкциялардың дизъюнкциясынан тұрса, онда формула дизъюнктивті нормаль формада немесе днф-та деп аталады. Анықтама 2

Формуланы дәлелдеу 3 кезеңнен тұрады:

• Формуланы дәлелдеу 3 кезеңнен тұрады:
• Формуладағы символдарын 16, 17 формулалар көмегімен жойып, алдыңғы А формуласына тепе-тең болатындай А А1 формуласын аламыз.
• Терістеу таңбасы тек қана логикалық айнымалылардың алдында ғана болатындай А1 формуласымен тепе-тең болатын А2 формуласын аламыз (А1 А2). (терістеу таңбасын жақшаның алдынан логикалық айнымалылардың алдына енгізу.) Бұл түрлендіру де Морган заңы бойынша жүргізіледі.
• Алынған А2 формуласын айнымалылар және олардың терістеулерінің көпмүшелі конъюкциясы және дизъюнкциясынан құрылған деп есептеуге болады. Бұдан соң дизъюнкцияны қосындыға, ал конъюкцияны көбейтіндіге аналогиялық деп есептеп конъюкцияның дизъюнкцияға қарағандағы жалпылама дистрибутивтілігін пайдаланып (8 формула) формуланы одан әрі түрлендіру керек. Алынған В формуласы теорема шартын қанағаттандыратын формула болып табылады. Осы А2 В формуласы берілген формуланың ДНФ-ы болады.

Мысал 3.

КНФ

• КНФ –конъюнктивті нормаль форма.

Анықтама. Егер формула логикалық айнымалылар мен олардың терістеулерінің дизъюнкциясынан тұрса, онда бұл формуланы элементар дизъюнкция деп атайды. Элементар дизъюнкция бір мүше болуы да мүмкін.

Анықтама. Егер формула элементар дизъюнкциялардың конъюнкциясынан тұрса, онда ол формула КНФ-та тұр делінеді.

Теорема 2. Кез-келген А формуласы үшін онымен тепе-тең болатын және КНФ-та болатын В формуласын табуға болады. Бұл В формуласы А формуласының КНФ-сы деп аталады. Осы теореманың дәлелдеуін формуланы ДНФ-қа келтіру теоремаға ұқсас түрде 3 кезеңде дәлелденеді.

• Теорема 2. Кез-келген А формуласы үшін онымен тепе-тең болатын және КНФ-та болатын В формуласын табуға болады. Бұл В формуласы А формуласының КНФ-сы деп аталады. Осы теореманың дәлелдеуін формуланы ДНФ-қа келтіру теоремаға ұқсас түрде 3 кезеңде дәлелденеді.

Мысал 4.

ЖДНФ

• ЖДНФ - жетілдірілген дизъюнктивті нормаль форма.

Есептер шығару барысында формуланың ДНФ-ң бір мәнінде анықталмайтындығын көруге болады.

айнымалылар тізіміне байланысты А формуласы берілсін. Егер А формуласы үшін мынандай 3 шарт орындалатын болса, онда А формуласы осы айнымалылар тізіміне байланысты ЖДНФ-та делінеді.

• А формуласы ДНФ-та болуы керек.
• Әрбір дизъюнктивті мүше к мүшелі конъюнкция болуы керек және әрбір конъюнкцияның -нші орнында айнымалысы немесе оның терістеуі болуы керек.
• Барлық дизъюнктивті мүшелер қос - қостан алғанда әртүрлі болуы керек.