Лекция «Пікірлер алгебрасын логикалық есептерді шешуде қолдану»
жүктеу/скачать 187,61 Kb.
|
|
1 – лекция «Пікірлер алгебрасын логикалық есептерді шешуде қолдану » Пікірлер алгебрасы «логикалық» деп аталатын біртипті есептерді шешу үшін табысты түрде қолданылуы мүмкін. Осы есептерді пайыммен шешуге болады, бірақ мұндай пайымдаулардың жолы әрқашан айқын бола бермейді. Пікірлер алгебрасын қолдану берілген есептерді шешетін жалғыз және жеткілікті жалпы әдістерін береді. Пікірлер алгебрасы әдісімен шығатын логикалық есептердің кейбір ерекшеліктерін белгілейік. Осындай есептерде пікірлердің қатары бар болады. Олардың кейбіреулері ақиқат, кейбіреулері жалған болады, бірақ қайсыс ақиқат, я жалған екені белгісіз. Мысалы, үш пікір бар, олардың екеуі ақиқат, ал біреуі жалған. Ақиқат (немесе жалған) болатынын біле отырып, бұл шарттарды ескеріп, пікірлерден әлдебір күрделі пікір құру керек. Содан соң логикалық заңдылықтарын қолдана отырып, есептердің сұрағына жауап анықтайтындай түрге түрлендіреміз. Мәндес түрлендірулер кезінде есептердің басқа да шарттарын қолданамыз. Қарастырылып отырған мысалда мұндай күрделі пікірлер келесідей ойлардан шығып құрастырылады. пікірлерінің екеуі ақиқат болғандықтан, онда олардың барлық дизъюнкция жұптары да ақиқат: . Осылайша бұл пікірлердің конъюнкциясы да ақиқат: Бұл пікірлердің мәндес түрлендіруі пікірлерінің құрылымына тәуелді. Келесі мысалды қарастырайық.[1]. Мысал: Ақбаев, Сарыбаев және Қарабаев қатысатын мектеп шахмат турнир финалының басталмай жатып бір жанкүйер бірінші орында Ақбаев ие болады, ал екінші жанкүйер Сарыбаев соңғы орынға ие болмайтынын, үшінші жанкүйер Қарабаев бірінші орынға ие болмайды деп айтты. Ойын біткен соң бір жанкүйер қателесіп, екеуі дұрыс тапты. Егер ешқандай екі қатысушы бір орынға ие болмаса, орындар қалай бөлінді?[1]. Шешу үшін келесі пікірлерді енгіземіз (i= 1, 2, 3): : «Ақбаев i-ші орын ға ие»; : «Сарыбаев i-ші орын ға ие»; : «Қарабаев i-ші орын ға ие»; Онда жанкүйерлердің келесі пікірлерін келесі түрде жазамыз: 1-ші жанкүйер : ; 2-ші жанкүйер : ; 3-ші жанкүйер : ; Көрінеу ақиқат болатын күрделі пікір құрастырамыз. пікірлерінің екеуі ақиқат болғандықтан, онда олардың дизъюнкциясы да ақиқат: . Осылайша бұл пікірлердің конъюнкциясы да ақиқат: Бұл пікірлерді мәндес түрде түрлендірейік: Кейбір пікірлердің дизъюнкциясы боп келетін алынған пікір ақиқат. Осылайша ақиқат кемдегенде бір қосылғыш болып табылады. Барлық жағдайларды тізбекті түрде қарастырайық: =1. Онда және =1, яғни =0. Біз орындардың келесідей үлестірімдерін аламыз: АСВ; =1. Онда және =1, яғни =0. Осында біз екі мүмкін болатын орындардың үлестірімін аламыз: АВС және АСВ; . Онда және =1, яғни =0. Осында үлестіру варианттары келесідей болады: АСВ, САВ, СВА. Қорыта келе келесідей жауап варианттарын аламыз: АСВ, АВС, САВ, СВА. Бірінші вариантты тексере отыра барлы үш жанкүйер пікірлері де ақиқат болып шыққанын көреміз, ал бұл есептін шартына сәйкес келмейді. Нәтижесінде үш шешімін аламыз: АВС, САВ, СВА. Қарастырылған шешу әдісі «артық түбір» - дің пайда болуына әкеледі. Бұл есептің шартына сәйкес алынған варианттардың тексеруін қажет етеді. Тек қана есептің шартын қанағаттандыратын жауаптарды беретін қысқа да нұсқа әдісті қарастырайық. Ол пікірлерінің орнына есептің шартын дәл орындайтын пікірлерді құрастыру негізінде орындалады. Осындай пікірлерді құру үшін пікірлерінен басқа келесідей пікірлерді қарастырамыз: X: « 1-ші жанкүйер дұрыс тапты»; Y: « 2-ші жанкүйер дұрыс тапты»; Z: « 3-ші жанкүйер дұрыс тапты»; Онда және екі пікірдің біреуі ақиқат екені айқын көрініп тұр. Онда олардың дизъюнкциясы да ақиқат . Осыдан 2-і және 3-ші жанкүйерлермен байланысты пікірлер де ақиқат: және . Осылайша бұл үш пікірдің конъюнкциясы да ақиқат: Бұл пікірді түрлендіру үшін дизъюнкцияға қатысты конъюнкцияның дистрибутивтік заңын қолдану керек. Қорытындысында айнымалыларына ДНФ болады. Бірақ оның нормаланған конъюнктивті бірмүшелері есептің шартына сәйкес 0-ге тең болады. үш пікірдің екеуі ақиқат болғандықтан, өзара көбейткіштері бар конъюнктивті бірмүшелері де 0-ге айналады. үш пікірдің біреуі жалған болғандықтан өзара көбейткіштерінен тұратын кнъюнктивті бірмүше де 0-ге тең. Сонымен ДНФ формасының өзара көбейткіштері бар тек үш нормаланған конъюнктивті бірмүшесі қалады:. ДНФ формасының түрі қарастырылып отырған есептің ДНФ формасының түрі: Бұл пікірдің ақиқаттылығы бұл- кемдегенде бір қарапайым конъюнктивтің ақиқат болуы. Барлық жағдайларды тізбекті түрде қарастырайық: . Онда және =1, осылайша =0 және = 1. Бұл жағдай орынға ие бола алмайды, себебі А және В бірінші орынға ие болады. Онда , =1, , және осылайша =0 және = 0, яғни, орын үлестіру үшін екі мүмкіндік пайда болады: CAB, CBA; Онда =1, , яғни және орындардың келесідей үлестірімі пайда болады: ABC. Нәтижесінде үш шешім аламыз: АВС, СВА, САВ. Мысал: Төрт дос – Ақылбаев (А), Балғынбаев (В), Серікбаев (С) және Дүйсенбаев (D) жазғы демалысқа төрт әртүрлі қалаларға Астана, Орал, Семей және Талдықорғанға баруды шешті. Әрбіреуі қай қалаға барады, егер келесі шектеулер болса: P) егер А Астанағ бармаса, онда С Оралға бармайды; Q) егер В Астанаға да, Талдықорғанға да бармаса, онда А Астанаға барады; R) егер С Талдықорғанға бармаса, онда онда В Семейге барады; S) егер D Астанаға бармаса, онда В Астанаға барады; T) егер D Оралға бармаса, онда В Астанаға бармайды;[2]. Шешуі: белгісімен «А Астанаға барады», ал белгісімен «А Астанаға бармайды»деп белгілейік. Соған сәйкес әріптермен келесі достарды да белгілейміз. Онда шектеулер төмендегідей болады: P Q( ) R ; S T Осылайша әрбіреуі ақиқат болатындай пікірлердің конъюнкциясын құрамыз: Бірнеше түрлендіруден соң, біз бір адамның екі әртүрлі қалаға немесе екі әртүрлі адамның бір қалаға бару конъюнкциялары жалған екенін көреміз. Осылайша конъюнкциясы ақиқат, яғни пікірлері ақиқат болып табылады. Т шарты мен ақиқаттылығынан – ақиқат, яғни жалған болады. Онда - ақиқат, осылайша -те ақиқат. Сонымен А-Оралға, В-Астанаға, С- Талдықорғанға және - Семейге барады. Математикалық логика пәнін меңгеру барысында пікірлер алгебрасын қолданып әртүрлі логикалық есептерді шешуді жүзеге асыруда мүмкіндіктерді есептеудің тәсілдерін көрсетуді жөн көрдім. Логикалық есептер жоғары сыныптарда, математикалық олимпиадаларда, әр түрлі жарыстарда жиі қолданылады. Пайдаланылған әдебиеттер тізімі: Игошин В. И . «Математическая логика и теория алгоритмов»,Москва, 2008г. Игошин В. И . «Задачи и упражнения по математической логике», Москва, 2007 г. Досанбай П. Т. «Математикалық логика», Алматы, 2011 ж. жүктеу/скачать 187,61 Kb. Достарыңызбен бөлісу:
|