XOR Majority Algebraic Logic

Question

How do you implement a Majority function with XOR and AND only? How do the authors of this paper get to the equation that they present below?

Answer 1

A Majority Function with three inputs can be written as CNF (product of sums)

(a or b) and (a or c) and (b or c)

or as DNF (sum of products)

ab or ac or bc

Using AND and XOR, you can write

maj(a,b,c) = ab xor bc xor ac

A truth-table is probably the easiest way to check this. An XOR with three inputs is true, if either one input is true or all three inputs.

             ab
       00  01  11  10
      +---+---+---+---+
   0  | 0 | 0 | 1 | 0 |
c     +---+---+---+---+
   1  | 0 | 1 | 1 | 1 |
      +---+---+---+---+