计算机问题求解-论题1-12 -偏序关系和格 2017年12-21
计算机问题求解--论题1-12 --偏序关系和格 2017年12-21
偏序关系 Suppose R is a relation on a set S satisfying the following three properties: [O](Reflexive)For any a e S,we have aRa. [O2](Antisymmetric)If a Rb and bRa,then a =b. [O3](Transitive)If a Rb and bRc,then aRc. Then R is called a partial order or,simply an order relation,and R is said to define a partial ordering of S.The s set S with the partial order is called a partially ordered set or,simply,an ordered set or poset.We write (S,R) when we want to specify the relation R
偏序关系
偏序关系 b器hy person wh business tion or trad be attended 问题1：查词典时，单词的“序”起 到了什么作用？单词的“序”是怎 么定义的？ ·字母表中字母的序关系 ·积序关系（定义在偏序集之上) (a,b)(a',b')if a<a'andb<b' ·词典序关系（定义在全序集合之上） (a,b)<(a',b')if a<b or if a=a'andb<b' (a1,a2,....an)<(a,a2,....an)if ai=af for i 1,2,....k-1 and ak <ak
偏序关系 •问题1：查词典时，单词的“序”起 到了什么作用？单词的“序”是怎 么定义的？ • 字母表中字母的序关系 • 积序关系（定义在偏序集之上） • 词典序关系（定义在全序集合之上）
偏序关系 bushy person wh business tion or trad be attended (a)Alphabetical (Lexicographical)Order:The reader is no doubt familiar with the usual alphabetical ordering of A*.That is: (i)<w,where A is the empty word and w is any nonempty word. (ii)Suppose u au'and v bu'are distinct nonempty words where a,b A and u',v'A*.Then u<v if a<b or if a=bbutu'<v' (b)Short-lex Order:Here A+is ordered first by length,and then alphabetically.That is,for any distinct words u,v in A*, u<v if lu<v or if lu=v but u precedes v alphabetically
偏序关系
偏序关系 bushy person wh business tion or trad be attended ·问题2： ·任意单词的长度有限 ·给定一个序关系，任意两个单词都可 以比较“序”，是否意味着单词的 “序位置”是唯一的？
偏序关系 •问题2： • 任意单词的长度有限 • 给定一个序关系，任意两个单词都可 以比较“序”，是否意味着单词的 “序位置”是唯一的？