复旦大学：《离散数学 Discrete Mathematics》英文讲稿_05 Formation tree Parsing algorithm

Discrete mathematics Yi Li Software school Fudan universit March 27. 2012

Discrete Mathematics Yi Li Software School Fudan University March 27, 2012 Yi Li (Fudan University) Discrete Mathematics March 27, 2012 1 / 1

Review Language o Truth table o Connectives

Review Language Truth table Connectives Yi Li (Fudan University) Discrete Mathematics March 27, 2012 2 / 1

utline o Formation tree o Parsing algorithm

Outline Formation tree Parsing algorithm Yi Li (Fudan University) Discrete Mathematics March 27, 2012 3 / 1

Ambiguity amp dle Consider the following sentences o The lady hit the man with an umbrella o He gave her cat food o They are looking for teachers of french, German and Japanese

Ambiguity Example 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. Yi Li (Fudan University) Discrete Mathematics March 27, 2012 4 / 1

Ambiguity dle Consider the following proposition A1VA2∧A3 We have two possible different propositions (A1VA2)∧A3 A1y(A2∧A3) Of course, they have different abbreviated truth tables

Ambiguity Example Consider the following proposition A1 ∨ A2 ∧ A3. We have two possible different propositions 1 (A1 ∨ A2) ∧ A3 2 A1 ∨ (A2 ∧ A3) Of course, they have different abbreviated truth tables. Yi Li (Fudan University) Discrete Mathematics March 27, 2012 5 / 1

Count of parentheses 「The eorem Every well-formed proposition has the same number of left as right parentheses O Consider the symbols without parentheses first O And then prove it by induction with more complicated propositions according to the Definition

Count of Parentheses Theorem Every well-formed proposition has the same number of left as right parentheses. Proof. 1 Consider the symbols without parentheses first. 2 And then prove it by induction with more complicated propositions according to the Definition. Yi Li (Fudan University) Discrete Mathematics March 27, 2012 6 / 1

Prefix 「The eorem Any proper initial segement of a well-defined proposition contains an excess of left parenthesis. Thus no proper initial segement of a well defined propositon can itself be a well defined propositions Prove it by induction from simple to complicated propositions

Prefix Theorem 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. Proof. Prove it by induction from simple to complicated propositions. Yi Li (Fudan University) Discrete Mathematics March 27, 2012 7 / 1

Formation tree am dle The formation tree of(AVB),(A∧B)→C) H Form a tree bottom-up while constructing the proposition according to the definition

Formation Tree Example The formation tree of (A ∨ B),((A ∧ B) → C) . How? Form a tree bottom-up while constructing the proposition according to the Definition. Yi Li (Fudan University) Discrete Mathematics March 27, 2012 8 / 1

Formation tree Definition(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 o The leaves are labeled with propositional letters O if a node o is labeled with a proposition of the form aVB),(a∧),(a→B) or (a 4> B) immediate successors, o0 and g 1 are labeled with a and B(in that order) O if a node o is labeled with a proposition of the form Ga), its unique immediate successor, 00, is labeled with

Formation Tree Definition (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 α. Yi Li (Fudan University) Discrete Mathematics March 27, 2012 9 / 1

Formation tree Definition O The depth of a proposition is the depth of associated formation tree o The support of a proposition is the set of propositional letters that occur as labels of the aves of the associated formation tree

Formation Tree Definition 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. Yi Li (Fudan University) Discrete Mathematics March 27, 2012 10 / 1