140
E. C. Ferraz et al.
Table 6.5 Proof of Ω.A by perfect induction
A
B
C
D
M(A, D, M(B, D, C))
M(C, D, M(B, D, A))
0
0
0
0
M(0,0,M(0,0,0)) = 0
M(0,0,M(0,0,0)) = 0
0
0
0
1
M(0,1,M(0,1,0)) = 0
M(0,1,M(0,1,0)) = 0
0
0
1
0
M(0,0,M(0,0,1)) = 0
M(1,0,M(0,0,0)) = 0
0
0
1
1
M(0,1,M(0,1,1)) = 1
M(1,1,M(0,1,0)) = 1
0
1
0
0
M(0,0,M(1,0,0)) = 0
M(0,0,M(1,0,0)) = 0
0
1
0
1
M(0,1,M(1,1,0)) = 1
M(0,1,M(1,1,0)) = 1
0
1
1
0
M(0,0,M(1,0,1)) = 0
M(1,0,M(1,0,0)) = 0
0
1
1
1
M(0,1,M(1,1,1)) = 1
M(1,1,M(1,1,0)) = 1
1
0
0
0
M(1,0,M(0,0,0)) = 0
M(0,0,M(0,0,1)) = 0
1
0
0
1
M(1,0,M(0,0,1)) = 0
M(1,1,M(0,1,0)) = 0
1
0
1
0
M(1,0,M(0,1,0)) = 0
M(1,0,M(1,0,1)) = 0
1
0
1
1
M(1,1,M(0,1,1)) = 1
M(1,1,M(0,1,1)) = 1
1
1
0
0
M(1,0,M(1,0,0)) = 0
M(0,0,M(1,0,1)) = 0
1
1
0
1
M(1,1,M(1,1,0)) = 1
M(0,1,M(1,1,1)) = 1
1
1
1
0
M(1,0,M(1,0,1)) = 1
M(1,0,M(1,0,1)) = 1
1
1
1
1
M(1,1,M(1,1,1)) = 1
M(1,1,M(1,1,1)) = 1
Equation (6.7) shows that the output value will be equal to the tie-breaking variable
in functions with the same number of true and false values.
M(A, A, B) = A
(6.6)
M(A, A, B) = B
(6.7)
Table 6.8 proves Ω.M by perfect induction.
6.2.2 Primitive Majority Functions
Primitive functions can be obtained by a single gate. In the majority algebra,
primitive functions (also called primitives) can be used as a base for the construction
of more complex functions. All primitives can be obtained from the sets C, V , G,
and T , where each set corresponds to functions with a specific number of inputs.
The total number of primitives is obtained by summing the functions in C, V , G,
and T [20].
The set C represents functions with no input variables, covering the constants 0
and 1. Therefore, |C| = 2.
E. C. Ferraz et al.
Table 6.5 Proof of Ω.A by perfect induction
A
B
C
D
M(A, D, M(B, D, C))
M(C, D, M(B, D, A))
0
0
0
0
M(0,0,M(0,0,0)) = 0
M(0,0,M(0,0,0)) = 0
0
0
0
1
M(0,1,M(0,1,0)) = 0
M(0,1,M(0,1,0)) = 0
0
0
1
0
M(0,0,M(0,0,1)) = 0
M(1,0,M(0,0,0)) = 0
0
0
1
1
M(0,1,M(0,1,1)) = 1
M(1,1,M(0,1,0)) = 1
0
1
0
0
M(0,0,M(1,0,0)) = 0
M(0,0,M(1,0,0)) = 0
0
1
0
1
M(0,1,M(1,1,0)) = 1
M(0,1,M(1,1,0)) = 1
0
1
1
0
M(0,0,M(1,0,1)) = 0
M(1,0,M(1,0,0)) = 0
0
1
1
1
M(0,1,M(1,1,1)) = 1
M(1,1,M(1,1,0)) = 1
1
0
0
0
M(1,0,M(0,0,0)) = 0
M(0,0,M(0,0,1)) = 0
1
0
0
1
M(1,0,M(0,0,1)) = 0
M(1,1,M(0,1,0)) = 0
1
0
1
0
M(1,0,M(0,1,0)) = 0
M(1,0,M(1,0,1)) = 0
1
0
1
1
M(1,1,M(0,1,1)) = 1
M(1,1,M(0,1,1)) = 1
1
1
0
0
M(1,0,M(1,0,0)) = 0
M(0,0,M(1,0,1)) = 0
1
1
0
1
M(1,1,M(1,1,0)) = 1
M(0,1,M(1,1,1)) = 1
1
1
1
0
M(1,0,M(1,0,1)) = 1
M(1,0,M(1,0,1)) = 1
1
1
1
1
M(1,1,M(1,1,1)) = 1
M(1,1,M(1,1,1)) = 1
Equation (6.7) shows that the output value will be equal to the tie-breaking variable
in functions with the same number of true and false values.
M(A, A, B) = A
(6.6)
M(A, A, B) = B
(6.7)
Table 6.8 proves Ω.M by perfect induction.
6.2.2 Primitive Majority Functions
Primitive functions can be obtained by a single gate. In the majority algebra,
primitive functions (also called primitives) can be used as a base for the construction
of more complex functions. All primitives can be obtained from the sets C, V , G,
and T , where each set corresponds to functions with a specific number of inputs.
The total number of primitives is obtained by summing the functions in C, V , G,
and T [20].
The set C represents functions with no input variables, covering the constants 0
and 1. Therefore, |C| = 2.