当前位置：文档之家 › 16布尔表达式

16布尔表达式

  • 格式：ppt
  • 大小：324.50 KB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

第五课布尔表达式IF语句

第五课布尔表达式IF语句

第五课
布尔表达式、IF语句
var y,x,a:real; begin writeln('Input a and x: '); readln(a, x); if x<a then y:=a; if x=a then y:=1; if x>a then y:=x; writeln('y=',y) end. 程序运行结果如下： Input a and x: 1 4 (从键盘输入a=1，x=4) y=4.0000000000E+00
第五课
布尔表达式、IF语句
例 4-3 读入一个小写字母。如果这个字母在字母表的前半部，则 输出其后继字母；否则输出其前趋字母。
var letter : char; begin readln(letter); if letter <= ’m’ then writeln(Succ(letter)) else writeln(Pred(letter)); readln; end.
第五课
布尔表达式、IF语句
FALSE 布尔表达式 布尔表达式
FALSE
TRUE
TRUE
பைடு நூலகம்
语句1
语句1
语句2
第五课
布尔表达式、IF语句
例4-1 输出两个整数中的较小数。
program example4_1_1; var x,y:integer; begin readln(x,y); if x<y then writeln(x) else writeln(y) end.
本例也可以用两条if语句来实现，程序如下。
program example4_1_2; var x,y: integer; begin readln(x,y); if x<y then writeln(x); if y<=x then writeln(y) end.

布尔表达式的标准形式

布尔表达式的标准形式

布尔表达式的标准形式
布尔表达式的标准形式有两种：
1. 简化标准形式（Simplified Standard Form）：每个布尔表达式都可以通过逻辑运算符（与、或、非）和最小项或最大项的组合表示。

最小项是指布尔表达式中只包含一个变量的项，最大项是指布尔表达式中包含所有变量的项。

简化标准形式的布尔表达式可以通过逻辑运算符和最小项或最大项的组合表示，且具有最简化的形式。

2. 范式标准形式（Canonical Standard Form）：每个布尔表达式都可以通过逻辑运算符（与、或、非）和字母表的所有变量的组合表示。

范式标准形式的布尔表达式可以通过逻辑运算符和字母表的所有变量的组合表示，且具有标准的形式。

范式标准形式包括两种形式：合取范式（Conjunctive Normal Form，简称CNF）和析取范式（Disjunctive Normal Form，简称DNF）。

合取范式是指布尔表达式由多个合取式（由逻辑与运算符连接的子句）相连而成，析取范式是指布尔表达式由多个析取式（由逻辑或运算符连接的子句）相连而成。

【国家自然科学基金】_布尔代数_基金支持热词逐年推荐_【万方软件创新助手】_20140730

【国家自然科学基金】_布尔代数_基金支持热词逐年推荐_【万方软件创新助手】_20140730

2009年 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
2012年 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
科研热词 布尔函数 流密码 代数攻击 非线性度 代数免疫阶 代数免疫度 代数免疫 br0代数 高层次数据通路 非零零化子 零化子 零化多项式 逻辑代数 自相关函数 线性结构 线性码 粗糙集 等价验证 相关免疫 电子设计自动化 正蕴涵滤子 模糊滤子 模糊布尔滤子 概念设计 核算子 析取范式 旋转对称布尔函数 支撑点集 扩散性 形式验证 弹性函数 布尔滤子 布尔代数 布尔mp滤子 差别矩阵 属性约简 对称布尔函数 密码函数 完备布尔代数 多项式符号代数 多维plateaued函数 基本对称布尔函数 固执滤子 商 功能树 创新推理 关联mp滤子 仿射空间 仿射子空间 代数正规形快速变换 代数正规型 代数次数
1 1 1 1 1 1
53 54 55 56 57 58 59 60 61 62 63 64 65
人工智能 二值决策图 事件分离状态 串空间模型 s盒 semi-bent函数 rijndael算法 psmtl-代数 psbck-代数 petri网 m-mbent函数 kloosterman和 hadamard变换

STEP7中的基本数据类型-重要

STEP7中的基本数据类型-重要

STEP7中的基本数据类型⑴位(BOOL )位数据的数据类型为BOOL (布尔)型，在软件编程中BOOL变量的值1和0常用英语词TURE (真)和FALSE (假)来表示，对应二进制数中的“ 1和“0,常用于开关量的逻辑运算，存储空间为1位。

