Математика

Эквивалентность пяти классов функций элементарных по Кальмару


                                   Реферат

        Эквивалентность пяти классов функций элементарных по Кальмару



                                                   студента группы ТК
                                                   четвертого курса
                                                   Польщи М.В.



    Научный руководитель: профессор Лисовик Леонид Петрович
Определение. Функция называется элементарной  по  Кальмару,  если  ее  можно
получить й из функций s1, Inm, x+y, x-y, S,  а  также  конечного  применения
операций суммирования и мультиплицирования.
    Определим пять классов функций, элементарных по Кальмару.
    L1  Класс функций, получаемый из функций s1, Inm, x+y, x-y, S, а  также
конечного применения операций суммирования и мультиплицирования.
    L2  Класс функций, получаемый из функций s1, Inm, x-y, 2x ,S,  а  также
конечного применения операции суммирования.
    L3  Класс функций, получаемый из функций s1, Inm, x-y, x*y,  2x  ,S,  а
также конечного применения операции ограниченной минимизации.
    L4  Класс функций, получаемый из функций s1, Inm, x-y,  x+y  2x  ,S,  а
также конечного применения операции ограниченной рекурсии.
    L5  Класс функций, получаемый из функций s1, Inm, x-y, x*y, S, а  также
конечного применения операции мультиплицирования.
    Доказательство будем проводить по следующей схеме:
    1. L1КL2КL3КL4КL1
    2. L1КL5
    3. L5КL3
    Докажем, что L1КL2 (для этого выразим 2x через функции L1 )
    [pic]
    Докажем, что L2КL3 (для  этого  выразим  x*y  и  операцию  ограниченной
минимизации через функции L2 )
    [pic]
    Пусть
    [pic] тогда
    [pic] [pic]
    Докажем, что L3КL4 (для  этого  выразим  x+y  и  операцию  ограниченной
рекурсии через функции L3 )
    [pic]
    Выразим операцию ограниченной рекурсии на основании следующего свойства
функции Геделя.
    [pic]
    Пусть
    [pic] тогда
    [pic]
    Отношение,  примененное  в  операция  конечной  минимизации,   является
элементарным по Кальмару.
    Докажем,  что  L4КL1  (для  этого  выразим  операции   суммирования   и
мультиплицирования через функции L4)
    Выразим м3ультиплицирование через ограниченную рекурсию.
    [pic]
    Где y(x,y)-к-ступенчатая функция.
    Выразим суммирование через ограниченную рекурсию.
    [pic]
    Докажем, что L1КL5 (для этого выразим x*y через функции L5 )
    [pic]
    Докажем, что L5КL3  (для  этого  выразим  2x  и  операцию  ограниченной
минимизации выразим через функции L5 )
    [pic]
    Пусть
    [pic] тогда
    [pic]
    Эквивалентность классов доказана.


смотреть на рефераты похожие на "Эквивалентность пяти классов функций элементарных по Кальмару "