Teng kuchli formulalar va asosiy teng kuchliliklar Ta’rif

Daraxtlar, ularni tadbiqlari.
Siklga ega bo‘lmagan orientirlanmagan bog'lamli graf daraxt deb ataladi. Ta’rifga
ko‘ra daraxt sirtmoqlar va karrali qirralarga ega emas. Siklga ega bo‘lmagan orientirlanmagan graf o‘rmon (asiklik graf) deb ataladi.
Quyidagi shaklda bog`lamli komponentli soni beshga teng bo`lgan graf tasvirlangan bo‘lib, u o‘rmondir. Bu grafdagi bog‘lamli komponentlaming har biri daraxtdir.
Q uyidagi shaklda esa to`rtta uchga ega bir biriga izomorf bo`lmagan barcha (ular bor yo`g`i ikkita)
daraxtlarning geometrik ifodalanishi ko`rsatilgan.
Beshta uchga ega bir-biriga izomorf bo‘lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko‘rsatish qiyin emas.
Dasturlashda xotirani va vaqtni tejash maqsadida mantiq algebrasi funksiyalari bilam ishlaganda, ularni “tabiiy” (massivlarda) ifodalamasdan,mantiqiy amallarni bajarishga maxsus yo‘naltirilgan ko‘rinishda ifodalash samaraliroq hisoblanadi. Buning uchun n o‘zgaruvchili Bul funksiyasi rostlik jadvalini n+1 balandlikdagi to‘liq binar daraxt ko‘rinishida ifodalash mumkin. Daraxt yaruslari (qavatlari) o‘zgaruvchilarga mos keladi, daraxt shoxlari esa o‘zgaruvchilar qiymatlariga mos keladi. Har bir mulohaza o’zgaruvchisidan ikkita shih chiqib, chap shoxga – 0, o‘ng shoxga esa – 1 qiymat mos qo‘yiladi. Daraxt yaproqlari – oxirgi yarusda esa daraxt ildizidan shu yaproqgacha bo‘lgan yo‘lga mos kortejdagi funksiya qiymatlari mos qo‘yiladi. Bunday daraxt yechimlar daraxti yoki semantik daraxt deyiladi. Buni quyidagicha misolda ko‘rib chiqamiz. F(A,B,C) funksiya quyidagicha rostlik jadvali bilan.berilgan,bo‘lsin:

Rekursiv va rekursiv sanaluvchi to‘plamlar

Biror alfavit berilgan bo‘lsin. Bu alfavitdagi hamma so‘zlar to‘plamini S bilan va S
to‘plamning qism to‘plamini M bilan belgilaymiz.

1. 
   t a ’ r i f . Agar x so‘zning M to‘plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo‘lsa, u holda M rekursiv to‘plam deb ataladi.
   
2.