CODEWITHSUNDEEP
booleanlogical-operatorsboolean-logicxorboolean-expression
Phil
Phil

Reputation: 7607

XOR Majority Algebraic Logic

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

Upvotes: 2

Views: 901

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11322

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 |
      +---+---+---+---+

Upvotes: 2

Related Questions