Discrete Mathematics(Il) Spring 2012 Lecture 6: Truth Assignments and valuations 1 Overview In this lecture, we define truth assignments and valuations in order to get rid of truth table, which is tedious. Finally, a truth valuation can be determined uniquely by a truth assignment. Sometimes, we call it the semantics of propositional logic. Correspondingly, well-defined proposition is called the syntax of propositional logic Given a set of propositions and a proposition, we can bind them in the point of view of truth valuation. Here we only connect them by truth valuation but syntax 2 Assignments and valuations Propositional letters are the simplest propositions. There is no constraint between each other. We just define an operation, called assignment, which assigns a value true or false on every propositional letter Definition 1(Assignment). A truth assignment A is a function that assigns to each propo sitional letter Aa unique truth value A(AEIT, FI Generally, a proposition is a sequence of symbols constructed according to some rules de- termined in previous lecture. Whether it is true or false can not be simply assigned like propositional letters Consider an example in Figure 1 Example 1. Truth assignment of a and B and valuation of(av B) TT T F F Figure 1: Truth assignment and valuationDiscrete Mathematics (II) Spring 2012 Lecture 6: Truth Assignments and Valuations Lecturer: Yi Li 1 Overview In this lecture, we define truth assignments and valuations in order to get rid of truth table, which is tedious. Finally, a truth valuation can be determined uniquely by a truth assignment. Sometimes, we call it the semantics of propositional logic. Correspondingly, well-defined proposition is called the syntax of propositional logic. Given a set of propositions and a proposition, we can bind them in the point of view of truth valuation. Here we only connect them by truth valuation but syntax. 2 Assignments and Valuations Propositional letters are the simplest propositions. There is no constraint between each other. We just define an operation, called assignment, which assigns a value true or false on every propositional letter. Definition 1 (Assignment). A truth assignment A is a function that assigns to each propo￾sitional letter A a unique truth value A(A) ∈ {T, F}. Generally, a proposition is a sequence of symbols constructed according to some rules de￾termined in previous lecture. Whether it is true or false can not be simply assigned like propositional letters. Consider an example in Figure 1. Example 1. Truth assignment of α and β and valuation of (α ∨ β). α β (α ∨ β) T T T T F T F T T F F F Figure 1: Truth assignment and valuation 1