 |
Предикаттар классификациясы
|
|
|
|
2 анықтама. М1,…,Мn жиындарында анықталған Р(х1,…,хn) предикат:
1) егер х1,…,хn айнымалылардың орнына М1,…,Мn жиындарынан сәйкес а1,…,аn нақты айнымалыларды қойғаннан Р (а1,…,аn) ақиқат пікірге айналса, онда ақиқат предикат деп аталады;
2) Р (а1,…,аn) жалған пікірге айналса, жалған предикат деп талады;
3) Орындалатын предикат (жалған да, ақиқат та)болса; Мысалдар.
1) R жиыныда анықталған бір орынды предикат «sin2x+cos2x=1», -ақиқат.
2) R- жиыныда анықталған «х2+у2<0»-екі орынды предикат жалған.
3) «х өзені Байкал көліне құяды» - бір орынды предикат - орындалатын, себебі берілген предикатты ақиқат пікірге айналдыратын басқа да, өзен (Баргузин) бар және жоққа шығарылатын, себебі «Ангара» жалған пікірге айналдырады.
Анықтама: М1,…,Мn жиындарында анықталған Р (х1,…,хn) предикаттың ақиқиттық жиыны деп берілген предикат х1=a1, х2=a2,…, хn=an мәндерінің орнына қойғанда Р (х1,…,хn) пікірі ақиқат болатындай реттелген (а1,…,аn) n-жүйелер жиынтығы аталады. Мұндағы, а1 
М1, …, аn 
Мn. Бұл жиын Р+ деп белгіленеді.
Мысалдар:
1) R жиынында берілген екі орынды S (х,у): «х2+у2=9» предикаттың ақиқаттық жиыны, центрі координаталар бас нүктесінде орналасқан және радиусы 3-ке тең шеңбер бойында орналасқан жазықтықтағы нақты сандардың қостар жиыны.
2) А (х): «
»-R гі бір өлшемді предикат.
А+= 
М1,…,Мn жиындарында берілген Р (х1,…,хn) n- орынды предикат:
I. ақиқат 
II. жалған 
Ø
III. орындалатын Р+ 
Ø
IV. жоққа шығарылатын 
Предикаттарға қолданылатын кванторлық операциялар
|
|
|
Предикаттарға пікірлерге қолданылатын (
) амалдардан басқа, олардан өзгеше басқа амалдар қолдануға болады.
Бұл – предикаттарға қолданылатын екі квантолық операциялар: жалпылау кванторы және табылу кванторы.
Бір орынды предикаттан пікір алу үшін, оның айнымалысының орнына предикаттың берілген облысынан бір мәнді қою керек.
Осылайша айналдырудың тағы бір тәсілі бар – бұл предикатқа жалпылау кванторымен және табылу кванторымен байланыстыру операциясын қолдану.
Бұл операциялардың әрқайсысы бір орынды предикатқа, берілген предикатқа тәуелді ақиқат немесе жалған мән қабылдайтын пікірді сәйкестендіреді (яғни бір орынды предикат нөлдік предикатқа айналады).
Анықтама: Жалпылау кванторымен байланыстыру операциясы деп, М жиынында анықталған әрбір бір орынды Р (х) предикатқа 
деп белгіленетін пікірді сәйкестендіретін ережені атайды. («барлық х үшін Р (х) орындалады» деп оқылады),
Бұл пікірлердің логикалық мәндері келесі формула бойынша анықталады:
Мысал. 
- ақиқат предикат
N сандар жиыныда –жоққа шығарылатын предикат
жалпылау кванторымен байланыстыратын операция, бірінші жағдайда ақиқат пікір, ал екінші жағдайда жалған пікірге айналады.
Қорытынды: егер берілген предикат М жиынының барлық элеметтеріне ақиқат болса, онда 
жалпылау кванторымен байланыстырғаннан:
р (х) оны ақиқат пікірге айналдырады.
Бұл жерде х айнымалысы «байланысты» болады, кәдімгі мағынадағы айнымалы болмайды.
Анықтама: Табылу кванторымен байланыстыру операциясы деп, М жиыныда анықталған әрбір бір орынды Р (х) предикатқа (
х)(Р(х)) деп белгіленетін пікірді сәйкестендіретін ережені атайды. («Р(х) орындалатындай, х табылады» деп оқылады), Бұл пікірлердің логикалық мәндері келесі формула бойынша анықталады:
|
|
|
Мысал: Р (х): «х=х+1» - жалған предикат
- орындалатын предикат
табылу кванторымен байланыстыратын операция, бірінші жағдайда жалған пікір, ал екінші жағдайда орындалатын пікірге айналады.
Қорытынды: егер берілген предикат М жиынының кем дегенде х М бір элементі үшін ақиқат болса, онда 
табылу кванторымен байланыстырғаннан: р (х) оны ақиқат пікірге айналдырады.
Бұл амалдардың ерекшеліктері.
а) 
логикалық операциялар бір немесе бірнеше предикаттарға жаңа предикаттар сәйкестендірді, ал квантолық операциялар бір орынды предикатқа пікірді сәйкестендіреді.
б) егер бірорынды Р(х) предикатМ={a1,…,аk}ақырлыжиындаберілсе, онда
пікірі
Р (а1) 
… Р (а k) конъюнкцияға эквивалентті
( х)(Р(х)) пікірі
Р (а1) 
… Р (а k) дизъюнкцияға эквивалентті
Әдебиет: 1,118-123 бет,17, 127-141 бет,3, 65-89 бет,5, 258 бет
6,122-141 бет
Бақылау сұрақтары:
1. Предикаттың анықтамасын беріңіз.
2. Предикаттардың қандай түрлерін білесіз?
3. Әртүрлі предикаттар арасындағы байланысты көрсетіңіз.
4. Предикаттың ақтқаттық жиыны қалай анықталады?
5. Қандай кванторлық операцияларды білесіз?
6. Осы операциялардың ерекшелігін көрсетіңіз.
7. Байланысты және байланысты емес айнымалылар түсінігін беріңіз.
16 тақырып
Алгоритмдер теориясының элементтері
Мақсаты:
1. Алгоритмдер түсінігін енгізу.
2. Қарапайым сандық функциялардың есептелуін қарастыру.
3. Тьюринг машинасының анықтамасын енгізу.
4. Тьюринг машинасын сөздерге қолданудағы дағды мен біліктілікті
қалыптастыру.
Жоспар:
1.Алгоритм түсінігі.
2.Есептелетін функциялар.
3. Тьюринг машинасы.
1 Алгоритм түсінігі
Алгоритмдер мысалдарын талдау арқылы, оларға тән жалпы қасиеттер мен ерекшеліктерді анықтаймыз.
1) Кез келген алгоритмде алғашқы берілгендер бар болады, олар арқылы анықталған ізделінді қорытындылар алынады.
2) Әрбір алгоритмді қолдану қадамдар деп аталатын, кейбір элементар іс-әрекеттер тізбегінен тұратын, дискретті тізбек арқылы жүзеге асады. Оларды қолдану процесі алгоритмдік процесс деп аталады, осылайша дискреттік қасиеттің ерекшеліктері пайда болады.
|
|
|
3) Алгоритмнің басты қасиетінің бірі оның көптік сипаты, яғни оны бастапқы берілгендердің өте көп класына қолдану мүмкіндігі, демеккез келген алгоритм арқылы көптеген мәселелерді шешуге болады, яғни біртипті есептерді шығаруға болады.
4) Алгоритмдер үшін қажетті шарт оның анықталғандығы болып табылады. (яғни, кім рындауына тәуелсіз, қорытынды кез келген жағдайда алынады)
Алгоритм – қандай-да бір берілген кластың барлық есептерін шығаруға арналған, анықталған ретте орындалатын нұсқаулар жүйесі.
«Алгоритм» термині ұлы ортаазиялық ғалым Мухаммед аль – Хорезм есімі арқылы шыққан (IX ғ).
|
|
|
