144
E. C. Ferraz et al.
Table 6.12 Complete list of primitives for n = 3
N
Classic function Majority function N
Classic function
Majority function
1
0
0
21 A + B
M(A, B, 1)
2
1
1
22 A + B
M(A, B, 1)
3
A
A
23 A + B
M(A, B, 1)
4
B
B
24 A + B
M(A, B, 0)
5
C
C
25 A + C
M(A, 0, C)
6
A
A
26 A + C
M(A, 1, C)
7
B
B
27 A + C
M(A, 1, C)
8
C
C
28 A + C
M(A, 0, C)
9
A · B
M(A, B, 0)
29 B + C
M(1, B, C)
10 A · B
M(A, B, 0)
30 B + C
M(1, B, C)
11 A · B
M(A, B, 0)
31 B + C
M(1, B, C)
12 A · B
M(A, B, 1)
32 B + C
M(0, B, C)
13 A · C
M(A, 0, C)
33 AB + AC + BC
M(A, B, C)
14 A · C
M(A, 0, C)
34 A · B + A · C + B · C M(A, B, C)
15 A · C
M(A, 0, C)
35 A · B + A · C + B · C M(A, B, C)
16 A · C
M(A, 1, C)
36 A · B + A · C + B · C M(A, B, C)
17 B · C
M(0, B, C)
37 A · B + A · C + B · C M(A, B, C)
18 B · C
M(0, B, C)
38 A · B + A · C + B · C M(A, B, C)
19 B · C
M(0, B, C)
39 A · B + A · C + B · C M(A, B, C)
20 B · C
M(1, B, C)
40 A · B + A · C + B · C M(A, B, C)
Table 6.12 shows the complete primitives table for n = 3. Note that |C| + |V | +
|G| + |T | = 40.
6.3 The MP C Algorithm
In this section we propose the MP C algorithm. The MP C receives a truth table
f as input and returns a majority function that covers the same set of minterms.
To generate a valid output function we use the expression M(X 1 , X 2 , X 3 ). Each
variable X c , where 1 ≤ c ≤ 3, represents a majority primitive or a 2-level majority
function.
6.3.1 Tables Formulation
The first step of MP C is the tables formulation phase, where the functions used to
build M(X 1 , X 2 , X 3 ) are formulated. The algorithm receives an input truth table
f , identifies the number of input variables, represented by n, and generates the