⑵字节(BYTE)字节数据长度为8位，数据格式为B#16#，B代表BYTE，表示数据长度为一个字节(8位)，# 16#表示十六进制，取值范围为B#16#0〜B#16#FF。

⑶字(WORD )字数据长度为16位，这种数据可采用4种方法进行描述。

二进制：二进制的格式为 2 #，如2 # 101，取值范围为2# 0〜2# 1111_1111_1111_1111, 书写时每4位可用下划线隔开，也可直接表示为2# 111111111111十六进制：十六进制的格式为W # 16#, W代表WORD，表示数据长度为16位，#16#表示十六进制，数据取值范围为W # 16# 0〜W # 16 # FFFF。

BCD码：BCD码的格式为C#,取值范围为C# 0〜C# 999。

BCD码是用4位二进制表示1位十进制数，4位二进制中的0000〜1001组合分别表示十进制中的0〜9, 4位二进制中的1010〜1111组合放弃不用。

BCD码的最高4位用来表示符号，十六位BCD码的取值范围为—999〜+999。

在STEP7的数据格式中，BCD码的取值只取正值，与最高4位的符号无关。

无符号十进制数：无符号十进制数的格式为 B #( X, X),取值范围为B #( 0, 0)〜B #( 255, 255),无符号十进制数是用十进制的0〜255对应二进制数中的0000_0000〜1111_1111 ( 8位),16位二进制数就需要两个0〜255的数来表示，例如：B# (12, 254)= 2# 0000_1100_1111_1110_12 ― 254上面4种数据都是描述一个长度位16位的二进制数，无论你使用哪种方式都可以。

第十章 布尔代数

第十章 布尔代数
19
10 布尔代数 Boolean Algebra
实数集上加法运算， 是单位元； 例 ： 实数集上加法运算 ， 0 是单位元 ； 乘 法运算则1是单位元。 法运算则1是单位元。 实数集R 上定义运算∀ a,b∈ a*b=a， 例 ： 实数集 R 上定义运算 ∀ a,b∈R ， a*b=a ， 不存在左单位 单位元 使得∀ *b=b; 不存在左单位元，使得∀b∈R，el*b=b; 对一切a b*a=b， 对一切a∈R，∀b∈R，有b*a=b， 该代数系统不存在左单位 单位元 ∴该代数系统不存在左单位元。 但是R中的每一个元素a都是右单位 单位元 但是R中的每一个元素a都是右单位元。
4
10.1 布尔函数 Boolean Functions
设B={0, 1}, 则Bn={(x1,x2,…,xn)|, xi∈B, 1≤i≤n}是由 和1构成的所有 元有序列 是由0和 构成的所有 构成的所有n元有序列 是由 的集合。 的函数称为n元 的集合。从Bn到B的函数称为 元布尔函 的函数称为 数。 例：F(x,y)=x+y
单位元=1,零元=0, 单位元= 零元=
23
10.1 布尔函数 Boolean Functions
布尔代数抽象的定义： 上的二元运算， 布尔代数抽象的定义：∧,∨是B上的二元运算， 是一元运算，如果∀a,b,c∈B,满足如下 满足如下： 是一元运算，如果∀a,b,c∈B,满足如下： H1:a (交换律 交换律) H1:a∧b=b∧a,a∨b=b∨a (交换律) H2:a H2:a∧(b∨c)=(a∧b)∨(a∧c) (分配律 分配律) a∨(b∧c)=(a∨b)∧(a∨c) (分配律) H3:B中有元素0 :B中有元素 H3:B中有元素0和1, (同一律 同一律) 对∀a∈B,a∧1=a,a∨0=a (同一律) H4: B,有 B,使 (互补律 互补律) H4:∀a∈B,有a∈B,使a∨a=1,a∧a=0 (互补律) ,0,1>是布尔代数 是布尔代数。 则<B,∧,∨ , ,0,1>是布尔代数。 B,

python-布尔表达式

python-布尔表达式

