Ma’ruza 24: Rekrusiv to‘plam. Rekrusiv sanaluvchi to‘plam. Post teoremasi

1-misol.

, , lar rekursiv to`plamlardir. Ularning harakteristik funksiyalari mos ravishda







1-teorema. Agar va lar rekursiv to`plamlar u holda lar ham rekursiv to`plamlardir.

Isbot: , mos ravishda larning harakteristik funksiyalari bo`lsin.

lar mos ravishda larning harakteristik funksiyasi bo`ladi.Bundan ko`rinib turibdiki lar primitiv rekursiv funksiyadir.

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 algaritmni topish kerak. Bu to`plamga ,,kirish muammosi” deyilib, bunday algaritmlarning mavjud bo`lishi to`plamning haraktetistik funksiyasining umumrekursiv bo`lishiga teng kuchlidir. Shuning uchun rekursiv to`plamlarni ,,kirish muammosi” algaritmik yechiluvchi to`plamlar deb qarash mumkin.

3-ta’rif. Bo`sh yoki biror umumrekursiv funksiya qiymatlarini to`plamidan iborat bo`lgan to`plam rekursiv sanab chiqiluvchi to`plam deyiladi. O`znavbatida mazkur funksiya to`plamni sanab chiquvchi funksiyasi deyiladi. (82-83 bet)

1. Toq sonlar to`plami, 3ga bo`lganda 2qoldiq beradigan natural sonlar:5,8,11,….,

barcha natural sonlar to`plami rekursiv sanab chiqiluvchi to`plamdir. Ularni mos ravishda

funksiyalar sanab chiqadi.

ham rekursiv sanab chiqiluvchi to`plamlardir ularni sanab chiquvchi funksiyalari mos ravishda

lardir.

Rekursiv sanab chiqiluvchi to`plam ta’rifidan ko`ramizki, rekursiv sanab chiqiluvchi to`plam, uni sanab chiquvchi umumrekursiv funksiyasi bo`lsa u holda bo`lib u sanoqlidir.Rekursiv sanab chiqiluvchi to`plamlarning birlashmasi va kesishmasi yana rekursiv sanab chiqiluvchi to`plam bo`ladi.

Masalan: va mos ravishda rekursiv sanab chiqiluvchi va to`plamlarning sanab chiquvchi funksiyasi bo`lsin.

funksiya ni sanab chiqadi.

Rekursiv sanab chiquvchi to`plamning to`ldiruvchisi rekursiv sanab chiqiluvchi to`plam bo`lmasligi mumkin. (82-83 bet)

Umumrekursiv funksiyalar sinfi sanoqli to`plam bo`lganligi, har bir umumrekursiv funksiya esa faqat bitta to`plamni sanab chiqa olishi sababli rekursiv sanab chiqiluvchi to`plamlar sinfi sanoqlidir. Ma’lumki barcha natural sonlar to`plamining barcha to`plamostilari sinfi sanoqsiz to`plamdir. Bu esa rekursiv sanab chiqilmaydigan to`plamlar mavjud deyishga asos bo`ladi.