1 Parity Functions and Terminals

Logical functions are used to determine parity in the binary bit strings. The typical functions used include:

• and(a,b) : returns 1 if a and b are 1, else 0,
• or(a,b) : returns 1 if a or b are 1, else 0,
• nand(a,b) : returns 0 if a and b are 1, else 1.
• nor(a,b) : returns 0 if a or b are 1, else 1.

In the Parity problem, the terminals representing the $n$ bits are denoted as:

• D1,...,D$n$.