南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）代数系统——第20章 布尔代数

布尔代数 离散数学一代数结构 南京大学计算机科学与技术系

布尔代数 离散数学－代数结构 南京大学计算机科学与技术系

内容提要 ·布尔函数 ·布尔代数 ·布尔代数的抽象定义 。布尔代数的性质 ·有限布尔代数 ·布尔代数与数字逻辑电路设计

内容提要  布尔函数  布尔代数  布尔代数的抽象定义  布尔代数的性质  有限布尔代数  布尔代数与数字逻辑电路设计 2

布尔函数 ●令B=0,1},B={c1,,x川x,∈B,i=1,,n,从B到B 的函数称为n度布尔函数，f:Bn→B。 ·取值范围为B的变元称为布尔变元，x∈B。 ●n度布尔函数的个数：2个2n(22,24,28,…) ·三种说法 。含个命题变量的命题逻辑表达式 ●n度布尔函数f:Bm→B 。有n个输入和一个输出的逻辑电路 3

布尔函数  令B={0, 1}, Bn={(x1 , …, xn )| xiB, i =1, …, n}, 从Bn到B 的函数称为n度布尔函数， f : BnB。  取值范围为B的变元称为布尔变元 ，xB。  n度布尔函数的个数：22 n (22 , 24 , 28 , …)  三种说法  含n个命题变量的命题逻辑表达式  n度布尔函数 f : BnB  有n个输入和一个输出的逻辑电路 3

一个逻辑电路设计的例子 举重比赛中三个裁判中两个或者两个以上判定为成功则该 次成绩有效，设计一个电子打分器，输出一个结果：“成功” 或”失败”。 布尔函数：fc,y,z)=1if.xy,z fx,v,) 至少有两个为1。 0 0 0 0 0 0 1 0 0 1 0 0 相应的布尔表达式： 0 1 1 1 (x'NNZ)V (AV)V 1 0 0 0 AVAZ)V (XAVAZ) 1 0 1 1 0 1 1 1 1

一个逻辑电路设计的例子  举重比赛中三个裁判中两个或者两个以上判定为成功则该 次成绩有效, 设计一个电子打分器, 输出一个结果: “成功” 或”失败”。 布尔函数: f(x,y,z)=1 iff. x,y,z 至少有两个为1。 x y z 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 0 0 0 1 0 1 1 1 相应的布尔表达式: (x’yz) (xy’z) (xyz’) (xyz) 4

回顾：命题表达式的主析取范式 。求(p→)分r的主析取范式 (pAr)v(MAr)V(PA-qN-T)(析取范式) PΛr←→PΛ(qVq)Λr →(pΛq∧r)V(pΛqΛ) 9∧→(p∧IAr)V(pΛ4Ar) 。(PAqA)V(-p∧qΛ)V(PAqA)Y (pAgn-T) ●(P∧qΛ)V(P∧qΛ)V(PAqA)VpΛq∧) 001 011 100 111 5

回顾：命题表达式的主析取范式  求 (pq)  r 的主析取范式  (¬p r)  (q r)  (p¬q¬r ) （析取范式）  (¬p ¬q  r)  (¬p  q  r)  (p  q  r)  (p ¬q¬r )  (¬p ¬q  r)  (¬p  q  r)  (p¬q¬r)  (p  q  r)  001 011 100 111 ¬p  r  ¬p  (¬q  q)  r  (¬p  ¬q  r )  (¬p  q  r ) q  r  ( p  q  r )  (¬p  q  r ) 5