2 Есептелетін функциялар
натурал сандар жиынында берілген немесе оның ішкі жиыныда берілген және N жиынынан мәндер қабылдайтын, бір аргументке немесе бірнеше аргументке тәуелді функциясын қарастырамыз.
1 анықтама. функциясы есептелімді деп аталады, егер оның барлық аргументтерінің мәндерін есептейтін және тоқтаусыз жұмыс жасайтын алгоритм табылса.
болсын.
2 анықтама. Егер кез келген элемент берілген М жиынына тиісті ме, жоқ па екенін анықтайтын алгоритм тбар болса, онда М жиыны шешілімді жиын деп аталады.
Егер функциясы М жиыныда берілсе және {0,1} екі элементті жиыннан мәндер қабылдаса, онда функциясы М жиынының сипаттамалық функциясы деп аталады және келесі түрде анықталады:
М жиыны шешілімді ó егер оның сипаттамалық функциясы есептелімді болса.
3 анықтама. М N жиыны саналамды (рекурсивті немесе алгоритмді) деп аталады, егер М жиыны немесе бос жиын болса немесе оның мәндер жиыны қандай да бір есептелімді функция болса, басқаша айтқанда оның барлық элементтерін тізбектеп табатын алгоритм табылса.
Мысал. М={1,4,9,…..} натурал сандардың квадраттары жиынын қарастырамыз. Ол 1,2,3…. сандарын біртіндеп квадраттау арқылы алынады, яғни саналымды жиын.
Басқаша айтқанда, М= жиыны есептелімді функцияның мәндер жиыны болып табылады.
Бұл жиын шешілімді де болады: қандай да бір сан берілген жиынға тиісті ме жоқ па тексеру үшін, оны жай көбейткіштерге жіктеу керек.
Кез келген шешілімді жиын саналымды, бірақ кері тұжырым дұрыс емес.
Достарыңызбен бөлісу: |
