Lesson 6

Each propositional formula defines a Boolean function \(\{0,1\}^{n} \to \{0,1\}\). Let \(B_{n}\) denote the set of all Boolean functions with \(n\) inputs. Let \(B^{*}=\cup_{n=1}^{\infty}B_{n}\) denote the entire set of Boolean functions.

There are exactly sixteen Boolean functions of two variables, many of which are used as logical connectives. The table below presents the standard notations of these functions, as well as their truth tables that specify the function's values for all inputs (the inputs are usually listed in lexicographic order).