真值表的C算法实现

1、08 届课程（设计）论文题题 目目命命题题公公式式的的真真值值表表算算 法法专专业业班班级级信信息息与与计计算算科科学学 (1)班班学学 号号0809030116学学生生姓姓名名上上官官业业云云指指导导教教师师李李圆圆媛媛指指导导教教师师职职称称讲讲师师学学院院名名称称理理学学院院完完成成日日期期： 2010 年年 09 月月 27 日日目目 录录目 录 .I摘 要 .III前 言 .IV第 1 章 课题背景 .111 背景 .112 性质 .113 意义 .114 实验数据与结果 .115 文献综述 .2第 2 章 问题的分析与算法的实现.321 问题的分析 .322 算法的实现 .3第 3

2、 章 总 结 .13致 谢 .14参考文献 .15附 录 .16摘摘 要要 为了解决命题公式的真值表算法问题， 本文采用 面向对象编程，输入命题变元，并以字符串形式读入命题公式，应用运算符重载来进行相关运算，并在C+（使用的编译工具为 VS2010）下，给出了问题的具体解决方案 。关键词关键词：命题公式；真值表；类；运算符重载；递归；字符串前前 言言本文解决了计算任意含个命题变元的命题公式的真值表的C+算)(Nnn法。全文共 3 章。第 1 章介绍了 问题背景、问题以及性质问题的意义。在本章中，还给出了具体的实验数据和我们查阅并借用的一些参考文献的主要内容。第 2 章主要介绍了在对问题的分析

3、后设计的算法 ，并编写程序，求出其具体调度方案。第 3 章是本次课程设计的总结。全文的最后是致谢、参考文献和程序的源代码。上官业云 武汉工程大学理学院第第 1 1 章章 课课题题背背景景1 11 1 背景背景 设为含有命题变元的命题公式，给一组确定的取值，FnPPP,21 nPPP,21 称为公式关于的一组真值指派。含有个命题变元的公式有组FnPPP,21 nn2不同的真值指派，对于每一组真值指派，公式都有一个确定的真值（一般用“0”表示假， “1”表示真）。公式与其命题变元之间的真值关系可以用真值表的方法方便的表示出来。1 12 2 性质性质 含有个命题变元的公式有组不同的真值指派，对于每一

4、组真值指派，nn2公式都有一个确定的真值（一般用 “0”表示假， “1”表示真）。1 13 3 意义意义使用计算机来完成各种复杂的真值表计算，尤其是当命题变元增多时，对应的取值成指数增长，计算量也指数增长，紧靠人很难完成。应用计算机强大的计算能力，可以又好又快的完成任意命题公式的真值表的计算。 1 14 4 实验数据实验数据与结果与结果实验时，本文主要是用编写的程序计算参考资料1上的相关命题公式来验证相关算法的正确性，稳定性。由程序计算得出的命题公式的真值表：)()(2SQQPF1上 236 页给出的答案： PQSQP QSQ )()(SQQP0001100001111101000100110

5、0101000100101011011010111111011二者除命题变元取值顺序不一样外，最后的真值结果完全吻合，表明算法的正确性、稳定性。1 15 5 文献综述文献综述文献 0 介绍了命题变元与命题公式真值表的相关知识 。文献 Error! Reference source not found.介绍了 C+程序设计基础知识 。文献 Error! Reference source not found.提供了 C+面向对象的 程序设计相关知识 。第第 2 2 章章 问问题题的的分分析析与与算算法法的的实实现现2 21 1 问题的分析问题的分析 对于含有个命题变元的公式有组不同的真值指派，对于

6、每一组真值指nn2派，公式都有一个确定的真值（这里 “0”表示假， “1”表示真）。为了枚举出所有的情形，须用重 for 循环，为了使程序具有通用性，的取值是不确nn定的。这时，使用递归的算法就较方便。 给命题变元赋值的问题解决后，还得解决计算问题，在这里，本文采用面向对象的方法，通过运算符的重 载来完成相关计算。定义了类Proposition，它包括两个变量 命题变元名和命题变元的真值，和相关成员函数、需重载的运算符。 再设计计算真值的函数，考虑到命题公式中可能会出现括号，改变了运算的优先级， 本文同样采用递归的算法，当遇到括号时，把括号里面的部分作为一个命题公式来计算，再把结果作为一个命题

7、变元放到整个命题公式进行计算，而当遇到相关的运算符时，重载运算符进行计算。最后返回真值。 最后，主函数只需完成输入并存储命题变元与命题公式，调用赋值函数就行了。 由以上方法可以进行真值的运算，但程序冗余太长，再对其进行优化处理，用另一函数来代替大量重复的代码，使程序更简洁。2 22 2 算算法法的的实实现现定义命题变元类 Proposition：class Propositionint data;char data1; /data:命题的真值（ 0/1） data1：命题名public:Proposition()data=2;data1=A;friend Proposition operato

8、r !(Proposition &q); /定义否定运算符 !friend Proposition operator &(Proposition &p,Proposition &q);/定义合取运算符 &friend Proposition operator |(Proposition &p,Proposition &q);/定义析取运算符 |friend Proposition operator (Proposition &p,Proposition &q);/定义蕴含运算符 friend Proposition ope

9、rator (Proposition &p,Proposition &q);/定义等值运算符 0) p.input1(1);else p.input1(0);return p;Proposition operator (Proposition &p,Proposition &q)if(p.get()=1&q.get()=0)p.input1(0);else p.input1(1);return p;Proposition operator (Proposition &p,Proposition &q)if(p.get()=q.get()

10、p.input1(1);else p.input1(0);return p;其中函数 void input1(int x)用于输入命题变元的真值，函数void input2(char x)用于输入命题名， int get()与 int get1()分别用于获取命题真值和命题名，运算符重载部分由 1中的知识得出 。给命题变元赋值（ void fuzhi(string A,int N,int M,Proposition a)）：for(int j=0;j1)fuzhi(A,N-1,M,&a0);elsefor(int i=0;iM;i+)coutai.get() ;coutbds(A,M,

11、&a0),;int L;int i=0;L=strlen(&A0); /计算表达式长度while(iL)if(Ai=() /括号的处理int k=1;for(int j=i+2;jL;j+)if(k!=0)if(Aj=()k+;if(Aj=)k-;if(k=0)int l=j-i-1;char *p=new charl+1;string B;for(int m=0;ml;m+)pm=Ai+1+m;pl=0;B=p;delete p;Temp.input1(bds(B,N,&a0);if(i=0)ANS.input1(Temp.get();i=j+1;break;else

12、if(Ai=!) /否定的计算Temp.input1(jisuan(A,i,L,N,&a0);ANS=!Temp;i+;continue;else if(Ai=|)Temp.input1(jisuan(A,i,L,N,&a0);ANS=ANS|Temp;i+;continue;else if(Ai=&)Temp.input1(jisuan(A,i,L,N,&a0);ANS=ANS&Temp;i+;continue;else if(Ai=)Temp.input1(jisuan(A,i,L,N,&a0);ANS=ANS)Temp.input1(jis

13、uan(A,i,L,N,&a0);ANS=ANSTemp;i+;continue;elsefor(int j=0;j,存储的是 5 个重载的运算符名，用于识别运算符。 jisuan(A,i,L,N,&a0)是为了减少程序的冗余而设计的，具体内容如下：Proposition Temp;if(Ai+1=()int k=1;for(int j=i+2;jL;j+)if(k!=0)if(Aj=()k+;if(Aj=)k-;if(k=0)int l=j-i-1;char *p=new charl+1;string B;for(int m=0;ml-1;m+)pm=Ai+2+m;pl-1=

14、0;B=p;delete p;Temp.input1(bds(B,N,&a0);i=i+j;break;elseint j=0;while(jL)if(Ai+1=char(aj.get1()i+;Temp=aj;break;j+;return Temp.get(); 为了使主函数看起来更简洁，把以上内容都放入头文件zzb.h 中，主函数部分同时还完成命题变元及命题公式的输入与储存，最后调用函数void fuzhi(string A,int N,int M,Proposition a)完成全部计算，其内容如下：Proposition a30;char x=1;int i=0,N;cout

15、请输入涉及的命题变元 (输入0按回车结束 )x; if(i19)cout命题变元个数超过 30，无法处理 endl;break;if(x!=0)ai.input2(x);i+;N=i;int M;M=N;string A;cout，等值： )A;coutA的真值表为： endl;for(int j=0;jM;j+)coutchar(aj.get1() ;cout真值endl;fuzhi(A,N,M,&a0);system(pause);return 0;从实验结果还可以看出，本程序的通用性强，能够识别全部五种运算及括号，这样在理论上是可以计算任意复杂的命题公式的真值表。当然，由于计算机

16、硬件及 C+的递归深度的限制，命题公式的复杂度超过一定限制也会无法计算，对于一般性的复杂命题公式的真值计算，本程序完全可以胜任。 完整的源代码在附录中。第第 3 3 章章 总总 结结在大学过去的两年里，我学习了 C+程序设计基础 ，C+面向对象程序设计 和算法与数据结构 。老实说，对这些课学的有些吃力，因为自己动手时总是困难重重 ，很多时候是处于理论的学习而没有上机的实践操作，在有限的上机操作时，经常是看懂老师提供的代码就算了。平时遇到问题，总是到网上找代码，几乎没有自己原创的程序，也没认真下功夫去写过代码。但是，这次课程设计从选题开始，就给自己定了一个较高的要求。选的题是自己觉得可供选择的题

17、中最难得一个，同时也力求100%独立自主完成 。在做这次课程设计的过程中，有遇到问题而一时又无法解决时的无奈，也有写代码调程序到深夜的艰辛，更有解决某个问题和最后成功的喜悦。一般来讲， 构想一个算法并不困难，难的是把设计的算法变成有效的代码。在代码的调试中，经常出现编译通过了，但运行时报错，而这类问题又很难查到，这就需要花时间和精力，没有足够的耐心是不行的。当遇到这类问题时，我常常不知所措。每每想要放弃时，都会想到我的程序员梦想，想到数模竞赛时的那股干劲和精神，这样又有了动力，重新开始调试。虽然有时一连几个小时都毫无进展，但我坚持下来了。最后写的程序基本上达到了预定目标，功能上完全达到了，只是

18、没有容错能力，稳定性还不够强。同时，经过这次的课程时机，我有了许多收获，意志得到了锻炼，获得了很多编程的经验。每每调试错误，我都会有新的发现，新的收获。能更好的利用现有的资源为我服务，如现在我能更好的利用MSDN2010 的资源，当遇到错误时，通过它，往往能够找到我想要的。无所谓会做或不会做，编程非登天般难，唯有做与不做。致致 谢谢不应该放弃 直到失去的那一刻我们见过多少 无私提供帮助甚至放弃休息来服务学生的老师默默奉献一生的父母还有热情鼓励和给予帮助的同学能忘记他们的期盼和自己的梦想吗不能为了不辜负他们的希望更为了自己的明天生活我坚持下来了因为我有这样的义务 使命哪怕时间紧 基础薄但是谁说我

19、不能独立完成程序创作不是吗经过半个月的奋斗达到预期没标不管最终评分的高低在做课程设计的半个月里我又一次刻画了人生的烙印仅以此篇课程设计感谢提供过帮助的老师 同学养育我二十年的父母参参考考文文献献1洪帆.离散数学 .第 3 版.武汉：华中科技大学出版社 .2008.2吴文虎.程序设计基础 (第 2 版)M .北京：清华大学出版社 .2004.3谭浩强.C+面向对象程序设计 M.北京：清华大学出版社 .2008.附附 录录命题公式的真值表算 法完整源代码（ VS2010 调试通过 ）：*真值表.CPP*/ 真值表.cpp : 定义控制台应用程序的入口点。#include stdafx.h#incl

20、udezzb.hint main()Proposition a30;char x=1;int i=0,N;cout请输入涉及的命题变元 (输入0按回车结束 )x; if(i19)cout命题变元个数超过 30，无法处理 endl;break;if(x!=0)ai.input2(x);i+;N=i;int M;M=N;string A;cout，等值： )A;coutA的真值表为： endl;for(int j=0;jM;j+)coutchar(aj.get1() ;cout真值endl;fuzhi(A,N,M,&a0);system(pause);return 0;*zzb.h*#if

21、ndef ZZB_H#define ZZB_H#include#include#includeusing namespace std;class Propositionint data;char data1; /data:命题的真值（ 0/1） data1：命题名public:Proposition()data=2;data1=A;friend Proposition operator !(Proposition &q); /定义否定运算符 !friend Proposition operator &(Proposition &p,Proposition &q)

22、;/定义合取运算符 &friend Proposition operator |(Proposition &p,Proposition &q);/定义析取运算符 |friend Proposition operator (Proposition &p,Proposition &q);/定义蕴含运算符 friend Proposition operator (Proposition &p,Proposition &q);/定义等值运算符 0) p.input1(1);else p.input1(0);return p;Proposition

23、 operator (Proposition &p,Proposition &q)if(p.get()=1&q.get()=0)p.input1(0);else p.input1(1);return p;Proposition operator (Proposition &p,Proposition &q)if(p.get()=q.get() p.input1(1);else p.input1(0);return p;void fuzhi(string A,int N,int M,Proposition a);int bds(string A,int N

24、,Proposition a);int jisuan(string A,int &i,int L,int N,Proposition a);void fuzhi(string A,int N,int M,Proposition a)/命题赋值并计算真值for(int j=0;j1)fuzhi(A,N-1,M,&a0);elsefor(int i=0;iM;i+)coutai.get() ;coutbds(A,M,&a0),;int L;int i=0;L=strlen(&A0); /计算表达式长度while(iL)if(Ai=() /括号的处理int k=1;for(int j=i+2;jL;j+)if(k!=0)if(Aj=()k+;if(Aj=)k-;if(k=0)int l=j-i-1;char *p=new charl+1;string B;for(int m=0;ml;m+)pm=Ai+1+m;pl=0;B=p;delete p;Temp.input1(bds(B,N,&a0);if(i=0)ANS.input1(Temp.get();i=j+1;break;elseif(Ai=!