Есеп. А(x,y,z) формуласының ақиқаттық кестесі берілсін.

х	у	z	А(x,y,z)
1	1	1	1
1	1	0	0
1	0	1	0
0	1	1	1
1	0	0	1
0	1	0	0
0	0	1	0
0	0	0	0

 

 

 

 

 

Формуланың ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген формула қарпайым тұжырымдардың 1, 4, 5 жолдардағы үлестірулерінде ақиқат мән қабылдайды. Конъюнкцияның ақиқаттық кестесңн пайдаланып, осы жолдардан қарапайым конъюнкция құрайық.

Бірінші жолдағы мәндерде  xyz ақиқат,

Төртінші жолдағы мәндерде Øxyz ақиқат,

Бесінші жолдағы мәндерде xØyØz ақиқат.

Енді, осы қарапайым конъюнкциялардан жетілдірілген нормал дизъюнктивті форма құрайық:

хyz Ú Øxyz Ú xØyØz.

Бұл формуланың ақиқаттық кестесінің  А(x,y,z) формуласының ақиқаттық кестесімен сәйкес кедетіндігін тексеру қиын емес. Себебі, басқа жолдардаңы қарапайым тұжырымдардың мәндерінің үлестірулерінде жоғырыдағы қарапайым конъюнкциялардың әрқайсысы жалған мән қабылдайды.

А(x,y,z)= хyz Ú Øxyz Ú xØyØz.

Демек, тепе-тең жалған емес формуланы жетілдірілген нормал дизъюнктивті формаға келтіру үшін оның ақиқаттық кестесіндегі ақиқат мәндерге сәйкес келетін жолдардан қарапайым конъюнкциялар құру қажет. Бұл қарапайым конъюнкцияларда, егер қарапайым тұжырым ақиқат мән қабылдаса, онда оның өзін, ал жалған мән қабылдаса, онда оның кері шамасын аламыз. ЖКНФ құру алгоритмін келтірейік.

Тепе-тең ақиқат емес формуланы жетілдірілген нормал конъюнктивті формаға келтіру үшін оның ақиқаттық кестесіндегі жалған мәндерге сәйкес келетін жолдардан қарапайым дизъюнкциялар құру қажет. Бұл қарапайым дизъюнкцияларда, егер қарапайым тұжырым ақиқат мән қабылдаса, онда оның кері шамасын, ал жалған мән қабылдаса, онда оның өзін аламыз.

Мәселен, жоғарыда қарастырылған формуланың ЖКНФ келесі түрде болады:

А(x,y,z)= (ØхÚØyÚz) (ØxÚyÚØz)(xÚØyÚz) (xÚyÚØz) (xÚyÚz).