python-布尔表达式1、布尔表达式条件语句和循环语句都使⽤布尔表达式作为条件布尔值为真或假，以False和True表⽰，前⾯经常使⽤布尔表达式⽐较两个值，如：while x>=02、布尔操作符（1）布尔操作符： and，or和 not布尔运算符and和or⽤于组合两个布尔表达式，并产⽣⼀个布尔结果<expr> and <expr><expr> or <expr>not运算符是⼀个⼀元运算符，⽤来计算⼀个布尔表达式的反not <expr>（2）Python中布尔操作符的优先级，从⾼分到低分依次是not、 and最低是or。

所以上⾯的达式等于如下这个带括号的版本壁球⽐赛计分例⼦a和b代表两个壁球选⼿的分数规则1：只要⼀个选⼿达到了15分，本场⽐赛就结束；如果⼀⽅打了七分⽽另⼀⽅⼀分未得时，⽐赛也会结束if (a==15 or b==15)or (a==7 and b==0) or (a==0 and b==7):print('⽐赛结束')规则2：需要⼀个团队赢得⾄少两分才算赢，即其中⼀个队已经达到了15分，且分数差异⾄少为2时⽐赛结束if (a==15 or b==15)or (a==7 and b==0) or (a==0 and b==7):print('⽐赛继续')（3）布尔代数（4）布尔表达式作为决策只要⽤户响应⼀个“Y” 程序就继续。

为了让⽤户输⼊⼀个⼤写或⼩写，可以使⽤以下的循环：对于序列类型来说，⼀个空序列被解释为假，⽽任何⾮空序列被指⽰为真1 >>> bool(0)2 False3 >>> bool(1)4 True5 >>> bool(32)6 True7 >>> bool(y)8 Traceback (most recent call last):9 File "<pyshell#6>", line 1, in <module>10 bool(y)11 NameError: name 'y'is not defined12 >>> bool('y')13 True14 >>> bool('')15 False16 >>> bool([])17 False这⾥可以解释，下⾯的程序，是判断response[0]等于y,或者Y，由于Y是bool型中始终为True，所以始终符合条件，形成死循环。

布尔逻辑运算符的数字符号

布尔逻辑运算符布尔逻辑运算符有4种，分别是And（逻辑与）、Or（逻辑或）、Not（逻辑非）、Xor（逻辑异或）。

1、And（逻辑与）逻辑与，释义是相当于生活中说的“并且”。

&&称为逻辑与，只有两个操作数都是true，结果才是true。

&& 称为简洁与或者短路与，也是只有两个操作数都是true，结果才是true。

2、Or（逻辑或）如果一个操作数或多个操作数为true，则逻辑或运算符返回布尔值true；只有全部操作数为false，结果才是false。

3、Not（逻辑非）逻辑非就是指本来值的反值。

4、Xor（逻辑异或）如果a、b两个值不相同，则异或结果为1。

如果a、b两个值相同，异或结果为0。

扩展资料：布尔逻辑（台湾翻译、布林运算、中国大陆翻译布尔逻辑）是以爱尔兰柯克皇后学院的英国数学家乔治·布尔命名的。

他首先定义了十九世纪中旬的逻辑代数系统。

现在，布尔逻辑在电子、计算机硬件和软件中有许多应用。

1937年，克劳德·埃尔伍德·香农展示了布尔逻辑在电子学中的应用。

集合代数是用来引入布尔逻辑的一种方法。

文的图表也用来显示各种布尔逻辑语句所描述的集合关系。

布尔逻辑运算符的由来：布尔用数学方法研究逻辑问题，成功地建立了逻辑演算。

他用等式表示判断，把推理看作等式的变换。

这种变换的有效性不依赖人们对符号的解释，只依赖于符号的组合规律。

这一逻辑理论人们常称它为布尔代数。

20世纪30年代，逻辑代数在电路系统上获得应用，随后，由于电子技术与计算机的发展，出现各种复杂的大系统，它们的变换规律也遵守布尔所揭示的规律。

运算符、布尔运算、表达式、标准函数

运算符、布尔运算、表达式、标准函数hb007 发表于 2006-3-22 19:24:26一、运算符1、算术运算符例如：4 +5 = 9 8 - 3 = 52 *3 = 6 12 * 24 = 4085 / 2 = 2.5 34 / 12 = 2.83 5 div 2 = 2 123 div 4 = 30 5 mod 2 = 1 12 mod 5 = 22、逻辑运算符它们的运算真值表如下：3、关系运算符例如：设a,b为标准数据类型的变量，则：a=b 如果a等于b结果为真，否则为假。

