Nawias Iversona

Nawias Iversona – nazwany na cześć Kennetha E. Iversona matematyczny zapis uogólniający deltę Kroneckera. Odwzorowuje on dowolne wyrażenie na funkcję zmiennych w tym wyrażeniu. Funkcja ta przyjmuje wartość 1 dla wartości zmiennych, dla których wyrażenie jest prawdziwe, w przeciwnym razie przyjmuje wartość 0. Zwykle oznacza się to poprzez umieszczenie wyrażenia w nawiasach kwadratowych:

$$[P]={\begin{cases}1&{\text{jeżeli }}P{\text{ jest prawdziwe;}}\\0&{\text{w innym przypadku.}}\end{cases}}$$

Inaczej mówiąc, nawias Iversona dla danego stwierdzenia jest funkcją charakterystyczną zbioru wartości, dla których to stwierdzenie jest prawdziwe.

Nawias Iversona umożliwia stosowanie notacji sumowania (w wykorzystaniem symbolu Σ) bez ograniczeń dotyczących indeksu sumowania. Dla dowolnej własności $P(k)$ liczby całkowitej $k$, można przepisać ograniczoną sumę $\sum _{k:P(k)}f(k)$ do postaci nieograniczonej $\sum _{k}f(k)\cdot [P(k)]$. W ramach tej konwencji nie trzeba definiować $f(k)$ dla wartości k, dla których nawias Iversona jest równy 0; składnik $f(k)\cdot [{\bf {{\text{fałsz}}]}}$ musi wynosić 0 niezależnie od tego, czy $f(k)$ jest określone czy nie.

Notacja została pierwotnie wprowadzona przez Kennetha E. Iversona w stworzonym przez niego języku programowania APL. Pierwotnie była ograniczona do pojedynczych operatorów relacyjnych umieszczonych w nawiasach. Donald Knuth zaproponował uogólnienie na dowolne stwierdzenia, zastosowanie nawiasów kwadratowych i wykorzystanie do sumowania, jako sposób na uniknięcie dwuznaczności wyrażeń logicznych umieszczonych w nawiasach.

Własności

Istnieje bezpośrednia zgodność pomiędzy arytmetyką wykorzystującą nawiasy Iversona, logiką i operacjami na zbiorach. Na przykład, niech A i B będą zbiorami, a $P(k_{1},\dots )$ dowolną właściwością liczb całkowitych. Mamy wtedy:$${\begin{aligned}[][\,P\land Q\,]~&=~[\,P\,]\,[\,Q\,]~~;\\[1em][\,P\lor Q\,]~&=~[\,P\,]\;+\;[\,Q\,]\;-\;[\,P\,]\,[\,Q\,]~~;\\[1em][\,\neg \,P\,]~&=~1-[\,P\,]~~;\\[1em][\,P{\scriptstyle {\mathsf {\text{ XOR }}}}Q\,]~&=~{\Bigl |}\,[\,P\,]\;-\;[\,Q\,]\,{\Bigr |}~~;\\[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\,{\Big |}\,P(k,m)\;{\Bigr \}}~&=~\sum _{m}\,[\,P(k,m)\,]~~.\end{aligned}}$$

Przykłady

Notacja umożliwia zapis ograniczeń zakresu sum (lub całek) w postaci osobnego składnika sumy, co zwalnia miejsce przy operatorze sumowania, a także, co ważniejsze, zwiększa elastyczność poprzez dopuszczenie szeregu przekształceń algebraicznych.

Zasada podwójnego zliczania

Mechanicznie wyprowadzamy dobrze znaną regułę dla sumy za pomocą nawiasów Iversona:$${\begin{aligned}\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{aligned}}$$

Wymiana indeksów w podsumowaniach

Znaną regułę ${\textstyle \sum _{j=1}^{n}\sum _{k=1}^{j}f(j,k)=\sum _{k=1}^{n}\sum _{j=k}^{n}f(j,k)}$ jest również łatwo wyprowadzić:$${\begin{aligned}\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{aligned}}$$

Zliczenia

