Дәрістер тезистері 1 тақырып Жиындар теориясының элементтері Мақсаты
Пікірлер алгебрасының формулалары үшін нормаланған формалар
жүктеу/скачать 2,42 Mb.
|
Дискретт математика. Дәрістер
абай
- Бұл бет үшін навигация:
- Анықтама
| Пікірлер алгебрасының формулалары үшін нормаланған формалар
Пікірлер алгебрасының әрбір формуласы үшін, тек қана терістеу, конъюнкция мен дизъюнкция арқылы байланысқан мәндес формуланы көрсетуге болады ( ол үшін , амалдары , арқылы өрнектеледі). Берілген флормуланы , , арқылы бірнеше тәсілмен өрнектеуге болады. Мысал: Анықтама. Х1 ,…,Хn айнымалылардың конъюнктивті бірмүшесі деп осы айнымалылардың конъюнкциясы немесе терістеуі аталады. Мысал: - элементар көбейтінді. Анықтама. Х1 ,…,Хn айнымалылардың дизъюнктивті бірмүшесі деп осы айнымалылардың дизъюнкция сы немесе терістеуі аталады. Мысал: - элементар қосынды. Анықтама. Конъюнктивті нормаланған форма (КНФ) деп дизъюнктивті бірмүшелердің конъюнкциясы аталады (немесе элементар қосындылардың көбейтіндісі ) Мысал: Анықтама. Дизъюнктивті нормаланған форма (ДНФ) деп конъюнктивті бірмүшелердің дизъюнкциясы аталады (немесе элементар көбейтінділердің қосындысы) Мысал: Әрбір формула үшін әрқашан да дизъюнктивті нормаланған форма да, конъюнктивті нормаланған форма да табылады. Де Морган және дистрибутивті қасиеттерді қолданып, бір формадан екінші формаға өтуге болады. Берілген F формуласы үшін шексіз көп дизъюнктивті, конъюнктивті нормаланған формалар табылады. Мысал: КНФ және ДНФ табу керек: және т.б. Көптеген ДНФ және КНФ арасында (берілген формула үшін) жалғыз келесі түрдегі форма табылады: жетілдірілген ДНФ және КНФ. Анықтама. Х1,…,Хn айнымалыларына қатысты (конъюнктивті немесе дизъюнктивті) бірмүше жетілдірілген деп аталады, егер оның құрамына немесе айнымалының өзі кіретін болса, немесе оның терістеуі кіретін болса. Анықтама. (Дизъюнктивті немесе конъюнктивті ) нормаланған форма жетілдірілген деп аталады, егер оның құрамына тек қана жетілдірілген бірмүшелер кіретін болса. Мысал: Х1,Х2 айнымалыларына қатысты жетілдірілген КНФ табу керек: жүктеу/скачать 2,42 Mb. Достарыңызбен бөлісу:
|