Category:Algebraic normal form (image set)

This category is an image set. It should contain only images that have the same style, and should have a parent category that is purely topical.

See also: v:Algebraic normal form

Algebraic normal forms are vertical, and truth tables are horiozontal bit-patterns.
The calculation ANF to TT uses an upper triangular Sierpiński triangle with rows corresponding to ANF.
The calculation ANF from TT uses a lower triangular Sierpiński triangle with columns corresponding to TT.

The sections below illustrate cycles and fixed points in Zhegalkin permutation Ж₃.
(It is a Walsh permutation corresponding to the 8×8 lower triangular Sierpiński triangle. It has 120 transpositions and 16 fixed points.)

This permutation is the self-inverse map between integers representing ANFs and truth tables of length 8.
(The pairs of bit-patterns are the same, no matter which is intepreted as ANF or TT.)

cycle (110, 142)
0111 0110 _{little-endian binary} = 110 _decimal 0111 0001 _{little-endian binary} = 142 _decimal ANF 142 to TT 110 ANF 142 from TT 110 ANF 110 to TT 142 ANF 110 from TT 142

cycle (143, 145)
1111 0001 _{little-endian binary} = 143 _decimal 1000 1001 _{little-endian binary} = 145 _decimal ANF 143 to TT 145 ANF 143 from TT 145 ANF 145 to TT 143 ANF 145 from TT 143

cycle (22, 150)
0110 1000 _{little-endian binary} = 22 _decimal 0110 1001 _{little-endian binary} = 150 _decimal ANF 22 to TT 150 ANF 22 from TT 150 ANF 150 to TT 22 ANF 150 from TT 22

fixed point 30
0111 1000 _{little-endian binary} = 30 _decimal ANF 30 to TT 30 ANF 30 from TT 30

compared to prefects
AND XNOR 8 Walsh functions (left) and their complements (right) The yellow matrix used to convert an ANF to its Boolean function is a Sierpiński triangle. Its rows are variadic ANDs. Instead using a matrix whose rows are variadic biconditionals (XNOR) also creates a Boolean function. It is always a linear function, i.e. either a Walsh function (variadic XOR) or its complement. So every Boolean function can be assigned a linear Boolean function, which shall be called its prefect. Sets of functions with the same prefect shall be called prefectures. (Linear functions are assigned to themselves. So each prefecture is named after the linear function it contains.) The 16 2-ary functions are partitioned into 2⋅4=8 prefectures, each with 2 functions. The 256 3-ary functions are partitioned into 2⋅8=16 prefectures, each with 16 functions. The 65536 4-ary functions are partitioned into 2⋅16=32 prefectures, each with 2048 functions.
ANF 123 to TT 77	ANF 38 to TT 198	ANF 142 to TT 110
ANF 123 to prefect 5	ANF 38 to prefect ¬6	ANF 142 to prefect ¬7