Функии и формулы. Парадокс.

[ogcjm]

В теории булевых функций вводится понятие формулы над каким-то множеством функций.
Возник следующий вопрос: чем отличается функция и формула? Если рассматривать эти определения с точки зрения авторов учебников, то складывается такое впечателение что это одно и то же.
Так вот, есть ли в чём то отличие? Если да, то в чём? Если нет, то зачем вводится понятие формулы?

[Joker_vD]

Формула — набор знаков. Она задает функцию. Однако одна и та же функция может задаваться разными формулами. $x\oplus x$ и $(x\wedge x)\oplus x$ — это разные формулы, но задают они, конечно же, одну и ту же функцию.

[ogcjm]

В курсе мат.анализа так же могут быть функции, которые принимают одинаковые значения, но там почему-то не вводится понятие формулы.
Разве нельзя сказать, что это просто разные функции, значение которых совпадают?

[Joker_vD]

ogcjm в сообщении #626294 писал(а):

Разве нельзя сказать, что это просто разные функции, значение которых совпадают?

А чем они тогда разные? Функция определяется тем, что во что она переводит. Вот у вас есть функция, которая определена на $\{0,1\}$ и переводит $0$ в $0$, а $1$ в $0$. Вы можете записать ее как $f(x)\equiv0$, или как $f(x)=x\oplus x$, или как $f(x)=(x\wedge x)\oplus x$, или еще тысячей способов.

ogcjm в сообщении #626294 писал(а):

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

Откройте практически любой учебник алгебры на главе "Многочлены", и вы увидите описание той же проблемы: два разных многочлена могут задавать одну и ту же функцию, и канонический пример: $x$ и $x^2$ над полем $\{0,1\}$.

[Munin]

Функция $\textit{формула}\mapsto\textit{функция}$ однозначна, но не инъективна, и поэтому не взаимно-однозначна. Она может быть как сюръективна, так и не сюрьективна: например, в курсе булевых функций она сюрьективна, а в курсе матанализа - нет (пример - функция Дирихле). Определена она на грамматически-правильных формулах. В курсе матанализа понятие формулы не вводится просто потому, что это уведёт в дебри, которые в курсе матанализа не нужны. В других курсах понятие формулы часто вводится, где это нужно для задач курса.

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

Если несколько расширить понятие формулы, например, чтобы оно включало в себя ряды, по крайней мере те, которые можно записать на бумаге в конечном числе символов, то возникнет и такая ситуация, когда формула есть, а функции нет. Впрочем, чего это я мудрю: формула $\tfrac{1}{x-x}$ не соответствует никакой функции (и я был неправ выше про область определения).

[ogcjm]

Joker_vD в сообщении #626301 писал(а):

ogcjm в сообщении #626294 писал(а):

Разве нельзя сказать, что это просто разные функции, значение которых совпадают?

т.е. если я вас правильно понял, следующее утверждение не верно:
можно сказать, что функция — это «закон», по которому каждому элементу одного множества (называемому областью определения) ставится в соответствие некоторый элемент другого множества (называемого областью значений).

Например sin(x) - это не функция, а формула. Верно?

[Xaositect]

Если подходить формально, то функция - это набор пар (аргумент, значение).

В дискретной математике эти пары можно явно выписать, и еще в некоторых областях дискретной математики как раз очень важно различие между формулой и функцией: так как любую функцию можно реализовывать разными формулами, то возникают задачи типа: найти формулу минимальной сложности для функции $f$, доказать, что все формулы для $f$ сложные, оценить максимальную сложность самой маленькой формулы для некоторой функции и т.п. Поэтому это различие важно и его отмечают с самого начала.

Для матанализа же вышеупомянутый набор пар - это график функции. А с формулами тут такая беда, что не всякая функция реализуется формулой, потому что формулы мы составляем из символов и их счетно, а функций их даже больше континуума. Поэтому в матанализе изучают именно функции, а формулы являются только языком и на них внимания не заостряют.

[ogcjm]

Xaositect в сообщении #626389 писал(а):

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

Вы могли бы привести пример функции, которая не реализуется формулой?

[Xaositect]

ogcjm в сообщении #626395 писал(а):

Вы могли бы привести пример функции, которая не реализуется формулой?

Ну, например, возьмем какую-нибудь конструкцию неизмеримого множества и возьмем его характеристическую функцию.

-- Ср окт 03, 2012 12:30:09 --

Или вот еще пример, который тут часто на форуме любят обсуждать: нелинейная аддитивная функция $\mathbb{R}\to\mathbb{R}$.
topic4330.html

[_Ivana]

ТС, все вам правильно говорят:

