离散数学实验指导书

一．前言

《离散数学》是现代数学的一个重要分支，是计算机科学与技术专业的基础理论课，也是该专业的核心课程和主干课程。“离散数学”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。该课程一方面为后继课程如数据结构、编绎原理、操作系统、数据库原理、人工智能和形式语言与自动机等提供必要的理论基础；同时，更为重要的是培养学生的抽象思维能力和逻辑推理能力，为今后的学习和工作打好基础。无论从计算机学科发展的过去、现在和未来看，《离散数学》都是计算机科学与技术专业不可缺少的重要组成部分。这门课程有着其它课程不可替代的地位和作用，是一门承前启后的课程。

根据《离散数学》课程本身的理论性较强的特性，设置《离散数学实验》实践环节十分重要。通过实验实践内容的训练，突出逻辑性思维训练的特征, 目的是提高学生学习的兴趣及实际动手的能力。

为了帮助学生更好地学习本课程，理解和掌握所学基本概念和方法，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题.本指导书根据本课程要求编写这本指导书。以期为同学作实验提供帮助！

二．目录

第一部分实验内容

实验1：真值表判断

实验2：集合运算及关系运算

实验3：求最短路径或平面图的判断（二选取一）

第二部分实验指导

实验1：真值表判断

实验2：集合运算及关系运算

实验3：求最短路径或平面图的判断（二选取一）

第三部分实验报告

三．正文

第一部分实验内容

实验1：真值表

1．实验目的：通过试验，了解命题的有关概念，真值表技术，连接词的作用与意义

2．实验类型：验证型实验

3．实验学时：2学时

4．实验原理及知识点

掌握命题公式及其类型的概念，熟悉逻辑连接词的运算规则，熟悉命题公式真值表的构成，并可用计算机实现

5．实验环境（硬件环境、软件环境）

1、试验环境visual C＋＋6.0

2、操作系统window 2000、xp

6．实验内容及步骤

1、编写操作界面

使用MFC提供的DLG类，在面板上添加一个输入文本框作为输入公式的实例输入。添加两个按钮分别表示在程序面板上显示结果和利用输出文本文件显示并保存结果。

2、按照运算规则编写求真值表函数

在对应按钮的触发事件中添加对应的处理函数

3、测试与修改

7．思考与练习

利用真值表技术和公式的演算方法，如何求得公式对应的主析取范式和主合取范式，如何判断两公式是否相等，是否为永真式、永假式、可满足式？

实验2：集合运算及关系运算

1．实验目的：通过试验，了解集合运算有关概念及计算技术，撑握合成关系运算条件与运算特点。

2．实验类型：验证型实验

3．实验学时：2学时

4．实验原理及知识点：

交运算：设A，B是两个集合，则A∩B={x｜(x A)并且(x B)}

?并运算：设A，B是两个集合，则A∪B={x｜(x A)或(x B)}

?差运算：设A，B是两个集合，则A B={x｜(x A)并且(x B)}

?笛卡儿集合：设A，B是两个集合，称集合A×B={|(x A)∧(y B)}

为集合A与B的笛卡儿积

?求子集或求幂集

设A有ｎ个元素，则ρ(A)有2n个元素。

证明：A的所有由ｋ个元素组成的子集个数为从ｎ个元素中取ｋ个元素的

组合数：

求关系合成运算:

设R是X到Y的关系，S是Y到Z的关系，则RοS称为R和S的复合关系，定义为：

RοS= { ?∣y(∈R∧∈S）}

5．实验环境（硬件环境、软件环境）

1、试验环境visual C＋＋6.0

2、操作系统window 2000、xp

6．实验内容及步骤

1、编写操作界面

使用MFC提供的DLG类，在面板上添加两个输入文本框作为输入集合A、B 的实例输入。添加四个按钮分别表示求交集，求并集，求差集和求笛卡儿积。

2、按照运算规则编写运算函数

在对应按钮的触发事件中添加对应的处理函数。

3、编译程序，连调发现程序中存在的问题并修改

7、思考与练习

1、在掌握集合运算与关系合成的基础上，思考如何使用集合的运算来证明集合间的包含、相等和真包含的关系？

实验3：求最短路径或平面图的判断

1．实验目的：通过求最短路径与对平面图的判断，撑握路与图在计算中处理与表示，同时撑握求最短路径的方法，另理解对平面图有关原理。

2．实验类型：验证型实验

3．实验学时：2学时

4．实验原理及知识点：

平面图判断的知识点

1、设G是连通平面图，有v个结点，e条边，r个面，则

v-e+r=2 (欧拉公式)

2、设G是有v个结点、e条边的连通简单平面图，且v≥3，则

e≤3v-6

3、设G是v个结点、e条边的连通平面图，且G的各面的次数大于等于4，则

e 2v-4

4推论2给出了各面次数大于等于4的连通平面图应满足的必要条件，所以可用来判断某些图不是平面图

例如，应用推论1可知K3，3不是平面图。因K3，3是连通平面图，每个面由四条边围成，v=6, 2v-4=8，而e=9，不满足推论给出的条件。

最短路径的算法：

设每个点都有一对标号(d j, p j)，其中d j是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；p j则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：

1) 初始化。起源点设置为：①d s=0, p s为空;②所有其他点: d i=∞, p i=?;③标记起源点s，记k=s,其他所有点设为未标记的。

2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：

d j=min［d j, d k+l kj］

式中，l kj是从点k到j的直接连接距离。

3) 选取下一个点。从所有未标记的结点中，选取d j中最小的一个i：

d i=min［d j, 所有未标记的点j］

点i就被选为最短路径中的一点，并设为已标记的。

4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：

i=j*

5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。

5．实验环境（硬件环境、软件环境）

1、试验环境visual C＋＋6.0

2、操作系统window 2000、xp

6．．实验内容及步骤

1、编写操作界面

2、按照求最短路径算法编写求短路径函数；

按照判断平面图的算法原理求平面图算法函数。

