Binary Boolean Functions

Theorem

There are $16$ distinct binary boolean functions:

• Two constant functions:
  • $f_F \left({p, q}\right) = F$
  • $f_T \left({p, q}\right) = T$

• Two projections:
  • $\operatorname{pr}_1 \left({p, q}\right) = p$
  • $\operatorname{pr}_2 \left({p, q}\right) = q$

• Two negated projections:
  • $\overline {\operatorname{pr}_1} \left({p, q}\right) = \neg p$
  • $\overline {\operatorname{pr}_2} \left({p, q}\right) = \neg q$

• The conjunction: $p \land q$
• The disjunction: $p \lor q$

• Two conditionals:
  • $p \implies q$
  • $q \implies p$

• The equivalence: $p \iff q$
• The exclusive or: $\neg \left({p \iff q}\right)$

• Two negated conditionals:
  • $\neg \left({p \implies q}\right)$
  • $\neg \left({q \implies p}\right)$

• The NAND: $p \uparrow q$
• The NOR: $p \downarrow q$

Proof

From Count of Boolean Functions there are $2^{\left({2^2}\right)} = 16$ distinct boolean functions on $2$ variables.

These can be depicted in a truth table as follows:

$\begin{array}{|r|cccc|} \hline p & T & T & F & F \\ q & T & F & T & F \\ \hline f_T \left({p, q}\right) & T & T & T & T \\ p \lor q & T & T & T & F \\ q \implies p & T & T & F & T \\ \operatorname{pr}_1 \left({p, q}\right) & T & T & F & F \\ p \implies q & T & F & T & T \\ \operatorname{pr}_2 \left({p, q}\right) & T & F & T & F \\ p \iff q & T & F & F & T \\ p \land q & T & F & F & F \\ p \uparrow q & F & T & T & T \\ \neg \left({p \iff q}\right) & F & T & T & F \\ \overline {\operatorname{pr}_2} \left({p, q}\right) & F & T & F & T \\ \neg \left({p \implies q}\right) & F & T & F & F \\ \overline {\operatorname{pr}_1} \left({p, q}\right) & F & F & T & T \\ \neg \left({q \implies p}\right) & F & F & T & F \\ p \downarrow q & F & F & F & T \\ f_F \left({p, q}\right) & F & F & F & F \\ \hline \end{array}$

That accounts for all sixteen of them.

$\blacksquare$