Discrete Mathematics(Il) Spring 2013 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)EIT, 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 Example 1. Truth assignment of a and B and valuation of(avB) B(avB) Figure 1: Truth assignment and valuation
Discrete Mathematics (II) Spring 2013 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 ions which it is based 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 of well-defined proposition. 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 n assignment a there is a unique truth valuation v such that V(a)=A(a)for every sitional letter a Proof. The proof can be divided into two step 1. Construct a 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 It shows us the relation between truth assignment and truth valuation. Actually, truth assignment and valuation characterize the semantics of proposition logic from different views For simplicity of theory, one is enough. For convenience, both are needed to make statement Specially, we just consider a specific proposition a. Then there are only finite propositional letters taken into consideration. There is a corollary Corollary 4. If Vi 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 n(a)=2(a Two valuation are different. But when the assignments determined agree with each other on support. They have the same truth value on a proposition Given a proposition, there is a case that it is always true whatever the truth valuation is Definition 5. A proposition o 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
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 of well-defined proposition. 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. It shows us the relation between truth assignment and truth valuation. Actually, truth assignment and valuation characterize the semantics of proposition logic from different views. For simplicity of theory, one is enough. For convenience, both are needed to make statement simple. Specially, we just consider a specific proposition α. Then there are only finite propositional letters taken into consideration. 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(α). Two valuation are different. But when the assignments determined agree with each other on support. They have the same truth value on a proposition. 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. 2
aBa→B aTT Bina B FF FFT Figure 2: Logically equivalent propositions Solution This tautology can not convey useful information. Because we just talk about both right and wrong side together. In many cases, we do think tautology nonsense. But it represents a very special set of propositions with an invariant feature Syntax of proposition logic make sure that two string are the same proposition if they are the same symbol sequence. Semantics will bring us more profound result. Consider the following example Example3.a→B≡aaVB. Proof. Prove by truth table in Figure 2 Although, they have different formation tree. But they are the same if they are only char 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 C= B With is definition, we can construct tautologies as many as possible. For a= B can be represented as a proposition a<>B 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
α β α → β T T T T F F F T T F F T α β ¬α ¬α ∨ β T T F T T F F F F T T T F F T T Figure 2: Logically equivalent propositions Solution: α ¬α α ∨ ¬α T F T F T T This tautology can not convey useful information. Because we just talk about both right and wrong side together. In many cases, we do think tautology nonsense. But it represents a very special set of propositions with an invariant feature. Syntax of proposition logic make sure that two string are the same proposition if they are the same symbol sequence. Semantics will bring us more profound result. 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 α ≡ β. With is definition, we can construct tautologies as many as possible. For α ≡ β can be represented as a proposition α ↔ β. 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. 3
Definition 7. Let y be a(possibly infinite) set of propositions. We say that o is a conse quence of 2(and write as 2ho) if, for any valuation V, D()= T for all T∈∑)→以(a)=T Especially when 2=0, its consequences are tautologies. For o must be satisfied by every truth valuati Another extreme case is that no truth valuation can satisfy all propositions in 2, which is also called unsatified defined later. Then every proposition is its consequence. Sometimes we call it vacuum/null satisfaction. It is mentioned for completeness for it can't give us some positive result Example 4. Consider the following eramples 1.Let∑={AVB}, we have∑≠B 2.Let∑={A,wAB}, we have∑hB 3.Let∑={A,AVB,C}, we have∑B. Definition 8. We say that a valuation v is a model of2 if v(o)=T for every o E2. We denote by M(∑) the set of all models of∑ Example 5. Let 2=A, AVB, we have following models 1. Let A(A)=T, A(B)=T 2.LetA(4)=T,A(B)=T,4(C)=T 3. Let A(A)=T, A(B)=T, A(C)=F, A(D)=F, Here just lists three of all models. It shows us that there are models as many as you wish once you can introduce new propositional letters. Actually the satisfaction depends only on its support set. So we just apply Corollary 4 in practice Definition 9. We say that propositions 2 is satisfiable if it has some model. Otherwise it is called invalid Reviewing example 4, we find that more consequence can be derived when 2 has more propositions. generally, we have the following properties 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.∑1g∑2→Cmn(∑1)sCn(2)
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. Especially when Σ = ∅, its consequences are tautologies. For σ must be satisfied by every truth valuation. Another extreme case is that no truth valuation can satisfy all propositions in Σ, which is also called unsatified defined later. Then every proposition is its consequence. Sometimes we call it vacuum/null satisfaction. It is mentioned for completeness for it can’t give us some positive result. Example 4. Consider the following examples: 1. Let Σ = {¬A ∨ B}, we have Σ ̸|= B. 2. Let Σ = {A, ¬A ∨ B}, we have Σ |= B. 3. Let Σ = {A, ¬A ∨ B, C}, we have Σ |= 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 following models: 1. Let A(A) = T, A(B) = T 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, . . .. Here just lists three of all models. It shows us that there are models as many as you wish once you can introduce new propositional letters. Actually the satisfaction depends only on its support set. So we just apply Corollary 4 in practice. Definition 9. We say that propositions Σ is satisfiable if it has some model. Otherwise it is called invalid. Reviewing example 4, we find that more consequence can be derived when Σ has more propositions. Generally, we have the following properties. 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). 4
2.∑gCm(∑) 3. Taut CCn(∑)=Cm(Cn(∑) 4.∑1∑2→M(∑2)sM(∑1) 5.Cn(∑)={|(o)= T for all v∈M(∑)} 6.σ∈Cm({σ1,,on})兮σ1→(02…→(an→a)…)∈Taat Proof. Proof of all except the property 6 just follows the definition of consequence. And you also need apply the techniques proving two sets which are equal Theorem11. For any propositions e,v,∑∪{}y分∑Fv→ yp holds Proof. Prove by the definition of consequence When we consider=, v which satisfy 2 are divided into two parts, V1(y)=T and v2() F. Then we investigate whether V satisfies y-p Conversely, v which makes v false are discarded. Because they are not taken into consider ation to satisfy∑U{} 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∧(BVC)分(A∧B)V(AAC 2. Prove or refute each of the following assertions (a) If either∑haor∑hB,then∑(aVB) (b)If∑(a∧B), then both∑aand∑hB 3. Prove the following assertio (a)Cm(∑)=Cm(Cn(∑). (b)∑1C∑→M(∑2)cM(∑1) (c)Cn(∑)={(0)= T for all k∈M(∑)} (d)a∈Cn({1,…,an})兮σ1→(2…→(n→a)…)∈Tat. 4. Suppose we have two assertions, where a and B both are propositions and 2 is a set of propositions
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. Proof. Proof of all except the property 6 just follows the definition of consequence. And you also need apply the techniques proving two sets which are equal. Theorem 11. For any propositions φ, ψ, Σ ∪ {ψ} |= φ ⇔ Σ |= ψ → φ holds. Proof. Prove by the definition of consequence. When we consider ⇒, V which satisfy Σ are divided into two parts, V1(ψ) = T and V2(ψ) = F. Then we investigate whether V satisfies ψ → φ. Conversely, V which makes ψ false are discarded. Because they are not taken into consideration to satisfy Σ ∪ {ψ}. 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(Σ)}. (d) σ ∈ Cn({σ1, . . . , σn}) ⇔ σ1 → (σ2 . . . → (σn → σ). . .) ∈ T aut. 4. Suppose we have two assertions, where α and β both are propositions and Σ is a set of propositions: 5
(a) If Eh A,then∑FB. (b)∑F(A→B) Show the relation between them. It means whether one can imply another
(a) If Σ |= A, then Σ |= B. (b) Σ |= (A → B). Show the relation between them. It means whether one can imply another. 6