Rekursiv va

Download 97.24 Kb.

bet	1/2
Sana	31.01.2023
Hajmi	97.24 Kb.
	#1145814

1 2

Bog'liq
22-Mavzu. REKURSIV VA REKURSIV SANALUVCHI TO`PLAMLAR

REKURSIV VA REKURSIV SANALUVCHI TO`PLAMLAR Reja:

1. Rekursiv to`plamlar.
2. Rekursiv sanaluvchi to`plamlar.
3. Post teoremasi.

Rekursiv va rekursiv sanaluvchi to`plamlar va ularning xossalari
A naturalsonlarto`plami N={0,1,2,…..n,…}ning qism to`plami bo`lsin.

₁_-_ta’rif. ^f^u^nk^si^y^a^A^to^`^p^l^a^mⁿⁱⁿ^g^har^a^k^t^erⁱ^s^ti^k^f^uⁿ^k^sⁱ^y^a^sⁱ^d^e^y^il^a^di^.² ⁽⁸²^-⁸³^b^e^t⁾

Ushbu tarifdan to`plamning harakteristik funksiyasi hamma yerda aniqlangan funksiya ekanligini ko`ramiz.
2-ta’rif .Harakteristik funksiyasi umumrekursiv bo`lgan to`plam rekursiv to`plam deyiladi.
Xususan harakteristik funksiyasi primitiv rekursiv bo`lgan to`plam primitiv rekursiv to`plam deyiladi.
1-misol.
A  , A  N , A  N₂lar rekursiv to`plamlardir. Ularning harakteristik funksiyalari mos ravishda

__x_ 0

_N_x_ 1

2
_N rest _x,2_

1-teorema. Agar A va B lar rekursiv to`plamlar u holda A  B, A  B va A _l_ar_h_am_rek_u_r_s_i_v_t_o_`_pl_a_m_l_ar_d_i_r.
Isbot:  _A( x) , _B( x) mos ravishda A va B larning harakteristik funksiyalari bo’lsin.

_Bundan ko`rinib turibdiki  _A__B(x),  _A__B(x),  _A(x) lar primitiv rekursiv _f_u_nk_si_y_a_d_i_r

Rekursiv to`plamlar algoritmlar nazariyasida asosiy ro`llardan birini o`ynaydi. x natural sonning A to`plamga kirishi yoki kirmasligi chekli qadamda ko`rsatib beradigan, ya‘ni A to`plamning harakteristik funksiyasi qiymatlarini hisoblaydigan algaritmni topish kerak. Bu A to`plamga ,,kirish muammosi‖ deyilib, bunday algaritmlarning mavjud bo`lishi A 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 ^m^az^ku^r^f^u^nk^si^y^{a t}^o^`^p^l^a^mⁿⁱ^s^aⁿ^ab^c^hⁱ^qu^v^c^hⁱ^f^uⁿ^k^sⁱ^y^a^sⁱ^de^yⁱ^l^a^dⁱ^.² ⁽⁸²^-⁸³^bet)

1-misol.

1.Toq sonlar to`plami, 3ga bo`lganda 2qoldiq beradigan natural

sonlar: 5,8,11,…., _b_ar_c_h_a_n_a_t_u_r_a_l_s_o_n_l_ar_to_`_pl_a_m_i_re_k_u_r_s_i_v_s_a_n_a_b_c_h_i_qi_l_u_v_c_h_i_t_o_`_pl_a_m_di_r._U_l_a_r_n_i_m_o_sravishda f (x)  2x 1 f (x)  3x  2, ^f⁽^x⁾^^xfunksiyalar sanab chiqadi

^E₁^⁰^,²^,⁴^,⁶^,^..^.
^E₂^_²^,³^,⁵^,⁷^,¹¹^,^.^._

^E3^_²⁰^,²¹^,²²^,²³^,^..^._^_¹^,²^,⁴^,⁸^,^..²ⁿ^.^._

ham rekursiv sanab chiqiluvchi to`plamlardir ularni sanab chiquvchi funksiyalari mos ravishda
(x)  2x,
(x)  Px
(x)  2^x_l_a_r_di_r.

_Re_k_u_r_si_v_s_a_n_ab_c_h_i_q_i_l_u_v_c_h_i_to_`_p_l_am_t_a_‘_r_i_f_id_a_n_k_o_`ra_m_i_z_k_i_,_A_r_e_k_u_r_si_v_s_a_n_a_{b c}_h_iq_i_lu_v_c_h_i_t_o_`_p_l_a_m_, _u_n_i_s_a_n_a_b_c_h_i_qu_v_c_h_i_u_m_u_m_re_ku_r_s_i_v_f_u_nk_si_y_a_s_i_bo_`_l_s_a_uholda bo`lib u sanoqlidir. Rekursiv sanab chiqiluvchi

to`plamlarning birlashmasi va kesishmasi yana rekursiv sanab chiqiluvchi to`plam
_bo_`_l_a_d_i_.

_Ma_s_a_l_a_n_:_f(x)_v_a_g(x)_m_o_s_r_a_v_i_sh_d_a_r_e_k_u_r_s_i_v_s_a_n_a_b_c_hi_q_i_l_u_v_c_h_i_A_v_a_B_to_`_p_l_a_m_l_ar_n_in_g_s_a_n_a_b_c_h_iq_u_v_c_h_i_f_u_n_k_s_i_y_a_s_i_bo_`_l_s_i_n_.

_f_u_nk_si_y_a _n_i_s_a_n_ab_c_hi_q_a_di_.

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

Umumrekursiv funksiyalar sinfi ^F_u_._rsanoqli 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.
2-teorema.Agar A rekursiv to`plam bo`lsa u holda u rekursiv sanaluvchi ^to^`^p^l^am^b^o^`^l^a^di^.² ⁽⁸²^-^bet)

Isbot. Mumkin bo`lgan 3ta holni qaraymiz.

