Predicado BIT

En matemáticas y ciencias de la computación, el predicado BIT, a veces escrito ${\displaystyle {\text{BIT}}(i,j)}$, es un concepto en matemáticas, lógica e informática. Es un tipo de predicado que comprueba si el ${\displaystyle j}$-ésimo bit del número ${\displaystyle i}$ (contando desde el bit menos significativo) es 1 cuando ${\displaystyle i}$ se escribe como número binario. Entre sus aplicaciones matemáticas figuran el modelado de la relación de pertenencia de los conjuntos finitos hereditariamente y la definición de la relación de adyacencia del grafo de Rado. En ciencias de la computación se utiliza para representar de forma eficiente estructuras de datos de conjuntos mediante vectores de bits, para definir el problema de la recuperación privada de información en la complejidad de la comunicación y, en la teoría de la complejidad descriptiva, para formular descripciones lógicas de clases de complejidad.

Historia

El predicado BIT aparece en 1937 en la obra de Wilhelm Ackermann, que lo utilizó para definir la codificación de Ackermann, con la que los conjuntos finitos hereditariamente se codifican como números naturales. El predicado BIT permite comprobar la pertenencia entre los conjuntos codificados: ${\displaystyle {\text{BIT}}(i,j)}$ es verdadero si y solo si el conjunto codificado por ${\displaystyle j}$ es elemento del conjunto codificado por ${\displaystyle i}$.

Ackermann denotó el predicado ${\displaystyle {\text{BIT}}(i,j)}$ como ${\displaystyle {\mathfrak {El}}(j,i)}$, con una tipografía Fraktur para distinguirlo de la notación ${\displaystyle \mathrm {El} (j,i)}$ que empleaba para la pertenencia a un conjunto (que se lee «${\displaystyle j}$ es elemento de ${\displaystyle i}$»). El nombre «predicado BIT» aparece en la obra de Neil Immerman, que aplicó este predicado en la teoría de la complejidad computacional a finales de la década de 1980.

Descripción e implementación

La representación binaria de un número ${\displaystyle i}$ es una expresión de ${\displaystyle i}$ como suma de potencias de dos distintas: $${\displaystyle i=\cdots b_{3}2^{3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0}}$$ donde cada bit ${\displaystyle b_{j}}$ de esta expresión vale 0 o 1. En notación binaria se suele escribir simplemente como la sucesión de estos bits, ${\displaystyle \cdots b_{3}b_{2}b_{1}b_{0}}$. Dado este desarrollo de ${\displaystyle i}$, el predicado BIT ${\displaystyle {\text{BIT}}(i,j)}$ se define como igual a ${\displaystyle b_{j}}$. Puede calcularse mediante la fórmula $${\displaystyle {\text{BIT}}(i,j)=\left\lfloor {\frac {i}{2^{j}}}\right\rfloor {\bmod {2}},}$$ donde ${\displaystyle \lfloor \cdot \rfloor }$ es la función suelo y mod es la operación módulo. Como relación binaria (que produce los valores verdadero y falso en lugar de 1 y 0, respectivamente), el predicado BIT es asimétrico: no existen dos números ${\displaystyle i}$ y ${\displaystyle j}$ para los que ${\displaystyle {\text{BIT}}(i,j)}$ y ${\displaystyle {\text{BIT}}(j,i)}$ sean ambos verdaderos.

En lenguajes de programación como C, C++, Java o Python, que disponen de un operador de desplazamiento a la derecha >> y de un operador booleano AND bit a bit &, el predicado BIT ${\displaystyle {\text{BIT}}(i,j)}$ puede implementarse mediante la expresión (i>>j)&1. La subexpresión i>>j desplaza los bits de la representación binaria de ${\displaystyle i}$ de modo que el bit ${\displaystyle b_{j}}$ pasa a la posición 0, y la subexpresión &1 enmascara los bits restantes y deja solo el bit de la posición 0. Al igual que con la fórmula de aritmética modular anterior, el valor de la expresión es 1 o 0 según que el valor de ${\displaystyle {\text{BIT}}(i,j)}$ sea verdadero o falso, respectivamente.

Aplicaciones

Construcción del grafo de Rado

En 1964, el matemático germano-británico Richard Rado utilizó el predicado BIT para construir el grafo infinito de Rado. La construcción de Rado es simplemente la simetrización de la construcción de Ackermann de 1937 de los conjuntos finitos hereditariamente a partir del predicado BIT: dos vértices numerados ${\displaystyle i}$ y ${\displaystyle j}$ son adyacentes en el grafo de Rado cuando ${\displaystyle {\text{BIT}}(i,j)}$ o ${\displaystyle {\text{BIT}}(j,i)}$ no es nulo.

El grafo resultante tiene muchas propiedades importantes: contiene todo grafo finito no dirigido como subgrafo inducido, y todo isomorfismo entre subgrafos inducidos finitos puede extenderse a una simetría del grafo completo.

Notas

Referencias