Binary Truth Functions

Theorem

There are $16$ distinct binary truth functions:

• 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$

• 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 Truth Functions there are $2^{\left({2^2}\right)} = 16$ distinct truth 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 \\ p \impliedby q & 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({p \impliedby q}\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$