大连理工Chapter5(格与布尔代数)(2008-3-27)(4)

《大连理工Chapter5(格与布尔代数)(2008-3-27)(4)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学（格与布尔代数）DiscreteMathematics徐喜荣大连理工大学电信学院计算机系9/21/20211第六章格与布尔代数格和布尔代数在计算机科学中有广泛的应用，有限自动机理论,开关网络理论,逻辑设计等领域都直接地应用了格和布尔代数的结论。9/21/202126.1布尔代数的定义与性质定义6.1.1给定,其中和是S上的二元运算，′是S上的一元运算，0，1∈S。若对于任意x,y,z∈S,下列定律：(1)xy=yx，xy=yx交换律(2)x(yz)=(xy)(xz)，x

2、(yz)=(xy)(xz)分配律(3)x0=x，x1=x幺律(4)xx′=1，xx′=0互补律(5)*x(yz)=(xy)z，x(yz)=(xy)z结合律则称为布尔代数,,和′分别称为并(或和)、交(或积)和补运算，0和1分别称为和的零元和幺元。9/21/20213为了表示布尔代数具有两个特殊元素0和1，常常把布尔代数表示为。值得注意的是，定律(5)即结合律是多余的，它可以从其它定律推出，后面将指出这一事实。这里所以把它列出,是因为它是一

3、个重要定律。6.1布尔代数的定义与性质9/21/20214例6.1.1给定，其中B={0，1}，，和′的运算表6.1.1如下:可以验证，B中元素满足五定律.因此它是布尔代数。6.1布尔代数的定义与性质9/21/20215例6.1.2给定，其中P(X)是集合X的幂集，∪和∩是集合的并与交运算，ˉ是补运算,其定义为:若A∈P(X),Ã=X-A，即A的相对补。则是布尔代数，通常称为布尔集合代数。当X=，此时零元与幺元是同一元素，这

4、便是退化布尔代数。6.1布尔代数的定义与性质9/21/20216由布尔代数的定义可知，分配律成立。利用归纳法可以证明推广的分配律:a(bi)=(abi)a(bi)=(abi)更一般地有:(ai)(bj)=((aibj))(ai)(bj)=((aibj))6.1布尔代数的定义与性质9/21/20217下面讨论布尔代数的零元。对任意x，y∈S，若01，02为其零元，则x01=x，y02=y，特别令x=02和y=01得0201=02，0102=01，根据交换律有0201

5、=0102，故01=02，即零元是惟一的。6.1布尔代数的定义与性质9/21/20218定理6.1.1幺元“1”是惟一的。定理6.1.2若x∈S，则x的补x′是惟一的。6.1布尔代数的定义与性质9/21/20219定理6.1.3(对合律)若x∈S，则(x′)′=x定理6.1.4零元“0”与幺元“1”是互补的，即0′=1和1′=0。6.1布尔代数的定义与性质9/21/202110定理6.1.5(等幂律)若x∈S，则xx=x且xx=x。定理6.1.6(零律)若x∈S，则x1=1且x0=0。6.1布尔代数的定义与

6、性质9/21/202111定理6.1.7(吸收律)若x，y∈S，则x(xy)=x∧x(xy)=x。定理6.1.8(结合律)若x，y，z∈S，则(xy)z=x(yz)和(xy)z=x(yz)。6.1布尔代数的定义与性质9/21/202112定理6.1.9(德·摩根律)若x，y∈S,则(xy)′=x′y′和(xy)′=x′y′。利用归纳法可证明推广形式的德摩根律.6.1布尔代数的定义与性质9/21/202113定理6.1.10(可约律)若x，y，z∈S，则(xy=xz)∧(xy=xz)

7、y=z定理6.1.11若x，y，z∈S，则(xy)(yz)(zx)=(xy)(yz)(zx)定理6.1.12若x,y∈S,则xy=xxy=y。6.1布尔代数的定义与性质9/21/2021146.2格定义6.2.1给定布尔代数，则集合≤：={

8、xy=x∧x，y∈S}称为S上的偏序关系，并称为偏序集。由定义不难得到：x≤yxy=x根据定理6.1.12可有x≤yxy=y9/21/2021156.2格若S是有限集，则可用偏序图哈氏(Hass

9、e)图方便地表示。用小园圈○代表S中的元素，若x≤y且不存在z使x≤z≤y，则由x在底y在上连一线段。例如,布尔集合代数可图示如下，这里“≤”是并且仅分别考虑X={a}，{a，b}和{a，b，c}的情形。9/21/2021166.2格当X={a}时，当X={a，b}时，当X={a，b