Funkcję tocjent Eulera $\varphi (n)$, która zlicza liczbę dodatnich liczb całkowitych mniejszych niż n, które są względnie pierwsze z n, można wyrazić wzorem:$$\varphi (n)=\sum _{i=1}^{n}[{\text{nwd}}(i,n)=1],\qquad {\text{dla }}n\in \mathbb {N} ^{+}.$$

Uproszczenie przypadków specjalnych

Innym zastosowaniem nawiasu Iversona jest uproszczenie równań mających specjalne przypadki. Na przykład wzór$$\sum _{1\leq k\leq n \atop {\text{nwd}}(k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)$$obowiązuje dla $n>1$, ale dla $n=1$ myli się o ${\frac {1}{2}}$. Aby uzyskać tożsamość obowiązującą dla wszystkich dodatnich liczb całkowitych n (tj. wszystkich wartości, dla których $\varphi (n)$ jest zdefiniowana), można dodać składnik korygujący wykorzystujący nawias Iversona:$$\sum _{1\leq k\leq n \atop {\text{nwd}}(k,n)=1}\!\!k={\frac {1}{2}}n{\Big (}\varphi (n)+[n=1]{\Big )}$$

Popularne funkcje

Delta Kroneckera jest szczególnym przypadkiem nawiasu Iversona:$$\delta _{ij}=[i=j].$$Funkcja charakterystyczna zbioru, oznaczana symbolami $\mathbf {1} _{A}(x)$, $\mathbf {I} _{A}(x)$ lub $\chi _{A}(x)$, jest nawiasem Iversona, którego argumentem jest przynależność do zbioru:$$\mathbf {I} _{A}(x)=[x\in A].$$Funkcję skokową Heaviside'a, funkcję signum i wartość bezwzględną są również łatwo wyrazić za pomocą tej notacji:$${\begin{aligned}H(x)&=[x>0],\\{\text{sgn}}(x)&=[x>0]-[x<0],\end{aligned}}$$i$${\begin{aligned}|x|&=x[x>0]-x[x<0]\\&=x([x>0]-[x<0])\\&=x\cdot {\text{sgn}}(x).\end{aligned}}$$Funkcje porównawcze max i min (zwracające większy lub mniejszy z dwóch argumentów) można zapisać jako$${\text{max}}(x,y)=x[x>y]+y[x\leq y]$$i$${\text{min}}(x,y)=x[x\leq y]+y[x>y].$$Funkcje podłoga i sufit można wyrazić jako$$\lfloor x\rfloor =\sum _{n}n\cdot [n\leq x<n+1]$$i$$\lceil x\rceil =\sum _{n}n\cdot [n-1<x\leq n],$$gdzie indeks $n$ przechodzi przez wszystkie liczby całkowite.

Trichotomia liczb rzeczywistych jest równoważna następującej tożsamości:$$[a<b]+[a=b]+[a>b]=1.$$Funkcja Möbiusa ma następującą właściwość (która może posłużyć jako jej definicja rekurencyjna)$$\sum _{d|n}\mu (d)\ =\ [n=1].$$

Sformułowanie w kategoriach zwykłych funkcji

W latach trzydziestych XIX wieku Guglielmo dalla Sommaja używał wyrażenia $0^{0^{x}}$, aby przedstawić $[x>0]$; stosował także warianty tego zapisu, na przykład $\left(1-0^{0^{-x}}\right)\left(1-0^{0^{x-a}}\right)$ dla $[0\leq x\leq a]$. Zgodnie z jedną z konwencji, wyrażenie $0^{0^{x}}$jest równe 1 dla x > 0, 0 dla x = 0, w pozostałych przypadkach jest niezdefiniowane.

Różnice notacyjne

Oprócz standardowych obecnie nawiasów kwadratowych [ · ] i stosowanych początkowo zwykłych nawiasów ( · ), stosowano także pogrubione nawiasy tablicowe, tzn. ⟦ · ⟧, a także inne nietypowe kroje nawiasów wraz z odpowiednim wyjaśnieniem.

Zobacz też

• Funkcja logiczna
• Konwersja typów w programowaniu komputerowym: wiele języków umożliwia używanie wielkości liczbowych lub wskaźników jako wielkości logicznych.
• Funkcja wskaźnikowa