5 дәріс Дизъюнктивті және конъюнктивті қалыпты формалар
жүктеу/скачать 468,55 Kb.
|
Д 5 ДКФ, КНФ
- Бұл бет үшін навигация:
- Логикалық функциялардың толық жүйелері
- Дизъюнктивті Қалыпты және Конъюнктивті Қалыпты Формалар
- Формуланы ҚКФ - ке келтіру ережесі
- Мысал 4.5
- Пайдаланылған әдебиеттер
- Интернет ақпарат көздері: 7 https://www.youtube.com/watchv=GtTkjE8fY8c 8 http://www.myshared.ru/slide/1253858/ Назарларыңызға рахмет!
5 - дәрісДизъюнктивті және конъюнктивті қалыпты формалар Сеитова Алия Амангалиевна Логикалық функциялардың булев алгебрасы. Логикалық функциялардың толық жүйелері Бірдей логикалық функцияны әр түрлі логикалық амалдар жиынтығын қамтитын формулалармен анықтауға болады. Мысалы, Кез-келген басқа логикалық функцияларды білдіруге болатын логикалық операциялардың (функциялардың) жиынтықтары бар. Анықтама: Егер кез-келген логикалық функция Σ-ден функциялардың суперпозициясы болса, онда Σ логикалық функциялар жүйесі функционалды түрде толық жүйе немесе негіз деп аталады. Функционалды толық жүйелердің мысалдары: және тағы басқалары болып табылады. Ең жақсы зерттелгені базисі. Айнымалылар мен жақшалардан басқа, тек конъюнкция, дизъюнкция және теріске шығару операциялары бар формулалар булев (логикалық) деп аталады. Теорема. Кез-келген логикалық функция булев (логикалық) формуламен ұсынылуы мүмкін (яғни, конъюнкция, ажырату және теріске шығарудың суперпозициясы ретінде). Бұдан шығатыны, жүйесі функционалды түрде толық. Кез - келген басқа операциялар жиынтығының функционалды толықтығын дәлелдеу үшін жиынтық операциялары арқылы конъюкцияны, дизъюнкцияны және теріске шығаруды білдіруге болатындығын көрсету жеткілікті. Және жалпы мәлімдеме де әділ. Теорема. Егер Σ толық жүйенің барлық функциялары Σ-ден жоғары формулалармен ұсынылса, онда Σ де функционалды түрде толық болады. Мысал 4.1 - және жүйелерін және базисін қарастырайық. де базистер екенін дәлелдейік. Шынында да, осы жүйелердің әрқайсысында -ге дейін жетіспейтін операцияны қалған екеуі арқылы білдіруге болады: 1) үшін 2) үшін жетіспейді жүйелеріндегі формуласы сәйкесінше формулаларға ауысады: Осылайша, функционалды толықтық тұрғысынан жүйесін артық деп санауға болады, өйткені ол одан дизъюнкция немесе конъюнкция жойылған кезде толықтық қасиетін сақтайды. Бірақ, көріп отырғанымыздай, жүйелерінің артықсыздығы үшін формулалардың артықтығымен төлеуге тура келеді, өйткені 1) және 2) формулаларға сәйкес бір операцияны екіншісіне ауыстыру формулаға артық терістеуді енгізеді. Жоғарыда айтылғандай, негізі ең көп зерттелген және практикада кеңінен қолданылғандықтан, оған басқа негіздер келтірілген. Дизъюнктивті Қалыпты және Конъюнктивті Қалыпты Формалар Анықтама. Элементар конъюнкция (дизъюнкция) - бұл айнымалылардың немесе олардың теріске шығаруларының конъюнкциясы (дизъюнкция). Мысал 4-2 - a) және - элементар дизъюнкциялар; б) және - элементар конъюнкциялар; в) - бір мезгілде және қарапайым дизъюнкция және қарапайым конъюнкция. Анықтама. Қалыпты дизъюнктивті форма (ҚДФ) деп қарапайым конъюнкциялардың дизъюнкциясы аталады. Қалыпты конъюктивті форма (ҚКФ) деп элементар дисъюнкция конъюнкциясы аталады. Мысал 4.3 - a) -ҚДФ, б) -ҚКФ. Теорема. Кез-келген формуланы ҚДФ (ҚКФ) - ке келтіруге болады (яғни кез-келген формула кейбір ҚДФ (ҚКФ) - ке тең). Формуланы ҚДФ-ке келтіру ережесі: a) формуладағы барлық логикалық амалдар эквиваленттерді қолдана отырып арқылы өрнектеледі: б) барлық теріске шығаруды де Морган Заңы бойынша айнымалыларға ауыстыру: в) дистрибутивтік Заңын қолдана отырып, барлық конъюкциялар дизъюнкциядан бұрын орындалуы үшін формулаларды түрлендіріңіз: Мысал 4.4 - формуласын ҚДФ - ке келтіру. Шешімі. - ті - ке ауыстыру, содан кейін де Морган заңын және Қос теріске шығару заңын қолданамыз: Кейбір оқулықтардағы мысалдағы соңғы формула қазірдің өзінде ҚДФ болып саналатынын ескеріңіз, ал басқаларында олар қарапайым конъюнкциялар мен дизъюнкцияларда әр айнымалы бір реттен көп болмауы керек деп санайды. Артық айнымалыларды жою үшін келесі эквиваленттер қолданылады: a) (идемпотенттілік Заңы); б) (алынып тасталған үшінші заңы), (қарама-қайшылық заңы); в) - (тұрақтылардың қасиеттері). Идемпотенттік Заңын қолдана отырып, соңғы мысалда ҚДФ аламыз: Формуланы ҚКФ - ке келтіру ережесі Формуланы ҚКФ-ке келтіру ҚДФ сияқты жүргізіледі, тек в) тармағының орнына в’) тармағы қолданылады: в') дистрибутивтік Заңын қолдана отырып, формулаларды барлық дизъюнкциялар конъюнкциялардан бұрын орындалатындай етіп түрлендіріңіз: Мысал 4.5 - формуласын ҚКФ - ке келтіру. Шешімі. операциясын формуласын қолданып ауыстырамыз: [ де Морган заңын және Қос теріске шығару заңы] - ҚКФ. Бақылау сұрақтары
Пайдаланылған әдебиеттер: 1 Иванов, Б.Н. Дискретная математика. Алгоритмы и программы. Расширенный курс / Б.Н. Иванов. - М.: Известия, 2011. - 512 c. 2 Иванов, О.А. Дискретная математика. Учебник для вузов / О.А. Иванов, Г.М. Фридман. - СПб.: Питер, 2014. - 296 c. 3 Соболева, Т.С. Дискретная математика: Учебник / Т.С. Соболева. - М.: Академия, 2018. - 240 c. 4 Ерусалимский, Я.М. Дискретная математика. Теория и практикум: Учебник / Я.М. Ерусалимский. - СПб.: Лань, 2018. - 476 c. 5 Астраханцева Л.Н. , Байсалова М.Ж. Дискретная математика. Конспект лекций для студентов всех форм обучения специальности 5В070300-Информацион. системы.- Алматы: АУЭС, 2014.- 35 с. 6 Астраханцева Л.Н. Дискретная математика. Учебное пособие. - Алматы: АУЭС, 2011. - 98 с. Интернет ақпарат көздері: 7 https://www.youtube.com/watch?v=GtTkjE8fY8c 8 http://www.myshared.ru/slide/1253858/ Назарларыңызға рахмет! жүктеу/скачать 468,55 Kb. Достарыңызбен бөлісу:
|