_a)A  _b_o_`_l_s_a_t_e_o_r_e_m_{a o`}_r_i_n_l_i_e_k_a_n_i_m_a_‘_lu_m

_b₎^A^_^a₀^,^a₁^,^..^.^a_k__c_h_e_k_l_i_t_o_`_p_l_am_bo_`_l_s_in_._U_h_o_l_d_a_b_u_to_`_p_l_a_m_n_i_s_a_n_a_b_c_hi_q_u_v_c_h_i

funksiya

v) A cheksiz to`plam  _A( x) ning harakteristik funksiyasi bo`lsin, u holda

f (0)   y _ _A( y)_ 1
f ( x  1)   y _ _A( y)  1  ( y f ( x))_

yordamida aniqlangan f ( x) funksiya A to`plamning sanab chiquvchi funksiyasidir.

₂_-_m_is_o_l_.^K^^x^^_x⁽^x⁾^^y^aqⁱⁿ^l^a^s^hu^vc^hⁱ ^-re^k^u^r^sⁱ^v^s^aⁿ^a^l^uv^c^hⁱ^t^o^`^p^l^am^l^e^kⁱⁿ^r^e^k^u^r^si^v

to`plam emas.

3-misol. ^M^_^x^^_x^^u^m^u^m^r^ek^u^rsⁱ^v__-re_k_u_r_s_i_v_s_a_n_a_l_uv_c_h_i_t_o_`_p_l_am_e_m_a_s_._₂_₍₈₃_{- b}_e_t)

3-teorema. (Post). A rekursiv to`plam bo`lishi uchun A ning o`zi va

to`ldiruvchisi ham rekursiv sanaluvchi bo`lishi zarur va yetarli. _2_(82- bet)
A  N \ A

Isbot. Zarurligi: 2-teoremaga ko`ra A rekursiv to`plam bo`lsa A rekursiv sanab chiqiluvchi to`plam bo`ladi. 1-teoremaga ko`ra esa A ham rekursiv to`plam va demak A rekursiv sanaluvchi to`plam bo`ladi.

_Y_e_t_ar_li_l_i_g_i:^A^v^a_l_ar_re_k_u_r_s_i_v_s_a_n_a_lu_v_c_h_i_t_o_`_p_l_a_m_l_ar_bo_`_l_s_i_n_.A  _b_o_`_ls_a

_y_e_t_ar_l_i_l_i_g_i_r_a_v_s_h_a_n_d_i_r._A_g_ar ^v^a_bo_`_l_s_a_u_ho_l_d_a^A^v^a_to_`_p_l_a_m_l_ar_m_o_sravishda qandaydir f(x) va g(x) umumrekursiv funksiyalar qiymatlari to`plamidan _i_b_o_r_a_t_b_o_`_l_a_di_.
_Ushbu algoritmik jarayonni qaraylik. ^a_n_a_t_u_r_a_l_so_n_b_o_`_l_s_a,_uA _to_`_pl_a_m_g_a_k_i_ra_d_i_m_i_y_ok_i_g_a_k_i_r_a_di_m_i_d_e_g_a_n_m_a_s_a_l_a_n_i_h_al_e_t_i_s_h_u_c_hu_nf (0), g(0), f (1), g(1),.... f (n), g(n),... _s_o_n_l_a_r_n_i_k_e_t_m_a_-_k_et_q_a_rab_c_h_i_q_a_m_i_z.

Agar a f(x) funksiyaning qiymati bo`lsa, u holda , _a_g_ar_{a g(x)}_f_u_nk_si_y_a_n_in_g_qi_y_m_a_t_i_bo_`_l_s_a

_b_o_`_l_i_b_,A  A  N
_bo_`_l_g_a_n_i_u_c_h_u_n^a

_a_l_b_a_t_t_a
f (x) yoki g(x)
_ni_n_g_q_i_y_m_a_tl_ar_i_d_an_ib_o_r_a_t_bo_`_l_a_d_i_._B_o_s_h_q_a_c_h_a_a_y_tg_a_n_d_aA

to`plamning harakteristik funksiyasi to`liq aniqlangan umumrekursiv funksiya, ^A

_n_in_g_o`_z_i_e_s_{a r}_e_k_u_r_s_i_v_t_o_`_p_l_am_b_o_`_l_a_di_.

₄_-_t_a_’_r_i_f._S_h_un_d_ay
f ( x)
_u_m_u_m_re_ku_r_s_i_v_f_u_n_k_si_y_a_m_a_v_j_u_d_b_o_`_l_s_a_k_i_,_A_t_o_`_p_l_am

f ( x)
_n_i_n_g_q_i_y_m_a_tl_ar_t_o_`_p_l_a_m_id_an_i_bo_r_at_b_o_`_l_i_b
f ( x)
_o_`_s_u_v_c_h_i_f_un_k_s_i_y_a_bo_`_l_s_a_u_h_o_l_d_a

A o`sib borish tartibida rekursiv sanaluvchi to`plam deyiladi.

₄_-_m_is_o_l_.₁_,3_,₅_,7_,₉_,_…_t_o_q_s_o_n_l_ar_t_o_`_pl_a_m_i_o_`_s_i_b_b_o_r_i_s_h_t_a_r_t_i_b_i_d_a_r_e_k_u_r_si_v

sanaluvchi to`plamlardir. f (x)  2x 1

_qi_y_m_a_tl_ari_t_o_`_p_l_a_m_id_a_n_i_b_o_ra_td_i_r.
o`suvchi umumrekursiv funksiyaning

Download 97.24 Kb.

Do'stlaringiz bilan baham:

1 2