Xaositect в сообщении #626389 писал(а):

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

Вот здесь topic62784.html я писал код, и мне нужна была функция, которая для каждого натурального аргумента возвращает ближайшую снизу степень тройки удвоенного модуля аргумента - ну так надо было для алгоритма. И в одном примере кода я написал её как

m = 1;
while m < 2*abs(int)/3
    m = m*3;
end

а в другом - эту же функцию другой формулой

m = 3^fix(log(2*abs(int))/log(3))

. Можете убедиться, что обе формулы задают одну и ту же функцию. А теперь возвращаемся к цитате - первая формула длиннее по визуальной записи кода, но вторая скорее всего более затратна по машинным ресурсам - это зависит от реализации логарифма и наличия аппаратного деления. Именно поэтому при написании кода для определенных платформ актуально искать компромисс между скоростью выполнения/требуемому объему ОЗУ/объему флеш под алгоритм - и все это в зависимости от аппаратных возможностей (есть аппаратное деление или нет, RISC или CISC архитектура и т.п.). Обобщая понятие функции от однозначного соответствия числового результата числовому аргументу на более общее понятие - набора реакции системы в зависимости от состояния и истории изменения управляющих параметров, мы приходим к обобщению формулы на понятие алгоритм. И, как сказано выше, можно ставить задачу оптимизации формулы/алгоритма при заданных критериях и ограничениях.

ЗЫ да даже банальные многочлены никто не считает как $y = a_3x^3 + a_2x^2 + a_1x + a_0$ - это 3 сложения, 3 умножения и 2 возведения в степень (которые можно расписать через умножения), а считают по схеме Горнера http://ru.wikipedia.org/wiki/%D0%A1%D1% ... 1%80%D0%B0

y = a_3
y = a_2 + y*x
y = a_1 + y*x
y = a_0 + y*x

- 3 сложения и 3 умножения.

[CptPwnage]

(Оффтоп)

Цитата:

Функция однозначна, но не инъективна, и поэтому не взаимно-однозначна. Она может быть как сюръективна, так и не сюрьективна: например, в курсе булевых функций она сюрьективна, а в курсе матанализа - нет (пример - функция Дирихле).

Функция Дирихле вроде бы задается формулой (что-то с пределом косинуса факториала кажется)..

[epros]

CptPwnage в сообщении #626446 писал(а):

Функция Дирихле вроде бы задается формулой

Словосочетание "задаётся формулой" не является вполне однозначным: необходимо уточнять формулой какого языка. В частности, функцию Дирихле можно задать формулой арифметики - т.е. с использованием кванторов. Тем не менее, алгоритма, разрешающего вопрос о рациональности любого действительного числа, быть не может.

[CptPwnage]

$D(x)=\lim_{n\to\infty}\lim_{m\to\infty}\cos^n(m! \pi x)$ имеется ввиду под формулой арифметики?

$D(x)$ функция Дирихле.

[epros]

CptPwnage в сообщении #626465 писал(а):

$\lim_{n\to\infty}\lim_{m\to\infty}\cos^n(m! \pi x)$ имеется ввиду под формулой арифметики?

Нет, конечно. Я имел в виду более простую вещь: Формулу, которой записывается утверждение о существовании таких целых чисел $m$ и $n$, что $x \times m = n$. Что касается вышезаписанного, то это, строго говоря, не формула, а просто некое выражение. Хотя может оно и эквивалентно функции Дирихле, не знаю.

-- Ср окт 03, 2012 17:58:03 --

CptPwnage в сообщении #626465 писал(а):

$D(x)=\lim_{n\to\infty}\lim_{m\to\infty}\cos^n(m! \pi x)$

Да, это уже ближе к понятию "формула". Остаётся расписать пределы (как утверждение о существовании того-то для любого этого-то и т.п.), а также расписать косинус (наверное, тоже как предел некоторого ряда). В общем, в итоге, наверное, получим формулу в языке некоторой теории, но явно гораздо более сложную, чем предложенный мной вариант.

Но интересен-то тот факт, что при всей выразимости формулой (некоторого языка) функция Дирихле остаётся невычислимой.

[Munin]

ogcjm в сообщении #626395 писал(а):

Вы могли бы привести пример функции, которая не реализуется формулой?

Можно доказать, что такая функция есть. Возьмём множество всех формул - его мощность не более чем счётная (если допускать формулы бесконечной длины, то мощность континуума). Возьмём множество функций, хотя бы, $[0,1]\to[0,1].$ Их уже 2 в степени континуум. Поскольку формула задаёт не более чем одну функцию, не все функции реализуются формулами.