The functions considered are binary functions of 3 bits to 1 bit (extended to bit vectors, that is bitwise functions). There are $2^{(2^3)}=256$ such functions.
All the functions considered are balanced; that is, there is an equal number of input combinations for which the function outputs 0 and for which the function outputs 1. That reduces the number of functions to $8!/(4!)^2=70$.
Aggregating balanced functions identical within the $3!=6$ orders and the $2^3=8$ polarities of the $3$ inputs leaves only $6$ classes (see final section); keeping the lexicographically first function in each class:
z y x g0 g1 g2 g3 g4 g5
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1 1
0 1 1 0 1 1 1 1 0
1 0 0 1 0 1 1 1 1
1 0 1 1 1 0 1 1 0
1 1 0 1 1 1 1 0 0
1 1 1 1 1 1 0 0 1
Of these, it is excluded g0 and g4 since at least one of their input has no influence on the output. The other four functions exhibit properties that tend to be good for diffusion:
- for any of their input fixed to either polarity, the output is non-constant when we vary the other inputs;
- any of their input influences the output for at least two of the four combinations of the other inputs.
These surviving functions are:
g1 Majority, used for $f_3$ of SHA-1 and $f_2$ of SHA-2 (which turn out to be identical)g2 Choice, used for $f_1$ and $f_2$ of MD5, $f_1$ of SHA-1, $f_1$ of SHA-2; this function is also called Select, or Digital Multiplexer (input x being 1 or 0 chooses which of y or z is the output);g3, used (within order and inversion of inputs) for $f_4$ of MD5; as noted in comment, that function $(x\wedge y)\oplus z$ is also the Toffoli gate's third output;g5 Parity, used for $f_3$ of MD5, $f_2$ and $f_4$ of SHA-1.
Addition per comment: g1 and g2 additionally have the property that any of their input influences the output for at most three of the four combinations of the other inputs; or, in other words, are not fully linear w.r.t. any of their input. This is desirable in some sense, as too much linearity opens to some differential attacks. This might be why g1 and g2 are preferred to g3 and g5 in SHA-2.
A comment asks for the derivation of classes of balanced functions of 3 bits to 1 identical within order and polarity of inputs. We'll represent a function by an 8-bit value $b_{000}\,b_{001}\,b_{010}\,b_{011}\,b_{100}\,b_{101}\,b_{110}\,b_{111}$ giving the output $b_{zyx}$ for the 8 combinations of the 3 inputs $z\,y\,x$.
Balanced functions have $b_{000}+b_{001}+b_{010}+b_{011}+b_{100}+b_{101}+b_{110}+b_{111}=4$. We scan them in lexicographic order (equivalently, numerical order when using big-endian convention); if not excluded, that's the function representative of a new class, and we exclude the functions obtainable from that by permutation of inputs, or changing the polarity of inputs. We can do this by considering any of the 6 following transformations applied, or not (there's some redundancy in applying the 64 combinations and many functions are excluded multiple times, but it does not harm):
- turning output to $b_{000}\,b_{010}\,b_{001}\,b_{011}\,b_{100}\,b_{110}\,b_{101}\,b_{111}$ (exchanging $x$ and $y$)
- turning output to $b_{000}\,b_{001}\,b_{100}\,b_{101}\,b_{010}\,b_{011}\,b_{110}\,b_{111}$ (exchanging $y$ and $z$)
- turning output to $b_{000}\,b_{100}\,b_{010}\,b_{110}\,b_{001}\,b_{101}\,b_{011}\,b_{111}$ (exchanging $z$ and $x$)
- turning output to $b_{001}\,b_{000}\,b_{011}\,b_{010}\,b_{101}\,b_{100}\,b_{111}\,b_{110}$ (complementing $x$)
- turning output to $b_{010}\,b_{011}\,b_{000}\,b_{001}\,b_{110}\,b_{111}\,b_{100}\,b_{101}$ (complementing $y$)
- turning output to $b_{100}\,b_{101}\,b_{110}\,b_{111}\,b_{000}\,b_{001}\,b_{010}\,b_{011}$ (complementing $z$)
We first get 00001111 = g0, and exclude 00110011, 01010101, 10101010, 11001100, 11110000; then get 00010111 = g1, and exclude 00101011, 01001101, 01110001, 10001110, 10110010, 11010100, 11101000; and so on. In the end, there are only 6 classes.
