复旦大学：《离散数学》习题课讲义（李弋）05 Formation tree Parsing algorithm

Discrete Mathematics() Software school Fudan University March 26. 2013

. . Discrete Mathematics(II) Yi Li Software School Fudan University March 26, 2013 Yi Li (Fudan University) Discrete Mathematics(II) March 26, 2013 1 / 20

Review o Language o Truth table o Connectives

Review Language Truth table Connectives Yi Li (Fudan University) Discrete Mathematics(II) March 26, 2013 2 / 20

utline o Formation tree o Parsing algorithm

Outline Formation tree Parsing algorithm Yi Li (Fudan University) Discrete Mathematics(II) March 26, 2013 3 / 20

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(II) March 26, 2013 4 / 20

Ambiguity dle Consider the following proposition A1VA2∧A3 We have two possible different propositions (41VA2)∧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(II) March 26, 2013 5 / 20

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(II) March 26, 2013 6 / 20

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(II) March 26, 2013 7 / 20

Formation tree am dle The formation tree of(A∨B),((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(II) March 26, 2013 8 / 20

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 (aVβ),(aA3),(a→B)or(a分B),its immediate successors o0 and o 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(II) March 26, 2013 9 / 20

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 leaves 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(II) March 26, 2013 10 / 20