Iverson-Halterung - Iverson bracket

In der Mathematik ist die Iverson-Klammer , benannt nach Kenneth E. Iverson , eine Notation, die das Kronecker-Delta verallgemeinert , die Iverson-Klammer der Aussage x = y . Es ordnet jede Aussage einer Funktion der freien Variablen darin zu, die den Wert Eins für die Werte der Variablen annimmt, für die die Aussage wahr ist, und ansonsten den Wert Null annimmt. Es wird im Allgemeinen dadurch gekennzeichnet, dass die Anweisung in eckige Klammern gesetzt wird:

${\displaystyle [P]={\begin{cases}1&{\text{if }}P{\text{ ist wahr;}}\\0&{\text{sonst.}}\end{cases}}}$

Im Kontext der Summation kann die Notation verwendet werden, um jede Summe als unendliche Summe ohne Grenzen zu schreiben: If is any property of the integer , ${\displaystyle P(k)}$${\displaystyle k}$

${\displaystyle \sum_{k}f(k)\,[P(k)]=\sum_{P(k)}f(k).}$

Beachten Sie, dass nach dieser Konvention ein Summand zu 0 ausgewertet werden muss, unabhängig davon, ob er definiert ist. Ebenso für Produkte : ${\displaystyle f(k)[{\textbf {false}}]}$${\displaystyle f(k)}$

${\displaystyle \prod_{k}f(k)^{[P(k)]}=\prod_{P(k)}f(k).}$

Die Notation wurde ursprünglich von Kenneth E. Iverson in seiner Programmiersprache APL eingeführt , obwohl sie auf einzelne relationale Operatoren in Klammern beschränkt war, während die Verallgemeinerung auf beliebige Aussagen, die Beschränkung der Notation auf eckige Klammern und Anwendungen auf Summation von Donald Knuth befürwortet wurde, um Vermeiden Sie Mehrdeutigkeiten in logischen Ausdrücken in Klammern.

Eigenschaften

Es gibt eine direkte Entsprechung zwischen Arithmetik auf Iverson-Klammern, Logik und Mengenoperationen. Seien beispielsweise A und B Mengen und eine beliebige Eigenschaft von ganzen Zahlen; dann haben wir ${\displaystyle P(k_{1},\dots)}$

${\displaystyle {\begin{ausgerichtet}[][\,P\land Q\,]~&=~[\,P\,]\,[\,Q\,]~~;\\[1em][ \,P\oder Q\,]~&=~[\,P\,]\;+\;[\,Q\,]\;-\;[\,P\,]\,[\,Q \,]~~;\\[1em][\,\neg \,P\,]~&=~1-[\,P\,]~~;\\[1em][\,P{\scriptstyle {\mathsf {\text{ XOR}}}}Q\,]~&=~{\Bigl |}\,[\,P\,]\;-\;[\,Q\,]\,{\ Größer |}~~;\\[1em][\,k\in A\,]\;+\;[\,k\in B\,]~&=~[\,k\in A\cup B \,]\;+\;[\,k\in A\cap B\,]~~;\\[1em][\,x\in A\cap B\,]~&=~[\,x \in A\,]\,[\,x\in B\,]~~;\\[1em][\,\forall \,m\ :\,P(k,m)\,]~&= ~\prod_{m}\,[\,P(k,m)\,]~~;\\[1em][\,\exists \,m\ :\,P(k,m)\,] ~&=~\min {\Bigl\{}\;1\,,\,\sum _{m}\,[\,P(k,m)\,]\;{\Bigr\}}=1 \;-\;\prod_{m}\,[\,\neg \,P(k,m)\,]~~;\\[1em]\#{\Bigl \{}\;m\, {\Groß |}\,P(k,m)\;{\Groß\}}~&=~\sum _{m}\,[\,P(k,m)\,]~~.\end {ausgerichtet}}}$

Beispiele

Die Notation ermöglicht das Verschieben von Randbedingungen von Summationen (oder Integralen) als separater Faktor in den Summanden, wodurch Platz um den Summationsoperator herum frei wird, aber noch wichtiger, dass er algebraisch manipuliert werden kann.

Doppelzählungsregel

Wir leiten mechanisch eine bekannte Summenmanipulationsregel unter Verwendung von Iverson-Klammern ab:

${\displaystyle {\begin{ausgerichtet}\sum _{k\in A}f(k)+\sum _{k\in B}f(k)&=\sum_{k}f(k)\, [k\in A]+\sum _{k}f(k)\,[k\in B]\\&=\sum _{k}f(k)\,([k\in A]+[ k\in B])\\&=\sum _{k}f(k)\,([k\in A\cup B]+[k\in A\cap B])\\&=\sum _ {k\in A\cup B}f(k)\ +\sum _{k\in A\cap B}f(k).\end{ausgerichtet}}}$

Summenaustausch

Die bekannte Regel lässt sich ebenfalls leicht herleiten: ${\displaystyle \textstyle \sum_{j=1}^{n}\,\sum_{k=1}^{j}f(j,k)=\sum_{k=1}^{n} \,\sum _{j=k}^{n}f(j,k)}$

${\displaystyle {\begin{ausgerichtet}\sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)&=\sum _{j,k }f(j,k)\,[1\leq j\leq n]\,[1\leq k\leq j]\\&=\sum _{j,k}f(j,k)\,[ 1\leq k\leq j\leq n]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq n]\,[k\leq j\leq n ]\\&=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k).\end{ausgerichtet}}}$