3、编译程序，连调发现程序中存在的问题并修改

第二部分实验指导

具体写实验方法，实验步骤及补充的实验知识。

实验1 真值表判断实验指导

●实验所属系列：离散数学课后实验

●实验对象：本科

●相关课程及专业：离散数学，计算机专业

●

实验目的

公式是由命题变元、逻辑联结词、括号组成的合法的符号串，而命题变元是一个抽象的概念，若不指定命题变元的真值，则公式没有真值可言。反之，若对所有的命题变元都指定一定的真值，则公式就变成了一个具有确切真值的命题。将所有的这些命题变元的可能取值一一列出形成一个表格的形式，这个表格称为该公式的真值表。利用真值表技术和公式的演算方法，能够求得一公式对应的主析取范式和主合取范式，还能够判断两公式是否相等，是否为永真式、永假式、可满足式。

实验内容与要求

设是命题变元P1、P2、P3、…、Pn是出现在公式G中的所有命题变元，指定P1、P2、P3、…、Pn一组真值，则这组真值称为G的一个解释（Explanation），常记为I。

因此，设G是一个公式，I是G的一个解释，显然，G在I下有真值。由于每一个公式可能存在着不止一种解释，这种解释的多少与公式中的命题变元的个数有关。对每一个命题变元都有“真”、“假”两种不同的解释，若有两个命题变元，按组合的方法，应有四种不同的解释。一般来说，若有n个命题变元，则应有2n个不同的解释。为了能直观地表示一个公式所有可能的解释与公式在此解释下的结果，可定义：

公式G在其所有可能的解释下所取真值的表，称为G的真值表（Truth）。

本实验要求大家利用C＋＋语言，实现任意输入公式的真值表计算。一般我们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。有时为了清楚起见，也可将求公式的中间结果也依次放在真值表中；或者将求公式的中间结果放在公式的相应的每个联结词的下方。有时也可将具有相同变元个数的公式之真值结果依次放在同一个真值表中。显然，对任何一公式都有一真值表。

请注意以下约定：

输入公式要由（）确定优先级\n\n

同时为了方便键盘输入做如下规定：

(1) 用! 代替非操作

(2) 用&& 代替∧操作

(3) 用|| 代替∨操作

(4) 用<> 代替<=> 操作

(5) 保持操作-> 不变

要求依据上述运算规则，实现任意给定公式真值表的计算，并显示运算结果。

六、实验器材（设备、元器件）：

1、试验环境visual C＋＋6.0

2、操作系统window 2000、xp

七、实验步骤及操作：

1、编写操作界面

使用MFC提供的DLG类，在面板上添加一个输入文本框作为输入公式的实例输入。添加两个按钮分别表示在程序面板上显示结果和利用输出文本文件显示并保存结果。

2、按照运算规则编写求真值表函数

在对应按钮的触发事件中添加对应的处理函数。

void CMyDlg::OnOK()

