Скачать/Жүктеу
А(а1, а2, …, аn) n тұжырымның формуласын қарастырайық.
Анықтама 1. n тұжырымның қарапайым конъюнкциясы (қарапайым дизъюнкциясы) деп тұжырымдардың немесе олардың терістеулерінің конъюнкциясын (дизъюнкциясын) айтады.
Мысал 1. xyz, Øxy – қарапайым конъюнкция;
- ØxÚyÚz, yÚz, xÚØz –қарапайым дизъюнкция.
Анықтама 2. Егер А формуладағы қарапайым дизъюнкциялар бір-бірімен конъюнкцияның көмегімен байланысқан болса, онда формуланы конъюнктивті нормал форма (КНФ) деп атаймыз.
Анықтама 3. Егер А формуладағы қарапайым конъюнкциялар бір-бірімен дизъюнкцияның көмегімен байланысқан болса, онда формуланы дизъюнктивті нормал форма (ДНФ) деп атаймыз.
Тұжырымдар алгебрасының кез келген формуласы үшін тепе-тең түрлендірулер көмегімен оның ДНФ немесе КНФ алуға болады, бұл формалар жалғыз болмайды.
Анықтама 4 Егер дизъюнктивті нормал формадағы қарапайым конъюнкцияның құрамына әрбір қарапайым тұжырымның өзі немесе кері шамасы міндетті түрде енетін болса, формуланы жетілдірілген дизъюнктивті нормал форма (ЖДНФ) деп атаймыз.
Анықтама 5 Егер конъюнктивті нормал формадағы қарапайым дизъюнкцияның құрамына әрбір қарапайым тұжырымның өзі немесе кері шамасы міндетті түрде енетін болса, формуланы жетілдірілген конъюнктивті нормал форма (ЖКНФ) деп атаймыз.
Мысал 2. А(x,y,z)= xyzÚØxy – дизъюнктивті нормал форма;
B(x,y,z)= (ØxÚyÚz)( yÚz)( xÚØz) – конъюнктивті нормал форма;
C(x,y,z)= xyzÚØxyz – жетілдірілген дизъюнктивті нормал форма;
D(x,y,z)= (ØxÚyÚz)( xÚyÚz)( xÚyÚØz) – жетілдірілген конъюнктивті нормал форма.
Теорем 1 Тұжырымдар алгебрасының кез келген формуласының оған пара-пар ДНФ және КНФ бар.
Теорема 2 Тұжырымдар алгебрасының кез келген тепе-тең жалған емес формуласының бірмәнді ЖДНФ түрінде өрнектелуі бар.
Теорема 3 Тұжырымдар алгебрасының кез келген тепе-тең ақиқат емес формуласының бірмәнді ЖКНФ түрінде өрнектелуі бар.