Простейшие функции. Операция суперпозиции

Содержание

Слайд 2

Алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f
Такие функции

Алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f Такие функции называются вычислимыми
называются вычислимыми

Слайд 3

Интуитивное понятие вычислимой функции заменим на точное понятие частично рекурсивной функции

Интуитивное понятие вычислимой функции заменим на точное понятие частично рекурсивной функции

Слайд 4

Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна

Простейшие функции

Простейшими функциями называются следующие

Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна Простейшие функции Простейшими функциями
арифметические функции:
1) Нулевая функция
Оn(x1, x2, … , xn) = 0 O(x) = 0
2) Функция следования
S(x) = x + 1, x ∈ N
3) Функция проецирования (выбора)
Im n(x1, x2, … , xn) = xm

Слайд 5

Замечание
Вычислимость функции проецирования обеспечивается нашей способностью найти в строке
(x1, x2,

Замечание Вычислимость функции проецирования обеспечивается нашей способностью найти в строке (x1, x2,
… , xn)
место с номером m и указать число на этом месте

Слайд 6

Пусть заданы арифметические функции:
f1(x1, x2, … , xn), f2(x1, x2, … ,

Пусть заданы арифметические функции: f1(x1, x2, … , xn), f2(x1, x2, …
xn), …, fm(x1, x2, … , xn),
ϕ(y1, y2, … , ym)

Операция подстановки (суперпозиции)

Говорят, что функция ψ(x1, x2, … , xn) получена из функций ϕ и f1, f2, …, fm операцией подстановки (суперпозиции), если:

Обозначение:

Слайд 7

Пример 1

Операция подстановки (суперпозиции)

Пример 1 Операция подстановки (суперпозиции)

Слайд 8

Пример 1

Операция подстановки (суперпозиции)

Пример 1 Операция подстановки (суперпозиции)

Слайд 9

Правильное применение суперпозиции:
необходимо соблюдать требования к набору аргументов каждой функции

Операция подстановки (суперпозиции)

Правильное применение суперпозиции: необходимо соблюдать требования к набору аргументов каждой функции Операция подстановки (суперпозиции)

Слайд 10

Пример 1

Операция подстановки (суперпозиции)

Преобразуем функции f1 и f2 так, чтобы они удовлетворяли

Пример 1 Операция подстановки (суперпозиции) Преобразуем функции f1 и f2 так, чтобы
требованиям к аргументам для применения суперпозиции

Корректно

Слайд 11

Замечание
Такое применение функции проецирования предложил К.Гёдель (1934)
Все функции fi, i = 1,…m

Замечание Такое применение функции проецирования предложил К.Гёдель (1934) Все функции fi, i
зависят от n переменных, а функция ϕ имеет m переменных (по количеству функций fi)
Результат подстановки, функция ψ зависит от n переменных

Слайд 12

Добиться выполнение условия на количество аргументов у функций можно введением фиктивных переменных

Добиться выполнение условия на количество аргументов у функций можно введением фиктивных переменных
и применения функции проецирования
Im n
Имя файла: Простейшие-функции.-Операция-суперпозиции.pptx
Количество просмотров: 57
Количество скачиваний: 0