1 пєнініњ ОЌу программасы syllabus

Формуланы дизюнктивті қалыпты формаға келтірудің алгоритмі

жүктеу 19,56 Mb.

бет	15/34
Дата	31.05.2018
өлшемі	19,56 Mb.
	#18555

1 ... 11 12 13 14 15 16 17 18 ... 34

Формуланы дизюнктивті қалыпты формаға келтірудің алгоритмі

1. Формула құрамындағы барлық логикалық операцияларды

эквиваленттіліктер және

, операцияларының анықтамаларын пайдаланып дизъюнкция, конъюнкция, терістеу арқылы өрнектейміз. (Дизъюнктивті қалыпты формаға түрлендіру )

2. Морган заңын пайдаланып, барлық терістеулерді айнымалыларға көшіріп, қос терістеулерді

формуласы бойынша қысқартамыз.

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

Мысалы,   (( xy)  ( xz)) формуласын дизъюнктивті қалыпты формаға түрлендіру керек болсын . ,  операцияларын ,,

 арқылы өрнектейміз.



;

Сонымен,   (( xy)  ( xz))

;

2-Теорема. Кез келген А формуласы үшін оған эквивалентті және ҚҚФ болатын В формуласын табуға болады АВ (дәлелдейміз) В А- ның ҚҚФ. Кез келген формула өзінің ҚҚФ эквивалентті.

Конюнктивті қалыпты формаға келтірудің алгаритмі алдыңғыға ұқсас, тек 3 пунктың орнына

қолданылады.

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

Мысалы.

формулада

болмайтындай түрлендіреміз:

-бұл формуланы одан әрі тағы түрлендіруге болады:

;

-ті ҚҚФ деуге де, ДҚФ деуге де болады. Бұлардан басқа егер формуланың ДҚФ белгілі болса ҚҚФ-ке , ҚҚФ белгілі болса ДҚФ көшудің алгоритмдері бар. Олар төмендегідей:

жүктеу 19,56 Mb.

Достарыңызбен бөлісу:

1 ... 11 12 13 14 15 16 17 18 ... 34