5-teorema.Har qanday cheksiz rekursiv sanaluvchi to`plam cheksiz rekursiv qism to`plamiga ega.
Isbot.cheksiz rekursiv sanaluvchi to`plam bo`lsin.
sxema yordamida berilgan funksiyani qaraylik. Bu funksiyaning qiymatlari to`plami qandaydir B to`plamdan iborat bo`lib, uni o`sib borish tartibida sanab chiqadi. Oldingi teoremaga asosan B cheksiz va rekursiv to`plamdir. ekanligi funksiyaning aniqlanishidan kelib chiqadi.
Asosiy darsliklar va o’quv qo’llanmalar
1. Kenneth H. Rosen, Discrete mathematics and its applications, 7-edition, The McGraw-Hill Companies, 2012. (888-988 betlar)
Rodjers H. Teoriya rekursivnih funktsiy I effektivnaya vichislimost. Moskva.
,,Mir”-1972.
Lavrov I.A., Maksimova L.L. Zadachi po teorii mnojestv, matematicheskoy logike i teorii algoritmov. M. «Nauka» 1995
G L O S S A R I Y
Rekursiv to`plamlar- algoritmlar nazariyasida asosiy ro`llardan birini o`ynaydi.natural sonning to`plamga kirishi yoki kirmasligi chekli qadamda ko`rsatib beradigan, ya’ni to`plamning harakteristik funksiyasi qiymatlarini hisoblaydigan algoritmni topish kerak. Bu to`plamga ,,kirish muammosi” deyilib, bunday algoritmlarning mavjud bo`lishi to`plamning haraktetistik funksiyasining umumrekursiv bo`lishiga teng kuchlidir. Shuning uchun rekursiv to`plamlarni ,,kirish muammosi” algoritmik yechiluvchi to`plamlar deb qarash mumkin.
Rekursiv sanab chiqiluvchi to`plam- bo`sh to`plam yoki biror umumrekursiv funksiyaning qiymatlarini to`plamidan iborat bo`lgan to`plamdir. O`znavbatida mazkur funksiya to`plamni sanab chiquvchi funksiyas deyiladi.
NAZORAT SAVOLLARI
Primitiv rekursiv funksiya.
Qismiy rekursiv funksiya.
Umumrekursiv funksiya.
Rekursiv funksiyalar.
Rekursiv funksiyalar xaqida asosiy teoremalar
Rekursiv to‘plamlar.
Rekursiv sanaluvchi to‘plamlar.
Post teoremasi.
Post teoremasining natijalari.
Rekursiv invariantlik.
Do'stlaringiz bilan baham: |
