Доклад

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

Работа добавлена на сайт bukvasha.net: 2015-10-25

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 3.4.2025



Реферат

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

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

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

Польщи М.В.

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


Определение. Функция называется элементарной по Кальмару, если ее можно получить й из функций s1, Inm, x+y, x-y, S, а также конечного применения операций суммирования и мультиплицирования.

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

L1 ­ Класс функций, получаемый из функций s1, Inm, x+y, x-y, S, а также конечного применения операций суммирования и мультиплицирования.

L
2
­ Класс функций, получаемый из функций s1, Inm, x-y, 2x ,S, а также конечного применения операции суммирования.

L
3
­ Класс функций, получаемый из функций s1, Inm, x-y, x*y, 2x ,S, а также конечного применения операции ограниченной минимизации.

L
4
­ Класс функций, получаемый из функций s1, Inm, x-y, x+y 2x ,S, а также конечного применения операции ограниченной рекурсии.

L
5
­ Класс функций, получаемый из функций s1, Inm, x-y, x*y, S, а также конечного применения операции мультиплицирования.

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

1.
L
1
L
2
L
3
L
4
L
1


2.
L
1
L
5


3.
L
5
L
3


Докажем, что L
1
L
2
(для этого выразим 2x через функции L
1
)



Докажем, что L
2
L
3
(для этого выразим x*y и операцию ограниченной минимизации через функции L
2
)



Пусть

 тогда

 

Докажем, что L3L4 (для этого выразим x+y и операцию ограниченной рекурсии через функции L
3
)



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



Пусть

 тогда



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

Докажем, что L
4
L
1
(для этого выразим операции суммирования и мультиплицирования через функции L
4
)

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



Где (x,y)-к-ступенчатая функция.

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



Докажем, что L
1
L
5
(для этого выразим x*y через функции L
5
)



Докажем, что L
5
L
3
(для этого выразим 2x и операцию ограниченной минимизации выразим через функции L
5
)



Пусть

 тогда



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

1. Реферат Общие условия производства по делам о нарушении таможенных правил и их рассмотрения
2. Курсовая Соціально-економічний розвиток Західно-Українських земель у складі Австро-Угорщини у ХІХ столітті
3. Курсовая на тему Технологія використання психолого-педагогічної діагностики в соціально-педагогічній роботі
4. Статья Как повысить устойчивость к болезням
5. Контрольная работа на тему Механизм административно правового регулирования 2
6. Курсовая Проблемы привлечения и использования иностранных инвестиций в Казахстане
7. Реферат на тему Alcohol Problems More Likely For Young Drinkers
8. Реферат Особенности автоматизированные системы бугталтерского учета
9. Реферат на тему The Mosquito Analysis Essay Research Paper Analysis
10. Контрольная работа Оптимизация размещения товара на складе