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

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

    Реферат

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

    студента группы ТК

    четвертого курса

    Польщи М.В.

    Научный руководитель: профессор Лисовик Леонид Петрович

    Определение. Функция называется элементарной по Кальмару, если ее можно получить й из функций

    x+y,

    x-y,

    а также конечного применения операций

    суммирования и мультиплицирования.

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

    Класс функций, получаемый из функций

    x+y,

    x-y,

    а также конечного применения операций

    суммирования и мультиплицирования.

    Класс функций, получаемый из функций

    x-y,

    а также конечного применения операции суммирования.

    Класс функций, получаемый из функций

    x-y,

    x*y,

    а также конечного применения операции ограниченной минимизации.

    Класс функций, получаемый из функций

    x-y,

    а также конечного применения операции ограниченной рекурсии.

    Класс функций, получаемый из функций

    x-y,

    а также конечного применения операции мультиплицирования.

    Доказательство будем проводить по следующей схеме:

    Докажем, что

    (для этого выразим 2

    через функции

    Докажем, что

    (для этого выразим

    и операцию ограниченной минимизации через функции

    Пусть

    тогда

    Докажем, что

    (для этого выразим

    и операцию ограниченной рекурсии через функции

    Выразим операцию ограниченной рекурсии на основании следующего свойства функции Геделя.

    Пусть

    тогда

    Отношение, примененное в операция конечной минимизации, является элементарным по Кальмару.

    Докажем, что

    (для этого выразим операции суммирования и мультиплицирования через функции

    Выразим м3ультиплицирование через ограниченную рекурсию.

    Где

    x,y)-

    к-ступенчатая функция.

    Выразим суммирование через ограниченную рекурсию.

    Докажем, что

    (для этого выразим

    через функции

    Докажем, что

    (для этого выразим 2

    и операцию ограниченной минимизации выразим через функции

    Пусть

    тогда

    Эквивалентность классов доказана.

    Язык: Русский

    Скачиваний: 265

    Формат: Microsoft Word

    Размер файла: 15 Кб

    Автор:

    Скачать работу...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены