Discrete Mathematics(II) Spring 2013 Lecture 4: Proposition, Connectives and Truth Tables 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 theore 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? They are interrogative, imperative, and interrogative sentences respectively. It is very different withe the sentences in previous examples. 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 propositional 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
Discrete Mathematics (II) Spring 2013 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? They are interrogative, imperative, and interrogative sentences respectively. It is very different withe the sentences in previous examples.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 propositional 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 1
is not as simple as"I am a student". A propositional letter is something like a word in a sentence. It can't be divide into more basic one 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. Sometimes we call it language, all complicated strings are constructed based on these symbols with some rules Definition 1. The language of propositional logic consists of the following symbols 1. Connectives:V,∧,-,→,+ 2. Parentheses:),( 3. Propositional Letters: A, Al, A2,..., B, B1, B 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 proposit 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 proposi- tional letters(1) and repeatedly applying(2) It is obvious that infinite propositions can be generated even if there are only finite propo 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.(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 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
is not as simple as ”I am a student”. A propositional letter is something like a word in a sentence. It can’t be divide into more basic one. 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. Sometimes we call it language, all complicated strings are constructed based on these symbols with some rules. 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. 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 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 aTT TT T LFFI (a)Disjunction V (b) Conjunction∧ 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→B aBa分 TT T TT T TF F ITFI LFIFI T (a)Conditional b)Bi-conditional t Figure 3: Truth table of binary connectives Truth tables of these connectives are the base of propositional logic system. They define the functional behavior of a connective, which will be formally represented as a function. They indeed reflect the human's naive reasoning system an obtain a correct consequence. The difficult is that why we let a>B true when a is false? e Condition can be represented as"If. then. ".If condition is satisfied, it is natural that 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. In another word, it the assertion reasonable? 3
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 Truth tables of these connectives are the base of propositional logic system. They define the functional behavior of a connective, which will be formally represented as a function. They indeed reflect the human’s naive reasoning system. 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. In another word, it the assertion reasonable? 3
Example 2. Consider the proposition, if n>2, then n">4. Let n= 3, 1,3. It is always true when i∈R. 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 It is ridiculous in our life To impress the understanding, consider the following examples Example 3. With the following assumption 1. If man can fly like a bird! 2. Everything in a folk world We can make many irrational assertion We hope they could help you. If you have any good examples, please sent me an ema 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 a(Al ly determined by the truth value of Al Definition 5. A k-place Boolean function is a function from F, r 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 f→(T,T T F F f→(T,F)=F F T T f→(F,T)=T FFTf→(F,F)=T Figure 4: Boolean function Let Ii(1, 2, .., In)=i, which is a projection function of i-th parameter. We have the following properties on truth function 1. For each n, there are 2- n-place Boolean functions. It can be easily calculated only if you just think about the truth table 0-ary connectives: T and F 3. Unary connectives: - ,I, T and F
Example 2. Consider the proposition, if n > 2, then n 2 > 4. Let n = 3, 1, −3. It is always true when n ∈ R. 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. To impress the understanding, consider the following examples: Example 3. With the following assumption: 1. If man can fly like a bird! 2. Everything in a folk world. We can make many irrational assertion. 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. We have the following properties on truth function. 1. For each n, there are 22 n n-place Boolean functions. It can be easily calculated only if you just think about the truth table. 2. 0-ary connectives: T and F. 3. Unary connectives: ¬, I , T and F. 4
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 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) 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 it false Generally, we have the following proof. Proof. Construct the truth table of any connective o(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 We may wonder whether there is a adequate set with only one connective. The answer is positive. You can refer to exercise 4. The propositional logic with only one connective elegant. However, it first serve people. In practice, we also hope that the system is friend tradeoff, most of text book will adopt the set (,A, V., and + are two one which chara cd. wvty human's thinking style. So they are also kept in the symbol set 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 followin Definition 9(DNF). a is called disjunctive normal form(abbreviated DNF). If a is a disjunction Q =1 where each ri is a conjunction n=B1∧……∧B and each Bij is a proposition letter or the negation of a proposition letter. Example5.a=(A1∧A2AA3)V(-B1∧B2)V(-C1∧=C2A-C3) is a dne For symmetry, we can also exchange the position of conjunction and disjunction in DNF and get the following: Definition 10(CNF). a is called conjunctive normal form(abbreviated CNF). If a is a conjunction where each i is a disjunction and each Bii is a proposition letter or the negation of a proposition letter 5
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). 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. We may wonder whether there is a adequate set with only one connective. The answer is positive. You can refer to exercise 4. The propositional logic with only one connective is very elegant. However, it first serve people. In practice, we also hope that the system is friend. With tradeoff, most of text book will adopt the set {¬, ∧, ∨}. → and ↔ are two one which characterize human’s thinking style. So they are also kept in the symbol set. 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 or 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 or the negation of a proposition letter. 5
Example 6. C=(A1 V A2 VA3)A(B1VB2)AGCIV-C2V-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. oof. According to adequacy theorem Exercies 1. Which of the following expressions are well-formed? (a)(=(AVB)∧C) (b)(A∧B)C (c)(CVB)AA)分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(aB)("not both. . and")called the Sheffer stroke whose truth table is given in the following table is adequat FF T 5. Prove that (A, V is not adequate 6. Let + be the ternary connective such that +aBy is equivalent to a+B+y (a) Show that (F, T,A,+) is complete (b) Show that no proper subset is complete Remark: +o is the ternary parity connective; +a10203 is true if and only if odd number of 01, 02, a is T 7. Prove that any proposition(Boolean function) can be represented as a CNF 6
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. 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