# Binary Truth Functions

Jump to navigation Jump to search

## Theorem

There are $16$ distinct binary truth functions:

• Two projections:
• $\map {\pr_1} {p, q} = p$
• $\map {\pr_2} {p, q} = q$
• Two negated projections:
• $\map {\overline {\pr_1} } {p, q} = \neg p$
• $\map {\overline {\pr_2} } {p, q} = \neg q$

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

## Proof

From Count of Truth Functions there are $2^{\paren {2^2} } = 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 \map {f_\T} {p, q} & \T & \T & \T & \T \\ p \lor q & \T & \T & \T & \F \\ p \impliedby q & \T & \T & \F & \T \\ \map {\pr_1} {p, q} & \T & \T & \F & \F \\ p \implies q & \T & \F & \T & \T \\ \map {\pr_2} {p, q} & \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 \\ \map \neg {p \iff q} & \F & \T & \T & \F \\ \map {\overline {\pr_2} } {p, q} & \F & \T & \F & \T \\ \map \neg {p \implies q} & \F & \T & \F & \F \\ \map {\overline {\pr_1} } {p, q} & \F & \F & \T & \T \\ \map \neg {p \impliedby q} & \F & \F & \T & \F \\ p \downarrow q & \F & \F & \F & \T \\ \map {f_\F} {p, q} & \F & \F & \F & \F \\ \hline \end{array}$

That accounts for all $16$ of them.

$\blacksquare$