Zählen

Zum Beispiel ist die Funktion Euler phi dass zählt die Anzahl von positiven ganzen Zahlen bis n , die teilerfremd zu n können ausgedrückt werden durch

${\displaystyle \phi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1],\qquad {\text{für}}n\in\mathbb{N} ^{+}.}$

Vereinfachung von Sonderfällen

Eine weitere Verwendung der Iverson-Klammer besteht darin, Gleichungen mit Sonderfällen zu vereinfachen. Zum Beispiel die Formel

${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)}$

ist gültig für n > 1, aber ausgeschaltet um1/2für n = 1 . Um eine gültige Identität für alle positiven ganzen Zahlen n (dh alle Werte, für die definiert ist) zu erhalten, kann ein Korrekturterm mit der Iverson-Klammer hinzugefügt werden: ${\displaystyle \phi(n)}$

${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n(\varphi(n)+ [n=1])}$

Gemeinsame Funktionen

Viele gebräuchliche Funktionen, insbesondere solche mit einer natürlichen stückweisen Definition, können durch die Iverson-Klammer ausgedrückt werden. Die Kronecker-Delta- Notation ist ein Sonderfall der Iverson-Notation, wenn die Bedingung Gleichheit ist. Das ist,

${\displaystyle \delta_{ij}=[i=j].}$

Die Indikatorfunktion , oft als , oder bezeichnet , ist eine Iverson-Klammer mit Mengenzugehörigkeit als Bedingung: ${\displaystyle \mathbf {1} _{A}(x)}$${\displaystyle \mathbf {I} _{A}(x)}$${\displaystyle \chi_{A}(x)}$

${\displaystyle\mathbf{I}_{A}(x)=[x\in A]}$.

Die Heaviside-Stufenfunktion , Vorzeichenfunktion und Absolutwertfunktion lassen sich ebenfalls leicht in dieser Notation ausdrücken:

${\displaystyle {\begin{aligned}H(x)&=[x>0],\\\Operatorname {sgn}(x)&=[x>0]-[x<0],\end{aligned} }}$

und

${\displaystyle {\begin{ausgerichtet}|x|&=x[x>0]-x[x<0]\\&=x([x>0]-[x<0])\\&=x \cdot \operatorname {sgn}(x).\end{aligned}}}$

Die Vergleichsfunktionen max und min (die das größere oder kleinere von zwei Argumenten zurückgeben) können geschrieben werden als

${\displaystyle \max(x,y)=x[x>y]+y[x\leq y]}$ und

${\displaystyle \min(x,y)=x[x\leq y]+y[x>y]}$.

Die Boden- und Deckenfunktionen können ausgedrückt werden als

${\displaystyle \lfloor x\rfloor =\sum _{n}n\cdot [n\leq x<n+1]}$

und

${\displaystyle \lceil x\rceil =\sum _{n}n\cdot [n-1<x\leq n],}$

wobei der Summationsindex so verstanden wird, dass er sich über alle ganzen Zahlen erstreckt. ${\displaystyle n}$

Die Rampenfunktion kann ausgedrückt werden

${\displaystyle R(x)=x\cdot [x\geq 0].}$

Die Trichotomie der reellen Zahlen entspricht der folgenden Identität:

${\displaystyle [a<b]+[a=b]+[a>b]=1.}$

Die Möbius-Funktion hat die Eigenschaft (und kann durch Rekursion definiert werden als)

${\displaystyle \sum_{d|n}\mu(d)\ =\ [n=1].}$

Formulierung in Bezug auf übliche Funktionen

In den 1830er Jahren benutzte Guglielmo dalla Sommaja den Ausdruck, um darzustellen, was jetzt geschrieben werden würde ; dalla Sommaja verwendet auch Varianten, wie zum Beispiel für . Nach einer gemeinsamen Konvention sind diese Größen gleich, wenn sie definiert sind: ist 1, wenn x > 0, ist 0, wenn x = 0 und ist ansonsten undefiniert. ${\displaystyle 0^{0^{x}}}$${\displaystyle [x>0]}$${\displaystyle \left(1-0^{0^{-x}}\right)\left(1-0^{0^{xa}}\right)}$${\displaystyle [0\leq x\leq a]}$${\displaystyle 0^{0^{x}}}$

Siehe auch

• Boolesche Funktion
• Typumwandlung in der Computerprogrammierung: Viele Sprachen erlauben die Verwendung von numerischen oder Zeigergrößen als boolesche Größen
• Anzeigefunktion

Verweise