{

// if(Lock!=1)

// {

strcpy(ShowList,"");

// }

// this->SetDlgItemText(IDC_EDIT1,ShowList);

this->SetDlgItemText(IDC_RSULT,ShowList);

// TODO: Add extra validation here

CString m_str;

CString Savem_str;

char *show;

show=new char[100];

if(ClenOrNot==1)

{

OnButton1();

// AfxMessageBox("出错!您未按要求操作，建议阅读帮助信息!");

}

else

{

this->GetDlgItemText(IDC_EDIT1,m_str);

Savem_str=m_str;

strcpy(show,m_str);

SequChar vc(show);

for(int ss=0;ss<40;ss++)

{

if(vc.BaseArry[ss+1]==1)

break;

canshu[as]=vc.BaseArry[ss+1];

as++;

}

int M=GivenCharFuction();

/////////////////////////////////////////////////////////////////////////

///

int NmberLine=mi(M);

int y=0;

for(int NmberLine_X=0;NmberLine_X

{ /////

NmberLine=NmberLine_X; /////

for(int i=10;i>10-M;i--) /////

{ ////

Arry[i]=NmberLine%2; /////

NmberLine=NmberLine/2;

//////

}

////

y=f(vc.BaseArry[0]);

if(y>1)

{

AfxMessageBox("错误!您未按要求操作，请先阅读帮助信息!");

OnButton1();

break;

}

}

if(y<=1)

{

for(int ShowCharWho=M-1;ShowCharWho>=0;ShowCharWho--)

{

m_str=CharWho[ShowCharWho];

strcat(ShowList,m_str);

strcat(ShowList," ");

}

strcat(ShowList,Savem_str);

strcat(ShowList,"\n");

for( NmberLine_X=0;NmberLine_X

{

NmberLine=NmberLine_X;

for(int i=10;i>10-M;i--)

{

Arry[i]=NmberLine%2;

NmberLine=NmberLine/2;

}

y=f(vc.BaseArry[0]);

for(int yx=11-M;yx<=10;yx++)

{

if(Arry[yx]==0)

strcat(ShowList,"0");

else

strcat(ShowList,"1");

strcat(ShowList," ");

}

if(y==0)

strcat(ShowList,"0");

else

strcat(ShowList,"1");

strcat(ShowList,"\n");

}

this->SetDlgItemText(IDC_RSULT,ShowList);

// strcpy(ShowList,"");

}

}

///////////////////////////////////////////////////////////////////////// //

// CDialog::OnOK();

3、编译程序，连调发现程序中存在的问题并修改

八、实验数据及结果分析：

例如：实验运行结果如下：

p∧q∨R<=>!S 真值，应输入：((p&&Q)||R)<>(!S)

运行结果如下：

Q R S p ((p&&Q)||R)<>(!S)

0 0 0 0 0

0 0 0 1 0

0 0 1 0 1

0 0 1 1 1

0 1 0 0 1

0 1 0 1 1

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 1

1 0 1 0 1

1 0 1 1 0

1 1 0 0 1

1 1 0 1 1

1 1 1 0 0

1 1 1 1 0

实验开设方式

本实验开设方式为个人实验；

实验思考

1、利用真值表技术和公式的演算方法，如何求得公式对应的主析取范式和主合取范式，

如何判断两公式是否相等，是否为永真式、永假式、可满足式？

实验二集合运算及关系运算

●实验所属系列：离散数学课堂实验

●实验对象：本科

●相关课程及专业：离散数学，计算机专业

●实验类型：课后实验

●实验时数（学分）：2学时

1实验目的

集合是一切数学的基础，每一门数学的讨论都离不开集合，为此，我们必须掌握集合的基本定义及运算规律，掌握集合的运算规则对与学习离散数学将有着极大的帮助。

本实验通过编写一个C＋＋程序，让计算机来完成两个集合的交、并、差、笛卡儿积及子集及简单关系运算。目的是让同学们更加深刻的理解集合的运算规则，特别是集合的笛卡儿积运算是我们接触的一个新的集合运算规则。

2实验内容与要求

集合的运算及关系的运算：

?交运算：设A，B是两个集合，则A∩B={x｜(x A)并且(x B)}

?并运算：设A，B是两个集合，则A∪B={x｜(x A)或(x B)}

?差运算：设A，B是两个集合，则A B={x｜(x A)并且(x B)}

?笛卡儿集合：设A，B是两个集合，称集合A×B={|(x A)∧(y B)}

为集合A与B的笛卡儿积

?求子集或求幂集

设A有ｎ个元素，则ρ(A)有2n个元素。

证明：A的所有由ｋ个元素组成的子集个数为从ｎ个元素中取ｋ个元素的

组合数：

求关系合成运算:

设R是X到Y的关系，S是Y到Z的关系，则RοS称为R和S的复合关系，定义为：

RοS= { ?∣y(∈R∧∈S）}

要求依据上述运算规则，实现任意给定两个集合的交、并、差、笛卡儿积运算，求幂集求关系的合成运算并显示运算结果。

3、实验步骤及操作：

1、编写操作界面

使用MFC提供的DLG类，在面板上添加两个输入文本框作为输入集合A、B 的实例输入。添加四个按钮分别表示求交集，求并集，求差集和求笛卡儿积。

2、按照运算规则编写运算函数

在对应按钮的触发事件中添加对应的处理函数

例如求交集：

void CMYcollectionDlg::Onjiaoji()

{

// TODO: Add your control notification handler code here

CSplitStr Split1;

CSplitStr Split2;

CString str1="{";

Split1.SetSplitFlag(",");

Split1.SetSequenceAsOne(TRUE);

Split2.SetSplitFlag(",");

Split2.SetSequenceAsOne(TRUE);

CString m_string1;

CString m_string2;

char m_char1[80];

char m_char2[80];

int i;

int j;

int m=0;

int n=0;

int k=0;

int counter=1;

this->GetDlgItemText(IDC_EDIT1,m_string1);

this->GetDlgItemText(IDC_EDIT2,m_string2);

strcpy(m_char1,m_string1);

strcpy(m_char2,m_string2);

Split1.SetData(m_char1);

Split2.SetData(m_char2);

CStringArray array1;

CStringArray array2;

Split1.GetSplitStrArray(array1);

Split2.GetSplitStrArray(array2);

for (i=0;i<=80;i++)

{

if(m_char1[i]==',')

m++;

}

for (j=0;j<=80;j++)

{

if(m_char2[j]==',')

n++;

}

for(i=0;i<=m;i++)

{

for(j=0;j<=n;j++)

{

if(!strcmp(array1[i],array2[j]))

{

str1=str1+array1[i];

str1=str1+",";

}

}

}

str1.TrimRight(",");

str1=str1+"}";

char *p=new char[1000];

strcpy(p,"A∩B=");

strcat(p,str1);

this->SetDlgItemText(IDC_STATICoutput,p);

delete[]p;

}

3、编译程序，连调发现程序中存在的问题并修改

4、实验数据及结果分析：

要有实验结果与结果分析

例如：运行结果如下：

●集合A={1,2,3,4}，集合B={3,4,5,6}

求并：{1,2,3,4}∪{3,4,5,6}={1,2,3,4,5,6}

求交：{1,2,3,4}∩{3,4,5,6}={3,4}

求补：{1,2,3,4} {3,4,5,6}={1,2}

●集合A={1,2}，集合B={a,b}

求笛卡儿积： A×B={<1,a>,<1,b>,<2,a>,<2,b

5、实验开设方式

本实验开设方式为个人实验；上机2学时；

6、实验思考

1、在掌握集合运算的基础上，思考如何使用集合的运算来证明集合间

的包含、相等和真包含的关系？

实验三求最短路径或平面图的判断

l 实验所属系列：离散数学课后实验

l 实验对象：本科

l 相关课程及专业：离散数学，计算机专业

l 实验类型：课后实验

l 实验时数（学分）：4学时

实验目的

学习图在计算机中的矩阵表示，并能利用课堂所学知识进行最短路径的计算。

实验内容与要求

题目：迷宫最短路径

⒈问题描述

从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。

⒉基本要求

(1)输入数据

a.输入迷宫的大小m行和n列，两者为整数

b.由随机数产生0或1，建立迷宫。

(2)输出数据

首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：

(m，n)，……，(I，j)，……，(1，1)

如无通道，则打印：

THERE IS NO PA TH.

⒊实现提示

(1)数据结构

a）为了在程序中判断方便，把迷宫扩展成为MAZE(0：m+1，0：n+1)，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。

b）用二维数组MOVE(1：8，1：2)存放八个方向上的位置量，如

图所示：

(I+MOVE[1，1]，j+MOVE[1，2])

(I+MOVE[8，1]，j+MOVE[8，2]) (I+MOVE[1，1]，j+MOVE[1，2])

(I+MOVE[7，1]，j+MOVE[7，2]) (I+MOVE[3，1]，j+MOVE[3，2])

(I+MOVE[6，1]，j+MOVE[6，2]) (I+MOVE[4，1]，j+MOVE[4，2]) (I+MOVE[5，1]，j+MOVE[5，2])

c)为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻找

路径的过程中，若通过了位置（I，j），则将MARK（I，J）置为为1。

d)为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1，0..2）数组，

对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置I和j，Q(P，2)记下其出发点在Q数组中的下标。

（2）算法基本思想

将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。

具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(I，j)=0 且MARK(I，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m ，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。

题目:是否是平面图

可以用

定理:::(非平面图判定)(库拉托夫斯基)：一线图为非平面图的充要条件是他包含同胚于K5或K3,3的子图。

来判定，但较复杂。

下面介绍不可分线图平面性的判定

算法思想与原理

--------------------

1 桥

线图G中选择一回路C，则C将G分为3个部分

用边集表示为3种：

I 回路上顶点在回路内连接的边

II 回路内的顶点与回路上的顶点连接的边

III 回路外的边和回路外的点与回路上的顶点连接的边

G中子图H的桥：H是G的子图(不一定是回路)，若G - E(H) 能表示为若干个I、II、III 类边集的直和，则这些I、II、III类边集为桥。

任一桥是连通的；它的任二顶点都有和子图H内部不相交的一条通路相连；除去H上的顶点外，H的任二桥都没有公共顶点。

H的附着点：桥Bh(i)和子图H的公共顶点称为Bh(i)对于H的附着顶点。

2 非平面图的判定

G可容纳的：平面图G有子图的平面嵌入? 图G的平面嵌入

G不可容纳的：若不存在这样的关系。

可画入：G某子图H的桥B，若他对H的全部附着点都在H嵌入图中的某个面f的周界上，则B是可画入的。F(B,H~)表示桥B在其中可画入的H~的面的集合。

不可画入：不都在某一个面的周界上，则是不可画入的。

定理：若H的平面嵌入图是G可容纳的，则对H的每一桥B有，F(B,H~)非空。(也是G是平面图的一个必要条件，可用于非平面判定)

3 平面性算法

算法：

-------------------------------------

有5步组成

1在G中选一回路G1，并求出G1的一个平面嵌入G1~，置i = 1

2若E(G)- E(Gi) = 空，则停止。于是Gi~是G的一个平面嵌入，G是平面图。

否则，确定G中Gi中的所有的桥，并对每一座桥B求出它的可画入的面的集合F(B,G i~)

3若有一座桥B，使得F(B,Gi~)=空，则停止。根据定理判定为非平面图。

若有一座桥B，使得|F(B,Gi~)|=1，则取{f}=F(B,Gi~)；

否则，从F(B,Gi~)中任选一个面作为f。

4在桥B中选一条连接Gi上两个附着顶点的通路Pi，Pi?B，置Gi+1=Gi∪Pi，由Pi在Gi ~的面f内的一个画法得到Gi+1的一个平面嵌入Gi+1。

5换i为i+1，转2

-------------------------------------

。实验的软硬件环境

PC机一台，装有VC++6.0或其它C语言集成开发环境。

实验准备

图可以用多种方式来表示，其中邻接矩阵是一种较简单的方式。复习离散数学教材12. 5节中关于邻接矩阵的描述。明确一下内容：

1．如何使用邻接矩阵表示图。

2．利用图的邻接矩阵求结点的出度和入度的方法。

3.利用最短路径算法与平面图的算法

实验步骤

1．编写一段代码，接收键盘的输入，并以输入的整数对作为边来建立图形的邻接矩阵grap h_matrix。

2．根据第一步得到的邻接矩阵计算每个结点的度数()。

一个结点i的出度等于邻接矩阵第i行之和。

deg_out[i] = graph_matrix[i][0]+ graph_matrix[i][1]+ …+graph_matrix[i][n]

一个结点i的入度等于邻接矩阵第i列之和。

deg_in[i] = graph_matrix[0] [i]+ graph_matrix[1] [i]+ …+graph_matrix[n][i]

3.利用DJKSTR最短路径算法与平面图的判定算法,进行实现.

实验开设方式

个人独立完成。

编译原理实验指导书2010

《编译原理》课程实验指导书 课程编号： 课程名称：编译原理/Compiler Principles 实验总学时数： 8 适用专业：计算机科学与技术、软件工程 承担实验室：计算机学院计算机科学系中心实验室、计算机技术系中心实验室 一、实验教学的目的与要求 上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实习题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的2次上机实验都属于一种设计类型的实验，每个实验的训练重点在于基本的编译技术和方法，而不强调面面俱到；实验的目的是旨在使学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容；培养学生编制算法的能力和编程解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法设计和程序代码的编写；上机时应随带有关的编译原理教材或参考书；要学会程序调试与纠错。 每次实验后要交实验报告，实验报告的内容应包括： （1）实验题目、班级、学号、姓名、完成日期； （2）简要的需求分析与概要设计； （3）详细的算法描述； （4）源程序清单； （5）给出软件的测试方法和测试结果； （6）实验的评价、收获与体会。 开发工具： （1）DOS环境下使用Turbo C； （2）Windows环境下使用Visual C++ 。 考核： 实验成绩占编译原理课程结业成绩的10%。 三、单项实验的内容和要求： 要求每个实验保证每个学生一台微机。 实验一（4学时）：单词的词法分析程序设计。 （一）目的与要求 1．目的 通过设计、编制、调试一个具体的词法分析程序，加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。

离散数学实验报告

《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月

目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现

实验一联结词的运算 一.实验目的 通过上机实验操作,将命题连接词运算融入到C语言的程序编写中,一方面加强对命题连接词运算的理解,另一方面通过编程实现命题连接词运算,帮助学生复习与锻炼C语言知识,将理论知识与实际操作结合,让学生更加容易理解与记忆命题连接词运算。 二.实验原理 (1) 非运算, 符号:? ,当P=T时 ,?P为F, 当P=F时 ,?P为T 。 (2) 合取, 符号: ∧ , 当且仅当P与Q的真值同为真,命题P∧Q的真值才为真;否则,P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P与Q的真值同为假,命题P∨Q的真值才为假;否则,P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P与Q的真值不同时,命题P▽Q的真值才为真;否则,P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时,命题P→Q的真值才为假;否则,P→Q 的真值为真。 (6) 等价, 符号: ? , 当且仅当P,Q的真值不同时,命题P?Q的真值才为假;否 则,P→Q的真值为真。 三.实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include void main() { printf("请输入P、Q的真值\n"); int a,b; scanf("%d%d",&a,&b); int c,d; if(a==1) c=0; else c=1; if(b==1) d=0; else d=1; printf("非P、Q的结果为%d,%d\n",c,d);

(完整版)离散数学实验指导书及其答案

实验一命题逻辑公式化简 【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。 【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。 实验用例：用化简命题逻辑公式的方法设计一个 5 人表决开关电路，要求 3 人以上（含 3 人）同意则表决通过（表决开关亮）。 【实验原理和方法】 （1）写出5人表决开关电路真值表，从真值表得出5 人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。 （2）上面公式中的每一个联结词是一个开关元件，将它们定义成 C 语言中的函数。 （3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。 （4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。 参考代码： #include int vote（int a,int b,int c,int d,int e） { // 五人中任取三人的不同的取法有10种。 i f（ a&&b&&c || a&&b&&d || a&&b&&e || a&&c&&d || a&&c&&e || a&&d&&e || b&&c&&d || b&&c&&e || b&&d&&e || c&&d&&e） return 1; else return 0; } void main（） { i nt a,b,c,d,e; printf（" 请输入第五个人的表决值（0 或1，空格分开）："）; scanf （"%d%d%d%d%d",&a,&b,&c,&d,&e）; i f（vote（a,b,c,d,e）） printf（" 很好，表决通过！\n"）; else printf（" 遗憾，表决没有通过！\n"）; } // 注：联结词不定义成函数，否则太繁 实验二命题逻辑推理 【实验目的】加深对命题逻辑推理方法的理解。【实验内容】用命题逻辑推理的方法解决逻辑

离散数学实验报告

离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间

目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。

7离散数学(集合的运算)实验报告

大连民族学院 计算机科学与工程学院实验报告 实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络111班 学生姓名：张山学号：2011083123 实验日期：2013年12月22日实验地点：I区实验机房 实验学时：8小时实验成绩： 指导教师签字：年月日老师评语：

实验题目：集合的运算 实验原理： 1、实验内容与要求： 实验内容：本实验求两个集合间的运算，给定两个集合A、B，求集合A与集合B之间的交集、并集、差集、对称差集和笛卡尔乘积。 实验要求：对于给定的集合A、B。用C++/C语言设计一个程序（本实验采用C++），该程序能够完成两个集合间的各种运算，可根据需要选择输出某种运算结果，也可一次输出所有运算结果。 2、实验算法： 实验算法分为如下几步： （1）、设计整体框架 该程序采取操作、打印分离（求解和输出分开）的思想。即先设计函数求解各部分运算并将相应结果传入数组（所求集合）中，然后根据需要打印运算结果。 （2）、建立一个集合类（Gather） 类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口（实现操作的函数）包括构造函数，菜单显示函数，求解操作函数，打印各种运算结果等函数。 （3）、设计类体中的接口 构造函数：对对象进行初始化，建立集合A与集合B。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下：

1*求交集：根据集合中交集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着把b中元素依次存入数组g（并集集合）中，存储前将b中每个元素依次与已存入数组g中的集合A的元素比较，若数组g中没有与该元素相同的元素，则将该元素存入g（并集集合）中，否则进行下一次比较，直到所有b中元素比较并存储完毕，即求得A与B 的并集。 3*求差集：根据集合中差集的定义知，差集分为两部分，A对B的差集（数组d）和B对A的差集（e）。设计求解A对B的差集，将集合A中元素依次与B中元素比较，若B中无元素与该元素相同，则将其存入数组d中（同时删除d中相同的元素，操作方法与求并集时删除相同元素类似），否则进行下一轮比较，直到A中所有元素比较完毕，即求得A对B的差集（数组d）。求解B对A的差集方法与求解A对B 的差集类似，这里不再重复。 4*求对称差：根据集合中对称差集的定义，将3*中所求两部分差集求并集并存入数组f中即可。操作过程与求并集相似，这里不再重复。 5*求笛卡尔乘积：根据集合中笛卡尔乘积集的定义，分为A*B和B*A。先设计A*B是我算法，将a中元素循环依次与b中元素配对即可。求B*A与求A*B类似，这里不再重复。 实验步骤： 一、分析实验 阅读实验指导书和离散数学课本，充分理解整个实验的实验内容及要求，以便对实验进行科学的设计。然后对整个实验进行“解剖”，即把整个实验系统地分成若干

离散数学(屈婉玲版)第一章部分习题分解

第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数.

是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若 2+2=4,则 3+3=6. (2)若 2+2=4,则 3+3≠6. (3)若 2+2≠4,则 3+3=6. (4)若 2+2≠4,则 3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。

离散数学实验报告--四个实验!!!

《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日

引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以 根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的?(?x)((x∈A)→(∈R))=1 对称关系：对任意的x,y∈A，如果∈R，那么∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的? (?x)(?y)((x∈A)∧(y∈A)∧(∈R)→(∈R))=1 传递关系：对任意的x,y,z∈A，如果∈R且∈R，那么∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的? (?x)(?y)(?z)[(x∈A)∧(y∈A)∧(z∈A)∧((∈R)∧(∈R)→(∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数 组的运算来实现二元关系的判断。 图示：

数据库原理与应用实验指导总结

1实验前的准备 1.1 课程实验标准 《数据库原理与应用》是计算机科学与技术专业及相近各专业的一门重要基础理论课程。课程概括性的介绍了数据库技术发展历程，详细介绍了数据库系统的基本概念、基本原理、基本方法，阐述了数据库设计、实现的基本过程，同时也介绍了数据库系统的最新进展。通过本课程的学习，使学生牢固掌握数据库系统的基本概念和基本原理，熟悉数据库系统的主要实现方法，能够根据应用需要分析设计实用的数据库管理系统。 《数据库原理与应用》是一门实践性很强的课程，通过实验实践，配合课堂教学内容加深对数据库系统的基本概念、基本原理、基本方法的理解，掌握数据库系统设计的基本思想和基本步骤，熟悉关系数据库的标准语言SQL，并对关系数据库系统的某一典型系统（如SQL Server 2000）有较深入的了解，使学生对数据库系统有一个完整的、全面的认识。 1.课程实验的目标 《数据库原理与应用》课程上机实验的主要目标是： (1)通过上机操作，加深对数据库系统理论知识的理解。 (2)通过使用具体的数据库管理系统，了解一种实际的数据库管理系统，并掌握 其操作技术。 (3)通过实验题目的上机实践，提高学生的实践动手能力，提高学生的分析问题 和解决问题的能力。 2.主要软件实验环境 操作系统为Microsoft Windows 2000或更高级的版本。 数据库管理系统为Microsoft SQL Server 2000标准版或更高级的版本。 3.课程实验的基本要求 (1)每次实验前，教师需要向学生讲清楚本次实验的目的和基本要求；学生应当先弄清楚相关的理论知识，预习实验内容、方法和步骤，认真准备好实验程序和数据，避免出现盲目上机的行为。 (2)实验1人1组，在规定的时间内，由学生独立完成，出现问题时，教师要做好指导，但不能包办代替。 (3)任课教师要在实验课前清点学生人数，实验中按要求做好学生实验情况及结果记录，实验后认真填写实验记录、批改实验报告。 (4)学生最好自备计算机，课下能多做练习，以便能够熟悉和精通实验内容。 4. 实验项目设置及考核 本课程设置了八个实验项目，共计20学时。具体情况如下： 实验1 数据库和数据表基本操作 4学时

《离散数学》试习题及答案

欢迎共阅 一、填空题 1设集合A,B ，其中A ＝{1,2,3},B={1,2},则A-B ＝____________________; ?(A)-?(B)＝__________________________. 2.设有限集合A,|A|=n,则|?(A×A)|=__________________________. 3.设集合A={a ,b },B={1,2},则从A 到B 的所有映射是_______________________________________,其中双射的是__________________________. 4.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题

离散数学实验报告()

《离散数学》实验报告 专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月

目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现

实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当P=T时，P为F, 当P=F时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include void main() { printf("请输入P、Q的真值\n"); int a,b; scanf("%d%d",&a,&b); int c,d; if(a==1) c=0; else c=1; if(b==1) d=0;

SQL实验指导大纲

广东水利电力职业技术学院 《关系数据库与SQL》 实验指导书 2004.6修订 计算机信息工程系

目录 实验大纲 (1) 实验一：SQL SERVER 2000安装、配置与操作 (2) 实验二：数据库和数据表的创建 (3) 实验三：数据库表结构修改和表操作 (6) 实验四：数据表的查询 (7) 实验五：链接查询和子查询 (8) 实验六：创建和使用视图 (11) 实验七:T-SQL程序设计 (12) 实验八：数据完整性技术 (15) 实验九：存储过程 (16) 实验十：触发器 (20) 实验十一：ADO连接技术 (22)

高等职业技术教育计算机应用技术专业《关系数据库与SQL》实验大纲 一、实验项目 1、SQL Server2000的安装和服务器的配置与注册 2、创建数据库和表格。 3、数据库表数据操作 4、数据基本检索 5、连接和子查询 6、建立和使用视图 7、流程控制程序设计 8、数据索引、数据完整性约束 9、存储过程 10、触发器 11、使用ADO技术访问数据库 二、实验的能力要求 1、掌握SQL Server2000软件的安装、配置。 2、掌握数据库和表格的创建和修改 3、掌握数据表记录的插入、修改和删除操作。 4、掌握数据的检索、汇总和排序。 5、掌握多表信息的联合检索 6、掌握建立和使用视图 7、掌握用T-SQL进行流程控制程序设计 8、掌握数据索引、数据完整性约束的作用和建立 9、掌握存储过程的编写和执行 10、掌握触发器的创建 11、掌握开发平台通过ADO技术连接访问数据库

实验一：SQL SERVER 2000安装、配置与操作 一、实验目的： 熟悉SQL SERVER 2000操作环境，掌握SQL Server2000软件的安装、配置。 二、实验内容： 1、用一台机去管理SQL SERVER服务器，都必须先做什么设置？ 2、企业管理器能完成什么功能？ 3、描述查询分析询器能完成的功能 4、描述对象浏览器的作用。如何显示/隐藏？ 5、服务管理器是用来_______、_______和______SQL Server 服务的。这些服务 在Windows NT/2000下也可以通过控制面板的服务项来启动或停止。 6、在“开始”菜单的Microsoft SQL Server程序中选择Enterprise Manager即可 启动______管理器。 7、在查询窗口中用户可以输入SQL语句，并按_______键，或单击工具栏上的 运行按钮，将其送到服务器执行，执行的结果将显示在输出窗口中。用户可 以打开一个含有SQL语句的文件来执行，执行的结果同样显示在输出窗口中。 8、分别用界面和T-SQL语句（SELECT * FROM 表名）显示pubs的一个表信息， 并保存显示结果（文件名为“实验一显示结果”）和T-SQL脚本（文件名“实 验一语句”）。 9、试用界面建一个“学生管理”数据库，在其内建一个“学生表”（属性自已定 义），输入几个信息，浏览一下你所录入的信息。 三、实验要求： 1、先操作再回答下面的内容，提交的答案内容用蓝色字体 2、文件以文件名：”xx专业xx班xx号xxxx（姓名）”保存，如：”03网络1班 2号李红”

离散数学题目大汇总

离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若是群，H 是G 的非空子集，则是的子群对任意的a 、b ∈H 有 a * b －1∈H 。 八、（15分）(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗 离散数学试题一（B 卷答案） 一、（15分）设计一盏电灯的开关电路，要求受3个开关A 、B 、C 的控制：当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。 u v w

《程序设计课程设计》指导书2017(1)

程序设计课程设计 指导书 软件学院软件工程系 2017 年 6 月 1 日

太原理工大学课程设计任务书 学生姓名专业班级软件 课程名称程序设计课程设计（Programming Curriculum Design） 设计名称相邻数对,ISBN 识别码,文本文件单词统计等设计周数 2 设计 1.基本要求 掌握C或C++语言、结构化程序和面向对象程序设计方法、数据结构和离任务散数学理论知识，熟悉C或C++程序的开发环境及调试过程，巩固和加深对理论课中知识的理解，提高学生对所学知识的综合运用能力。 主要 2.培养学生以下技能 ①培养学生查阅参考资料、手册的自学能力，通过独立思考深入钻研问题， 设计学会自己分析、解决问题。 ②通过对所选题目分析，找出解决方法，设计算法，编制程序与调试程序。 参数③能熟练调试程序，在教师的指导下，完成课题任务。 ④按课程设计报告的要求撰写设计报告。 1.设计内容 ①相邻数对；②ISBN 识别码；③文本文件单词统计；④构造可以使 n 个城 设计内容市连接的最小生成树；⑤送货；⑥学生信息管理系统 2.设计要求 设计要求 ①至少完成上述设计内容中的 4 个设计题目；②对每个题目要给出设计方 案、功能模块划分、算法思想；③选择使用的数据结构；④给出题目的程序实 现；⑤按要求撰写设计报告。 主要参考 1.《程序设计课程设计》指导书； 2.《程序设计技术》、《数据结构》等课程教材； 资料 3. 其他自选的相关资料。 学生提交课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期。 每个设计题目的内容包括以下几项：设计题目、问题描述、问题分析、功能实归档文件现、测试实例及运行结果、源程序清单。 注： 1.课程设计完成后，学生提交的归档文件应按照：封面—任务书—说明书—图纸的顺序进行装订上交（大张图纸不必装订）。 2.可根据实际内容需要续表，但应保持原格式不变。 指导教师签名：日期：2017.6.3

离散数学考试题详细答案

离散数学考试题(后附详细答案) 一、命题符号化(共6小题,每小题3分,共计18分) 1.用命题逻辑把下列命题符号化 a)假如上午不下雨,我去瞧电影,否则就在家里读书或瞧报。 设P表示命题“上午下雨”,Q表示命题“我去瞧电影”,R表示命题“在家里读书”,S表示命题“在家瞧报”,命题符号化为:(?P?Q)∧(P?R∨S) b)我今天进城,除非下雨。 设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:?Q→P或?P→Q c)仅当您走,我将留下。 设P表示命题“您走”,Q表示命题“我留下”,命题符号化为: Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不就是有理数 设R(x)表示“x就是实数”,Q(x)表示“x就是有理数”,命题符号化为: ?x(R(x) ∧?Q(x)) 或??x(R(x) →Q(x)) b)对于所有非零实数x,总存在y使得xy=1。 设R(x)表示“x就是实数”,E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为: ?x(R(x) ∧?E(x,0) →?y(R(y) ∧E(f(x,y),1)))) c) f 就是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b、 设F(f)表示“f就是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为:F(f)??a(A(a)→?b(B(b) ∧ E(f(a),b) ∧?c(S(c) ∧ E(f(a),c) →E(a,b)))) 二、简答题(共6道题,共32分) 1.求命题公式(P→(Q→R))?(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋 值。(5分) (P→(Q→R))?(R→(Q→P))?(?P∨?Q∨R)?(P∨?Q∨?R) ?((?P∨?Q∨R)→(P∨?Q∨?R)) ∧ ((P∨?Q∨?R) →(?P∨?Q∨R))、 ?((P∧Q∧?R)∨ (P∨?Q∨?R)) ∧ ((?P∧Q∧R) ∨(?P∨?Q∨R)) ?(P∨?Q∨?R) ∧(?P∨?Q∨R) 这就是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 (?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) 2.设个体域为{1,2,3},求下列命题的真值(4分) a)?x?y(x+y=4) b)?y?x (x+y=4) a) T b) F 3.求?x(F(x)→G(x))→(?xF(x)→?xG(x))的前束范式。(4分) ?x(F(x)→G(x))→(?xF(x)→?xG(x)) ??x(F(x)→G(x))→(?yF(y)→?zG(z))??x(F(x)→G(x))→?y?z(F(y)→G(z)) ??x?y?z((F(x)→G(x))→ (F(y)→G(z))) 4.判断下面命题的真假,并说明原因。(每小题2分,共4分) a)(A?B)－C=(A-B) ?(A-C) b)若f就是从集合A到集合B的入射函数,则|A|≤|B| a) 真命题。因为(A?B)－C=(A?B)?~C=(A?~C)?(B?~C)=(A-C)?(B-C) b) 真命题。因为如果f就是从集合A到集合B的入射函数,则|ranf|=|A|,且ranf?B,故命题 成立。

