離散數(shù)學(xué)及其應(yīng)用實(shí)驗(yàn)報(bào)告

PAGEPAGE2浙江萬(wàn)里學(xué)院實(shí)驗(yàn)報(bào)告成績(jī)成績(jī)：教師：肖啟莉課程名稱(chēng)：離散數(shù)學(xué)實(shí)驗(yàn)名稱(chēng)：數(shù)理邏輯實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康蘑龠M(jìn)一步理解有關(guān)數(shù)理邏輯的基本概念；②掌握真值表的求解方法；③能夠利用真值表解決命題邏輯中的相關(guān)問(wèn)題。實(shí)驗(yàn)內(nèi)容①分別編寫(xiě)函數(shù)，實(shí)現(xiàn)┓、∧、∨、→以及?運(yùn)算。要求在主函數(shù)輸入命題變?cè)狿、Q的真值，并輸出命題公式┓P、P∧Q、P∨Q、P→Q以及P?Q的真值。②編寫(xiě)程序，構(gòu)造命題公式P∧Q∨R的真值表。③利用真值表，求命題公式P∧Q∨R的主范式。④利用真值表證明P→Q，┓(Q∨R)┣┓P。⑤*編寫(xiě)程序，構(gòu)造任意一個(gè)命題公式的真值表。⑥*編寫(xiě)程序，利用真值表求任意一個(gè)命題公式的主范式。（其中2、3與5、6可以寫(xiě)成同一個(gè)程序）實(shí)驗(yàn)過(guò)程算法思想：要求輸入P、Q實(shí)現(xiàn)┓、∧、∨、→以及?運(yùn)算；可以用switch語(yǔ)句對(duì)其進(jìn)行判斷也可以用if-else語(yǔ)句。因?yàn)檫@一題與最后一題中的功能函數(shù)Opereat(a,op,b)類(lèi)似。所以這里直接打印了他們的結(jié)果。實(shí)驗(yàn)代碼：專(zhuān)業(yè)班級(jí)：計(jì)算機(jī)111姓名：李俊學(xué)號(hào)：2011014620實(shí)驗(yàn)日期：2012.10#include<stdio.h>voidmain()調(diào)試報(bào)告：{調(diào)試報(bào)告： intP,Q; printf("請(qǐng)輸入布爾型變量P的值(0或1),P="); scanf("%d",&P); printf("\n請(qǐng)輸入布爾型變量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)));}算法思想：編寫(xiě)P∧Q∨R的真值表。需要構(gòu)建一個(gè)結(jié)構(gòu)體存放這個(gè)真值表對(duì)其賦值再將其打印就可以得到真值表。structList{intP,Q,R;intanswer;}a[8]而主范式則是要對(duì)結(jié)構(gòu)體遍歷當(dāng)a[i].answer為真時(shí)輸出下標(biāo)index就可以得到主范式最后用格式控制符’\b’取消掉最后一個(gè)析取符號(hào)。實(shí)驗(yàn)代碼：專(zhuān)業(yè)班級(jí)：姓名：學(xué)號(hào)：實(shí)驗(yàn)日期：voidmain(){ intp,q,r,i=0; for(p=0;p<2;p++)//利用for循環(huán)為結(jié)構(gòu)數(shù)組賦值 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++)//利用循環(huán)將結(jié)果打印 { 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)); }調(diào)試報(bào)告： print(a);調(diào)試報(bào)告：}voidprint(structLista[]){ inti; printf("P∧Q∨R的主范式是:");專(zhuān)業(yè)班級(jí)：姓名：學(xué)號(hào)：實(shí)驗(yàn)日期： for(i=0;i<8;i++) { if(a[i].answer==1) { printf("m%d∨",i); } } printf("\b");}（4）算法思想：證明P→Q，┓(Q∨R)┣┓P。只需構(gòu)建結(jié)構(gòu)數(shù)組存放這個(gè)真值表。structList{ intP,Q,R; intanswer1,answer2,answer3;}a[8];分別存放P→Q，┓(Q∨R)，┓P的真值當(dāng)answer1和answer2都為真時(shí)若answer3也為真則返回ture若假則返回false實(shí)驗(yàn)代碼：voidiniList(structLista[]);//初始化這個(gè)結(jié)構(gòu)數(shù)組voidprint(structLista[]);//打印這個(gè)主范式voidmain()//主函數(shù)只需要調(diào)用這個(gè)功能（API）{ iniList(a); print(a);}

