Discrete Mathematics(ID) Spring 2014 Lecture 5: Formation Tree and Parsing algorithm 1 Overview In this lecture, we completely focus on syntax of proposition. And the term"proposition"does always mean well-defined proposition without explicit declaration The most important topic is to make sure the unique readability of a well defined proposition. And then a proposition is associated with a tree, called formation tree. Therefore, we find the properties of a well-defined proposition based on its tree form. Finally, we introduce a parsing algorithm to check the validity of a sequence of symbols, with a formation tree as a by-product 2 Some properties of proposition 2.1 Ambiguity of a sentence In everyday language, we sometimes could speak some sentence which could be understood totally th different meaning, which is called ambiguous Example 1. Consider the following sentences 1. The lady hit the man with an umbrella. 2. He gave her cat food They are looking for teachers of french, German and Japanese Once you read these sentences, you way wonder 1. Is the lady using an umbrella to hit or is she hitting a man who is carrying an umbrella? 2. Is he giving cat food to her or is he giving her cat some food? 3. Are they looking for teachers who can each teach one language or all three languages? You may find more examples Here, the ambiguity is not caused by the meaning/semantics of some word. The reason is just the way to group words in different approaches example is the way to nest if and else. You can also consider the following expression4/2X2, o Similarly, you could encounter the same trouble when you write a piece of segment of code. TI Without the help of parentheses, proposition could also run into the same trouble. Consider the following example
Discrete Mathematics (II) Spring 2014 Lecture 5: Formation Tree and Parsing Algorithm Lecturer: Yi Li 1 Overview In this lecture, we completely focus on syntax of proposition. And the term “proposition” does always mean well-defined proposition without explicit declaration. The most important topic is to make sure the unique readability of a well defined proposition. And then a proposition is associated with a tree, called formation tree. Therefore, we find the properties of a well-defined proposition based on its tree form. Finally, we introduce a parsing algorithm to check the validity of a sequence of symbols, with a formation tree as a by-product. 2 Some properties of proposition 2.1 Ambiguity of a sentence In everyday language, we sometimes could speak some sentence which could be understood totally with different meaning, which is called ambiguous. Example 1. Consider the following sentences: 1. The lady hit the man with an umbrella. 2. He gave her cat food. 3. They are looking for teachers of French, German and Japanese. Once you read these sentences, you way wonder: 1. Is the lady using an umbrella to hit or is she hitting a man who is carrying an umbrella? 2. Is he giving cat food to her or is he giving her cat some food? 3. Are they looking for teachers who can each teach one language or all three languages? You may find more examples. Here, the ambiguity is not caused by the meaning/semantics of some word. The reason is just the way to group words in different approaches. Similarly, you could encounter the same trouble when you write a piece of segment of code. The example is the way to nest if and else. You can also consider the following expression “4/2 × 2”. Without the help of parentheses, proposition could also run into the same trouble. Consider the following example. 1
Example 2. Consider the following proposition A1VA2∧A which is definitely not well-defined Solution. We have two possible different propositions 1.(A1VA2)∧A3 2.A1V(A2∧A3) Of course, they have different abbreviation truth tables Mathematics is rigid. One of the responsibilities of mathematical logic is to eliminate ambiguity from mathematics. So we should first eliminate ambiguity in mathematical logic 2.2 Parentheses Finally, we want to design a systematic approach to recognize/parse a well defined proposition But we first dig some properties of well defined propositions A proposition is a sequence of symbols generated by proposition language. We just take it string. Parentheses are very important to construct a well-defined proposition. We just count number of left and right parenthesis and have the following theorem Theorem 1. Every well-defined proposition has the same number of left as right parentheses Proof. Consider the symbols without parenthesis first. They are the simplest cases: propositional letters. And we know that a complicated proposition consists of two or one simpler proposition(s) with a connective. If a simpler one keep the property, we can derive the invariant for the complicated Obviously, we can prove it by induction to investigate all propositions by following the approach to construct a compound proposition What metric is chosen for induction? It is magic. Here, we actually use the depth of nested connectives, which will be introduced in the next section. Some guy may take the number of parenthesis. It is difficult to characterize the feature and to apply inductive proof. The exercise will demonstrate this Theorem 2. Any proper initial segement of a well defined proposition contains an excess of left trenthesiss. Thus no proper initial segement of a well defined propositon can itself be a well defined propositions Go back to lecture three if your forget what is a proper initial segment Proof. Prove it by induction from simple to complicated propositions. And we also need Theorem 1
Example 2. Consider the following proposition A1 ∨ A2 ∧ A3, which is definitely not well-defined. Solution. We have two possible different propositions 1. (A1 ∨ A2) ∧ A3 2. A1 ∨ (A2 ∧ A3) Of course, they have different abbreviation truth tables. Mathematics is rigid. One of the responsibilities of mathematical logic is to eliminate ambiguity from mathematics. So we should first eliminate ambiguity in mathematical logic. 2.2 Parentheses Finally, we want to design a systematic approach to recognize/parse a well defined proposition. But we first dig some properties of well defined propositions. A proposition is a sequence of symbols generated by proposition language. We just take it as a string. Parentheses are very important to construct a well-defined proposition. We just count the number of left and right parenthesis and have the following theorem. Theorem 1. Every well-defined proposition has the same number of left as right parentheses. Proof. Consider the symbols without parenthesis first. They are the simplest cases: propositional letters. And we know that a complicated proposition consists of two or one simpler proposition(s) with a connective. If a simpler one keep the property, we can derive the invariant for the complicated one. Obviously, we can prove it by induction to investigate all propositions by following the approach to construct a compound proposition. What metric is chosen for induction? It is magic. Here, we actually use the depth of nested connectives, which will be introduced in the next section. Some guy may take the number of parenthesis. It is difficult to characterize the feature and to apply inductive proof. The exercise will demonstrate this. Theorem 2. Any proper initial segement of a well defined proposition contains an excess of left parenthesiss. Thus no proper initial segement of a well defined propositon can itself be a well defined propositions. Go back to lecture three if your forget what is a proper initial segment. Proof. Prove it by induction from simple to complicated propositions. And we also need Theorem 1. 2
3 Formation Tree A proposition is a sequence of symbols. The structure determines the reading of a proposition. In this section, we are to map a proposition to a tree, named formation tree. It will help us to read proposition Definition 3(Top-down). A formation tree is a finite tree T of binary sequences whose nodes are all labeled with propositions. The labeling satisfies the following conditions: 1. The leaves are labeled with propositional letters 2. if a node a is labeled with a proposition of the form(avB),(oAB),(a-B)or(a+ B), its immediate successors, a0 and o'l, are labeled with a and B (in that order) 3. if a node o is labeled with a proposition of the form (a), its unique immediate successor, g 0. is labeled with a How to map a well-defined proposition to a tree? Consider the following example Example3. The formation tree of(AVB),(A∧B)→C It is easy to draw its formation tree for this example. However, when a proposition is complicated enough, it is not easy. Just rethink your approach. We may follow the procedure of constructing a proposition from a propositional letters in a bottom-up way, even we define it in a top-down approach These two examples are specified. What about the other propositions? Given proposition, we have the following questions 1. Is there a formation tree? 2. Is it unique? It is lucky that we have the following Theorem Theorem 4. Each well-defined proposition has a unique formation tree associated with it Proof.(Sketch) It is divided into two parts. Both are inductive proof on depth of a proposition 1. Existence of the formation tree by induction on depth 2. Uniqueness of the formation tree by induction on depth. From now on, we sometimes call the labeled tree of a proposition associated formation tree Once we have formation tree of a proposition, we can define these following terms Definition 5. Given an associated formation tree, we have
3 Formation Tree A proposition is a sequence of symbols. The structure determines the reading of a proposition. In this section, we are to map a proposition to a tree, named formation tree. It will help us to read a proposition. Definition 3 (Top-down). A formation tree is a finite tree T of binary sequences whose nodes are all labeled with propositions. The labeling satisfies the following conditions: 1. The leaves are labeled with propositional letters. 2. if a node σ is labeled with a proposition of the form (α ∨ β),(α ∧ β),(α → β) or (α ↔ β), its immediate successors, σˆ0 and σˆ1, are labeled with α and β (in that order). 3. if a node σ is labeled with a proposition of the form (¬α), its unique immediate successor, σˆ0, is labeled with α. How to map a well-defined proposition to a tree? Consider the following example. Example 3. The formation tree of (A ∨ B),((A ∧ B) → C) . It is easy to draw its formation tree for this example. However, when a proposition is complicated enough, it is not easy. Just rethink your approach. We may follow the procedure of constructing a proposition from a propositional letters in a bottom-up way, even we define it in a top-down approach. These two examples are specified. What about the other propositions? Given proposition, we have the following questions: 1. Is there a formation tree? 2. Is it unique? It is lucky that we have the following Theorem. Theorem 4. Each well-defined proposition has a unique formation tree associated with it. Proof. (Sketch) It is divided into two parts. Both are inductive proof on depth of a proposition. 1. Existence of the formation tree by induction on depth. 2. Uniqueness of the formation tree by induction on depth. From now on, we sometimes call the labeled tree of a proposition associated formation tree. Once we have formation tree of a proposition, we can define these following terms. Definition 5. Given an associated formation tree, we have 3
1. The depth of a proposition is the depth of associated formation tree 2. The support of a proposition is the set of propositional letters that occur as labels of the leaves of the associated formation tree Actually, all inductive proof could be based on the depth of a proposition. 4 Parsing There are infinitely many sequence of symbols. How to identify which is well-defined and which is not? If we want to build a proof system executed on a computer it is very important to construct first a method to check whether it is valid or not 4.1 Algorithm As a well-defined proposition can be uniquely mapped into a formation tree, which is easy to check every node well-defined or not. We can now introduce a recursive algorithm to analyze a sequence of symbols 1. If all leaf nodes are labeled with proposition letters, stop it. Otherwise select a leaf node having expressions other than letter and examine it 2. The first symbol must be(. if the second symbol is " jump to step 4. Otherwise go to step 3.(a)Scan the expression from the left until first reaching(a, where a is a nonempty expression having a balance between( and (b) The a is the first of the two constituents (c) The next symbol must be∧,v,→+,or分 (d) The remainder of the expression, B)must consist of a an expression B and (e) Extend the tree by adding a and B as left and right immediate successor respectively 4. The first two symbols are now known to be(. The remainder of the expression, B)must consist of a an expression B and). Then we extend the tree by adding B as its immediate successor. Goto step 1 In algorithm, we omit the procedure to exit for sequence which is not well-defined. Check every node, if a internal node is not well defined or terminal node is not a proposition letter, the algorithm just stops and asserts a non-well-defined sequence What's most important is that the algorithm checks the sequence recursively. It is the similar te the approach to define the formation tree of a well-defined proposition. According to Theorem 4 the parsing algorithm construct a unique tree
1. The depth of a proposition is the depth of associated formation tree. 2. The support of a proposition is the set of propositional letters that occur as labels of the leaves of the associated formation tree. Actually, all inductive proof could be based on the depth of a proposition. 4 Parsing There are infinitely many sequence of symbols. How to identify which is well-defined and which is not? If we want to build a proof system executed on a computer it is very important to construct first a method to check whether it is valid or not. 4.1 Algorithm As a well-defined proposition can be uniquely mapped into a formation tree, which is easy to check every node well-defined or not. We can now introduce a recursive algorithm to analyze a sequence of symbols. 1. If all leaf nodes are labeled with proposition letters, stop it. Otherwise select a leaf node having expressions other than letter and examine it. 2. The first symbol must be (. if the second symbol is ¬, jump to step 4. Otherwise go to step 3. 3. (a) Scan the expression from the left until first reaching (α, where α is a nonempty expression having a balance between ( and ). (b) The α is the first of the two constituents. (c) The next symbol must be ∧, ∨, →, or ↔. (d) The remainder of the expression, β) must consist of a an expression β and ). (e) Extend the tree by adding α and β as left and right immediate successor respectively. 4. The first two symbols are now known to be (¬. The remainder of the expression, β) must consist of a an expression β and ). Then we extend the tree by adding β as its immediate successor. Goto step 1. In algorithm, we omit the procedure to exit for sequence which is not well-defined. Check every node, if a internal node is not well defined or terminal node is not a proposition letter, the algorithm just stops and asserts a non-well-defined sequence. What’s most important is that the algorithm checks the sequence recursively. It is the similar to the approach to define the formation tree of a well-defined proposition. According to Theorem 4, the parsing algorithm construct a unique tree. 4
4.2 Parentheses Parentheses are tedious for us to handle. We can introduce some rule to reduce the num arentheses without ambiguity 1. The outermost parenthesis need not be explicitly mentioned 2. The negation symbol applies to a proposition as little as possible 3. The conjunction and disjunction symbols also apply as little as possibl 4. Where one connective symbols is used repeatedly, grouping is to the right All these explicit rules make our parsing algorithm complicated if you want to accommodate the right proposition other than well-defined ones for convenience. Furthermore, you should prove that explicit rule would not result in ambiguity. 4.3 Polish notation Rules are not convenient. However there is a smart way to get rid of parentheses permanently, it is just the Polish notation. As we have already known, any connective is just a function with one or two parameters. We can represent a proposition as following without any parentheses 1.D-(a)=-a. V(a, B) 3.DA(a,B)=∧aB (a,B)=→aB 5. D+a, B)=taB It is called Polish notation. Actually, it can be expanded to any n-ary function Consider the following example, which is translated from a well-defined proposition Example 4. Determine the well defined proposition of →∧AD∨=BCB. It is easy to recover the well-defined form. Do it as an exercise Yah! We do eliminate parentheses successfully. But what is your feeling about Polish notation when you try to figure out what it represents. In fact, it is an approach very suitable for machine but human. To us, the well-defined way is much better There are several approached to translate Polish representation into regular one, which is left as
4.2 Parentheses Parentheses are tedious for us to handle. We can introduce some rule to reduce the number of parentheses without ambiguity. 1. The outermost parenthesis need not be explicitly mentioned. 2. The negation symbol applies to a proposition as little as possible. 3. The conjunction and disjunction symbols also apply as little as possible. 4. Where one connective symbols is used repeatedly, grouping is to the right. All these explicit rules make our parsing algorithm complicated if you want to accommodate the right proposition other than well-defined ones for convenience. Furthermore, you should prove that explicit rule would not result in ambiguity. 4.3 Polish notation Rules are not convenient. However there is a smart way to get rid of parentheses permanently, it is just the Polish notation. As we have already known, any connective is just a function with one or two parameters. We can represent a proposition as following without any parentheses: 1. D¬(α) = ¬α. 2. D∨(α, β) = ∨αβ. 3. D∧(α, β) = ∧αβ. 4. D→(α, β) =→ αβ. 5. D↔(α, β) =↔ αβ. It is called Polish notation. Actually, it can be expanded to any n-ary function. Consider the following example, which is translated from a well-defined proposition. Example 4. Determine the well defined proposition of → ∧AD ∨ ¬B ↔ CB. It is easy to recover the well-defined form. Do it as an exercise. Yah! We do eliminate parentheses successfully. But what is your feeling about Polish notation when you try to figure out what it represents. In fact, it is an approach very suitable for machine but human. To us, the well-defined way is much better. There are several approached to translate Polish representation into regular one, which is left as an exercise. 5
5 Appendix: Inductive definition In our class, many definitions are defined recursively or inductively. We just introduce Definition 6. A set S is closed under a single operation f (s1, .. Sn)if and only if every S1 S,f(81,…,sn)∈S Definition 7. The closure of a set S under (all) the operations in a set T is the smallest C such that 1. SCC and 2.计f∈Tisn- ary and sI,…,sn∈C,then∫(81,…,sn)∈C. With these concepts, we have an Theorem on the property of inductive definition Theorem 8. Suppose that s is closed under the operations of T, there is a smallest closure C such that SCc Proof. Given a set D, sCD and D is closed under the operations of T. Consider the set C=nDISCDAD is closed under the operations of T) It is obvious that S CC. And C is the smallest set according to definition of C As a direct application of Theorem 8, we have the following Theorem about well-defined Definition Theorem 9. If s is a set of well defined propositions and is closed under all five connectives, then s is the set of all well defined propositions Exercises 1. Show that there are no well-defined propositions of length 2, 3, or 6, but that any other positive length is possi 2. Given an example such that(onB)=(rnd)but afr, where a and B are well-defined and r and 8 are two expressions 3. Draw formation tree of the following propositions (a)(AVB)→(-C)∧D) (b)((=A)VB)∧(AV(=B)) 4. Let a be a well-defined proposition; let c be the number of places at which binary connective symbols(A, V,7,,)occur in a; let s be the number of places at which proposition letters occur in a Show by using the induction principle that s=c+1 5. Determine the Polish notation of proposition or vice versa
5 Appendix: Inductive definition In our class, many definitions are defined recursively or inductively. We just introduce Definition 6. A set S is closed under a single operation f(s1, . . . , sn) if and only if every s1, . . . , sn ∈ S, f(s1, . . . , sn) ∈ S Definition 7. The closure of a set S under (all) the operations in a set T is the smallest C such that 1. S ⊆ C and 2. if f ∈ T is n-ary and s1, . . . , sn ∈ C, then f(s1, . . . , sn) ∈ C. With these concepts, we have an Theorem on the property of inductive definition. Theorem 8. Suppose that S is closed under the operations of T, there is a smallest closure C such that S ⊆ C. Proof. Given a set D, S ⊆ D and D is closed under the operations of T. Consider the set C = ∩{D|S ⊆ D ∧ D is closed under the operations of T}. It is obvious that S ⊆ C. And C is the smallest set according to definition of C. As a direct application of Theorem 8, we have the following Theorem about well-defined Definition: Theorem 9. If S is a set of well defined propositions and is closed under all five connectives, then S is the set of all well defined propositions Exercises 1. Show that there are no well-defined propositions of length 2, 3, or 6, but that any other positive length is possible. 2. Given an example such that (α ∧ β) = (γ ∧ δ) but α ̸= γ, where α and β are well-defined and γ and δ are two expressions. 3. Draw formation tree of the following propositions: (a) ((A ∨ B) → ((¬C) ∧ D)). (b) (((¬A) ∨ B) ∧ (A ∨ (¬B))). 4. Let α be a well-defined proposition; let c be the number of places at which binary connective symbols(∧, ∨, →, ↔ ) occur in α; let s be the number of places at which proposition letters occur in α. Show by using the induction principle that s = c + 1. 5. Determine the Polish notation of proposition or vice versa. 6
(a)(AVB)→(-C)∧D) (b)(A)B)∧(Av(=B) (c)→∧→AB+C=D 6. Design a algorithm which can translate Polish notation of proposition into well defined propo- ition without a stack or with at most one. In addition, your algorithm can detect a bad polish string 7. Design a algorithm to translate a well-defined proposition into a Polish notation form
(a) ((A ∨ B) → ((¬C) ∧ D)). (b) (((¬A) ∨ B) ∧ (A ∨ (¬B))). (c) → ∧¬AB ↔ C¬D. 6. Design a algorithm which can translate Polish notation of proposition into well defined proposition without a stack or with at most one. In addition, your algorithm can detect a bad Polish string. 7. Design a algorithm to translate a well-defined proposition into a Polish notation form. 7
