乐读窝

程序员的数学思维修炼

乐读窝 > 科普学习 > 程序员的数学思维修炼

8.4考虑到各种可能了吗

书籍名:《程序员的数学思维修炼》    作者:周颖



我们经常可以在媒体中看到有一些招聘、招生等信息,这些信息中通常都会对应聘者(或应考者)的资格做一些限制,并且这些限制信息一般描述得比较详细。可是,如果我们仔细对这些信息进行分析,可能会发现有的单位发布的资料限制信息存在漏洞(或者条件有重叠),让人读起来感觉不够清晰、明了。

这时,我们可以运用命题逻辑来对这些资格限制条件进行分析。将发布的资格限制条件看作为一个复合命题,在进行分析时,通常需要将复合命题分解成简单命题,以方便用逻辑表达式来表示。对分解出的简单命题进行分析,可以查看复合命题的描述有没有重复和遗漏之处。



8.4.1 逻辑重叠的实例


首先来看一个逻辑重叠的实例。

某市教育局为了解决外来务工人员子女上学问题,每年都要举办外地生招生考试,今年举行该考试之前,教育局公布了参加此次考试考生的资格限制条件。该教育局官网发布公告表述为:

符合以下条件之一的学生可以参加本次网上报名。

(1)非本市中心城区户籍,且未在本市中心城区参加高中阶段教育学校统一招生考试报名的初三毕业生。

(2)本市中心城区户籍,且未在本市中心城区参加高中阶段教育学校统一招生考试报名的初三毕业生。

通过对以上两条限制条件进行分析,可分解出两个简单命题:

定义了这两个简单命题之后,就可以定义每个条件的逻辑表达式了。

第一个条件的命题公式为:

第二个条件的命题公式为:

符合以上两个条件之一,就有报名资格。也就是说,这两个条件之间可用联接词“或”进行联接,于是可得到如下命题公式:

根据逻辑运算的相关规则,将以上命题公式转换为如下逻辑表达式:

对于以上逻辑表达式,可进行化简运算,具体计算过程如下:

可以看出,经过化简后,看起来很复杂的一个逻辑表达式最后只剩一项,即“非B”。也就是说,只需要满足“非(参加本市中心城区高中招生考试)”,即只要没有参加本市中心城区高中招生考试,就满足报名条件。而该市教育局发布的公告中的条件就有了重叠,而这种重叠让人看起来觉得条件较多,需要分门别类去核对自己是否满足报名条件。其实质就只有一个条件:“未在本市中心城区参加高中阶段教育学校统一招生考试报名的初三毕业生”。

提示,本章后面还要介绍一种用卡诺图化简逻辑表达式的方法。

对于以上逻辑重叠的实例,不会影响考生的判断,不同类别的考生能够根据条件作出正确的判断,只是稍显啰嗦而已。

我们还可能会遇到另外一种逻辑重叠,且重叠部分自相矛盾,使得规则不符合逻辑的情况。看下面的例子:

某超市开展促销活动,顾客单张购物小票达到一定金额后将送购物券,具体的送券条件如下:

列一个表格,看看不同购物金额可领取的购物券金额,如表8-8所示。

表8-8 不同购物金额对应的购物券

可以看出,表8-8中标了箭头的行都存在重叠,按送券规则第1条,购物1000元只能领取50元购物券1张;但是按第2条规则,1000元又可领取50元购物券2张。类似地,2000元时也存在重叠的问题。



8.4.2 逻辑遗漏的实例


在定义逻辑规则时有可能出现重叠,当然也有可能出现遗漏。仍然以超市促销政策为例,假设定义以下规则:

可以看出,以上规则只定义了购物金额不足500元(<500)和超过500元(>500)的情况,但是,遗漏了购物金额正好是500元的情况。这样,就使得定义的规则不恰当了。

可以将以上规则修改为以下形式:

将“超过500元”修改为“500元以上”,就将所有情况都包含了。

通常,用“xx以上”或“xx以下”,都表示包含“xx”这个值。因此,如果将规则写成以下形式,又会出现重叠的情况(两个规则都包含500元):



8.4.3 用数轴确定边界


通过前面的例子可看出,在定义规则时,如果稍有疏忽就会导致定义的规则出现重叠或遗漏。并且,最容易出现重叠或遗漏的值通常是我们定义规则的边界值。例如,在前面超市促销的例子中,以500元为边界,容易出现漏掉500元的情况,也可能出现两个规则中都包含500元的这种情况。

那么,有没有什么好的方法可以辅助我们进行边界的界定呢?

在初中数学中,我们曾学过用数轴理解不等式的解集。其实,我们通常定义的规则也是一种不等式,因此,也可考虑使用数轴来辅助确定边界。

例如,将以下规则绘制到数轴中,如图8-9所示。

图8-9

在数轴图形中,空心圆表示在规则中不包含该点的值。如图8-9所示,则表示购物金额大于0且小于500的为“不足500”,而“超过500”表示购物金额大于500。从图8-9中可直观的看到,500元这个点没有包含到任何规则中。这样,通过数轴图形就可以快速发现被遗漏的点。

而对于以下规则,可用图8-10所示的数轴来表示。

图8-10

在图8-10中,实心圆表示在规则中包含该点的数据。从图8-10中可看出,“500以下”中包含500,而“500以上”中也包含500。因此,可直观地发现500元这个点重叠了。

而以下规则可用图8-11所示的数轴图来表示。

图8-11

在图8-11中,“500以上”规则中500处是实心圆,表示在该规则中包含500这个点,而“不足500”规则中500处是空心圆,表示在该规则中不包含500这个点。即500这个点在两个规则中被(且只被)一个规则包含,没有出现遗漏或重叠,因此这两个规则是合符逻辑的。