Lesson 5

Using connectives \(\{\lor, \land, \neg\}\), one can build more complex propositions. The resulting propositions are called propositional formulas. Here is an example of such a formula: \[y \lor ((x \lor (\neg y)) \land z) \ .\] Here, \(x,y,z\) are elementary propositions or propositional variables. By substituting truth values for \(x,y,z\), the formula evaluates to a truth value. Thus, our formula is a function from \(\{0,1\}^{3}\) to \(\{0,1\}\). Here \(0,1\) denote falsehood and truth, respectively. This correspondence is convenient in notation and will be substantively useful (we will multiply and add these values much like integers), and is used in programming languages.