Дискрет анал

2. Приметив – рекурсив ва қисмий – рекурсив функциялар.
1-тариф. Х ва У бўш бўлмаган тўпламлар бўлсин. Агар Х тўпламнинг баъзи элементларига У тўпламнинг бир қийматли аниқланган элементлари мос қўйилган бўлса, у холда Х тўпламда қисмий функция берилган дейилади. Бунда Х тўпламнинг У тўпламда образи (акси) мавжуд бўлган элементлари тўпламостиси аниқланган қисмий функциясининг аниқланиш сохаси У тўпламнинг Х прообрази (асли)мавжуд бўлган барча элементлари тўпламостиси қисмий функциянинг қийматлари тўплами дейилади.
2- таьриф. Базис функцияларга суперпозиция ва примитив рекурсия операторларини чекли марта қўллаб хосил қилинадиган хар қандай функция приметив рекурсив функция дейилади.
, ва базис функцияларга суперпозиция, примитив рекурсия ва минимизация операторларини чекли сонда қўлланиши натижасида хосил қилиниши мумкин бўлган қисмий рекурсив функция дейилади.


3. Алгоритмик ечилувчи ва ечилмайдиган муаммолар.
Теорема . Предикатлар хисобининг барча умумкийматли формулалари тўплами Т рекурсив эмас, предикатлар хисобининг ихтиёрий А формуласи умумқийматли ёки умумкийматли эмаслигини аниқлаб берадиган алгоритм мавжуд эмас.