离散数学第12讲布尔表达式.ppt

该【离散数学第12讲布尔表达式 】是由【1557281760】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【离散数学第12讲布尔表达式 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。离散数学第12讲布尔表达式布尔表达式布尔表达式11布尔表达式主范式与布尔代数2主要内容:布尔表达式的定义重点:重点和难点:布尔表达式与布尔代数的关系3布尔表达式主范式难点:2020/12/182一、布尔表达式问题的引入:我们知道在布尔代数<B,∨,∧,ˉ>上,“∨”关于“∧”是可分配的,所以a∨(b∧c)=(a∨b)∧(a∨c)是<B,∨,∧,ˉ><B,∨,∧,ˉ>上的两个表达式是恒等式<B,∨,∧,ˉ>上有多少种互不恒等的表达式为了回答这些问题,我们先引入布尔表达式的概念,、布尔表达式设<B,∨,∧,ˉ>是一个布尔代数,现在考虑一个从Bn到B的函数。设B={0,1},下表给出了一个从B3到B的函数f。2020/12/184一、布尔表达式设B={0,a,b,1},右表给出了一个从B2到B的函数。2020/12/185一、布尔表达式下面我们试图用别的方法来描述函数,。定义1设<B,∨,∧,ˉ>是一个布尔代数,取值于B中元素的变元称为布尔变元;B中的元素称为布尔常元。定义2设<B,∨,∧,ˉ>是一个布尔代数,这个布尔代数上的布尔表达式定义如下:(1)单个布尔常元是一个布尔表达式;(2)单个布尔变元是一个布尔表达式;(3)如果e1和e2是布尔表达式,则(),(e1∨e2),(e1∧e2)也是布尔表达式;(4)有限次应用规则1-3形成的字符串是布尔表达式。2020/12/186一、布尔表达式定义3一个含有n个相异变元的布尔表达式,称为n元布尔表达式,记为E(x1,x2,…,xn)或f(x1,x2,…,xn),其中x1,x2,…,xn是式中可能含有的布尔变元。我们约定运算“∨”、“∧”和“ˉ”的优先级依次为“ˉ”,“∧”,“∨”。这样一来,布尔表达式中的某些圆括号可以省略,约定类似于命题公式。例2设<{0,a,b,1},∨,∧,ˉ,0,1>是布尔代数,则f1=af2=0∧xf3=(1∧x1)∨x2f4=f5=f6=都是这个布尔代数上的布尔表达式。2020/12/187一、布尔表达式定义4布尔代数<B,∨,∧,ˉ>上的布尔表达式f(x1,x2,…,xn)的值是指:将B的元素作为变元xi(i=1,2,…,n)的值而代入表达式以后(即对变元赋值),计算出来的表达式的值。例3(a)取x1=a,x2=b,则例2中的f3的值是f3=(1∧a)∨b=a∨b=1(b)设布尔代数<{0,1},∨,∧,ˉ,0,1>上的表达式f(x1,x2,x3)=,则f(1,0,1)=(0∧1)∧(0∨1)∧=0∧1∧0=02020/12/188一、布尔表达式定义5布尔代数<B,∨,∧,ˉ,0,1>上两个n元布尔表达式f1(x1,x2,…,xn)和f2(x1,x2,…,xn),如果对n个变元的任意指派,f1和f2的值均相等,则称这两个布尔表达式是等价的或相等的。记作f1(x1,x2,…,xn)=f2(x1,x2,…,xn)。在实践上,如果能有限次应用布尔代数公式,将一个布尔表达式化成另一个表达式,就可以判定这两个布尔表达式是等价的。例4在布尔代数<{0,1},∨,∧,ˉ>上的两个布尔表达式f1(x1,x2,x3)=(x1∨x2)∧(x1∨x3)和f2(x1,x2,x3)=x1∨(x2∧x3)是等价的。2020/12/189二、布尔表达式主范式与布尔代数定义5给出的等价(或相等)关系将n元布尔代数表达式集合划分成等价类,处于同一个等价类中的表达式都相互等价(或相等)。可以证明当|B|有限时,等价类数目是有限的。为此,我们考察以下定义。定义6给定n个布尔变元x1,x2,…,xn,表达式称为极小项。这里表示xi或两者之一。定义7具有如下形式的布尔表达式称为主析取范式。这里mi是极小项,αi是布尔常元。(i=0,1,2,…2n-1)。2020/12/1810