Итерированная бинарная операция

В математике итерированная бинарная операция — это расширение бинарной операции над множеством S до функции на конечных последовательностях элементов S посредством многократного применения. Общие примеры включают расширение операции сложения до операции суммирования и расширение операции умножения до операции произведения . Другие операции, например теоретико-множественные операции объединение и пересечение , также часто повторяются , но итерациям не присваиваются отдельные имена. В печати сумма и произведение обозначаются специальными символами; но другие итерированные операторы часто обозначаются более крупными вариантами символа обычного бинарного оператора. Таким образом, итерации четырех упомянутых выше операций обозначаются

$\sum ,\ \prod ,\ \bigcup ,$ и $\bigcap$, соответственно.

В более общем смысле итерация бинарной функции обычно обозначается косой чертой: итерация $f$ над последовательностью $(a_{1},a_{2}\ldots ,a_{n})$ обозначается $f/(a_{1},a_{2}\ldots ,a_{n})$, следуя обозначению сокращения в формализме Берда – Мертенса .

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

Определение

Обозначим через a _{j , k} , j ≥ 0 и k ≥ j , конечную последовательность длины k − j элементов S с членами ( a _i ) для j ≤ i < k . Обратите внимание: если k = j , последовательность пуста.

Для f : S × S определим новую функцию F _l на конечных непустых последовательностях элементов S , где

$$F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1.\end{cases}}$$

Аналогично определите

$$F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1.\end{cases}}$$

Если f имеет уникальный левый идентификатор e , определение F _l можно изменить для работы с пустыми последовательностями, задав значение F _l для пустой последовательности равным e (предыдущий базовый случай для последовательностей длины 1 становится излишним). Аналогично, F _r можно модифицировать для работы с пустыми последовательностями, если f имеет уникальную правую идентичность.

Если f ассоциативен, то F _l равен F _r , и мы можем просто написать F . Более того, если единичный элемент e существует, то он уникален (см. Моноид ).

Если f коммутативен , и ассоциативен, то F может работать с любым непустым конечным мультимножеством применяя его к произвольному перечислению мультимножества. Если f, кроме того, имеет единичный элемент e , то он определяется как значение F в пустом мультимножестве. Если f идемпотентно, то приведенные выше определения можно распространить на конечные множества .

Если S также оснащен метрикой или , в более общем смысле, , так топологией Хаусдорфа что понятие предела последовательности определено в S , то бесконечная итерация счетной последовательности в S определяется точно тогда, когда соответствующая последовательность конечных итерациях сходится. Таким образом, например, если a ₀ , a ₁ , a ₂ , a ₃ , … является бесконечной последовательностью действительных чисел , то бесконечное произведение  ${\textstyle \prod _{i=0}^{\infty }a_{i}}$ определен и равен ${\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}$ тогда и только тогда, когда этот предел существует.

Неассоциативная бинарная операция

Общая неассоциативная бинарная операция задается магмой . Процесс итерации неассоциативной бинарной операции может быть представлен в виде двоичного дерева .

Обозначения

Итерированные двоичные операции используются для представления операции, которая будет повторяться над набором с учетом некоторых ограничений. Обычно нижняя граница ограничения записывается под символом, а верхняя граница над символом, хотя они также могут быть записаны в виде верхних и нижних индексов в компактной записи. Интерполяция выполняется над положительными целыми числами от нижней до верхней границы, чтобы получить набор, который будет подставлен в индекс (ниже обозначен как i   ) для повторяющихся операций.

Общие обозначения включают обозначения big Sigma ( повторяющаяся сумма ) и big Pi ( повторяющееся произведение ) .

$$\sum _{i=0}^{n-1}i=0+1+2+\dots +(n-1)$$

$$\prod _{i=0}^{n-1}i=0\times 1\times 2\times \dots \times (n-1)$$

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

$$\sum _{x\in S}x=x_{1}+x_{2}+x_{3}+\dots +x_{n}$$

Несколько условий могут быть записаны либо вместе с логическим, либо отдельно:

$$\sum _{(i\in 2\mathbb {N} )\wedge (i\leq n)}i=\sum _{\stackrel {i\in 2\mathbb {N} }{i\leq n}}i=0+2+4+\dots +n$$

Реже любой бинарный оператор , например исключающий или ( $\oplus$) или установить объединение ( $\cup$) также можно использовать. Например, если S — набор логических предложений :

$$\bigwedge _{p\in S}p=p_{1}\wedge p_{2}\wedge \dots \wedge p_{N}$$

что верно тогда и только тогда, когда все элементы S истинны.

См. также

• Непрерывная дробь
• Сгиб (функция высшего порядка)
• Бесконечный продукт
• Бесконечная серия

Внешние ссылки

• Массовое действие
• Параллельная работа префикса. Архивировано 3 июня 2013 г. на Wayback Machine.
• Nuprl итерационные бинарные операции