Нормал және жетілдірілген формалар туралы қазақша реферат

Нормал және жетілдірілген формалар туралы қазақша реферат

А(а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 Тұжырымдар алгебрасының кез келген тепе-тең ақиқат емес формуласының бірмәнді ЖКНФ түрінде өрнектелуі бар.