离散数学第六章第一节.pptVIP

第六章 格与布尔代数 格是另一类代数系统。格的理论形成于1935年前后，是代数学的一个分支。 本章介绍格的基本知识，特殊的格：分配格、有补格，最后介绍布尔代数。 第六章 目录 第6-1讲 格的概念 第6-2讲 分配格和有补格 第6-3讲 布尔代数 第6-4讲 布尔表达式 第6-1讲 格的概念 1. 格的定义 2.格的对偶原理 3.格的基本性质 4.格与代数系统间的关系 5.格同态 6. 课堂练习 7. 第6-1讲 作业 1、格的定义(1) 如果集合A上的关系?具有自反性、反对称性和传递性，称之为偏序。A，?称之为偏序集。 设X={1,2,3,4,6,12},Y={2,3,6,12,24,36}。集合X和Y上的整除关系“|”就构成两个偏序集：X,|，Y,|。它们的哈斯图如下： 1、格的定义(2) 定义1 如果偏序集A,?中任意两个元素都有最小上界和最大下界，则称A,? 是格。 1、格的定义(3) 定义3 设A,?是格, A,?,?是A,?诱导的代数系统。如果B?A且B??，若运算?和?在B中封闭，则称B,?是A,?的子格。 2、格的对偶原理 对偶原理 设P是格A,?的真命题，将P中的? 、?、?分别换成? 、?、?得命题P’，则P’在格A,?中亦真。 3、格的基本性质(1) 3、格的基本性质(2) 3、格的基本性质(3) 4、格与代数系统间的关系（1） 4、格与代数系统间的关系（2） 4、格与代数系统间的关系（3） 4、格与代数系统间的关系（4） 5、格同态(1) 定义4 设A1,?1、A2,?2是格。它们所诱导的代数系统分别是A1,?1,?1、A2,?2,?2。如果存在映射f：A1?A2，使对任意a,b?A1,有 f(a?1b)=f(a)?2f(b), f(a?1b)=f(a)?2f(b) 则称f是从A1,?1,?1到A2,?2,?2的格同态。称f(A1), ?2是A1,?1的格同态象。 如果f是双射，则称f是从A1,?1,?1到A2,?2,?2的格同构。也称格A1, ?1、A2, ?2同构。 5、格同态(2) 定理2 设f是格A1,?1到A2,?2格同态。对任意a,b?A1,如果a?1b,则f(a)?2f(b)。 5、格同态(3) 定理3 f是格A1,?1到A2,?2的格同构，当且仅当对任意a,b?A1, a?1b?f(a)?2f(b)。 5、格同态(3) 定理3 f是格A1,?1到A2,?2的格同构，当且仅当对任意a,b?A1, a?1b?f(a)?2f(b)。 5、格同态(4) 6、课堂练习 练习1 设L={1,2,3,4,5,6,7,8,9,10,11,12},L,?是偏序集, ?定义为：对于n1、n2?L， n1?n2当且仅当n1是n2的因子。问L,?是否为格？ 第6-1讲 作业 P242 1，2ab，8 * * 虽然都是哈斯图,但是它们有一个重要的差别： X,|中每两个元素构成的集合都有最大下界和最小上界。但Y,|无此特点。 定义2 设A,?是格，在A上定义两个二元运算?和?，对任意a,b?A，a?b等于a和b的最小上界，a?b等于a和b的最大下界，则称A,?,?是格A,?诱导的代数系统。?和?分别称为并运算和交运算。 注：定义2中定义的两个运算是本节证明过程中反复要用的基本依据。两个元素的集合{a,b}的上界可以属于该集合，也可以不属于该集合。但是， 如果a ? b，则a?b=b， a?b=a。 如果a 、b不可比，也应有a,b ? a?b ，a?b ? a ,b。 可以证明，子格也是格。 注意：若A,?是格, B?A且B??，则B,?任然是偏序集，但B,?不一定是格。即使是格，也不一定是A,?的子格。 例如，设S={a,b,c},?(S), ? 是格，其哈斯图如右，取 A={?,{a},{c},{a,c}} B={?,{a},{c},{a,b},{a,c}, {b,c},{a,b,c}} 则A, ? 是?(S), ? 的子格，而B, ? 虽是格，但非子格。 设A,?是偏序集,用?表示偏序关系?的逆关系， 则A,?也是偏序集。将A,?的哈斯图旋转180度，就是A,?的哈斯图。称A,?为A,?彼此对偶的偏序集。如果A,?是格，则A,?也是格。 由格A,?诱导的代数系统的并(交)运算，正好是由格A,?诱导的代数系统的交(并)运算。 设A,?是格,a,b,c,d?A，则如下性质成立： (1)并、交定义 a?a?b, b?a?b a?a?b, b?a?b a?b?a, a?b?b a?b?a, a