a<>b 如果a不等于b结果为真，否则为假。

a<b 如果a小于b结果为真，否则为假。

a>b 如果a大于b结果为真，否则为假。

a<=b 如果a小于等于b结果为真，否则为假。

a>=b 如果a在于等于b结果为真，否则为假。

例如：5=5 结果为真。

5=10 结果为假。

false<true 结果为真。

false>true 结果为假。

'A'<'C' 结果为真。

12.5>-8 结果为真。

24>=21 结果为真。

10.3<10 结果为假。

二、运算符的优先级三、布尔运算要判断“X>Y”是否成立，其结果不是一个算术量（即数值），而是“成立”或“不成立”，也可以用“真”表示“成立”，用“假”表示“不成立”，也就是说，它的结果是一个逻辑值（“真”或者“假”）。

逻辑运算又叫布尔运算。

布尔(Bool)是英国数学家的名字，他首先提出对二值变量进行逻辑运算的代数，称为布尔代数。

1、布尔常量Pascal语言中“真”用true表示，“假”用False表示。

所以布尔类型只有true与false两个常量。

2、布尔型符号常量（boolean）在程序的说明部分，可以定义布尔符号常量。

如：constt=true;f=false;执行部分就可以用t代表true，用f 代表false。

SIMPLE语言定义

SIMPLE语言定义一、字符集定义1．<字符集> →<字母>│<数字>│<单界符>2．<字母> →A│B│…│Z│a│b│…│z3．<数字> →0│1│2│…│94．<单界符> →+│-│*│/│=│<│>│(│)│[│]│:│. │; │, │'二、单词集定义5．<单词集> →<保留字>│<双界符>│<标识符>│<常数>│<单界符>6．<保留字> →and│array│begin│bool│call│case│char│constant│dim│do│else│end│false│for│if│input│integer│not│of│or│output│procedure│program│read│real│repeat│set│stop│then│to│true│until│var│while│write7．<双界符> →<>│<=│>=│:= │/*│*/│..8．<标识符> →<字母>│<标识符> <数字>│<标识符> <字母>9．<常数> →<整数>│<布尔常数>│<字符常数>10．<整数> →<数字>│<整数> <数字>11．<布尔常数> →true│false12．<字符常数> →' 除{'} 外的任意字符串'三、数据类型定义13．<类型> →integer│bool│char四、表达式定义14．<表达式> →<算术表达式>│<布尔表达式>│<字符表达式>15．<算术表达式> →<算术表达式> + <项>│<算术表达式> - <项>│<项>16．<项> →<项> * <因子>│<项> / <因子>│<因子>17．<因子> →<算术量>│- <因子>18．<算术量> →<整数>│<标识符>│（<算术表达式> ）19．<布尔表达式> →<布尔表达式> or <布尔项>│<布尔项>20．<布尔项> →<布尔项> and <布因子>│<布因子>21．<布因子> →<布尔量>│not <布因子>22．<布尔量> →<布尔常量>│<标识符>│（<布尔表达式> ）│<标识符> <关系符> <标识符>│<算术表达式> <关系符> <算术表达式> 23．<关系符> →<│<>│<=│>=│>│=24．<字符表达式> →<字符常数>│<标识符>五、语句定义25．<语句> →<赋值句>│<if句>│<while句>│<repeat句>│<复合句>26．<赋值句> →<标识符> := <算术表达式>27．<if句>→if <布尔表达式> then <语句>│if <布尔表达式> then <语句> else <语句> 28．<whilet句> →while <布尔表达式> do <语句>29．<repeat句> →rpeat <语句> until <布尔表达式>30．<复合句> →begin <语句表> end31．<语句表> →<语句> ；<语句表>│<语句>六、程序定义32．<程序> →program <标识符> ；<变量说明> <复合语句> .33．<变量说明> →var <变量定义>│ε34．<变量定义> →<标识符表> ：<类型> ；<变量定义>│<标识符表> ：<类型> ；35．<标识符表> →<标识符> ，<标识符表>│<标识符>七、SIMPLE语言单词编码八、实验一：设计SAMPLE语言的词法分析器检查要求：a)启动程序后，先输出作者姓名、班级、学号（可用汉语、英语或拼音）；b)请求输入测试程序名，键入程序名后自动开始词法分析并输出结果；c)输出结果为单词的二元式序列（样式见样板输出1和2）；d)要求能发现下列词法错误和指出错误性质和位置：非法字符，即不是SAMPLE字符集的符号；字符常数缺右边的单引号（字符常数要求左、右边用单引号界定，不能跨行）；注释部分缺右边的界符*/（注释要求左右边分别用/*和*/界定，不能跨行）。

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

