6 Synthesis of Majority Expressions Through Primitive Function Manipulation
141
Table 6.6 Proof of Ω.D by perfect induction
A B C D E M(A, B, M(D, E, C)) M(M(A, B, D), M(A, B, E), M(A, B, C))
0
0
0
0
0
M(0,0,M(0,0,0)) = 0
M(M(0,0,0), M(0,0,0), M(0,0,0)) = 0
0
0
0
0
1
M(0,0,M(0,1,0)) = 0
M(M(0,0,0), M(0,0,1), M(0,0,0)) = 0
0
0
0
1
0
M(0,0,M(1,0,0)) = 0
M(M(0,0,1), M(0,0,0), M(0,0,0)) = 0
0
0
0
1
1
M(0,0,M(1,1,0)) = 0
M(M(0,0,1), M(0,0,1), M(0,0,0)) = 0
0
0
1
0
0
M(0,0,M(0,0,1)) = 0
M(M(0,0,0), M(0,0,0), M(0,0,1)) = 0
0
0
1
0
1
M(0,0,M(0,1,1)) = 0
M(M(0,0,0), M(0,0,1), M(0,0,1)) = 0
0
0
1
1
0
M(0,0,M(1,0,1)) = 0
M(M(0,0,1), M(0,0,0), M(0,0,1)) = 0
0
0
1
1
1
M(0,0,M(1,1,1)) = 0
M(M(0,0,1), M(0,0,1), M(0,0,1)) = 0
0
1
0
0
0
M(0,1,M(0,0,0)) = 0
M(M(0,1,0), M(0,1,0), M(0,1,0)) = 0
0
1
0
0
1
M(0,1,M(0,1,0)) = 0
M(M(0,1,0), M(0,1,1), M(0,1,0)) = 0
0
1
0
1
0
M(0,1,M(1,0,0)) = 0
M(M(0,1,1), M(0,1,0), M(0,0,0)) = 0
0
1
0
1
1
M(0,1,M(1,1,0)) = 1
M(M(0,1,1), M(0,1,1), M(0,1,0)) = 1
0
1
1
0
0
M(0,1,M(0,0,1)) = 0
M(M(0,1,0), M(0,1,0), M(0,1,1)) = 0
0
1
1
0
1
M(0,1,M(0,1,1)) = 1
M(M(0,1,0), M(0,1,1), M(0,1,1)) = 1
0
1
1
1
0
M(0,1,M(1,0,1)) = 1
M(M(0,1,1), M(0,1,0), M(0,1,1)) = 1
0
1
1
1
1
M(0,1,M(1,1,1)) = 1
M(M(0,1,1), M(0,1,1), M(0,1,1)) = 1
1
0
0
0
0
M(1,0,M(0,0,0)) = 0
M(M(1,0,0), M(1,0,0), M(1,0,0)) = 0
1
0
0
0
1
M(1,0,M(0,1,0)) = 0
M(M(1,0,0), M(1,0,1), M(1,0,0)) = 0
1
0
0
1
0
M(1,0,M(1,0,0)) = 0
M(M(1,0,0), M(1,0,0), M(1,0,0)) = 0
1
0
0
1
1
M(1,0,M(1,1,0)) = 1
M(M(1,0,1), M(1,0,1), M(1,0,0)) = 1
1
0
1
0
0
M(1,0,M(0,0,1)) = 0
M(M(1,0,0), M(1,0,0), M(1,0,1)) = 0
1
0
1
0
1
M(1,0,M(0,1,1)) = 1
M(M(1,0,0), M(1,0,1), M(1,0,1)) = 1
1
0
1
1
0
M(1,0,M(1,0,1)) = 1
M(M(1,0,1), M(1,0,0), M(1,0,1)) = 1
1
0
1
1
1
M(1,0,M(1,1,1)) = 1
M(M(1,0,1), M(1,0,1), M(1,0,1)) = 1
1
1
0
0
0
M(1,1,M(0,0,0)) = 1
M(M(1,1,0), M(1,1,0), M(1,1,0)) = 1
1
1
0
0
1
M(1,1,M(0,1,0)) = 1
M(M(1,1,0), M(1,1,1), M(1,1,0)) = 1
1
1
0
1
0
M(1,1,M(1,0,0)) = 1
M(M(1,1,1), M(1,1,0), M(1,1,0)) = 1
1
1
0
1
1
M(1,1,M(1,1,0)) = 1
M(M(1,1,1), M(1,1,1), M(1,1,0)) = 1
1
1
1
0
0
M(1,1,M(0,0,1)) = 1
M(M(1,1,0), M(1,1,0), M(1,1,1)) = 1
1
1
1
0
1
M(1,1,M(0,1,1)) = 1
M(M(1,1,0), M(1,1,1), M(1,1,1)) = 1
1
1
1
1
0
M(1,1,M(1,0,1)) = 1
M(M(1,1,1), M(1,1,0), M(1,1,1)) = 1
1
1
1
1
1
M(1,1,M(1,1,1)) = 1
M(M(1,1,1), M(1,1,1), M(1,1,1)) = 1
The set V represents all functions formed by a single input variable, in its
complemented form or not. Equation (6.8) shows how to calculate the number of
functions in V .
|V | = 2 · n
(6.8)
In Table 6.9, we can observe the listing of V for three input variables. The number
of input variables are represented by n. Note that the classical functions and their