調(diào)試報(bào)告：voidiniList(structLista[]){調(diào)試報(bào)告：voidiniList(structLista[]){ intp,q,r,i=0; for(p=0;p<2;p++)//利用for循環(huán)為結(jié)構(gòu)數(shù)組賦值 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))//當(dāng)前兩個(gè)表達(dá)式為真而結(jié)果為假時(shí)條件不成立輸出false并推出函數(shù) { printf("false\n"); exit(0); } } printf("true\n");}

（5、6）算法思想：（5、6）算法思想：這個(gè)算法有兩處難點(diǎn)需要思考。第一：如何利用程序?qū)崿F(xiàn)真值表的計(jì)算;這里可以用類(lèi)似求任意表達(dá)式的值的算法來(lái)求;即算符優(yōu)先算法。創(chuàng)建一個(gè)算符優(yōu)先的dictionary。這個(gè)字典要是9*9的。字典的定義如下圖所示。這樣只需按列按行查找相應(yīng)的算符保存i,j就可以得到表達(dá)式是什么值了tab[9][9]={ "0=-|&!()@", "=><<<<<>>", "->><<<<>>", "|>>><<<>>", "&>>>><<>>", "!>>>>><>>", "(<<<<<<=E", ")>>>>>E>>", "@<<<<<<E=", }第二：怎樣實(shí)現(xiàn)命題變?cè)馁x值。這里有以下幾點(diǎn)。我們可以看到P、Q、R這三個(gè)命題變?cè)恼嬷当碣x值應(yīng)該是P Q R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 可以看到P、Q、R中0與1替換的頻率是不同的那么這樣我們就可以創(chuàng)建出一個(gè)數(shù)組A[1024][10]來(lái)存放這一種賦值。然后每次計(jì)算的時(shí)候我們只需要取其中某一行的賦值調(diào)用寫(xiě)好的函數(shù)就可以了。因?yàn)槲覀冇昧薉ivi函數(shù)將表達(dá)式去掉運(yùn)算符按其出現(xiàn)的先后順序?qū)⑵浯嬖诹薽yopnd[10]這個(gè)數(shù)組中這樣當(dāng)我們要取某個(gè)變?cè)闹档臅r(shí)候只要知道這個(gè)變?cè)趍yopnd數(shù)組中的下標(biāo)(index);取到得A[i][index]就是這時(shí)候變?cè)馁x值;最后我們就可以按照計(jì)算表達(dá)式的值的常規(guī)思路對(duì)棧進(jìn)行存儲(chǔ)獲取這時(shí)候的值。[注]：參考《計(jì)算機(jī)工程與科學(xué)》2008年第30卷第一期《命題公式真值表的生成算法》作者：徐鳳生；李天志。#include<stdio.h>#include<string.h>#include<stdio.h>#include<string.h>#include<math.h>#defineMAX_SIZE20/*函數(shù)聲明*/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);/*操作運(yùn)算符棧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];}/*操作數(shù)據(jù)棧OPND*/typedefstruct/*操作數(shù)據(jù)棧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];}/*主函數(shù)*/voidmain(){ charexp[30]; printf("請(qǐng)輸入你要生成的真值表的命題公式\n(=,-,|,&,!,分別表示雙條件、單條件、析取、合取,取反):"); gets(exp); evalu(exp);}/**/intcountPQ(char*exp)//計(jì)算表達(dá)式中命題變?cè)膫€(gè)數(shù){ inti,count=0; for(i=0;exp[i]!='@';i++) if(exp[i]>='A'&&exp[i]<='Z') count++; returncount;}voidevalu(char*exp)//主要功能函數(shù){voidevalu(char*exp)//主要功能函數(shù){ charmyopnd[10]; intA[1024][10],M[1024];//最多多可以生成10命題變?cè)恼嬷当?intflag,m,n,i,j,k,length; length=strlen(exp); exp[length]='@';//在表達(dá)式末尾插入@ exp[length+1]='\0'; n=countPQ(exp);//生成具體的行列數(shù) m=(int)pow(2,n);//計(jì)算每列有多少個(gè)元素 for(j=0;j<n;j++) { flag=1; k=(int)pow(2,n-j-1);//計(jì)算該列中應(yīng)該算多少個(gè)0后換1;例如三個(gè)變?cè)獣r(shí)第一列是00001111;而第二列是00110011;依次類(lèi)推; 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]);//輸出改行運(yùn)算結(jié)果 printf("\n"); } printf("\n"); printf("主范式\n"); for(i=0;i<m;i++) { if(M[i])printf("m%d∨",i); } printf("\b");}charPrecede(charop1,charop2)//按字典索引兩個(gè)算符的優(yōu)先級(jí){charPrecede(charop1,charop2)//按字典索引兩個(gè)算符的優(yōu)先級(jí){ 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)//返回雙條件運(yùn)算符的結(jié)果{ switch(op) { case'=':return(((!x)||y)&&(x||(!y)));break; case'-':return((!y)||x);break; //一定要!y||x要不然數(shù)據(jù)會(huì)出錯(cuò) case'|':returnx||y;break; case'&':returnx&&y;break; }}voidDivi(charexp[],charmyopnd[])//得到命題公式包涵的命題變?cè)蛄衜yopnd(按命題變?cè)霈F(xiàn)的先后順序排序){ 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為表達(dá)式，p為這個(gè)時(shí)候表達(dá)式的賦值；返回該表達(dá)式在p賦值時(shí)的真值{ charmyopnd[10];charc,op;intk=0,d,a,b;intCalExpression(char*exp,int*p)//exp為表達(dá)式，p為這個(gè)時(shí)候表達(dá)式的賦值；返回該表達(dá)式在p賦值時(shí)的真值{ charmyopnd[10];charc,op;intk=0,d,a,b; IniOPTR(&OPTR);PushOPTR(&OPTR,'@'); IniOPND(&OPND); Divi(exp,myopnd);//將exp中的命題變?cè)闯霈F(xiàn)的先后順序存入myopnd;例如exp為"P|Q&R";myopnd為"PQR"; c=exp[k++];//取出表達(dá)式第一個(gè)元素 while(c!='@'||GetTopOPTR(&OPTR)!='@')//循環(huán)的條件是表達(dá)式中取出的元素不為@或者算符操作棧OPTR的棧頂元素不為@ { if(c>='A'&&c<='Z') { d=p[Locate(myopnd,c)];//取出命題變?cè)猚對(duì)應(yīng)的賦值;Locate返回了c在myopnd的數(shù)組下標(biāo) PushOPND(&OPND,d); c=exp[k++]; } else { switch(Precede(GetTopOPTR(&OPTR),c)) { case'<':{PushOPTR(&OPTR,c);c=exp[k++];break;}//操作符棧;棧頂?shù)膬?yōu)先級(jí)低,將c壓棧,讀取下一個(gè)字符 case'=':{PopOPTR(&OPTR);c=exp[k++];break;}//脫去括號(hào) case'>'://運(yùn)算符