Boolean lattice

Boolean lattice (plural Boolean lattices)

  1. (algebra) The lattice corresponding to a Boolean algebra.
    A Boolean lattice always has 2n elements for some cardinal number 'n', and if two Boolean lattices have the same size, then they are isomorphic. A Boolean lattice can be defined "inductively" as follows: the base case could be the "degenerate" Boolean lattice consisting of just one element. This element is less than or equal to itself, which reflects the first "law of thought". Inductive step: given the structure of a 2n-element Boolean lattice, make an exact and separate duplicate of it, which preserves the order relation isomorphically. Then connect the two lattices as follows: choose one as the "bottom" and one as the "top", then draw an arrow connecting each element of the "bottom" lattice to its corresponding element of the "top" lattice. The result is the 2n+1-element Boolean lattice (unique up to order-isomorphism). The 0 of the bottom lattice becomes the new 0, and the 1 of the top lattice becomes the new 1. Note that the 4-element (Boolean) lattice is a square, the 8-element lattice is a cube, the 16-element lattice is a tesseract, and higher-order lattices are higher-dimensional hypercubes in general, with the 0 and 1 always diagonally opposite, i.e., at the highest possible Hamming/taxicab distance from each other (equal to 'n' for an n-dimensional hypercube) and the edges directed so as to connect the vertex closer to 0 to the vertex further away from 0 (in terms of Hamming/taxicab distance).

This text is extracted from the Wiktionary and it is available under the CC BY-SA 3.0 license | Terms and conditions | Privacy policy 0.048
Offline English dictionary