7_2格与布尔代数范例.ppt

格和布尔代数 格与布尔代数 在第一章我们介绍了命题逻辑。当时被侧重的只是形式系统。如果视P为全体命题的集合，于是逻辑联词∨，∧就可以被看作P上的两个二元代数运算。因而，(P,∨,∧)是一个代数,即通常所说的命题代数。 在命题代数中，运算∨,∧满足幂等律，交换律，结合律，分配律和吸收律。 在第三章我们介绍了集合的最为一般的一些理论，被关心的只是集合的基本概念，集合的运算和基数等方面的事实。如果我们令S＝2A，对于?X,Y?S,则都有X∪Y，X∩Y?S。在这两种二元运算下，(S,∪,∩)是代数,即所谓幂集代数。 在幂集代数中, 运算∪, ∩满足幂等律, 交换律, 结合律, 分配律和吸收律. 在幂集代数中引进了补集的概念和在命题代数中引进了否定的概念之后, 则在这两种代数中, 都具有了De Morgan律. 从代数的观点出发，我们是否能对一种更为抽象的代数系统进行研究, 使得幂集代数, 命题代数仅仅是它的特例? 回答是肯定的. 这种抽象的代数系统就是格和布尔代数. 研究布尔代数首先要研究格, 因为布尔代数是一种特殊的格. 格作为数学中一个很有特色的分支, 大体上说形成于二十世纪的三十到四十年代. 格作为一种理论, 它不只是代数学的一个部分, 而且在近代解析几何, 半序空间等方面也都有重要的作用. 布尔代数的问世比格要早,在十九世纪中叶,由英国数学家乔治·布尔研究并提出。 格和布尔代数在计算机科学中有广泛的应用，象有限自动机理论,开关网络理论，逻辑设计等领域都直接地应用了格和布尔代数的结论。 一个布尔代数是一个有补分配格. 一个格是这样的一个偏序集, 在这个偏序集中, 每两个元素都有唯一一个最小上界和唯一一个最大下界. 可见, 我们首要的任务是讨论偏序和确界的一些有关的性质, 以作为我们本章要讲述内容的基础. 1 格的概念 定义1.1 设A， 是一个偏序集，如果A中任意两个元素都有最小上界(上确界)和最大下界(下确界)，则称A， 为格。 说明： 由于确界唯一，所以在格A， 中，对A中任意元素a,b ，求其上确界或下确界的结果是A， 中唯一的元素. 从代数的意义上说，求上确界和下确界都是格A， 中的二元运算。 例： 考查下面Hasse图（哈斯图）:是偏序集但非格的Hasse图中,总有元素a,b,使得{a,b}没有上确界或下确界。 例1 设S是任意集合, 则P(S),?是格。|S|=1时和|S|=2时,此格的Hasse图为: 例2 设I+为集, 偏序关系为整除｜,则I+,｜是格, 此时对a,b∈I+, a、b的上确界是[a,b](最小公倍数)，a、b的下确界是(a,b)(最大公因数)。 例 设n为正整数,Sn是n的全部正因数的集合,则Sn,｜是格.S24,｜和 S30, |的Hasse图如下: 2 格诱导的代数系统 定义1.2 设A， 是一个格，如果在A上定义两个二元运算∨和∧，使得对于任意的a，b∈A，a∨b等于a和b的最小上界，a∧b等于a和b的最大下界，那么，就称A，∨，∧为由格A， 所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。 例3 给定S＝{a，b}，P(S)＝{φ，{a}，{b}，{a，b}}，那么，格P(S)，?如图1.3所示。 由格P(S)，?所诱导的代数系统为P(S)，∨，∧，其中运算∨是集合的并，运算∧是集合的交。故∨和∧的运算表可分别由表1.1的(a)和(b)所示。 3 子格 定义1.3 设A， 是一个格，由A， 诱导的代数系统为A，∨，∧，设B ? A且B≠φ，如果A中的这两个运算∨和∧关于B是封闭的，则称B， 是A， 的子格。 注意： 对于格A， ，设B是A的非空子集，尽管B， 必定是一个偏序集，然而B， 不一定是格，而且即使B， 是格，也不一定是A， 的子格。 例5 设S, 是一个格，其中 S={a, b, c, d, e, f, g, h}，如图所示。 例题1 设S， 是一个格，任取a∈S，构造S的子集T为：T＝{x | x∈S 且 x a}则T， 是S， 的一个子格。 4 对偶 在命题代数、集合代数中,我们应用了对偶原理。在比命题代数和集合代数更为一般的格与布尔代数中,我们也将应用对偶原理。对偶原理是很重要的概念，它出现在许多不同的场合和领域。下面是两个生活中的例： 人体镜面成像中,如果人体(或镜中的像)X能将左手覆于右臂之上,那么X的像(或原像)X*就能将右手覆于左臂之上。 国内汽车交通规则,司机座在驾驶室左侧,并规定汽车前行要沿马路右侧,超车须从左边道,红灯禁行时汽车可以右转弯; 英国汽车,司机座在驾驶室右侧,英国交通规则规定汽车前行要沿马路左侧,超车要从右边道,红灯禁行时汽车可以左