Mavjudlik kvantori. predikat to’plamda aniqlangan bo’lsin. Hech bo’lmaganda bitta uchun predikat chin va aks holda yolg’on qiymat qabul qiluvchi mulohaza ifodasini shaklda yozamiz. Bu mulohaza ga bog’liq emas va uni quyidagicha o’qish mumkin: “shunday mavjudki, ”, ya’ni
simvol mavjudlik kvantori deb ataladi. mulohazada o’zgaruvchi kvantori bilan bog’langan bo’ladi.
Misol: natural sonlar to’plamida predikat berilgan bo’lsin: “ – tub son” . Kvantorlardan foydalanib ushbu predikatdan quyidagi mulohazalarni hosil qilish mumkin: – “ Hamma natural sonlar tub sonlar bo’ladi ” ;
– “Shunday natural son mavjudki, u tub son bo’ladi” . Ravshanki, birinchi mulohazo yolg’on va ikkinchi mulohaza chindir.
Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari.
Biror alfavit berilgan bo'lsin. Bu alfavitdagi hamma so‘zlar to'plamini S bilan va S to‘plamning qism to'plamini M bilan belgilaymiz.
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‘plain deb ataladi.
2- t a ’ r i f . Agar M to‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo‘lsa, и holda M effektiv rekursiv sanaluvchi to ‘plam deb ataladi.
Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari.
1- t e o r e m a . Agar M va L effektiv rekursiv sanaluvchi to 'plamlar bo ‘Isa, и holda va ham effektiv rekursiv sanaluvchi to'plam bo'ladi.
M va L effektiv rekursiv sanaluvchi to'plamlar bo'lsin. Uholda, 2- ta’rifga asosan, ularning har biri uchun alohida algoritmmavjudki, ular orqali mos ravishda M va L dagi hamma elementlamisanab chiqish mumkin. va L to'plamlaming effektiv sanaluvchi algoritmi M va L to'plamlaming effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi.
Do'stlaringiz bilan baham: |
