Get the latest tech news
Minimal Boolean Formulas (2011)
Posted on Wednesday, May 18, 2011. 28.
Function Truth Table ( f= f(V, W, X, Y, Z)) f(¬V, W, X, Y, Z)(f&0x55555555)<< 1 | (f>> 1)&0x55555555 f(V, ¬W, X, Y, Z)(f&0x33333333)<< 2 | (f>> 2)&0x33333333 f(V, W, ¬X, Y, Z)(f&0x0f0f0f0f)<< 4 | (f>> 4)&0x0f0f0f0f f(V, W, X, ¬Y, Z)(f&0x00ff00ff)<< 8 | (f>> 8)&0x00ff00ff f(V, W, X, Y, ¬Z)(f&0x0000ffff)<<16 | (f>>16)&0x0000ffff Being able to invert a specific input lets us consider all possible inversions by building them up one at a time. Function Truth Table ( f= f(V, W, X, Y, Z)) f( W, V, X, Y, Z) f&0x99999999 | (f&0x22222222)<<1 | (f>>1)&0x22222222 f(V, X, W, Y, Z) f&0xc3c3c3c3 | (f&0x0c0c0c0c)<<1 | (f>>1)&0x0c0c0c0c f(V, W, Y, X, Z) f&0xf00ff00f | (f&0x00f000f0)<<1 | (f>>1)&0x00f000f0 f(V, W, X, Z, Y) f&0xff0000ff | (f&0x0000ff00)<<8 | (f>>8)&0x0000ff00 Being able to swap a pair of adjacent inputs lets us consider all possible permutations by building them up one at a time. The most convenient for our purposes is Algorithm P, which generates a sequence that considers all permutations exactly once with only a single swap of adjacent inputs between steps.
Or read this on Hacker News