Soporte de Iverson

Notación matemática

En matemáticas , el corchete de Iverson , llamado así por Kenneth E. Iverson , es una notación que generaliza el delta de Kronecker , que es el corchete de Iverson del enunciado x = y . Asigna cualquier enunciado a una función de las variables libres en ese enunciado. Esta función está definida para tomar el valor 1 para los valores de las variables para las que el enunciado es verdadero, y toma el valor 0 en caso contrario. Generalmente se denota poniendo el enunciado dentro de corchetes: En otras palabras, el corchete de Iverson de un enunciado es la función indicadora del conjunto de valores para los que el enunciado es verdadero. $${\displaystyle [P]={\begin{cases}1&{\text{if }}P{\text{ is true;}}\\0&{\text{otherwise.}}\end{cases}}}$$

El corchete de Iverson permite utilizar la notación sigma mayúscula sin restricción en el índice de suma. Es decir, para cualquier propiedad del entero , se puede reescribir la suma restringida en la forma no restringida . Con esta convención, no necesita estar definido para los valores de k para los cuales el corchete de Iverson es igual a 0 ; es decir, un sumando debe evaluarse a 0 independientemente de si está definido. ${\displaystyle P(k)}$ ${\displaystyle k}$ ${\displaystyle \sum _{k:P(k)}f(k)}$ ${\displaystyle \sum _{k}f(k)\cdot [P(k)]}$ ${\displaystyle f(k)}$ ${\displaystyle f(k)[{\textbf {false}}]}$ ${\displaystyle f(k)}$

La notación fue introducida originalmente por Kenneth E. Iverson en su lenguaje de programación APL , ^{[1] [2]} aunque restringida a operadores relacionales individuales encerrados entre paréntesis, mientras que la generalización a declaraciones arbitrarias, la restricción de la notación a corchetes y las aplicaciones a la suma, fueron defendidas por Donald Knuth para evitar la ambigüedad en expresiones lógicas entre paréntesis. ^[3]

Propiedades

Existe una correspondencia directa entre la aritmética sobre corchetes de Iverson, la lógica y las operaciones con conjuntos. Por ejemplo, sean A y B conjuntos y cualquier propiedad de los números enteros; entonces tenemos ${\displaystyle P(k_{1},\dots )}$ $${\displaystyle {\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}}}$$

Ejemplos

La notación permite mover las condiciones de contorno de las sumas (o integrales) como un factor separado en el sumando, liberando espacio alrededor del operador de suma, pero más importante aún, permitiendo manipularlo algebraicamente.

Regla de doble contabilización

Derivamos mecánicamente una regla de manipulación de sumas bien conocida utilizando corchetes de Iverson: $${\displaystyle {\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}}}$$

Intercambio de suma

La regla conocida también se deduce fácilmente: ${\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{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}}}$$

Cálculo

Por ejemplo, la función totient de Euler que cuenta el número de números enteros positivos hasta n que son coprimos con n se puede expresar mediante $${\displaystyle \varphi (n)=\sum _{i=1}^{n}[\gcd(i,n)=1],\qquad {\text{for }}n\in \mathbb {N} ^{+}.}$$

Simplificación de casos especiales

Otro uso del corchete de Iverson es simplificar ecuaciones con casos especiales. Por ejemplo, la fórmula $${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)}$$

es válido para n > 1 pero está desfasado por ⁠1/2⁠ para n = 1. Para obtener una identidad válida para todos los números enteros positivos n (es decir, todos los valores para los que está definido), se puede agregar un término de corrección que involucre el corchete de Iverson: ${\displaystyle \phi (n)}$ $${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n{\Big (}\varphi (n)+[n=1]{\Big )}}$$

Funciones comunes

Muchas funciones comunes, especialmente aquellas con una definición natural por partes, pueden expresarse en términos del corchete de Iverson. La notación delta de Kronecker es un caso específico de notación de Iverson cuando la condición es la igualdad. Es decir, $${\displaystyle \delta _{ij}=[i=j].}$$

La función indicadora de un conjunto , a menudo denotada como o , es un corchete de Iverson cuya condición es la pertenencia al conjunto: ${\displaystyle A}$ ${\displaystyle \mathbf {1} _{A}(x)}$ ${\displaystyle \mathbf {I} _{A}(x)}$ ${\displaystyle \chi _{A}(x)}$ $${\displaystyle \mathbf {I} _{A}(x)=[x\in A].}$$

La función escalonada de Heaviside , la función de signo ^[1] y la función de valor absoluto también se expresan fácilmente en esta notación: $${\displaystyle {\begin{aligned}H(x)&=[x\geq 0],\\\operatorname {sgn}(x)&=[x>0]-[x<0],\end{aligned}}}$$

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

Las funciones de comparación max y min (que devuelven el mayor o el menor de dos argumentos) se pueden escribir como y $${\displaystyle \max(x,y)=x[x>y]+y[x\leq y]}$$ $${\displaystyle \min(x,y)=x[x\leq y]+y[x>y].}$$

Las funciones de suelo y techo se pueden expresar como y donde se entiende que el índice de suma abarca todos los números enteros. $${\displaystyle \lfloor x\rfloor =\sum _{n}n\cdot [n\leq x<n+1]}$$ $${\displaystyle \lceil x\rceil =\sum _{n}n\cdot [n-1<x\leq n],}$$ ${\displaystyle n}$

La función rampa se puede expresar $${\displaystyle R(x)=x\cdot [x\geq 0].}$$

La tricotomía de los reales es equivalente a la siguiente identidad: $${\displaystyle [a<b]+[a=b]+[a>b]=1.}$$

La función de Möbius tiene la propiedad (y puede definirse por recurrencia como ^[4] ) $${\displaystyle \sum _{d|n}\mu (d)\ =\ [n=1].}$$

Formulación en términos de funciones usuales

En la década de 1830, Guglielmo dalla Sommaja utilizó la expresión para representar lo que ahora se escribiría ; también utilizó variantes, como para . [ ^3] Siguiendo una convención común , esas cantidades son iguales donde se define: es 1 si x > 0 , es 0 si x = 0 , y no está definido en caso contrario. ${\displaystyle 0^{0^{x}}}$ ${\displaystyle [x>0]}$ ${\displaystyle \left(1-0^{0^{-x}}\right)\left(1-0^{0^{x-a}}\right)}$ ${\displaystyle [0\leq x\leq a]}$ ${\displaystyle 0^{0^{x}}}$

Variaciones de notación

Además de los corchetes ahora estándar [ · ] y los paréntesis originales ( · ), también se han utilizado corchetes de pizarra en negrita , por ejemplo ⟦ · ⟧ , así como otras formas inusuales de marcas de corchetes disponibles en la tipografía del editor, acompañadas de una nota marginal.

Véase también

• Función booleana
• Conversión de tipos en programación informática: muchos lenguajes permiten utilizar cantidades numéricas o de puntero como cantidades booleanas
• Función indicadora

Referencias

1. Kenneth E. Iverson (1962). Un lenguaje de programación. Wiley. p. 11. Consultado el 7 de abril de 2016 .
2. Ronald Graham , Donald Knuth y Oren Patashnik . Matemáticas concretas , Sección 2.1: Notación.
3. Donald Knuth, "Dos notas sobre la notación", American Mathematical Monthly , volumen 99, número 5, mayo de 1992, págs. 403–422. (TeX, arXiv :math/9205211).
4. Ronald Graham , Donald Knuth y Oren Patashnik . Matemáticas concretas , Sección 4.9: Phi y Mu.