Binary Truth Functions

From ProofWiki
Jump to navigation Jump to search

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$


Sources