离散数学及其应用实验报告

PAGEPAGE2浙江万里学院实验报告成绩成绩：教师：肖启莉课程名称：离散数学实验名称：数理逻辑实验实验目的①进一步理解有关数理逻辑的基本概念；②掌握真值表的求解方法；③能够利用真值表解决命题逻辑中的相关问题。实验内容①分别编写函数，实现┓、∧、∨、→以及«运算。要求在主函数输入命题变元P、Q的真值，并输出命题公式┓P、P∧Q、P∨Q、P→Q以及P«Q的真值。②编写程序，构造命题公式P∧Q∨R的真值表。③利用真值表，求命题公式P∧Q∨R的主范式。④利用真值表证明P→Q，┓(Q∨R)┣┓P。⑤*编写程序，构造任意一个命题公式的真值表。⑥*编写程序，利用真值表求任意一个命题公式的主范式。（其中2、3与5、6可以写成同一个程序）实验过程算法思想：要求输入P、Q实现┓、∧、∨、→以及«运算；可以用switch语句对其进行判断也可以用if-else语句。因为这一题与最后一题中的功能函数Opereat(a,op,b)类似。所以这里直接打印了他们的结果。实验代码：专业班级：计算机111姓名：李俊学号：2011014620实验日期：2012.10#include<stdio.h>voidmain()调试报告：{调试报告： intP,Q; printf("请输入布尔型变量P的值(0或1),P="); scanf("%d",&P); printf("\n请输入布尔型变量Q的值(0或1),Q="); scanf("%d",&Q); printf("\n┓P=%d",(!P)); printf("\nP∧Q=%d",(P&Q)); printf("\nP∨Q=%d",(P||Q)); printf("\nP→Q=%d",((!P)||Q)); printf("\nP←→Q=%d\n",((!P)&&(!Q))||((P)&&(Q)));}算法思想：编写P∧Q∨R的真值表。需要构建一个结构体存放这个真值表对其赋值再将其打印就可以得到真值表。structList{intP,Q,R;intanswer;}a[8]而主范式则是要对结构体遍历当a[i].answer为真时输出下标index就可以得到主范式最后用格式控制符’\b’取消掉最后一个析取符号。实验代码：专业班级：姓名：学号：实验日期：voidmain(){ intp,q,r,i=0; for(p=0;p<2;p++)//利用for循环为结构数组赋值 for(q=0;q<2;q++) for(r=0;r<2;r++) { a[i].P=p; a[i].Q=q; a[i].R=r; a[i].answer=(a[i].P&&a[i].Q||a[i].R); i++; } printf("P\tQ\tR\tP∧Q∨R\n"); for(i=0;i<8;i++)//利用循环将结果打印 { printf("%d\t%d\t%d\t%d\n",a[i].P,a[i].Q,a[i].R,(a[i].P&&a[i].Q||a[i].R)); }调试报告： print(a);调试报告：}voidprint(structLista[]){ inti; printf("P∧Q∨R的主范式是:");专业班级：姓名：学号：实验日期： for(i=0;i<8;i++) { if(a[i].answer==1) { printf("m%d∨",i); } } printf("\b");}（4）算法思想：证明P→Q，┓(Q∨R)┣┓P。只需构建结构数组存放这个真值表。structList{ intP,Q,R; intanswer1,answer2,answer3;}a[8];分别存放P→Q，┓(Q∨R)，┓P的真值当answer1和answer2都为真时若answer3也为真则返回ture若假则返回false实验代码：voidiniList(structLista[]);//初始化这个结构数组voidprint(structLista[]);//打印这个主范式voidmain()//主函数只需要调用这个功能（API）{ iniList(a); print(a);}

