Нормал және жетілдірілген формалар


Скачать/Жүктеу

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


Скачать/Жүктеу

Комментировать

Вам необходимо войти, чтобы оставлять комментарии.




1Referat.kz сайтында кез-келген тақырыпқа мәліметтер, қазақша рефераттар, курстық жұмыстар жинақталған. Барлық мәліметтер тегін. Керек мағлұматты Жүктеп (Скачать) немесе Көшіріп (Скопировать) ала аласыз.

Наш сайт — это огромная Коллекция рефератов, курсовых работ, дипломных работ. Все материалы на сайте бесплатные. Нужную работу вы можете, скачать или скопировать.
Сайт картасы