*A*`x`*B*:- The Cartesian product of the sets
*A*and*B*. **AND:**- The Boolean function that returns 1 if and only if every input bit is 1.
*D*(*f*):- The decision tree complexity of the function
*f*. *D*(*f*,*x*):- The minimum number of bits of input
*x*that determine the value of*f*(*x*). *D*_{0}(*f*):- The nondeterministic decision tree complexity
of verifying that
*f*(*x*) = 0. *D*_{1}(*f*):- The nondeterministic decision tree complexity
of verifying that
*f*(*x*) = 1. *N*(*f*):- The nondeterministic decision tree complexity of the function
*f*. **OR:**- The Boolean function that returns 0 if and only if every input bit is 0.
**PARITY:**- The Boolean function that returns 1 if and only if the number of 1 bits in the input is even.
**MAJORITY:**- The Boolean function that returns 1 if and only if more than half of the input bits are 1.