调试报告：voidiniList(structLista[]){调试报告：voidiniList(structLista[]){ intp,q,r,i=0; for(p=0;p<2;p++)//利用for循环为结构数组赋值 for(q=0;q<2;q++) for(r=0;r<2;r++) { a[i].P=p; a[i].Q=q; a[i].R=r; a[i].answer1=(!a[i].P||a[i].Q); a[i].answer2=!(a[i].Q||a[i].R); a[i].answer3=!a[i].P; i++; }}voidprint(structLista[]){ inti; printf("推理P→Q，┓(Q∨R)┣┓P的值为:"); for(i=0;i<8;i++) { if(a[i].answer1&&a[i].answer2&&(a[i].answer3==0))//当前两个表达式为真而结果为假时条件不成立输出false并推出函数 { printf("false\n"); exit(0); } } printf("true\n");}

（5、6）算法思想：（5、6）算法思想：这个算法有两处难点需要思考。第一：如何利用程序实现真值表的计算;这里可以用类似求任意表达式的值的算法来求;即算符优先算法。创建一个算符优先的dictionary。这个字典要是9*9的。字典的定义如下图所示。这样只需按列按行查找相应的算符保存i,j就可以得到表达式是什么值了tab[9][9]={ "0=-|&!()@", "=><<<<<>>", "->><<<<>>", "|>>><<<>>", "&>>>><<>>", "!>>>>><>>", "(<<<<<<=E", ")>>>>>E>>", "@<<<<<<E=", }第二：怎样实现命题变元的赋值。这里有以下几点。我们可以看到P、Q、R这三个命题变元的真值表赋值应该是P Q R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 可以看到P、Q、R中0与1替换的频率是不同的那么这样我们就可以创建出一个数组A[1024][10]来存放这一种赋值。然后每次计算的时候我们只需要取其中某一行的赋值调用写好的函数就可以了。因为我们用了Divi函数将表达式去掉运算符按其出现的先后顺序将其存在了myopnd[10]这个数组中这样当我们要取某个变元的值的时候只要知道这个变元在myopnd数组中的下标(index);取到得A[i][index]就是这时候变元的赋值;最后我们就可以按照计算表达式的值的常规思路对栈进行存储获取这时候的值。[注]：参考《计算机工程与科学》2008年第30卷第一期《命题公式真值表的生成算法》作者：徐凤生；李天志。#include<stdio.h>#include<string.h>#include<stdio.h>#include<string.h>#include<math.h>#defineMAX_SIZE20/*函数声明*/intcountPQ(char*exp);voidevalu(char*exp);charPrecede(charop1,charop2);intOperate(intx,charop,inty);voidDivi(charexp[],charmyopnd[]);intLocate(char*myopnd,charc);intCalExpression(char*exp,int*p);/*操作运算符栈OPTR*/typedefstruct{ chardata[MAX_SIZE]; inttop;}OptrStack;OptrStackOPTR;voidIniOPTR(OptrStack*S){ S->top=0;}voidPushOPTR(OptrStack*S,charelem){ S->data[S->top]=elem; S->top++;}charPopOPTR(OptrStack*S){ S->top--; returnS->data[S->top];}charGetTopOPTR(OptrStack*S){ returnS->data[S->top-1];}/*操作数据栈OPND*/typedefstruct/*操作数据栈OPND*/typedefstruct{ intdata[MAX_SIZE]; inttop;}OpndStack;OpndStackOPND;voidIniOPND(OpndStack*S){ S->top=0;}voidPushOPND(OpndStack*S,intelem){ S->data[S->top]=elem; S->top++;}intPopOPND(OpndStack*S){ S->top--; returnS->data[S->top];}intGetTopOPND(OpndStack*S){ returnS->data[S->top-1];}/*主函数*/voidmain(){ charexp[30]; printf("请输入你要生成的真值表的命题公式\n(=,-,|,&,!,分别表示双条件、单条件、析取、合取,取反):"); gets(exp); evalu(exp);}/**/intcountPQ(char*exp)//计算表达式中命题变元的个数{ inti,count=0; for(i=0;exp[i]!='@';i++) if(exp[i]>='A'&&exp[i]<='Z') count++; returncount;}voidevalu(char*exp)//主要功能函数{voidevalu(char*exp)//主要功能函数{ charmyopnd[10]; intA[1024][10],M[1024];//最多多可以生成10命题变元的真值表 intflag,m,n,i,j,k,length; length=strlen(exp); exp[length]='@';//在表达式末尾插入@ exp[length+1]='\0'; n=countPQ(exp);//生成具体的行列数 m=(int)pow(2,n);//计算每列有多少个元素 for(j=0;j<n;j++) { flag=1; k=(int)pow(2,n-j-1);//计算该列中应该算多少个0后换1;例如三个变元时第一列是00001111;而第二列是00110011;依次类推; for(i=0;i<m;i++) { if(i%k==0)flag=!flag; A[i][j]=flag; } } Divi(exp,myopnd); printf("真值表\n"); for(i=0;myopnd[i]!='\0';i++)printf("%4c",myopnd[i]); exp[length]='\0'; printf("%s\n",exp); exp[length]='@'; for(i=0;i<m;i++) { for(j=0;j<n;j++)printf("%4d",A[i][j]);//按行输出真值表的赋值 M[i]=CalExpression(exp,A[i]); printf("%6d",M[i]);//输出改行运算结果 printf("\n"); } printf("\n"); printf("主范式\n"); for(i=0;i<m;i++) { if(M[i])printf("m%d∨",i); } printf("\b");}charPrecede(charop1,charop2)//按字典索引两个算符的优先级{charPrecede(charop1,charop2)//按字典索引两个算符的优先级{ inti,j; chartab[9][9]={ "0=-|&!()@", "=><<<<<>>", "->><<<<>>", "|>>><<<>>", "&>>>><<>>", "!>>>>><>>", "(<<<<<<=E", ")>>>>>E>>", "@<<<<<<E=", }; for(i=1;i<9;i++) if(tab[i][0]==op1) for(j=1;j<9;j++) if(tab[0][j]==op2) returntab[i][j];}intOperate(intx,charop,inty)//返回双条件运算符的结果{ switch(op) { case'=':return(((!x)||y)&&(x||(!y)));break; case'-':return((!y)||x);break; //一定要!y||x要不然数据会出错 case'|':returnx||y;break; case'&':returnx&&y;break; }}voidDivi(charexp[],charmyopnd[])//得到命题公式包涵的命题变元序列myopnd(按命题变元出现的先后顺序排序){ inti,j=0; for(i=0;exp[i]!='@';i++) { if(exp[i]>='A'&&exp[i]<='Z') { myopnd[j]=exp[i]; j++; } } myopnd[j]='\0';}intCalExpression(char*exp,int*p)//exp为表达式，p为这个时候表达式的赋值；返回该表达式在p赋值时的真值{ charmyopnd[10];charc,op;intk=0,d,a,b;intCalExpression(char*exp,int*p)//exp为表达式，p为这个时候表达式的赋值；返回该表达式在p赋值时的真值{ charmyopnd[10];charc,op;intk=0,d,a,b; IniOPTR(&OPTR);PushOPTR(&OPTR,'@'); IniOPND(&OPND); Divi(exp,myopnd);//将exp中的命题变元按出现的先后顺序存入myopnd;例如exp为"P|Q&R";myopnd为"PQR"; c=exp[k++];//取出表达式第一个元素 while(c!='@'||GetTopOPTR(&OPTR)!='@')//循环的条件是表达式中取出的元素不为@或者算符操作栈OPTR的栈顶元素不为@ { if(c>='A'&&c<='Z') { d=p[Locate(myopnd,c)];//取出命题变元c对应的赋值;Locate返回了c在myopnd的数组下标 PushOPND(&OPND,d); c=exp[k++]; } else { switch(Precede(GetTopOPTR(&OPTR),c)) { case'<':{PushOPTR(&OPTR,c);c=exp[k++];break;}//操作符栈;栈顶的优先级低,将c压栈,读取下一个字符 case'=':{PopOPTR(&OPTR);c=exp[k++];break;}//脱去括号 case'>'://运算符