Two Boolean function problems.

摘要

The first part introduces truth table and algebraic normal form (ANF) in Boolean logaic. It, then, presents an algorithm to find the corresponding algebraic normal form given a true table, as well as the proof of correctness for this algorithm. The second part deals with the sums of the Thue-Morse sequence over arithmetic progression from theory of Boolean functions. It contains an explicit proof for the following theorem [1], stated by T.W. Cusick and P. Stanica in 01/2008, "In any finite initial string from the arithmetic progression of nonnegative integer multiples of 5 written in binary form, there are always more such integers with an even number of 1's in their binary form".