2n
n
一个 n 元布尔表达式化成等价的主析取范式, 主要应用德· 摩根定
律等,其方法与“数理逻辑”中化成主析取范式的方法完全一致。
德· 摩根定律
非(P 且 Q)＝(非 P)或(非 Q) 非(P 或 Q)＝(非 P)且(非 Q)
平行地可讨论极大项和主合取范式:
二、布尔表达式主范式与布尔代 数
定义8 给定n个布尔变元x1,x2,…,xn, 表达式
例5 将布尔代数<{0, a, b, 1},∨,∧,ˉ, 0, 1>上的布尔表达式
f ( x1 , x2 ) (a x1 ) ( x1 x2 ) (b x1 x2 )
化成主析取范式。
f ( x1 , x2 ) (a x1 ) ( x1 x2 ) (b x1 x2 )
三、布尔函数
布尔代数<B,∨,∧,ˉ, 0, 1>上的任一n元布尔表达式f(x1,x2,…,xn), 对n个变元的每一指派, 都可得到相应的表达式的值, 这值属于B。 所以, f(x1,x2,…,xn) 可视为 Bn 到B 的函数。但n 个变元的主析取范式 (或主合取范式)最多只有 B 个,所以,至多只能代表 B 个不同的函 数。从B 到B的函数共有 B 个。现分情况讨论:
是<B,∨,∧,ˉ>上的一个恒等式.
那么如何判定<B,∨,∧,ˉ>上的两个表达式是恒
等式? <B,∨,∧,ˉ>
一、布尔表达式
设<B,∨,∧,ˉ>是一个布尔代数,现在考虑一个 从Bn到B的函数。 设B={0, 1}, 下表给出了一个从B3到B的函数f。
一、布尔表达式
设B={0,a,b,1}, 右
表给出
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

