138
E. C. Ferraz et al.
Table 6.1 Example of a
majority operation
X Y Z M(X, Y, Z)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Table 6.2 Generation of
functions AN D and OR
B C B · C M(0, B, C) B + C M(1, B, C)
0 0 0
0
0
0
0 1 0
0
1
1
1 0 0
0
1
1
1 1 1
1
1
1
Table 6.3 Equivalence
between M(A, B, C) and its
dual form
A B C M(A, B, C) M(A, B, C)
0 0 0 0
0
0 0 1 0
0
0 1 0 0
0
0 1 1 1
1
1 0 0 0
0
1 0 1 1
1
1 1 0 1
1
1 1 1 1
1
Majority functions are also self-dual functions, meaning that a majority function
is always equivalent to its dual form. A function’s dual form can be obtained by
complementing all input variables and gates [13]. For example, the function (X ·
Y ) + (X · Z) is equal to its dual form (X + Y ) · (X + Z).
Table 6.3 shows the equivalence between a majority function M(A, B, C) and
its dual form M(A, B, C).
6.2.1 Axiomatization of Majority Functions (Ω)
The set of axioms that defines the majority algebra is represented by Ω and
can be divided into axioms of Commutativity, Associativity, Distribution, Inverter
Propagation, and Majority [4]. Every axiom in Ω can be proved by perfect
induction.