Iverson Klammer – Wikipedia

Posted on by

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

[P]={1wenn P. ist wahr;0Andernfalls.{ displaystyle [P]= { begin {Fälle} 1 & { text {if}} P { text {ist wahr;}} \ 0 & { text {sonst.}} end {Fälle}}}

Im Kontext der Summation kann die Notation verwendet werden, um eine beliebige Summe als unendliche Summe ohne Grenzen zu schreiben: If

P.((k){ displaystyle P (k)}

ist eine Eigenschaft der Ganzzahl

k{ displaystyle k}

,

∑kf((k)[P(k)]=∑P.((k)f((k).{ displaystyle sum _ {k} f (k) ,[P(k)]= sum _ {P (k)} f (k).}

Beachten Sie, dass nach dieser Konvention ein Summand

f((k)[false]{ displaystyle f (k)[{textbf {false}}]}}

muss auf 0 ausgewertet werden, unabhängig davon, ob

f((k){ displaystyle f (k)}

ist definiert. Ebenso für Produkte:

∏kf((k)[P(k)]=∏P.((k)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.[1][2] Donald Knuth befürwortete die Verallgemeinerung auf willkürliche Aussagen, die Beschränkung der Notation auf eckige Klammern und Anwendungen auf die Summierung, obwohl sie auf einzelne relationale Operatoren in Klammern beschränkt war, um Mehrdeutigkeiten in logischen Ausdrücken in Klammern zu vermeiden.[3]

Eigenschaften[edit]

Es gibt eine direkte Entsprechung zwischen Arithmetik für Iverson-Klammern, Logik und Mengenoperationen. Zum Beispiel lassen EIN und B. gesetzt werden und

P.((k1,…){ displaystyle P (k_ {1}, dots)}

jede Eigenschaft von ganzen Zahlen; dann haben wir

[P∧Q]=[P][Q],[¬P]=1– –[P].[P∨Q]=[P]+[Q]– –[P][Q].[k∈A]+[k∈B]=[k∈A∪B]+[k∈A∩B].[x∈A∩B]=[x∈A][x∈B].[∀m . P(k,m)]=∏m[P(k,m)].[∃m . P(k,m)]=Mindest((1,∑m[P(k,m)])=1– –∏m((1– –[P(k,m)]).#{m∣P.((k,m)}}=∑m[P(k,m)].{ displaystyle { begin {align}[][Pland Q]& =[P][Q], qquad [neg P]= 1-[P]. \[1em][Plor Q]& =[P]+[Q]- -[P][Q]. \[1em][kin A]+[kin B]& =[kin Acup B]+[kin Acap B]. \[1em][xin Acap B]& =[xin A][xin B]. \[1em][forall m . P(k,m)]& = prod _ {m}[P(k,m)]. \[1em][exists m . P(k,m)]& = min { Big (} 1, sum _ {m}[P(k,m)]{ Big)} = 1- prod _ {m} left (1-[P(k,m)]Recht).\[1em] # {m mid P (k, m) } & = sum _ {m}[P(k,m)]. end {align}}}

Beispiele[edit]

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

Doppelzählregel[edit]

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

∑k∈EINf((k)+∑k∈B.f((k)=∑kf((k)[k∈A]+∑kf((k)[k∈B]=∑kf((k)(([k∈A]+[k∈B])=∑kf((k)(([k∈A∪B]+[k∈A∩B])=∑k∈EIN∪B.f((k) +∑k∈EIN∩B.f((k).{ displaystyle { begin {align} sum _ {k in A} f (k) + sum _ {k in B} f (k) & = sum _ {k} f (k) ,[kin A]+ sum _ {k} f (k) ,[kin B]\ & = sum _ {k} f (k) , ([kin A]+[kin B]) \ & = sum _ {k} f (k) , ([kin Acup B]+[kin Acap B]) \ & = sum _ {k in A cup B} f (k) + sum _ {k in A cap B} f (k). end {align}}}

Summationsaustausch[edit]

Die bekannte Regel

∑j=1n∑k=1jf((j,k)=∑k=1n∑j=knf((j,k){ displaystyle textstyle sum _ {j = 1} ^ {n} , sum _ {k = 1} ^ {j} f (j, k) = sum _ {k = 1} ^ {n} , sum _ {j = k} ^ {n} f (j, k)}

ist ebenfalls leicht abzuleiten:

∑j=1n∑k=1jf((j,k)=∑j,kf((j,k)[1≤j≤n][1≤k≤j]=∑j,kf((j,k)[1≤k≤j≤n]=∑j,kf((j,k)[1≤k≤n][k≤j≤n]=∑k=1n∑j=knf((j,k).{ displaystyle { begin {align} sum _ {j = 1} ^ {n} , sum _ {k = 1} ^ {j} f (j, k) & = sum _ {j, k } f (j, k) ,[1leq jleq n],[1leq kleq j]\ & = sum _ {j, k} f (j, k) ,[1leq kleq jleq n]\ & = sum _ {j, k} f (j, k) ,[1leq kleq n],[kleq jleq n]\ & = sum _ {k = 1} ^ {n} , sum _ {j = k} ^ {n} f (j, k). end {align}}}

Zählen[edit]

Zum Beispiel die Euler-Phi-Funktion, die die Anzahl der positiven ganzen Zahlen bis zu zählt n welche sind coprime zu n kann ausgedrückt werden durch

ϕ((n)=∑ich=1n[gcd(i,n)=1],zum n∈N.+.{ displaystyle phi (n) = sum _ {i = 1} ^ {n}[gcd(i,n)=1], qquad { text {for}} n in mathbb {N} ^ {+}.}

Vereinfachung von Sonderfällen[edit]

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

∑1≤k≤ngcd((k,n)=1k=12nφ((n){ displaystyle sum _ {1 leq k leq n atop gcd (k, n) = 1} ! ! k = { frac {1} {2}} n varphi (n)}

gilt für n > 1 ist aber weg von 1/.2 zum n = 1. Um eine Identität zu erhalten, die für alle positiven ganzen Zahlen gültig ist n (dh alle Werte für die

ϕ((n){ displaystyle phi (n)}

definiert ist), kann ein Korrekturterm mit der Iverson-Klammer hinzugefügt werden:

∑1≤k≤ngcd((k,n)=1k=12n((φ((n)+[n=1]){ displaystyle sum _ {1 leq k leq n atop gcd (k, n) = 1} ! ! k = { frac {1} {2}} n ( varphi (n) +[n=1])}

Gemeinsame Funktionen[edit]

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

δichj=[i=j].{ displaystyle delta _ {ij} =[i=j].}

Die oft bezeichnete Indikatorfunktion

1EIN((x){ displaystyle mathbf {1} _ {A} (x)}

,

ichEIN((x){ displaystyle mathbf {I} _ {A} (x)}

oder

χEIN((x){ displaystyle chi _ {A} (x)}

ist eine Iverson-Klammer mit festgelegter Mitgliedschaft als Bedingung:

ichEIN((x)=[x∈A]{ displaystyle mathbf {I} _ {A} (x) =[xin A]}}

.

Die Heaviside-Schrittfunktion, Vorzeichenfunktion,[1] und Absolutwertfunktion lassen sich auch leicht in dieser Notation ausdrücken:

H.((x)=[x≥0],sgn⁡((x)=[x>0]– –[x<0],{ displaystyle { begin {align} H (x) & =[xgeq 0], \ operatorname {sgn} (x) & =[x>0]- -[x<0], end {align}}}

und

|x|=x[x>0]– –x[x<0]=x(([x>0]– –[x<0])=x⋅sgn⁡((x).{ displaystyle { begin {align} | x | & = x[x>0]-x[x[x<0]\&=x([x>0]-[x<0]) \ & = x cdot operatorname {sgn} (x). end {align}}}

Die Vergleichsfunktionen max und min (Rückgabe des größeren oder kleineren von zwei Argumenten) können wie folgt geschrieben werden

max((x,y)=x[x>y]+y[x≤y]{ displaystyle max (x, y) = x[x>y]+ y[xleq y]}}

Mindest((x,y)=x[x≤y]+y[x>y]{ displaystyle min (x, y) = x[xleq y]+ y[x>y]}}

⌊x⌋=∑nn⋅[n≤x<n+1]{ displaystyle lfloor x rfloor = sum _ {n} n cdot [nleq x

und

⌈x⌉=∑nn⋅[n−1<x≤n],{ displaystyle lceil x rceil = sum _ {n} n cdot [n-1

wo der Index

n{ displaystyle n}

Unter Summation versteht man alle ganzen Zahlen.

Die Rampenfunktion kann ausgedrückt werden

R.((x)=x⋅[x≥0].{ displaystyle R (x) = x cdot [xgeq 0].}

Die Trichotomie der Realen entspricht der folgenden Identität:

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

[4])
∑d|nμ((d) = [n=1].{ displaystyle sum _ {d | n} mu (d) = [n=1].}

Formulierung in Bezug auf übliche Funktionen[edit]

In den 1830er Jahren verwendete Guglielmo dalla Sommaja den Ausdruck

00x{ displaystyle 0 ^ {0 ^ {x}}}

zu repräsentieren, was jetzt geschrieben werden würde [x>0]{ displaystyle [x>0]}}

((1– –00– –x)((1– –00x– –ein){ displaystyle left (1-0 ^ {0 ^ {- x}} right) left (1-0 ^ {0 ^ {xa}} right)}

zum [0≤x≤a]{ displaystyle [0leq xleq a]}}

.[3]

Nach einer gemeinsamen Konvention sind diese Mengen gleich, wo definiert:

00x{ displaystyle 0 ^ {0 ^ {x}}}

ist 1 wenn x > 0, ist 0 wenn x = 0 und ist ansonsten undefiniert.

Siehe auch[edit]

Verweise[edit]

  1. ^ ein b Kenneth E. Iverson (1962). Eine Programmiersprache. Wiley. p. 11. Abgerufen 7. April 2016.
  2. ^ Ronald Graham, Donald Knuth und Oren Patashnik. Konkrete Mathematik, Abschnitt 2.2: Beträge und Rückfälle.
  3. ^ ein b Donald Knuth, “Zwei Anmerkungen zur Notation”, American Mathematical MonthlyBand 99, Nummer 5, Mai 1992, S. 403–422. ((TeX, arXiv:math / 9205211).
  4. ^ Ronald Graham, Donald Knuth und Oren Patashnik. Konkrete Mathematik, Abschnitt 4.9: Phi und Mu.