离散数学课件-第1章-8(上).pptx

离散数学Discrete Mathematics 汪荣贵 教授合肥工业大学软件学院专用课件2010.05第一页，共五十八页。第一章 逻辑与证明第二页，共五十八页。 学习内容1.1逻辑1.2 命题等价1.3 谓词和量词 1.4 对偶与范式1.5 推理规则1.6 证明导论1.7 证明的方法和策略1.8 数理逻辑的应用第三页，共五十八页。布尔函数及其表示引入 计算机和其他电子设备中的电路都有输入和输出，输入是0或1，输出也是0或1.电路可以用任何具有两个不同状态的基本元件来构造，开关和光学装置都是这样的元件。 1854年，乔治.布尔第一次给出逻辑的基本规则。1938年，克劳德.香农揭示了怎么用逻辑的基本规则来设计电路，这些基本规则形成了布尔代数的基础。 在本章中我们对布尔代数的基本性质进行了讨论，并利用布尔代数的基本元素构造的表达式来表示布尔函数，以及介绍一个能产生这些表达式的算法。 第四页，共五十八页。一、布尔函数1.引言 布尔代数提供的是集合{0，1}上的运算和规则，这个集合及布尔代数的规则还可以用来研究电子和光学开关。我们用的最多的三个布尔代数运算是补、布尔和与布尔积。 下面具体介绍一下这三种运算。1） 元素的补 用上划线加以标记，其定义为： 和第五页，共五十八页。2. 布尔和记为+或OR，它的值如下：3.布尔积记为 或AND ，它的值如下： 注意：为了避免混淆可以删去“ ”。就像在写代数积时一样。除非使用括号布尔运算的优先级规则是：首先计算所有补，然后是布尔积，然后是布尔和。第六页，共五十八页。【example 1】计算 的值。Solution： 根据补、布尔积与布尔和的定义得注：补、布尔积和布尔和分别对应于逻辑运算?、∨和∧，且0对应于F(假)，1对应于T(真)。关于布尔代数的结果可以直接翻译成关于命题的结果。相反地，关于命题的结果也能翻译成关于布尔代数的命题。第七页，共五十八页。2.布尔表达式和布尔函数布尔函数定义： 设B={0,1}, 则Bn={(x1,x2,…,xn) | xi ∈B, 1≤i≤n }是由0和1所能构成的所有n元有序列的集合。变元x如果仅从B中取值，则称该变元为布尔变元，即它的值只可能为0或1. 从Bn到B的函数称为n度布尔函数。第八页，共五十八页。【example 2】从布尔变元有序对之取值集合到集合{0，1}的函数 就是一个2度布尔函数，且F的值如下表所示。第九页，共五十八页。布尔函数也可用由变元和布尔运算构成的表达式来表示。关于变元x1,x2,…,xn的布尔表达式递归定义如下： 1）0，1，x1，x2，…，xn是布尔表达式； 2）如果E1和E2是布尔表达式，则也是布尔表达式。 每个布尔表达式都表示一个布尔函数，此函数的值是通过在表达式中用0和1替换变元得到的。 第十页，共五十八页。【example 3】 求由 表示的布尔函数的值。Solution： 这个函数的值由下表所示。第十一页，共五十八页。布尔函数还可以用图形来表示，方法是:将n元二进制数组与n方体的顶点一一对应，再标出那些函数值为的顶点。【example 4】例3中从B3到B的函数可如下表示：标出满足 的五个3元组 所对应的顶点。如下图所示，这些顶点用实心的黑圈标出。第十二页，共五十八页。n个变元的布尔函数F和G是相等的，当且仅当F( b1,b2,…bn )=G( b1,b2,..bn ),其中b1,b2,…bn 属于B.表示同一个函数的不同的布尔表达式称为是等价的。 例如，布尔表达式 都是等价的。布尔函数F的补函数是 此处 设F和G是n度的布尔函数，函数的布尔和F+G与布尔积FG分别为第十三页，共五十八页。2度布尔函数是从一个4个元素的集合到B的函数，这4个元素是B={0,1}中元素构成的元素对，B是有2个元素的集合，因而有16个不同的2度布尔函数。在下表中我们列出了这16个2度布尔函数的值，这16个不同的2度布尔函数被记为F1, F2, …, F16.第十四页，共五十八页。【example 5】有多少个不同的n度布尔函数？Solution： 由计数的乘积规则知：有2n个由0和1构成的不同的n元组。因为布尔函数就是对这2n个n元组中的每一个进行赋值，故乘积规则表明有 个不同的n度布尔函数。下表列出了1~6度不同布尔函数的个数。第十五页，共五十八页。3.布尔代数恒等式布尔代数有许多恒等式，下表中列出了其中最重