离散数学实验报告
目录
第一章 实验概述......................................................................................................... 3
1.1 实验目的......................................................................................................... 3
1.2 实验内容......................................................................................................... 3
1.3 实验环境......................................................................................................... 3
第二章 实验原理和实现过程..................................................................................... 4
2.1 实验原理......................................................................................................... 4
2.1.1 逻辑连接词的运算............................................................................... 4
2.1.2 真值表与主范式................................................................................... 4
2.2 实验过程(算法描述)................................................................................. 4
2.2.1 程序整体思路....................................................................................... 4
2.2.2 实现实验A算法................................................................................... 4
2.2.3 实现实验BC算法................................................................................. 5
第三章 实验数据及结果分析..................................................................................... 7
3.1主程序ABC.c的功能测试及结果分析.......................................................... 7
3.1.1输入数字“1”........................................................................................ 7
3.1.2输入数字“2”........................................................................................ 7
3.1.3输入数字“3”........................................................................................ 8
3.1.4输入其他字符时.................................................................................... 8
3.2 实验A的功能测试和结果分析..................................................................... 8
3.2.1测试数据为“p=T和q=F”..................................................................... 9
3.2.2测试数据为“p=F和q=F”..................................................................... 9
3.2.3测试数据为“p=A和q=F”.................................................................... 9
3.2.4测试数据为“p=T和q=A”.................................................................... 9
3.2.5测试数据为“p=F和q=F”,之后返回主界面...................................... 10
3.3 实验BC的功能测试和结果分析................................................................ 10
3.3.1测试数据为“a&b|c#”........................................................................ 10
3.3.2测试数据为“(a>b)|(c&d)#”............................................................... 11
3.3.3测试数据为“(a>b)|(c&d)”................................................................. 12
3.3.4测试数据为“a&b|c”.......................................................................... 13
第四章 实验收获和心得体会................................................................................... 14
4.1 实验收获....................................................................................................... 14
4.2 心得体会....................................................................................................... 14
第五章 实验源程序清单........................................................................................... 15
5.1 主程序ABC.c的代码.................................................................................... 15
5.2 头文件A.h的代码........................................................................................ 17
5.3 头文件BC.h的代码...................................................................................... 20
1. 掌握离散数学中涉及的相关概念。
2. 培养学生的逻辑思维能力和算法设计的思想。
3. 熟练掌握C/C++语言程序设计的基本方法和各种调试手段。
4. 熟练掌握包括数组、链表以及邻接表或邻接矩阵等数据结构的建立和运用。
1. 从键盘输入两个命题变元P和Q的真值,求它们的合取、析取、条件和双条件的真值。(A)
2. 求任意一个命题公式的真值表(B),并根据真值表求主范式(C)
注意:题目类型分为A,B,C三类,其中A为基本题,完成A类题目可达到设计的基本要求,其他均为加分题,并按字母顺序分数增加越高。
C或C++语言编程环境实现。
真值表是数理逻辑中的一个重要概念,实践证明运用真值表可以解答数理逻辑的绝大部分问题,也无须高深的知识和技巧,具有直观明了的特点,尽管某些列表比较麻烦,但仍不失为是一种行之有效的好办法。
为了实现二元合取、析取、条件和双条件表达式的计算,可以充分利用联接词和逻辑运算符之间的相似性实现程序功能。
命题公式的主析(合)取范式具有重要的意义,根据公式的主析(合)取范式,不仅可以判断两个公式是否等价,而且还可以判断一个公式是否为永真式(重言式)或永假式(矛盾式)。
一般我们将公式中的命题变元放在真值表的左边,将公式的结果放在真值表的右边。命题变元可用数值变量表示,合适公式的表示及求真值表转化为逻辑运算结果;可用一维数表示合式公式中所出现的n个命题变元,同时它也是一个二进制加法器的模拟器,每当在这个模拟器中产生一个二进制数时,就相当于给各个命题变元产生了一组真值指派。
本程序的一大特色就是开发者同时使用了C语言和C++语言来进行开发,用C语言来开发主程序ABC.c和实验A.h头文件,用C++语言来开发实验BC.h头文件,通过编译实现了全部的功能。
在实验A中,为了实现二元合取、析取、条件和双条件表达式的计算,我充分利用联接词和逻辑运算符之间的相似性实现程序功能。
详细说来,编写了一个用于判断的函数,先将从键盘获取的“T”或“F”的字符转化为对应的1或0,然后运用C语言中的位运算符号进行相应运算,并且在显示屏上输出相应的真值。
值得注意的一点是,在本子程序中,开发者使用了“标志号”的概念来进行程序控制。具体说来就是,在进行程序检查时和退出实验A功能界面时使用了标志号进行程序的跳转,同时还有在进行输入判断时对输入函数进行控制。
例如,在每次调用判断函数进行判断前,对标志号进行检测。判断函数是一个根据标志号来判断是否循环的循环函数。一般情况下进行判断时,标志号为0,当每次判断完成后,就会根据用户相应的选择来对标志号进行置数;当用户想要退出实验A所实现的功能界面时,程序会根据用户的键盘输入值将标志号置为1,那么判断函数再次循环之前,在对标志号进行检测时,程序会自动退出子函数调用,返回主界面。
实验BC的实现算法,开发者采用了指导老师所推荐的算法逻辑,其具体说明如下:
(1)将二进制加法模拟器赋初值0。
(2)计算模拟器中所对应的一组真值指派下合式公式的真值。
(3)输出真值表中对应于模拟器所给出的一组真值指派及这组真值指派所对应的一行真值。
(4)产生下一个二进制数值,若该数值等于2n-1,则结束,否则转(2)。
注意,在进行表达式求值的时候,可先将带括号的中缀表达式利用栈结构转换为不带括号的后缀表达式(逆波兰式),然后进行计算。
实验BC的程序编写思路大体上完全符合这样的设计思路,通过对数据结构中“堆栈”的概念来进行设计。
具体说来,程序中定义了两个重要的数组,一个用于表达式的计算,另外一个用于指派真值。首先编写了一个将输入的字符串转化为可计算的表达式的函数,之后定义联结词的栈内和栈外的优先级,用于表达式的转化。
然后,编写了一个计算函数,用于模仿实数加法器进行表达式计算,并且用数组构建了一个二进制加法器,用于指派真值。为了提高程序的容错能力,还编写了一个检查输入格式的函数。
最后,就是问题的解决函数了,首先将用户输入的表达式进行输入格式的检查,确认无误后,将字符串转化为可计算的表达式,保存在特定的堆栈中,之后,模仿实数加法器产生一个真值,同时对表达式进行计算,输出到真值表的显示界面上,并且根据真值来入栈,成真指派入析合栈,成假指派入合析栈,最后根据析合栈和合析栈的内容来进行析合范式与合析范式的输出。
这就是主程序控制的主界面。
当输入数字“2”时 ,程序会显示实现实验BC的功能界面。
当输入数字“3”时 ,程序会显示退出界面。
当输入其他字符时时 ,程序会在屏幕上显示相应的提示语,要求用户重新输入。
当测试数据为“p=T和q=F”时,程序会显示他们的合取、析取、条件和双条件的真值。
当测试数据为“p=F和q=F”时,程序会显示他们的合取、析取、条件和双条件的真值。
当测试数据为“p=A和q=F”时,程序检测出p是非法的输入格式,会在屏幕上显示相应的提示语,要求用户重新输入。
当测试数据为“p=T和q=A”时,程序检测出q是非法的输入格式,会在屏幕上显示相应的提示语,要求用户重新输入。
当测试数据为“a&b|c#”时,程序会求出这个命题公式的真值表,并根据真值表求出主范式。
当测试数据为“(a>b)|(c&d)#”时,程序会求出这个命题公式的真值表,并根据真值表求出主范式。
当测试数据为“(a>b)|(c&d)”时,程序检测出表达式的后面没有“#”,判断此次是非法的输入格式,会在屏幕上显示相应的提示语,要求用户重新输入。
当测试数据为“a&b|c”时,程序检测出表达式的后面没有“#”,判断此次是非法的输入格式,会在屏幕上显示相应的提示语,要求用户重新输入。
在刚开始编写程序的时候,为了实现最基本的输入和输出功能,我却花了大量的时间在那上面。原因在后来查阅的很多资料后才知道的,像scanf函数之类的小函数,其实是还有很多需要注意的地方的。
之后,在编写头文件程序的时候,遇到很多诸如跳转控制、数组操作、堆栈运用等等具体的问题。经过不断的尝试摸索,通过查阅大量资料,后来才慢慢的攻克一个个的难点。在C语言和C++语言的运用时,经常会有混淆的地方,通过一次次的提醒和注意,到后来终于可以慢慢的将它们区分开了。
#include "stdafx.h"
#include "iostream"
#include "cstring"
#include "stack"
#include "cmath"
#define maxsize 100
using namespace std;
char str[100];//输入的表达式
int zhipai[20]={0};//用于指派真值的数组
int length;//逻辑表达式长度
char expression[100];//用于计算的数组
class symbol {
public:
void solve();
void Clear(){}
private:
void change();
int Calculate();
void check();
bool Get2Operands(double &left,double &right);
void DoOperator(char op);
stack<int> s; //运算栈
};
bool symbol ::Get2Operands(double &left,double &right){ //取两运算值
if(s.size()==0){
cerr<<"Miss Operand!"<<endl;
return false;
}
right=s.top();
s.pop();
if(s.size()==0){
cerr<<"Miss Operand!"<<endl;
return false;
}
left=s.top();
s.pop();
return true;
}
void symbol ::DoOperator(char op){ //单次运算
double left,right;
bool result=Get2Operands(left,right);
if(result)
switch(op){
case '|':s.push(left||right);break;//或运算
case '&':s.push(left&&right);break;//与运算
case '>':s.push(!left||right);break;//蕴涵运算
case '!':s.push((!right)&&left);break;//非运算
case '=':s.push(left==right);break;//等价运算
}
else
Clear();
}
void symbol ::change() //将输入的字符串转化为可计算的表达式
{
int k=0;
int flag=1;
int count=0; //命题变元个数
for(int i=0;i<pow(2,count);i++)
{
k=1;
for(int m=0;m<length;m++)
{
if(isalpha(str[m]))//将原来的命题变元修改为真值
{
if(flag==1)
{
if(zhipai[k]==0)
expression[m]='0';
else
expression[m]='1';
k++;
}
else
expression[m]='0';
flag=1;
for(int t=m;t>=0;t--)
{
if((str[m+1]==str[t])&&isalpha(str[m+1])&&isalpha(str[t]))
flag=0;
}
}
else
expression[m]=str[m];//逻辑联结词不变
}
for(int t=0;t<length;t++)
{
for(int j=t;j<length;j++)
{
if(str[t]==str[j])
{
expression[j]=expression[t];//相同的命题变元复制赋值
}
}
}
}
}
void plus(int a[],int q)//二进制加法器,用于指派真值
{
a[q]=a[q]+1;
for(int i=q;a[i]==2;i--)
{
a[i]=0;
a[i-1]=a[i-1]+1;
}
}
int isp(char ch) //联结词的栈内优先级
{
switch(ch){
case '#':return 0;break;
case '(':return 1;break;
case '!':return 10;break;
case '=':return 9;break;
case '&':return 7;break;
case '|':return 5;break;
case '>':return 3;break;
case ')':return 12;break;
default:return -1;break;
}
}
int icp(char ch) //联结词的栈外优先级
{
switch(ch){
case '#':return 0;break;
case '(':return 12;break;
case '!':return 11;break;
case '=':return 8;break;
case '&':return 6;break;
case '|':return 4;break;
case '>':return 2;break;
case ')':return 1;break;
default:return -1;break;
}
}
int symbol ::Calculate() //模仿实数加法器进行表达式计算
{
stack<char> h;
char ch,y;
h.push('#');
for(int temp=0;temp<length-1;temp++){
ch=expression[temp];
if(isdigit(ch))//命题变元真值入栈
{
if(ch=='0')
s.push(0);
else
s.push(1);
}
else if(ch==')')//运算括号内的
{
for(y=h.top(),h.pop();y!='(';y=h.top(),h.pop()){
DoOperator(y);}
}
else{
if(ch=='!')//非运算,在!前加1,将!视作双目操作符
{
s.push(1);
}
for(y=h.top(),h.pop();isp(y)>icp(ch);y=h.top(),h.pop())
DoOperator(y);
h.push(y);
h.push(ch);
}
}
while(h.size()!=1){
y=h.top();
h.pop();
DoOperator(y);
}
cout <<s.top()<<endl;//输出最终结果
return s.top();
}
void symbol::check();//检查函数的预先声明
void symbol::solve()//问题的解决
{
cout<<"********************************************************************************"<<endl;
cout<<"请输入命题逻辑表达式:"<<endl;
cout<<"(注意:命题变元在a~z中选取,变元个数不要超过20个,或运算用|,与运算用&,非运算用!,蕴涵运算用>,等价运算用=,以#结尾)"<<endl;
cout<<""<<endl;
cout<<"********************************************************************************"<<endl;
int flag=1;//标记,防止重复添加命题变元
int count=0;//命题变元的数目
cin >>str; //输入命题逻辑表达式
length=strlen(str);
char bianyuan[100]; //命题变元数组
for(int i=0;i<length;i++)//逐次添加命题变元
{
if(isalpha(str[i])&&(flag==1))
{
bianyuan[count]=str[i];count++;
}
flag=1;
for(int k=0;k<count;k++)
{
if(bianyuan[k]==str[i+1])flag=0;
}
}
if(count==0)
{cout<<"无命题变元,重新输入!"<<endl;solve();}
cout<<"真值表(用0代替false,用1代替true):" <<endl;
check();//合法性检查
for(int w=0;w<count;w++)
cout<<bianyuan[w]<<' ';
cout<<"fc"<<endl;
int* truth=new int[pow(2,count)];
stack<char> xh1;
xh1.push('(');
stack<char> xh2;
stack<char> hx1;
hx1.push('(');
stack<char> hx2;
for(int r=0;r<pow(2,count);r++)//输出真值表
{
for(int j=1;j<=count;j++)
{cout<<zhipai[j]<<' ';}
change();
truth[r]=Calculate();
if(truth[r]==1) //成真指派入析合栈
{
for(int t=0;t<count;t++)
{
if(zhipai[t+1]==1)
{
xh1.push(bianyuan[t]);
xh1.push('&');
}
else
{
xh1.push('!');
xh1.push(bianyuan[t]);
xh1.push('&');
}
}
xh1.pop();
xh1.push(')');
xh1.push('|');
xh1.push('(');
}
if(truth[r]==0) //成假指派入合析栈
{
for(int c=0;c<count;c++)
{
if(zhipai[c+1]==1)
{
hx1.push(bianyuan[c]);
hx1.push('|');
}
else
{
hx1.push('!');
hx1.push(bianyuan[c]);
hx1.push('|');
}
}
hx1.pop();
hx1.push(')');
hx1.push('&');
hx1.push('(');
}
plus(zhipai,count);
}
//析合范式与合析范式的输出
cout<<"析合范式为:";
if(xh1.size()==1)
cout<<"无析合范式,此表达式为矛盾式";
else{
xh1.pop();//弹出'('
xh1.pop();//弹出'|'
while(xh1.size()!=0)
{
xh2.push(xh1.top());
xh1.pop();
}
while(xh2.size()!=0)
{
cout<<xh2.top();
xh2.pop();
}
}
cout<<endl;
cout<<"合析范式为:";
if(hx1.size()==1)
cout<<"无合析范式,此表达式为重言式";
else{
hx1.pop();//弹出'('
hx1.pop();//弹出'&'
while(hx1.size()!=0)
{
hx2.push(hx1.top());
hx1.pop();
}
while(hx2.size()!=0)
{
cout<<hx2.top();
hx2.pop();
}
}
cout<<endl;
cout<<"是否继续运算?Y/N"<<endl;
char goon;
cin>>goon;
if(goon=='y'||goon=='Y')
solve();//递归调用solve,重新计算
}
void symbol::check()//检查输入的逻辑表达式是否合法(只对部分语法做检查)
{
if(str[length-1]!='#'){cout<<"未以#结尾,重新输入!"<<endl;solve();}
if(!isalpha(str[length-2])&&str[length-2]!=')'){cout<<"错误,重新输入!"<<endl;solve();}
for(int i=0;i<length-1;i++)
{
if(!isalpha(str[i])&&str[i]!='&'&&str[i]!='|'&&str[i]!='>'&&str[i]!='='&&str[i]!='!'&&str[i]!='('&&str[i]!=')')
{
cout<<"错误的字符,重新输入!"<<endl;solve();
}
if(isalpha(str[i])&&isalpha(str[i+1])){cout<<"命题变元之间无联结词,重新输入!"<<endl;solve();}
if(isalpha(str[i])&&str[i+1]=='('){cout<<"命题变元后不可接(,重新输入!"<<endl;solve();}
if(!isalpha(str[i])&&!isalpha(str[i+1])&&(str[i]!='('&&str[i+1]!='!')&&str[i+1]!='('&&str[i]!=')')
{
cout<<"联结词间无命题变元,重新输入!"<<endl;solve();
}
}
int left=0,right=0,j=0;
while(j<length-1)
{
if(str[j]=='(')
left++;
if(str[j]==')')
right++;
if(right>left)
{cout<<"括号次序不匹配,重新输入!"<<endl;solve();}
j++;
}
if(left!=right){cout<<"括号个数不匹配,重新输入!"<<endl;solve();}
}#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int datatype;
typedef struct node
{
datatype key;
struct node *lchild,*rchild;
}bsnode;
typedef bsnode *bstree;
void insertbstree(bstree *t,datatype x)
{
bstree f,p;
p = *t;
//cout<<p;
while(p)//找到插入点的位置
{
//if(x == (p->key))//
// return;
f = p;
if(x < p->key)
p = p ->lchild;
else
p = p ->rchild;
//f = p;
}
//f = p;
p =(bstree)malloc(sizeof(bsnode));
p->key = x;
p->lchild=p->rchild=NULL;
if(*t == NULL)
*t = p;
else
{
if(x < (f->key))
f->lchild = p;
else
f->rchild = p;
}
}
bstree creatbstree(bstree t)
{
datatype key;
//scanf("%d",&key);
cin>>key;
while(key != -1)
{
insertbstree(&t,key);
//scanf("%d",&key);
cin>>key;
}
return t;
}
void inorder(bstree t)
{
if (t)
{
inorder(t->lchild);
printf("%d ",t->key);
inorder(t->rchild);
}
}
int main(void)
{
bstree t = NULL,p;
//cout<<t;
cout<<"创建一个输入-1为作为结束标记:排序二叉树:"<<endl;
//printf("请输入一个-1为结束标记的结点序列:\n");
p = creatbstree(t);
//inorder(creatbstree(t));
inorder(p);
return 0;
}
高等数学数学实验报告实验人员院系学号姓名实验地点计算机中心机房实验一一实验题目设数列xn由下列递推关系式给出x观察数列1x111x…
数学实验报告实验名称matlab学院专业班级姓名学号20xx年6月一实验目的通过课后习题的练习掌握利用matlab进行概率运算和数…
重庆大学学生实验报告实验课程名称数学实验开课实验室学院年级专业班学生姓名学号开课时间学期数学与统计学院制开课学院实验室数学与统计D…
西安交通大学数学实验报告高等数学实验报告MATLAB实验操作报告同组人髙加西20xx年04月10日电气工程学院电气工程与自动化专业…
离散数学实验报告题目专业学号姓名指导教师提交日期实验一五种连结词的逻辑运算一实验目的用C语言实现两个命题变元的合取析取蕴涵和等价表…
离散数学应用实践实验报告课序号03学号姓名任课教师陈瑜评阅成绩评阅意见提交报告时间20xx年1月3日课程名称离散数学运用实践学生姓…
离散数学实验报告目录第一章实验概述311实验目的312实验内容313实验环境3第二章实验原理和实现过程421实验原理4211逻辑连…
实验一命题逻辑推理1实验用例根据下面的命题试用逻辑推理方法确定谁是作案者写出推理过程1营业员A或B偷了手表2若A作案则作案不在营业…
实验1闭包离散数学闭包实验报告专业10计算机科学与技术嵌入式软件人才培养方向学号1045534148姓名周谦益时间20xx1115…