首页 附中概况 附中党建 名师风采 人才培养 成就展示 对外交流 招生信息 专题子站 办公系统 English 联系我们
首页>>研究性学习展示平台>>在pascal环境下的数学命题推理
在pascal环境下的数学命题推理
发布时间: 2012-03-19 14:07:16 点击次数: 0 字号:

  研究背景:

  在这个学习,我们同学们开始进入数学选修2-1的学习,在这本书中,除了高考的重点圆锥曲线外,另一个重点便是逻辑推理。逻辑推理在高考和平时的大考小考中无处不在,而在逻辑推理的过程中,在手工计算中最令人头疼的、用时最多的单纯的命题逻辑推理问题便是已知几个命题的关系,判断一个命题与另一个命题的关系,即一个命题是另一个命题的充分必要条件、充分不必要条件、必要不充分条件和不充分不必要条件。当命题有4个时,告诉相关的条件,来推理的时间便需要至少三分钟,并且错误率极高。如果给出十个、二十个甚至五十个一百个命题,那又如何能推理出命题之间的关系呢。

  探究原理:

  在我做有关命题推理的题目时,总会画一个图,如在题目中A是B的充分不必要条件,B是C的充分不必要条件,那么我们可以将它们之间的关系画成这样一个图。

\

  我们把每一个点当作一个命题,那么我们便可以这样解释这个图,即a能推出b,b能推出c。我们可以将它转化成一个图论的问题,即a与b之间有一条有向边,方向为a指向b;同理,b与c之间有一条有向边,那么我们很容易看出,a与b是连通的,b与c是连通的,很明显,a与c便是连通的。所有的命题之间的关系的推断都可以是通过这样一种方法来传递起来。在读入数据的过程中我们做以下处理。

  1.将每一个点与其他点的初始距离设为无穷大,由于我们设计的命题的个数不超过500个即点的个数不超过500个,因此两点之间的距离最多不会超过500,因此我们可以把无穷大设为501,为保险起见,我们将最大值设为二的十六次方。

  2.每读入一组数据,都将两点之间连一条长度为一的边。

  3. 通过最短路径的算法来计算出两点之间的距离

  4. 通过两点之间的最短距离来判断两点之间的联通性,如果两点之间的距离是预设的二的十六次方,那么说明两点之间不连通,因为两点之间的距离没有比无限大更加短的距离。

  5.通过两点之间的联通性,我们可以知道一个命题是否能推出另一个命题,反过来将前面的一到四步执行一遍,可以知道另一个命题是否能推出一个命题,最后可以通过这两个命题之间的互推关系来得出这两个命题中一个是另一个的命题的类型(充分必要,充分不必要,必要不充分,不充分不必要。)。

  研究过程

  在第一次活动中,我们发现,由于这个问题的核心便是在一个有向图和无向图的混杂图中出现的最短路问题,因此我们首先想到的是最为简单的弗洛伊德(floyed)算法,它以代码长度短而著称。但它的缺点也是很明显的,它的时间复杂度是n的三次方,复杂度相当高,在n取到100的时候,它可以在一秒钟完成计算,但当n的大小到500时,就会有很明显的延迟。并且我们只是为了求得两点之间的最短路径,并且是固定的两点,弗洛伊德算法可以将整个图中点的最小距离全部求出,很明显会带来很多不必要的运算。因此我们可以将他改进。

  在第二次活动中,我们致力于优化该算法,由于是求单元最短路问题,即一个点为起始的最短路问题(所求的点也包括在其中),我们选择了时间复杂度为n(命题个数)*m(关系个数)的由中国西南交通大学的段凡丁老师与1994年发明的spfa算法来解决,由于剪掉了很多不必要的计算,因此这个算法的时间复杂度远优于前面运用弗洛伊德算法的时间复杂度。但由于我们需要进行两次这样的计算(首先求出a到b的距离,再求出b到a的距离),因此,代码量会非常的长。在这个过程中,我们想到了通过将这个程序分为两个计算两点之间距离的程序和一个判断两命题之间关系的程序,成功减少了写程序的难度,最后得以成功的将程序写出。

  在第三次活动中,我们讨论发现我们并不用求出这两个点之间的最短距离,因为如果a和b是连通的,即使一遍遍更新,也无法改变这两个点之间的连通性,因此不必要求出两点之间的最短路的长度。那么前面做的一遍遍更新都是没有用处的,我们从此想到一种遍历的方法,即将整个图走一遍。因此我们从我们指定的第一个点开始,枚举每一条边,并且用两个数组记录每一个点,每一条边是否走过从而减少程序的时间复杂度(每一条边走过后,连接它的两个点都已经能遍历到)。便可以得到我们指定的命题a是否能推出命题b。从b开始遍历,便可以知道命题b是否能推出命题a。这样我们便可以用最小的时间复杂度即o(n+m)来得出a是b的什么命题了。

  结论

  可以将命题推理问题来转化成计算机图论问题来解决,在解决的过程中,同学们一次次的优化自己前一步所设计的程序,增强了创新精神,充实了假期生活,收获了快乐。

  参考文献

  百度百科。

  Malash链式前向星

  算法导论

在pascal环境下的命题逻辑推理-朱鹤鸣-赵宗昌.rar

 
     
 
 
Copyright Fuzhong All Rights Reserved
版权所有:山东师范大学附属中学  鲁ICP备06004854号  
      山东师大附中本校区地址:济南市历下区山师北街3号      邮编:250014  电话:(86)0531-86187151  校长信箱
      山东师大附中幸福柳校区地址:历城区王舍人街道幸福柳路10号  邮编:250100  电话:(86)0531-81921555