离散数学课程设计报告.doc

“离散数学”课程设计题目： 命题公式的真值表算法 专 业 班 级 学 号 姓 名 2014.11.3目录一.实验目的2二.实验内容21. 逻辑联接词的运算22. 求任意一个命题公式的真值表3三.实验环境3四. 实验原理和实现过程（算法描述）31.实验原理32.实验过程4五.实验数据及结果分析81.题A82.B,C题10六. 源程序清单141.A题部分源代码142.B,C题部分源代码15七. 其他收获和体会23一.实验目的；本实验课程是信息专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。二.实验内容；1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。（A）2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C）详细说明：1. 逻辑联接词的运算本实验要求大家利用C/C语言，实现二元合取、析取、条件和双条件表达式的计算。充分利用联接词和逻辑运算符之间的相似性实现程序功能。2. 求任意一个命题公式的真值表本实验要求大家利用C/C语言，实现任意输入公式的真值表计算。一般我们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。命题变元可用数值变量表示，合适公式的表示及求真值表转化为逻辑运算结果；可用一维数表示合式公式中所出现的n个命题变元，同时它也是一个二进制加法器的模拟器，每当在这个模拟器中产生一个二进制数时，就相当于给各个命题变元产生了一组真值指派。算法逻辑如下：（1）将二进制加法模拟器赋初值0（2）计算模拟器中所对应的一组真值指派下合式公式的真值。（3）输出真值表中对应于模拟器所给出的一组真值指派及这组真值指派所对应的一行真值。（4）产生下一个二进制数值，若该数值等于2n-1，则结束，否则转（2）。三.实验环境；采用C语言为编程语言实现。四. 实验原理和实现过程（算法描述）；1.实验原理（1）合取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P、Q的合取, 也可读作P与Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = T时方可PQ =T, 而P、Q只要有一为F则PQ = F。这样看来，PQ可用来表示日常用语P与Q, 或P并且Q。（2）析取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P、Q的析取, 也可读作P或Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = F, Q = F时方可PQ =F, 而P、Q只要有一为T则PQ = T。这样看来，PQ可用来表示日常用语P或者Q。（3）条件：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P条件Q, 也可读作如果P，那么Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = F时方可PQ =F, 其余均为T。（4）双条件：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P双条件于Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为当两个命题变项P = T, Q =T时方可PQ =T, 其余均为F。（5）真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。 真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。（6）主范式：主析取范式：在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项。由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的。主合取范式：在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若干个不同的大项组成的合取式称为主合取范式;与A等价的主合取范式称为A的主合取范式。任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的。2.实验过程（1）A题部分，首先是对各个输入量的处理，要确定输入的为0或1，否则则为出错，接下来就是运算处理，在C语言中本身支持的有与或非这三种，可以用!,&&,|来表示，而在这个实验中，不是与或非的可以通过转化而变为与或非的形式，具体流程图如下：开始P为1或0P为1或0运算是否继续结束YYYNNN输入P值输入Q值输出结果求合取、析取、条件和双条件的真值流程图（2）B，C题部分，首先是输入一个合理的式子，然后从式子中查找出变量的个数，开辟一个二进制函数，用来生成真值表，然后用函数运算，输出结果，并根据结果归类给范式，最后输出范式。函数部分，主要是3个函数，一个为真值表递加函数，通过二进制的加法原理递进产生，一个为分级运算函数，这个函数是通过判断括号，选出最内级括号的内容执行运算函数，这样一级一级向外运算，最后得出最终结果，剩下一个为主运算函数，按照运算符号的优先级按顺序进行运算，如先将所有非运算运算完，再执行与运算。如此运算。开始输入式子计算变量个数生成真值表输出真值表变量赋值运算式子输出结果归类主范式输出主范式结束循环是否结束YN主函数开始检查括号是否是最内级括号运算内容是否是最后结果返回结果结束开始结束YYNN非运算与运算或运算蕴含运算等值运算返回结果主运算函数分级运算函数五.实验数据及结果分析；题A：进入界面正确运算结果错误控制和输入正确后退出 结果分析：这道题比较简单，主要是读取值并进行计算，同时要注意输入的值要是0或1，如果不是，则进行错误提示，并进行重新输入。B,C题：欢迎界面非运算与运算或运算蕴含运算等值运算综合运算带括号的综合运算结果分析：B,C题由于本身关系比较密切，故我直接将两个做在了一起，这个程序从功能上来说，达到了题目要求的各个功能，可以运算与，或，非，蕴含，等值条件组成的表达式，并且支持括号运算，所以，总体上来说，虽然还有一些不完善的部分，但是整体是比较可以的。六. 源程序清单；A题部分源代码：#include <stdio.h> main() int a3; int i=-1,j=-1; char s; tt:printf("*n");/标语 printf("* *n"); printf("* 欢迎进入逻辑运算软件 *n"); printf("* *n"); printf("*nn"); mm:printf("n 请输入P的值（0或1）,以回车结束:"); scanf("%d",&i);/读取P的值 if (i=0|i=1);/校验输入的P值是否在允许范围内，出错则重新输入 else printf("n P的值输入有误，请重新输入"); goto mm; nn:printf("n 请输入Q的值（0或1）,以回车结束:"); scanf("%d",&j);/读取Q的值 if (j=0|j=1);/校验输入的Q值是否在允许范围内，出错则重新输入 else printf("n q的值输入有误，请重新输入"); goto nn; a0=i&&j;/与运算 a1=i|j;/或运算 a2=(!i)|j;/蕴含运算，将其转化为与或非形式 a3=(!i)|j)&&(!j)|i);/等值运算，将其转化为与或非形式 printf("nn 合取：n P/Q=%dn",a0);/输出结果 printf(" 析取：n P/Q=%dn",a1); printf(" 条件：n P->Q=%dn",a2); printf(" 双条件：n P<->Q=%dn",a3); bb:printf("n是否继续运算？（y/n）");/询问是否继续操作 scanf("%s",&s); if (s='y'|s='n') if (s='y') system("cls"); /清屏 goto tt;/返回顶层 else printf("欢迎下次再次使用！");/退出 else printf("输入错误，请重新输入n");/错误校验 goto bb; BC题部分源代码：#include "stdio.h"#include "stdlib.h"#include "string.h"#include "conio.h"#include "math.h"#define N 50 void panduan(int bN,int f);/赋值函数int tkh (char szN, char ccuN, int icuN, int h0);/分级运算函数int fkh (char szN, char ccuN, int icuN, int h0);/主运算函数main() int i1,i2,d=1,icuN,kh=0,jg,j=0,h0;/icuN用于存放变量值,kh括号计数,jg存放结果 int bj=0,hqN,h=0,x=0,xqN;/hqN存放合取结果xqN存放析取结果 char szN,ccuN,sz0N,s;/szN存放式子,ccuN存放变量,sz0N也是用于存放式子 hq0=-1; xq0=-1; printf("*n");/标语 printf("* *n"); printf("* 欢迎进入逻辑运算软件 *n"); printf("* (可运算真值表，主范式，支持括号) *n"); printf("* *n"); printf("* 用!表示非 *n"); printf("* 用&表示与 *n"); printf("* 用|表示或 *n"); printf("* 用表示蕴含 *n"); printf("* 用表示等值 *n"); printf("* *n"); printf("*nn"); printf("请输入一个合法的命题公式:n");/输入式子 gets(sz);/读取式子 strcpy(sz0,sz);/复制式子 for(i1=0;i1<strlen(sz);i1+) if(szi1=')' | szi1='(')/存储括号数量 kh+; if(szi1>='a' && szi1<='z' | szi1>='A' && szi1<='Z') for(i2=0;i2<j;i2+) /判断并储存变量。 if(ccui2=szi1)/去除重复变量 d=0; if(d=1) ccuj=szi1; j+; d=1; printf("nd该式子中的变量个数为：%dn",j);/输出变量个数 h0=j; printf("n输出真值表如下：n n"); /输出真值表表头 for(i1=0;i1<h0;i1+) printf(" %c ",ccui1); printf(" "); puts(sz); printf("n"); for(i1=0;i1<j;i1+) /先将所有的变量赋值为零。 icui1=0; for(i2=0;i2<j;i2+)/输出真值表前项 printf(" %d ",icui2); jg=tkh(sz,ccu,icu,h0); /用函数求结果 if(jg=0)/结果为0，合取加1 hqh+=bj; else /否则，析取加1 xqx+=bj; printf(" %dn",jg);/输出运算结果 strcpy(sz,sz0); for(i1=0;i1<(int)pow(2,j)-1;i1+) +bj; panduan(icu,j-1); /赋值变量 jg=tkh(sz,ccu,icu,h0); if(jg=0)/结果为0，合取加1 hqh+=bj; else /否则，析取加1 xqx+=bj; strcpy(sz,sz0); /恢复被修改的数组。 for(i2=0;i2<j;i2+) printf(" %d ",icui2);/输出真值表前项 printf(" %dn",jg);/输出运算结果 if(hq0=-1)/不存在合取范式时 printf("n该命题公式不存在主合取范式。n"); else printf("n该命题公式的主合取范式：nt"); for(i1=0;i1<h;i1+) if (i1>0)/判断并添加符号 printf("/"); printf("M(%d)",hqi1); /输出主合取范式 if(xq0=-1)/不存在析取范式时 printf("n该命题公式不存在主析取范式。n"); else printf("nn该命题公式的主析取范式：nt"); for(i1=0;i1<x;i1+) if (i1>0)/判断并添加符号 printf("/"); printf("m(%d)",xqi1);/输出主析取范式 printf("n"); printf("n欢迎下次再次使用！n ");/结束 getch();void panduan(int bN,int f) / 二进制赋值。 int i; i=f; if(bf=0)/加1 bf=1; else/进位 bf=0; panduan(b,-i); int tkh (char szN,char ccuN,int icuN,int h0)/分级运算函数 int i,j,h,s,kh=0,wzN,a; char xs1N,ckhN; /xs1用来保存括号内的字符 ckh用来保存括号。 s=strlen(sz); for(i=0;i<s;i+) if(szi='(' | szi=')')/判断括号 wzkh=i;/存储括号位置 ckhkh=szi;/存储括号类型 kh+; if(kh=0) return fkh(sz,ccu,icu,h0);/如果无括号，直接运行 else for(i=0;i<kh;i+) if(ckhi=')')/找到第一个） break; for(j=wzi-1+1,h=0;j<wzi;j+,h+) /存储最内级括号中的内容 xs1h=szj; xs1h='0' a=fkh(xs1,ccu,icu,h0);/运行最内级括号的式子，得到结果 if(a=1)/判断并存储结果 szwzi-1=1; else szwzi-1=-2; for(j=wzi-1+1;j<s+wzi-1-wzi;j+)/将括号后内容前移 szj=szj+wzi-wzi-1; szj='0' return tkh(sz,ccu,icu,h0);/循环执行 int fkh(char szN,char ccuN,int icuN,int h0)/主运算函数 int i,h=0,j=0,j1=0,j2=0,j3=0,j4=0,j5=0,i1,i2,p1=-1,p2=-1,s; char dtN; s=strlen(sz); if(s=1) if(sz0=-2)/判断是否是最后一项 return 0; else return 1; /1 就是sz0的值、 else for(i=0;i<s-j;i+) /先处理非 if(szi='!') for(i1=0;i1<h0;i1+) if(szi+1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(p1=-1)/如果是数字，直接给P1 p1=szi+1; dtj+2=!p1;/非运算 szi=j+2; j+; p1=0; for(i1=i+1;i1<s-j;i1+) szi1=szi1+1;/将后续式子前移一项 p1=-1; j1=j; for(i=0;i<s-j1-2*j2;i+) / 处理与 if(szi='&') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1) /如果是数字，直接给P1 p1=(int)(szi-1); if(p2=-1)/如果是数字，直接给P2 p2=(int)(szi+1); dtj+2=p1 && p2;/与运算 szi-1=j+2; j+; j2+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2;i1+)/将后续式子前移两项 szi1=szi1+2; i=i-1; for(i=0;i<s-j1-2*j2-2*j3;i+) / 处理或。 if(szi='|') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2)/如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1)/如果是数字，直接给P1 p1=szi-1; if(p2=-1)/如果是数字，直接给P2 p2=szi+1; dtj+2=p1 | p2;/或运算 szi-1=j+2; j+; j3+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3;i1+)/将后续式子前移两项 szi1=szi1+2; i-; for(i=0;i<s-j1-2*j2-2*j3-2*j4;i+) / 处理蕴含。 if(szi='') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2;if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0;if(p1=-1)/如果是数字，直接给P1 p1=szi-1;if(p2=-1)/如果是数字，直接给P2 p2=szi+1;dtj+2=!p1 | p2;/蕴含运算szi-1=j+2;j+;j4+;p1=-1;p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3-2*j4;i1+)/将后续式子前移两项 szi1=szi1+2;i-; for(i=0;i<s-j1-2*j2-2*j3-2*j4-2*j5;i+) / 处理等值。 if(szi='') for(i1=0;i1<h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2<j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1)/如果是数字，直接给P1 p1=szi-1; if(p2=-1)/如果是数字，直接给P2 p2=szi+1; dtj+2=(!p1 | p2)&&(!p2 | p1);/等值运算 szi-1=j+2; j+; j5+; p1=-1; p2=-1; for(i1=i;i1<s-j1-2*j2-2*j3-2*j4-2*j5;i1+)/将后续式子前移两项 szi1=szi1+2; i-; return dtj+1;/返回结果 七. 其他收获和体会。这个实验分3个题，A类题其实是很简单的，而C类题如果是在B类题的基础上构建，相对来说也是一个不困难的题，所以主要在B类题上花费了大量时间，一开始想用中序表达式转变为逆波兰式的方法来解决，但是总有一些零零散散的问题困扰，况且对于栈和二叉树之类的东西在学习C语言时接触很少，所以困难更大，经过多次失败后，还是最后用最简单同时也是最麻烦的方法来解决这个问题。利用函数一步步来解决，所以在个别功能上来说有一些不完美，比如纠错，因为时间有限，有个别地方没有设置出错提示。也许是很久没看C语言了，导致很多基本的语句都已经并不熟练了，通过这次实验，让我从一定程度上找回了一点以前做课程设计时的感觉。在编程过程中，最重要的其实是对细节方面的把握。A类题的逻辑抽象和编程语言的表达都非常基础，所以能不能把程序的细节考虑完善是非常重要的，有没有输入提示，错误提示等等，这些东西是考验一个人考虑问题的全面性的一个方式，我们应该从现在就养成这样良好的习惯。B类题，在设计上主要有以下几个问题：1.优先级的问题，要如何解决优先级的问题，最后我直接用先后执行来解决。2.括号问题，对于运算来说，解决括号问题很重要，而我是从最内级括号向外层层运算，最后得出结果。3.真值表问题，真值表利用二进制的原理，递加得到。4.赋值问题，一开始这个问题困扰了我很久，后来发现直接用一个赋值函数，每次运行都直接运行一次就可以很好的解决了。这些是在做B类题时主要遇到的问题。C类题，其实这个题在B类题得出结果之后可以比较简单的解决，因为已经有真值表，只要将最后结果分类，并将其分类列出就可以了。总的来说，本次实验总体上是比较成功的，也让我学到了很多东西。