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