离散数学实验报告

离散数学实验报告 姓名： 学号： 班级： 实验地点： 实验时间：

1 实验目的和要求 运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下： 八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km 。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？ 2 实验环境和工具 实验环境：Windows 7 旗舰版 工具：Dev-C++ 5.8.3 3 实验过程 3.1 算法流程图

3.2程序核心代码 //油管铺设问题Prim算法实现 #include #include using namespace std; #define MAXV 10 #define INF 32767 //INF表示∞ typedef int InfoType; typedef struct{ int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct{ //图的定义 float edges[MAXV][MAXV]; //邻接矩阵 int vexnum; //顶点数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型

/*输出邻接矩阵g*/ void DispMat(MGraph g){ int i,j; for (i=0;i

实践指导书_多表查询与子查询

一、实验题目：多表查询与子查询 二、实验目的： 掌握如何进行多表查询与子查询 三、实验步骤： 附加XSCJ数据库，改名为XSCJ学号姓名，完成以下习题后把习题语句保存为学号姓名.sql 文件并上传至教师机指定共享文件夹 连接习题： --1、查找XSCJ数据库每个学生的情况以及选修的课程情况。 --2、查询xscj数据库中学号，姓名，课程号，成绩 --3、查询xscj数据库中学号，姓名，课程名，成绩 --4、查询xscj数据库中选修了计算机基础课程同学的学号，姓名，成绩 --5、查询xscj数据库中程明选修的课程名，成绩 --6、查询班级表中学制相同的班级编号 一、连接 1．什么是连接 连接是两元运算，可以两个或多个表进行查询，其结果通常是含有参加连接运算的两个表（或多个表）的指定列的表。 在实际应用中，多数情况下，用户查询的列都来自于多个表。 涉及多个表的查询被称为连接查询。 2．连接表现形式 在T-sql语言中连接查询有两大类表示形式 1）符合sql标准连接谓词表示形式。 2）T-sql扩展的使用关键字join的表示形式。 3．连接分类 内连接表名1 join 表名2 on 条件 外连接左连接left join ，右连接right join，全连接full join 自连接 谓词连接：where 条件（两个表中的字段条件） 4．建立连接的步骤 1）要连接哪几个表 2）以什么条件连接——关系：主键、外键，等值 3）查询记录的条件 4）要查询什么信息 如：查询studentscore数据库中学生信息表和学生成绩表的全部信息 附加studentscore数据库 Select From Where

离散数学实验报告格式

《离散数学》实验报告 专业 班级 姓名 学号 授课教师 二 O 一六年十二月

目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系实验三利用算法求关系的传递闭包实验四图的可达矩阵实现

实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当时，P为F, 当时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: → , 当且仅当P为为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当的真值不同时，命题P?Q的真值才为假；否则，P→Q 的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 <> () { ; ("请选择运算方式\n"); ("1.析取\n"); ("2.合取\n"); ("3.非\n"); ("4.蕴含\n"); ("5.等价\n");

m; (""); ( m>=1 m<=4 ) { ("请输入P Q的值\n"); (" " ); = 1; (m) { 1( ( >= 1)( < 4 ) ) { (0 0) ("P 析取Q = 0\n"); ("P 析取Q = 1\n"); ; (4) ; ("请输入P Q的值\n"); (" " ); } ; 2( ( >= 0)( < 4 ) ) { (1 1) ("P 合取Q = 1\n"); ("P 合取Q = 0\n"); ; (4) ; ("请输入P Q的值\n"); (" " ); } ; 3( ( >= 0)( < 4 ) ) { (0) ("非Q = 1\n"); ("非Q = 0\n");

离散数学关系性质的C++或C语言判断实验报告

1.【实验目的】 对称： 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法 自反： 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 2.【实验内容】 已知关系R 由关系矩阵M 给出，要求判断由M 表示的这个关系是否为对称关 系。假定R 的关系矩阵为：?????? ? ??=1234210330124321M 3.【实验要求】 C 语言编程实现 4.【算法描述】 对称： 从给定的关系矩阵来判断关系R 是否为对称是很容易的。若M （R 的关系矩阵）为对称矩阵，则R 是对称关系；若M 为反对称矩阵，则R 是反对称关系。因为R 为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 算法实现： （1） 输入关系矩阵M （M 为n 阶方阵）； （2） 判断对称性，对于i=2，3，….，n ；j=1，2,……，i-1，若存在m ij =m ji ， 则R 是对称的； （3） 判断反对称性； （4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。

自反： 从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。 算法实现 （1）输入关系矩阵M（M为n阶方阵）。 （2）判断自反性，对于i=1，2，….，n；若存在m =0，则R不是自反 ii =1，则R是自反的；否则R既不是自反关系也不是的；若存在m ii 反自反关系。 （3）输出判断结果。 源代码 #include void z(); void r(); void main() { int d; while(d) { printf("欢迎使用关系性质的判断系统\n\n 1. 对称关系的判断 2. 自反关系的判断\n\n请输入选项："); scanf("%d",&d); switch(d){ case 1: r();break; case 2: z();break; case 0: break; }

离散数学题库及答案

数理逻辑部分 选择、填空及判断 ?下列语句不是命题的（ A ）。 (A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物。 (C) 离散数学是计算机系的一门必修课。 (D) 雪是黑色的。 ?命题公式P→(P∨?P)的类型是（ A ） (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A是重言式，那么A的否定式是( A ) A. 矛盾式 B. 重言式 C. 可满足式 D.不能确定 ?以下命题公式中，为永假式的是( C ) A. p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值是( D ) A. 00,11 B. 00,01,11 C.10,11 D. 10 ?谓词公式) x xP∧ ?中，变元x是 ( B ) R , ( x ) (y A. 自由变元 B. 既是自由变元也是约束变元 C. 约束变元 D. 既不是自由变元也不是约束变元 ?命题公式P→(Q∨?Q)的类型是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x，) x x→ ?等值于( A ) A ) ( (B A. B ( D. B x xA→ x ?) ( ( ? C. B x∧ A ?) ( B. ) ?) xA→ x ) ( A x (B x∨ ?下列语句中是真命题的是( D )。 A．你是杰克吗？ B．凡石头都可练成金。 C．如果2+2=4，那么雪是黑的。 D．如果1+2=4，那么雪是黑的。 ?从集合分类的角度看，命题公式可分为( B ) A. 永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A. ﹁p∨q B. ﹁(p∨q) C. ﹁p∧q D. p→﹁q ?一个公式在等价意义下，下面写法唯一的是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p，q，r的公式中，是主析取范式的是( D )。