Discrete Mathematics(II) Spring 2012 Lecture 4: Proposition, Connectives and Truth Tables Lecturer. yil 1 Overview In last lecture, we give a brief introduction to mathematical logic and then redefine order and tree which has minor differences with the structures presented in last semester In this lecture, we discuss sentential logic. Topics focus first on the syntax of proposition. Semantics would be discussed shallowly. And the Adequacy Theorem is a very important theorem 2 Propositions What is a proposition? It is the base of proposition logic. We should define clearly the object discussed in our class. Rethinking about every day language, especially the English, we need define some elementary objects to construct some complicated one before starting to learn the language Let's consider the following statements I am a student 2.I am not a student 3. I am a student and I study computer science. 4. I am a boy or I am a girl. 5. If i am a student. i have a class in a week 6. I am student if and only if I am a member of some university They are the statements in our life. "I am a student"is just declarative. And"I am not a student" Ist denies the former one However, we do not consider the statements like the following 1. Are you a student? 2. Sit down please. 3. What are you doing? Why we do not handle the sentence like"are you a student? " Because it is not determined or it is not declarative. all these statements are not declarative We first define a proposition letter, which represents a statement and claims one thing. For xample," I am a student"is a sentence. But" I am a boy or I am a girl"is hard to say because it is not as simple as"I am a student". Proposition letter is something like a word in a sentence. It ant be divide into more basic one
Discrete Mathematics (II) Spring 2012 Lecture 4: Proposition, Connectives and Truth Tables Lecturer: Yi Li 1 Overview In last lecture, we give a brief introduction to mathematical logic and then redefine order and tree, which has minor differences with the structures presented in last semester. In this lecture, we discuss sentential logic. Topics focus first on the syntax of proposition. Semantics would be discussed shallowly. And the Adequacy Theorem is a very important theorem. 2 Propositions What is a proposition? It is the base of proposition logic. We should define clearly the object discussed in our class. Rethinking about every day language, especially the English, we need define some elementary objects to construct some complicated one before starting to learn the language. Let’s consider the following statements: 1. I am a student. 2. I am not a student. 3. I am a student and I study computer science. 4. I am a boy or I am a girl. 5. If I am a student, I have a class in a week. 6. I am student if and only if I am a member of some university. They are the statements in our life. ”I am a student” is just declarative. And ”I am not a student” just denies the former one. However, we do not consider the statements like the following: 1. Are you a student? 2. Sit down please. 3. What are you doing? Why we do not handle the sentence like ”are you a student?”. Because it is not determined or it is not declarative. All these statements are not declarative. We first define a proposition letter, which represents a statement and claims one thing. For example, ”I am a student” is a sentence. But ”I am a boy or I am a girl” is hard to say because it is not as simple as ”I am a student”. Proposition letter is something like a word in a sentence. It can’t be divide into more basic one. 1
A sentence is composed of some words linked by some function word such as verbal word, just like I am a student and I study computer science". To describe a complicated case, we need some word such as and, or, and if . not..., which are called conjunctions. Furthermore, if some more complicated scenario is to be depicted, we may need several sentences, a paragraph, which separated by a series of punctuation We also need define some symbols in propositional logic Definition 1. The language of propositional logic consists of the following symbols 1. Connectives:V,∧,→,→,分 the 3. Propositional Letters: A, A1, A2,..., B, B1, B2, There we suppose the set of proposition letters is countable, which is reasonable for human can hardly grasp uncountable set book. We also define a inductive approach to construct a proposito tence, a paragraph, even a There are many words. But we need the grammar to write a ser Definition 2(Proposition). A proposition is a sequence of many symbols which can be constructed in the following approach 1. Propositional letters are propositions. 2. if a and B are propositions, then(avB),(aAB), (a),(a-B)and(a +B)are propositions 3. A string of symbols is a proposition if and only if it can be obtained by starting with propo tional letters(1)and repeatedly applying(2) It is obvious that infinite propositions can be generated even if there are only finite proposition Actually, there are more strings(a sequence of symbols defined in Definition 1)than those generated according to Definition 2 Example 1. Given the following strings, check whether it is a proposition 1.(AVB),(A∧B)→C) 2.AV-,(A∧B In practice, we also admit A V B as a valid proposition. But it is not generated to definition of proposition. So we give a definition of those propositions generated according to definition Definition 3. The proposition constructed according to Definition 2 is well-defined or well-formed We call them well-formed because of their good properties, which are good for us to design some procedure to recognize a proposition. This is a topic in the next lec
A sentence is composed of some words linked by some function word such as verbal word, just like ”I am a student and I study computer science”. To describe a complicated case, we need some word such as and, or, and if. . . not . . . , which are called conjunctions. Furthermore, if some more complicated scenario is to be depicted, we may need several sentences, a paragraph, which is separated by a series of punctuation. We also need define some symbols in propositional logic. Definition 1. The language of propositional logic consists of the following symbols: 1. Connectives: ∨, ∧, ¬, →, ↔ 2. Parentheses: ), ( 3. Propositional Letters: A, A1, A2, · · · , B, B1, B2, · · · . where we suppose the set of proposition letters is countable, which is reasonable for human can hardly grasp uncountable set. There are many words. But we need the grammar to write a sentence, a paragraph, even a book. We also define a inductive approach to construct a proposition. Definition 2 (Proposition). A proposition is a sequence of many symbols which can be constructed in the following approach: 1. Propositional letters are propositions. 2. if α and β are propositions, then (α∨β),(α∧β),(¬α),(α → β) and (α ↔ β) are propositions. 3. A string of symbols is a proposition if and only if it can be obtained by starting with propositional letters (1) and repeatedly applying (2). It is obvious that infinite propositions can be generated even if there are only finite proposition letters. Actually, there are more strings (a sequence of symbols defined in Definition 1) than those generated according to Definition 2. Example 1. Given the following strings, check whether it is a proposition. 1. (A ∨ B),((A ∧ B) → C) . 2. A ∨ ¬,(A ∧ B In practice, we also admit A ∨ B as a valid proposition. But it is not generated according to definition of proposition. So we give a definition of those propositions generated according to definition. Definition 3. The proposition constructed according to Definition 2 is well-defined or well-formed. We call them well-formed because of their good properties, which are good for us to design some procedure to recognize a proposition. This is a topic in the next lecture. 2
3 Truth table We only consider two value logic. It means for any proposition it is whether true or false. S it is clear for propositional letters. For connectives is concerned, the semantics of a proposition other than propositional letter is not self-evident. We define the following truth tables for a given connectives We first define the truth table of unary connective - It is easy to understand and to find the T F Figure 1: Truth table of unary connective corresponding example in our life. Conjunction and disjunction both are easy to be understood. They have the following truth table. Actually, we can find that V and A obey De Morgan Law. BTF a∧B (a)Disjunction V (b) Conjunction∧ Figure 2: Truth table of binary connectives However. the truth table of- is not well understandable. but the truth table of bi-condition (equality) is intuitive to be understood. In table, a is called premise and B is called consequence a月a→B Ba+b FT T FT F (a) Conditional→ (b)Bi-conditional + Figure 3: Truth table of binary connectives Condition can be represented as"If.. then... . If condition is satisfied, it is natural that we can obtain a corre The difficult is that why we let a-B true when a is false? As we said in previous lecture, logic is a discipline to study deduction. a,B should be taken as a whole, which characterizes a way of deduction Example 2. Consider the proposition, if n>2, then n2>4. Let n=3,1,-3 Remark 1. We have TT, FF, FT, which all sounds reasonable. However, when premise is true consequence is false. It means we can reach wrong result from right basis step by step without fault
3 Truth table We only consider two value logic. It means for any proposition it is whether true or false. So it is clear for propositional letters. For connectives is concerned, the semantics of a proposition other than propositional letter is not self-evident. We define the following truth tables for a given connectives. We first define the truth table of unary connective ¬. It is easy to understand and to find the α ¬α T F F T Figure 1: Truth table of unary connective ¬ corresponding example in our life. Conjunction and disjunction both are easy to be understood. They have the following truth table. Actually, we can find that ∨ and ∧ obey De Morgan Law. α β α ∨ β T T T T F T F T T F F F (a) Disjunction ∨ α β α ∧ β T T T T F F F T F F F F (b) Conjunction ∧ Figure 2: Truth table of binary connectives However, the truth table of → is not well understandable. But the truth table of bi-condition (equality) is intuitive to be understood. In table, α is called premise and β is called consequence. α β α → β T T T T F F F T T F F T (a) Conditional → α β α ↔ β T T T T F F F T F F F T (b) Bi-conditional ↔ Figure 3: Truth table of binary connectives Condition can be represented as “If ... then ...”. If condition is satisfied, it is natural that we can obtain a correct consequence. The difficult is that why we let α → β true when α is false? As we said in previous lecture, logic is a discipline to study deduction. α → β should be taken as a whole, which characterizes a way of deduction. Example 2. Consider the proposition, if n > 2, then n 2 > 4. Let n = 3, 1, −3. Remark 1. We have T T, F F, F T, which all sounds reasonable. However, when premise is true consequence is false. It means we can reach wrong result from right basis step by step without fault. It is ridiculous in our life. 3
To impress the understanding, consider the following examples Example 3. Think about the following statements: 1. Figure out what would happen if man can fy like a bird! 2. Everything is possible in folk world. We hope they could help you. If you have any good examples, please sent me an email 4 Connectives From the point of view of function, every connective can be taken as a function with form f 0,1}→{0,1} Definition 4(Truth function). An n-ary connective is truth functional if the truth value for o(Al,., An) is uniquely determined by the truth value of A1,..., An Definition 5. A k-place Boolean function is a function from F, Ti to iT, F]. We let F and T themselves to be 0-place Boolean functions Example 4. We can define- as a Boolean function in Figure 4 x1→x2f→(x1,x2) f→(T,T)=T T FFf,T,,, F)=F FTTf→(F, FF T f→(F,F)=T Let I(a1, T2, .. n)=Ti, which is a projection function of i-th parameter 1. For each n, there are 22 n-place Boolean functions 2. 0-ary connectives: T and F 3. Unary connectives: ,I,T and F 4. Binary connectives: 10 of 16 are real binary functions Definition 6(Adequate connectives). A set S of truth functional connectives is adequate if, given ny truth function connective o, we can find a proposition built up from the connectives is S with the same abbreviated truth table as g In general, we have the following Adequacy theorem Theorem 7(Adequacy)., V, A is adequate(complete)
To impress the understanding, consider the following examples: Example 3. Think about the following statements: 1. Figure out what would happen if man can fly like a bird! 2. Everything is possible in folk world. We hope they could help you. If you have any good examples, please sent me an email. 4 Connectives From the point of view of function, every connective can be taken as a function with form f : {0, 1} k → {0, 1}. Definition 4 (Truth function). An n-ary connective is truth functional if the truth value for σ(A1, . . . , An) is uniquely determined by the truth value of A1, . . . , An. Definition 5. A k-place Boolean function is a function from {F, T} k to {T, F}. We let F and T themselves to be 0-place Boolean functions. Example 4. We can define → as a Boolean function in Figure 4. x1 x2 x1 → x2 f→(x1, x2) T T T f→(T, T) = T T F F f→(T, F) = F F T T f→(F, T) = T F F T f→(F, F) = T Figure 4: Boolean Function Let Ii(x1, x2, . . . , xn) = xi , which is a projection function of i-th parameter. 1. For each n, there are 22 n n-place Boolean functions. 2. 0-ary connectives: T and F. 3. Unary connectives: ¬, I , T and F. 4. Binary connectives: 10 of 16 are real binary functions. Definition 6 (Adequate connectives). A set S of truth functional connectives is adequate if, given any truth function connective σ, we can find a proposition built up from the connectives is S with the same abbreviated truth table as σ. In general, we have the following Adequacy theorem. Theorem 7 (Adequacy). {¬, ∨, ∧} is adequate(complete). 4
It means that a few connectives is enough. Before formal proof. We first consider whether we can use{→,v,∧} to represent→. As our expectation,(a→B)≡(-a)VB). It can be observed from the abbreviated truth table of -, as shown in Figure 3a We first just consider a very special case, all Ai are true and o(Al,., Ak)is also true. Consider the conjunction A1∧A2∧……∧Ak, you would find that the configuration of other row would make Generally, we have the following proof Proof. Construct the truth table of any connective a(Al, .. Ak. Consider the row with function value 1. For details, please refer to our textbook Furthermore, we can remove connective A such that the remainders are still adequate Corollary 8.-,v is adequate as a proposition with form of disjunction of conjunction. It is called as following, . h is represented In class, we have not mentioned the following to definition. Any truth functi Definition 9(DNF). a is called disjunctive normal form(abbreviated DNF). If a is a disjunction a=my…Vk, where each ri is a conjunction n=BnA…∧mn and each Bij is a proposition letter of the negation of a proposition letter. Example5.a=(A1∧A2∧A3)V(-B1∧B2)V(=C1A=C2∧=C3) is a Dna For symmetry, we can also exchange the position of conjunction and disjunction in DNF and Definition 10(CNF). a is called conjunctive normal form(abbreviated CNF). Ifa is a conjunction a=m1∧……∧k and each Biy is a proposition letter of the negation of a proposition letter a=(A1VA2VA3)∧(=B1VB2)∧(C1V=C2V=C3)isaC According to proof of Adequacy theore have the following thed Theorem 11. Any proposition can be reformed as a DNF and a CNF
It means that a few connectives is enough. Before formal proof. We first consider whether we can use {¬, ∨, ∧} to represent →. As our expectation, (α → β) ≡ ((¬α) ∨ β). It can be observed from the abbreviated truth table of → as shown in Figure 3a. We first just consider a very special case, all Ai are true and σ(A1, . . . , Ak) is also true. Consider the conjunction A1 ∧ A2 ∧ · · · ∧ Ak, you would find that the configuration of other row would make it false. Generally, we have the following proof. Proof. Construct the truth table of any connective σ(A1, . . . , Ak). Consider the row with function value 1. For details, please refer to our textbook. Furthermore, we can remove connective ∧ such that the remainders are still adequate. Corollary 8. {¬, ∨} is adequate. In class, we have not mentioned the following to definition. Any truth function is represented as a proposition with form of disjunction of conjunction. It is called as following: Definition 9 (DNF). α is called disjunctive normal form (abbreviated DNF). If α is a disjunction α = γ1 ∨ · · · ∨ γk, where each γi is a conjunction γi = βi1 ∧ · · · ∧ βini and each βij is a proposition letter of the negation of a proposition letter. Example 5. α = (A1 ∧ A2 ∧ A3) ∨ (¬B1 ∧ B2) ∨ (¬C1 ∧ ¬C2 ∧ ¬C3) is a DNF. For symmetry, we can also exchange the position of conjunction and disjunction in DNF and get the following: Definition 10 (CNF). α is called conjunctive normal form (abbreviated CNF). If α is a conjunction α = γ1 ∧ · · · ∧ γk, where each γi is a disjunction γi = βi1 ∨ · · · ∨ βini and each βij is a proposition letter of the negation of a proposition letter. Example 6. α = (A1 ∨ A2 ∨ A3) ∧ (¬B1 ∨ B2) ∧ (¬C1 ∨ ¬C2 ∨ ¬C3) is a CNF. According to proof of Adequacy theorem, we have the following theorem. Theorem 11. Any proposition can be reformed as a DNF and a CNF. Proof. According to adequacy theorem. 5
Exercies 1. Which of the following expressions are well-formed? (a)(-(AVB)∧C) (b)(AAB)VC (c)(CV∨B)∧A)分D) 2. Prove that set of propositions generated according to definition is countable 3. Prove that - is an adequate set of connectives 4. Prove that the binary connective(alB)("not both. . and")called the Sheffer stroke whose truth table is given in the following table is adequate n alB FIT T FF T 5. Prove that (A, V is not adequate 6. Let +3 be the ternary connective such that +aBy is equivalent to a +B+y (a) Show that F, T, A, +3) is complete (b) Show that no proper subset is complete Remark: is the ternary parity connective; +a1@2a is true if and only if odd number of a1,a2, a3 is T 7. Prove that any proposition(Boolean function) can be represented as a CNF
Exercies 1. Which of the following expressions are well-formed? (a) ((¬(A ∨ B)) ∧ C) (b) (A ∧ B) ∨ C (c) (((C ∨ B) ∧ A) ↔ D) 2. Prove that set of propositions generated according to definition is countable. 3. Prove that {¬, →} is an adequate set of connectives. 4. Prove that the binary connective (α|β) (“not both . . . and”) called the Sheffer stroke whose truth table is given in the following table is adequate. α β α|β T T F T F T F T T F F T 5. Prove that {∧, ∨} is not adequate. 6. Let +3 be the ternary connective such that +3αβγ is equivalent to α + β + γ. (a) Show that {F, T, ∧, +3} is complete. (b) Show that no proper subset is complete. Remark: +3 is the ternary parity connective; +α1α2α3 is true if and only if odd number of α1, α2, α3 is T. 7. Prove that any proposition(Boolean function) can be represented as a CNF. 6