142
E. C. Ferraz et al.
Table 6.7 Proof of Ω.I by
perfect induction
A B C M(A, B, C) M(A, B, C)
0 0 0 1
1
0 0 1 1
1
0 1 0 1
1
0 1 1 0
0
1 0 0 1
1
1 0 1 0
0
1 1 0 0
0
1 1 1 0
0
Table 6.8 Proof of Ω.M by
perfect induction
A B M(A, A, B) = A M(A, A, B) = B
0 0 M(0,0,0) = 0
M(0,1,0) = 0
0 1 M(0,0,1) = 0
M(0,1,1) = 1
1 0 M(1,1,0) = 1
M(1,0,0) = 0
1 1 M(1,1,1) = 1
M(1,0,1) = 1
Table 6.9 List of set V for
n = 3
Classic function Majority function
A
A
B
B
C
C
A
A
B
B
C
C
corresponding majority forms are equal because the V set is composed only by
functions without operators.
The set G is formed by functions with a single AN D or OR operator, having
a total of 2 input variables. The number of functions in G can be calculated
by Eq. (6.9). The variables E and O represent the possible combinations of
inputs, for AN D and OR operations, respectively. For n = 3, we have E =
{A · B, A · C, B · C} and O = {A + B, A + C, B + C}. Each combination has
4 inversion variations, the combination A + B, for example, has the variations
A + B, A + B, A + B, A + B
.
|G| = (4 · |E|) + (4 · |O|)
(6.9)
In Table 6.10, we present the functions in G for n = 3.
The set T represents functions with a single majority gate, no constant value and
no repeated variable as input. Equation (6.10) calculates the number of functions in
T . The variable t represents the number of possible combinations among the input