称为含有n元的布尔表达式，记为E(x1,x2,„,xn)，
其中x1,x2,„,xn为变元。
定义6-5.3
布尔代数<A,∨,∧,->上的一个含有n
元的布尔表达式E(x1,x2,„,xn)的值是指：将A中的 元素作为变元xi(i=1,2,„,n)的值来代替表达式中 相应的变元（即对变元赋值）,从而计算出表达式的值。 定义6-5.4 布尔代数<A,∨,∧,->上两个n元的布
(e1),(e1∨e2) ,(e1∧e2) 也是布尔表达式。 （4）除有限次使用条款（2），（3）生成的表达式 是布尔表达式外，没有别的是布尔表达式。 例1 给出了两个布尔函数的例子,见表6-5.1和6-5.2。 15 例2 给出了布尔表达式的例子,见P-262页。
定义6-5.2
一个含有n个相异变元的布尔表达式，
12
. 设 f(a∨b)=S3,若xS3,则x是满足xa∨b的原 子，所以必有xa或xb，这是因为： 若xa且xb,则由引理6-4.4可知必有 xa且xb,所 以xa∧b= a∨b 。再由条件xa∨b,便得 x (a∨b)∧(a∨b)=0 这与x是原子相矛盾。 因此，若xa则xS1或者若xb则xS2 ，所以 x S1∪S2 这就证明了S3 S1∪S2 。 反之,若xS1∪S2, 则xS1或xS2,若xS1，则 xa a∨b 所以xS3,同理，若xS2，则 xb a∨b 所以xS3,这就证明了 S1∪S2 S3 。 综上所述，就有S3 = S1∪S2 ，即 13 f(a∨b)= f(a)∪f(b)
次。
4
> 是一个格，且具有全下界0， 如果有元素a盖住0，则称元素a为原子。
原子：与0相邻且比0“大”
定义6-4.5 设<A, ≤
> 是一个具有全下界0的有限格， 则对于任何一个非零元素b（即不等于全下界0的元素） 至少存在一个原子a ，使得a ≤ b 。 证明：若b是原子，则有b ≤ b ，若b不是原子，则必 有b1存在，使得0b1b 若b1是原子，则定理得证，否则，必存在b2使得 0b2b1b 由于<A, ≤ >是一个有下界的有限格，所以通过有限不骤 总可以找到一个原子bi ，使得0bi... b2b1b
尔表达式为E1(x1,x2,„,xn)和E2(x1,x2,„,xn), 如果对于n个变元的任意赋值xi=xi’,xi’A时均有
则称这两个布尔表达式是等价的。
E1(x1’,x2’,„,xn’)=E2(x1’,x2’,„,xn’)
16
例4 布尔代数<{0,1},∨,∧,->上两个3元的布尔表达 式为 E1(x1,x2,x3)=(x1∧x2)∨(x1∧x3) 和 E2(x1,x2,x3)=x1∧(x2∨x3) 验证这两个布尔表达式是等价的。 E1(0,1,1)=(0∧1)∨(0∧0)=0 E2(0,1,1)=0∧(1∨0)=0 E1(1,1,1)=(1∧1)∨(1∧0)=1 E2(1,1,1)=1∧(1∨0)=1 E1(0,0,0)=(0∧0)∨(0∧1)=0 E2(0,0,0)=0∧(0∨1)=0 等等(全部赋值状况共8种需要验证。)。 结论：一个n元布尔表达式确定一个从An到A的函数。 定义6-5.5 设<A,∨,∧,->为布尔代数,一个从An到A 的函数，如果它能够用<A,∨,∧,->上的一个n元布尔表达 式E(x1,x2,„,xn)来表示，-5.1 对于两个元素的布尔代数<{0,1},∨,∧, ->, 任何一个从{0,1}n到{0,1}的函数,都是布尔函数。
证明：n元布尔表达式若有x1’∧x2’∧„∧xn’形式(其 中xi’是xi或xi中的任一个),则称它为小项,若一个布尔表 达式能表示成小项的并,则称它为析取范式。对于一个从 {0,1}n到{0,1}的函数,先用那些使函数值为1的有序n元组 分别构造小项，其中 xi 若n元组中第i个分量为1 ’= xi xi 若n元组中第i个分量为0 由这些小项构成的析取范式就是原函数对应的布尔表达式。
6-4 布尔代数 定义6-4.1 一个有补分配格称为布尔格。
求一个元素的补元素可以看作一元运算，称为补运算。 定义6-4.2 设<A,∨,∧，- > 是由布尔格<A, ≤
>
是所诱导的代数系统。称这个代数系统为布尔代数。
∪,∩，~>是由布尔格<(S),> 是所诱导的代数系统。这个代数系统为布尔代数。 当S={a,b}时的运算表如表6-4.1所示。P-253页
第(2)部分证明：<A,∨,∧,- >和<(S),∪,∩,~>同构 第2部分同构性格证明： . 设 f(a∧b)=S3,若xS3,则x必是满足xa∧b的原 子，因为a∧ba和a∧bb，所以xa且xb，推得xS1 = f(a)且xS2 = f(b) ，即xS1∩S2 ，这就证得 S3 S1∩S2 。 反之,若xS1∩S2,则xS1且xS2,所以x必是满足xa 和xb的原子,推得x必是满足xa∧b的原子,所以xS3,这 就证明了 S1∩S2 S3 。 综上所述，就有S3 = S1∩S2 ，即 f(a∧b)= f(a)∩f(b)
其中aj1,aj1,…,ajt是原子。因为b是aj1,aj1,…,ajt的最小上 界,所以必有aj1 ≤ b, aj2 ≤ b,..., ajt ≤ b。而a1, a2, … , ak是A 中所有满足ai ≤ b （i=1,2,…,k）的不同原子。 所以必有 t≤k 反设tk,那么在a1, a2, … , ak中必有aj0且aj0≠ajl 于是,由aj0∧(aj1∨aj1∨…∨ajt)= aj0∧(a1∨a2∨…∨ak) 即 (aj0∧aj1)∨ (aj0∧aj2)∨ … ∨ (aj0∧ ajt) = (aj0∧a1)∨ (aj0∧a2)∨ … ∨ (aj0∧ ak) 导致的0= aj0矛盾。tk假设不成立 。 T=k定理得证。 8
因为a∧ba, a是原子,所以只能是
a∧b=0 或 a∧b=a 若a∧b=0，则 a∧(b) =0 ，由引理6-4.1得 ab； 若a∧b=a,由引理6-1.6得ab。
9
定理6-4.3(Stone 表示定理) 设<A,∨,∧,- > 是由
>所诱导的一个有限布尔代数， S是布 尔格中的所有原子的集合，则<A,∨,∧,- >和<(S), ∪,∩,~>同构。 证明：本定理的证明过程分三部分
例1 设<(S),
1
2
定理6-4.1 在一个有界分配格中，对于布尔代数中的 任意两个元素a，b，必定有
( a )=a a∨b= a∧b a∧b= a∨b 证明：只证第(2)个等式
先证互补的两个式子相并等于全上界“1”。
(a∨b)∨(a∧b)= ((a∨b)∨a)∧((a∨b)∨b) =(b∨(a∨a))∧(a∨(b∨b)) =(b∨1)∧(a∨1) =1 再证互补的两个式子相交等于全下界“0”。 (a∨b)∧(a∧b)= 0
5
定理6-4.2 设<A, ≤
引理6-4.1 设在一个布尔格中,b∧c=0当且仅当b ≤c。
证明：(1)先证 b∧c=0 b ≤ c 若 b∧c=0， 因为 0∨c=c ， 则 (b∧c)∨c=c
根据分配性，就有
(b∨c) ∧ (c∨c) =c 即 (b∨c) ∧1 =c 所以 b∨c =c 又因为 b ≤ b∨c 所以 b≤c (2)再证 b ≤ c b∧c=0 若b≤c,则b∧cc∧c,即b∧c0，所以b∧c=0
.最后证明同构性的f(a)= f(a)式： 将S看作全集,另f(a)=S1,则f(a)=S-S1=S-f(a),可以证 明xf(a)当且仅当xa,这是因为,若xf(a),必有xa,则 由引理6-4.4可知必有 xa,反之,若原子x满足xa,则必 有xa,所以xf(a) 。 还可以证明,对于原子x,xa当且仅当xf(a),这是 因为,若xa而xf(a),将导致xa的矛盾,所以xf(a),反 之,若xf(a)而xa,也将导致xf(a)的矛盾,所以xa 。 另外还可以证明, xf(a)当且仅当xf(a),所以,对于 原子x, xf(a)当且仅当xf(a),因此, f(a)=f(a) 第2部分同构性证明完毕。 (3)总结概括结论:<A,∨,∧,- >和<(S),∪,∩,~>同构。 推论6-4.1 有限布尔格的元素个数必定等于2n，其中n 是该布尔格中所有原子的个数。 推论6-4.2 任何一个具有2n个元素的有限布尔代数都 14 是同构的。
有限布尔格<A,
(1)构造一个映射，并证明它是双射（既是入射又是满 射）； (2)描述代数系统<A,∨,∧,- >和<(S), ∪,∩,~> 同构并证明之； (3)总结概括结论。
10
第(1)部分证明：对于任意非0aA,必有的唯一表示： a=a1∨a2∨„∨ ak （引理6-4.2a的原子表示） 其中aia （i=1,2,…,k）,作映射 f(a)=S1 = {a1,a2 ,…, ak} 那么，这个映射是 一个从A到(S)的一个双射。 第1部分双射证明： . 对于全下界0A，规定 f(0)= 。 .如果 S1 ={a1,a2 ,…, ak}(S)，而有a,bA,使得 f(a)= f(a)=S1 ，则a=a1∨a2∨„∨ ak = b， 所以 f是一个从A到(S)的一个入射。 .对于任一个S1(S)，若S1 ={a1,a2 ,…, ak}，则由 于运算∨的封闭性，所以 a1∨a2∨„∨ak = aA 这就说明(S)中任一元素，必是A中某个元素的象，所以 是一个从A到(S)的一个满射。 11 第1部分双射证明完毕。
6-5 布尔表达式 定义6-5.1 设<A,∨,∧,->为布尔代数,如下递归 地定义A上布尔表达式(Boolean （1）布尔常元(取值于A的常元)是布尔表达式,布尔
expressions)：
常元常用a,b，c等符号表示。