Читайте также:
|
Пусть задана функция 
и функции 
.
Определение. Говорят, что функция 
получена из этих функций с применением операции подстановки, если выполняется следующее равенство:
= 
и обозначается 
, где S означает операции подстановки.
Пример 1. Пусть 
и
Тогда по определению подстановки получим, что:
Пример 2. Пусть и
Тогда по определению операции подстановки получим, что:
Как видим, это не является результатом операции подстановки, так как по условию задачи 
являются трехместными функциями, а получаемая функция f - четырехместная, что противоречит определению
В теории множеств, теории алгоритмов и математической логике, перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество [1]) — множество конструктивных объектов (например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым [2]. Всякое перечислимое множество являетсяарифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню 
арифметической иерархии (англ.), а корекурсивно перечислимые — уровню 
Всякое разрешимое множество является перечислимым. Перечислимое множество является разрешимым, тогда и только тогда, когда его дополнение также перечислимо. Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножествоперечислимого множества может не быть перечислимым (и даже может не быть арифметическим).
Совокупность всех перечислимых подмножеств 
является счётным множеством, а совокупность всех неперечислимых подмножеств — несчётным.
Дата добавления: 2015-10-24; просмотров: 71 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Цели анализа. | | | Вычислимые функции и разрешимые множества. |