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

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

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

Реферат


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


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


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


Польщи М.В.



 


 


 


 


 


 


 


 


 


 

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



Определение. Функция называется элементарной по Кальмару, если ее можно получить й из функций 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. L1L2L3L4L1


2. L1L5


3. L5L3


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


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


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


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


Пусть


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


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


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


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


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


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


Пусть


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


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


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


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


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


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


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


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


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


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


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


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


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


Пусть


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


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


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


Скачиваний: 1
Просмотров: 0
Скачать реферат Заказать реферат