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 valuation
Discrete 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 propositional letter A a unique truth value A(A) ∈ {T, F}. Generally, a proposition is a sequence of symbols constructed according to some rules determined 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
We can infer from the example that truth valuation of a propostion is determined by those propositions which it is based on We define the following term to guarantee the truth of a compound proposition Definition 2(Valuation). A truth valuation v is a function that assigns to each proposi- tion a a unique truth value v(a) so that its value on a compound proposition is determined in accordance with the appropriate truth tables Here, we should remember that truth valuation determines all propositions generated ac- cording to definition. Especially, when a is a propositional letter we have V(a)=A(a)for some A Generally, we have the following theorem: Theorem 3. Given a truth assignment a there is a unique truth valuation v such that V(a)=A(a) for every propositional letter a Proof. The proof can be divided into two step 1. Construct a v from A by induction on the depth of the associated formation tree 2. Prove the uniqueness of v with the same A by induction bottom-up which show us the relation between truth assignment and truth valuation We now consider a specific proposition a. There is a corollary Corollary 4. If V1 and v2 are two valuations that agree on the support of a, the finite set of propositional letters used in the construction of the proposition of the proposition a, then vi(a)=v2(a) Given a proposition, there is a case that it is always true whatever the truth valuation is. Definition 5. A proposition g of propositional logic is said to be valid if for any valuation v, v(o)=T. Such a proposition is also called a tautology Example 2. aVna is a tautology Solution
We can infer from the example that truth valuation of a propostion is determined by those propositions which it is based on. We define the following term to guarantee the truth of a compound proposition. Definition 2 (Valuation). A truth valuation V is a function that assigns to each proposition α a unique truth value V(α) so that its value on a compound proposition is determined in accordance with the appropriate truth tables. Here, we should remember that truth valuation determines all propositions generated according to definition. Especially, when α is a propositional letter we have V(α) = A(α) for some A. Generally, we have the following theorem: Theorem 3. Given a truth assignment A there is a unique truth valuation V such that V(α) = A(α) for every propositional letter α. Proof. The proof can be divided into two step. 1. Construct a V from A by induction on the depth of the associated formation tree. 2. Prove the uniqueness of V with the same A by induction bottom-up. which show us the relation between truth assignment and truth valuation. We now consider a specific proposition α. There is a corollary. Corollary 4. If V1 and V2 are two valuations that agree on the support of α, the finite set of propositional letters used in the construction of the proposition of the proposition α, then V1(α) = V2(α). Given a proposition, there is a case that it is always true whatever the truth valuation is. Definition 5. A proposition σ of propositional logic is said to be valid if for any valuation V, V(σ) = T. Such a proposition is also called a tautology. Example 2. α ∨ ¬α is a tautology. Solution: α ¬α α ∨ ¬α T F T F T T 2
Ba→B na B TT F LF FFI Figure 2: Logically equivalent propositions Consider the following example Example3.a→B≡-VB. Proof. Prove by truth table in Figure 2 Although, they have different formation tree. But they are the same if they are only chan acterized by truth valuation Definition 6. Two proposition a and B such that, for every valuation v, v(a)=v(B)are called logically equivalent. We denote this by a= B 3 Consequence practice,we often mention a pattern that a result can be inferred from some facts.We now consider this pattern from the point of view of semantics Definition 7. Let 2 be a(possibly infinite) set of propositions. We say that o is a conse ence o ∑( and write as∑ha)ij, for any valuation, ((7)= T for all T∈∑)→(a)=T Example4.1.Let∑={A,=AVB}, we have∑hB 2.Let∑={A,=AVB,C},ehae∑hB 3.Let∑={AB}, e have z b. Definition 8. We say that a valuation v is a model ofe ifv(o)=T for every o EE. We denote by M(∑) the set of all models of∑ Example 5. Let 2=A, AVB, we have models 1. Let A(A)=T,A(B)=T
α β α → β T T T T F F F T T F F T α β ¬α ¬α ∨ β T T F T T F T F F T T T F F T T Figure 2: Logically equivalent propositions Consider the following example. Example 3. α → β ≡ ¬α ∨ β. Proof. Prove by truth table in Figure 2. Although, they have different formation tree. But they are the same if they are only characterized by truth valuation. Definition 6. Two proposition α and β such that, for every valuation V, V(α) = V(β) are called logically equivalent. We denote this by α ≡ β. 3 Consequence In practice, we often mention a pattern that a result can be inferred from some facts. We now consider this pattern from the point of view of semantics. Definition 7. Let Σ be a (possibly infinite) set of propositions. We say that σ is a consequence of Σ (and write as Σ |= σ) if, for any valuation V, (V(τ ) = T for all τ ∈ Σ) ⇒ V(σ) = T. Example 4. 1. Let Σ = {A, ¬A ∨ B}, we have Σ |= B. 2. Let Σ = {A, ¬A ∨ B, C}, we have Σ |= B. 3. Let Σ = {¬A ∨ B}, we have Σ 6|= B. Definition 8. We say that a valuation V is a model of Σ if V(σ) = T for every σ ∈ Σ. We denote by M(Σ) the set of all models of Σ. Example 5. Let Σ = {A, ¬A ∨ B}, we have models: 1. Let A(A) = T, A(B) = T 3
2. Let A(A)=T, A(B=T,A(C)=T 3. Let A(A)=T, A(B)=T, A(C)=F, A(D)=F, Definition 9. We say that propositions 2 is satisfiable if it has some model. Otherwise it is called invalid Proposition 10. Let 2, 21, 22 be sets of propositions. Let Cn(e) denote the set of conse quence of 2 and Taut the set of tautologies 1.∑1s∑2→Cn(1)sCn(∑2) 2.∑Cn(∑) 3. Taut CCn(∑)=Cn(Cn(∑) 4.∑1∑2→M(∑2)sM(∑1) 5.Cn(∑)={|(a)= T for all∈M∑)} 6.σ∈Cn({a1,…,on}兮a1→(02…→(n→0)…)∈Tat Theorem11. For any propositions e,v,∑∪{}y分∑Fv→ p holds. Proof. Prove by the definition of consequence With this Theorem 11, we can prove result 6 in Proposition 10 by induction Exercises 1. Check whether the following propositions are valid or not (b)A∧(BVC)分(A∧B)V(AAC) 2. Prove or refute each of the following assertions (a) If either∑haor∑hB,then∑F(aVB) (b)If∑(aAB), then both∑ F a and∑hB 3. Prove the following assertion (a)Cn(∑)=Cn(Cm(∑). (b)∑1C∑2→M(∑2)cM(∑1) (c)Cn(∑)={0|()= T for all v∈M∑)}
2. Let A(A) = T, A(B) = T, A(C) = T. 3. Let A(A) = T, A(B) = T, A(C) = F, A(D) = F, . . .. Definition 9. We say that propositions Σ is satisfiable if it has some model. Otherwise it is called invalid. Proposition 10. Let Σ, Σ1, Σ2 be sets of propositions. Let Cn(Σ) denote the set of consequence of Σ and T aut the set of tautologies. 1. Σ1 ⊆ Σ2 ⇒ Cn(Σ1) ⊆ Cn(Σ2). 2. Σ ⊆ Cn(Σ). 3. T aut ⊆ Cn(Σ) = Cn(Cn(Σ)). 4. Σ1 ⊆ Σ2 ⇒ M(Σ2) ⊆ M(Σ1). 5. Cn(Σ) = {σ|V(σ) = T for all V ∈ M(Σ)}. 6. σ ∈ Cn({σ1, . . . , σn}) ⇔ σ1 → (σ2 . . . → (σn → σ). . .) ∈ T aut. Theorem 11. For any propositions ϕ, ψ, Σ ∪ {ψ} |= ϕ ⇔ Σ |= ψ → ϕ holds. Proof. Prove by the definition of consequence. With this Theorem 11, we can prove result 6 in Proposition 10 by induction. Exercises 1. Check whether the following propositions are valid or not (a) (A → B) ↔ ((¬B) → (¬A)) (b) A ∧ (B ∨ C) ↔ (A ∧ B) ∨ (A ∧ C) 2. Prove or refute each of the following assertions: (a) If either Σ |= α or Σ |= β, then Σ |= (α ∨ β). (b) If Σ |= (α ∧ β), then both Σ |= α and Σ |= β. 3. Prove the following assertion: (a) Cn(Σ) = Cn(Cn(Σ)). (b) Σ1 ⊂ Σ2 ⇒ M(Σ2) ⊂ M(Σ1). (c) Cn(Σ) = {σ | V(σ) = T for all V ∈ M(Σ)}. 4
(d)a∈Cmn({ (an→a)…)∈Taut 4. Suppose we have two assertions, where a and B both are propostions and 2 is a set of positions (a)If∑hA,then∑hB (b)∑F(A→B Show the relation between them. It means whether one can imply another
(d) σ ∈ Cn({σ1, . . . , σn}) ⇔ σ1 → (σ2 . . . → (σn → σ). . .) ∈ T aut. 4. Suppose we have two assertions, where α and β both are propostions and Σ is a set of propositions: (a) If Σ |= A, then Σ |= B. (b) Σ |= (A → B). Show the relation between them. It means whether one can imply another. 5