Predykat BIT

W matematyce i informatyce predykat BIT , czasami zapisywany jako BIT( i , j ), jest predykatem , który sprawdza, czy j -ty bit liczby i (licząc od najmniej znaczącej cyfry ) wynosi 1, gdy i jest zapisane binarnie .

Historia

Predykat BIT został po raz pierwszy wprowadzony w 1937 roku przez Wilhelma Ackermanna w celu zdefiniowania kodowania Ackermanna , które koduje dziedzicznie skończone zbiory jako liczby naturalne . Predykat BIT może służyć do przeprowadzania testów przynależności dla zakodowanych zbiorów.

Opis

W notacji matematycznej predykat BIT można opisać jako

{\ Displaystyle {\ tekst {BIT}} (i, j) = \ lfloor i \ mathbin {/} 2 ^ {j} \ rfloor {\ bmod { 2}}}

gdzie jest $podłogi,$ a mod funkcją modulo

Predykat BIT jest prymitywnie rekurencyjny .

Realizacja

W językach programowania, takich jak C , C++ , Java lub Python , które zapewniają operator przesunięcia w prawo >> oraz bitową wartość logiczną i operator & , predykat BIT BIT $(i, j)$ można zaimplementować za pomocą wyrażenia (i>>j) &1 . Tutaj bity $i$ są numerowane od bitów niższego rzędu do bitów wyższego rzędu w binarnej reprezentacji i , przy czym bit jedynek jest numerowany jako bit 0. Podwyrażenie i>>j przesuwa te $bity$ tak, że bit $j$ jest przesunięty do pozycji 0, a podwyrażenie &1 maskuje pozostałe bity, pozostawiając tylko bit na pozycji 0. Wartość wyrażenia wynosi odpowiednio 1 lub 0, ponieważ wartość BIT $(i, j)$ jest fałszem lub prawdą.

W przypadku zestawu reprezentowanego jako tablica bitów predykat BIT może być użyty do testowania członkostwa w zbiorze. $}$ przykład podzbiory nieujemnych liczb całkowitych mogą $,$ bitów z jedynką na pozycji { ${\ displaystyle i}$ jest członkiem podzbioru i zero na tej pozycji, gdy nie jest członkiem. Gdy taka $ja, j, k, \ kropki}$ $\}}$ jest interpretowana jako liczba binarna, zbiór dla { $kropki$ wszystkie różne są reprezentowane jako liczba binarna ${\ Displaystyle 2 ^ {i} + 2 ^ {j} + 2 ^ {k} + \ cdots }$ . Jeśli jest zbiorem reprezentowanym w ten sposób i jest liczbą, która $,$ $,$ być elementem ${\ displaystyle S}$ to BIT $(S,i)$ zwraca wartość różną od zera, gdy $członkiem$ i zero, gdy nim nie jest.

Tej samej techniki można użyć do zakodowania podzbiorów dowolnej sekwencji $są$ wartości, używając potęg dwójki, w tej kolejności, a nie ich wartości. Kodowanie dziedzicznie skończonych zbiorów Ackermanna jest przykładem tej techniki dla rekurencyjnie generowanej sekwencji dziedzicznie skończonych zbiorów.

Aplikacje

Wyszukiwanie informacji prywatnych

W matematycznym badaniu bezpieczeństwa komputerowego problem odzyskiwania informacji prywatnych można modelować jako problem, w którym klient, komunikując się ze zbiorem serwerów przechowujących liczbę binarną i , chce określić wynik predykatu BIT BIT ( i , j ) bez ujawniania wartości j serwerom. Chor i in. (1998) opisują metodę replikacji i na dwóch serwerach w taki sposób, że klient może rozwiązać problem odzyskiwania prywatnych informacji przy użyciu znacznie mniejszej ilości komunikacji, niż byłoby to konieczne do odzyskania pełnej wartości i .

Logika matematyczna

Predykat BIT jest często badany w kontekście logiki pierwszego rzędu , gdzie systemy logiki wynikają z dodania predykatu BIT do logiki pierwszego rzędu. W złożoności opisowej klasa złożoności FO + BIT wynikająca z dodania predykatu BIT do FO skutkuje bardziej solidną klasą złożoności. Klasa FO + BIT, logiki pierwszego rzędu z predykatem BIT, jest taka sama jak klasa FO + PLUS + CZASY, logiki pierwszego rzędu z predykatami dodawania i mnożenia.

Budowa grafu Rado

Wykres Rado: na przykład istnieje krawędź od 0 do 3, ponieważ bit 0 liczby 3 jest różny od zera.

Ackermann w 1937 i Richard Rado w 1964 użyli tego predykatu do skonstruowania nieskończonego wykresu Rado . W swojej konstrukcji wierzchołki tego grafu odpowiadają nieujemnym liczbom całkowitym zapisanym binarnie, a od wierzchołka $i$ do wierzchołka $j istnieje nieskierowana krawędź$ dla $i < j$ , gdy BIT $(j, i)$ jest niezerowe.

Otrzymany graf ma wiele ważnych właściwości: zawiera każdy skończony graf nieskierowany jako podgraf indukowany , a dowolny izomorfizm jego podgrafów indukowanych można rozszerzyć do symetrii całego grafu.