西安电子科技大学离散数学大作业

离散数学大作业

离散数学大作业

班级：021231

学号：02123120

姓名：

题目：编程实现赋权有向图的最小生成树

摘要

求解图的最小生成树有三种算法，分别为Prim算法、Kruskal算法和Boruvka算法。这三种算法都是贪心算法。

所以本次实验分别使用Kruskal算法和Prim算法实现赋权有向图的最小生成树。

Kruskal算法基本思想为：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。

Prim算法基本思想是：首先选取图中任意一个顶点 v 作为生成树的根，之后继续往生成树中添加顶点 w，则在顶点 w 和顶点 v 之间必须有边，且该边上的权值应在所有和 v 相邻接的边中属最小。

关键词：邻接矩阵；邻接表；Kruskal算法；Prim 算法；最小生成树

一、最小生成树的研究进展

最小生成树可以使用Kruskal算法和Prim算法。下面具体介绍这两种算法。Kruskal算法

求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n条边）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

该算法的时间复杂度为O(elge);Kruskal算法的时间主要取决于边数,它较适合于稀疏图。

Kruskal算法构造最小生成树的过程图解:

Prim算法

Prim算法可以说是所有MST算法中最简单的，比较适用于稠密图。以图中任意一个顶点S 开始，选择与之相关连的边中权值最小的边加入到MST中，假设这条边的终点为T，则MST 初始化为(S, T)，称之为“当前MST”。接下来在剩余的边中选择与当前MST中s所有顶点相关连的边中权值最小的边，并添加到当前MST中。这一过程一直迭代到图中所有顶点都添加到MST中为止。

从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U 是T的顶点集，TE是T的边集。prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。

二、最小生成树的实现

Kruskal算法关键部分的实现

Kruskal算法的计算流程大致如下：

1.将无向图的边按距离长短递增式排序，放到集合中

2.遍历该集合，找出最短的边，加入到结果生成树的集合中

3.如果结果生成树出现回路，则放弃这条边

4.重新执行步骤2，直至所有顶点被遍历

可以看出在每次遍历过程中采用了贪心算法

Kruskal算法代码如下：

//**********************最小生成树kruscal算法*******************

int acrvisited[100];//kruscal弧标记数组

int find(int acrvisited[],int f)

{

while(acrvisited[f]>0)

f=acrvisited[f];

return f;

}

void kruscal_arc(MGraph_L G,algraph gra)

{

edg edgs[20];

int i,j,k=0;

for(i=0;i!=G.vexnum;++i)

for(j=i;j!=G.vexnum;++j)

{

if(G.arcs[i][j].adj!=10000)

{

edgs[k].pre=i;

edgs[k].bak=j;

edgs[k].weight=G.arcs[i][j].adj;

++k;

}

}

int x,y,m,n;

int buf,edf;

for(i=0;i!=gra.arcnum;++i)

acrvisited[i]=0;

for(j=0;j!=G.arcnum;++j)

{

m=10000;

for(i=0;i!=G.arcnum;++i)

{

if(edgs[i].weight

{

m=edgs[i].weight;

x=edgs[i].pre;

y=edgs[i].bak;

n=i;

}

}

buf=find(acrvisited,x);

edf=find(acrvisited,y);

edgs[n].weight=10000;

if(buf!=edf)

{

acrvisited[buf]=edf;

cout<<"("<

cout<

}

}

}

//**************************************************************

Prim算法关键部分的实现

Prim算法的计算流程大致如：

（1）初始状态，TE为空，U={v0}，v0∈V；

（2）在所有u∈U，v∈V-U的边(u，v) ∈E中找一条代价最小的边(u′，v′)并入TE，同时将v′并入U；

重复执行步骤（2）n-1次，直到U=V为止。

Prim算法代码如下：

//**********************最小生成树PRIM算法******************* typedef struct

{

int adjvex;

int lowcost;

}closedge;

int prim(int g[][max],int n)//最小生成树PRIM算法

{

int lowcost[max],prevex[max];//LOWCOST[]存储当前集合U分别到剩余结点的最短路径

//prevex[]存储最短路径在U中的结点

int i,j,k,min;

for(i=2;i<=n;i++)//n个顶点，n-1条边

{

lowcost[i]=g[1][i];//初始化

prevex[i]=1;//顶点未加入到最小生成树中

}

lowcost[1]=0;//标志顶点1加入U集合

for(i=2;i<=n;i++)//形成n-1条边的生成树

{

min=inf;

k=0;

for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]

{

min=lowcost[j];

k=j;

}

printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);

lowcost[k]=0;//顶点k加入U

for(j=2;j<=n;j++)//修改由顶点k到其他顶点边的权值

if(g[k][j]

{

lowcost[j]=g[k][j];

prevex[j]=k;

}

printf("\n");

}

return0;

}

//************************************************************** 三、代码

#include

#include

#include

using namespace std;

#define int_max 10000

#define inf 9999

#define max 20

//**********************邻接矩阵定义************************* typedef struct ArcCell

{

int adj;

char*info;

}ArcCell,AdjMatrix[max][max];

typedef struct

{

char vexs[max];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph_L;

//***********************************************************

int localvex(MGraph_L G,char v)//返回V的位置

{

int i=0;

while(G.vexs[i]!=v)

++i;

return i;

}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示

{

char v1,v2;

int i,j,w;

cout<<"请输入图的顶点和弧的个数:例如4 6 (4表示顶点的个数，5表示弧的个数)"<

cin>>G.vexnum>>G.arcnum;

for(i=0;i!=G.vexnum;++i)

{

cout<<"输入顶点"<

cin>>G.vexs[i];

}

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

for(int k=0;k!=G.arcnum;++k)

{

cout<<"输入一条边依附的顶点和权:例如a b c (a,b表示顶点，c表示权)"<

cin>>v1>>v2>>w;//输入一条边依附的两点及权值

i=localvex(G,v1);//确定顶点V1和V2在图中的位置

j=localvex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

}

cout<<"图G邻接矩阵创建成功！"<

return G.vexnum;

}

int visited[max];//访问标记

int we;

typedef struct arcnode//弧结点

{

int adjvex;//该弧指向的顶点的位置

struct arcnode *nextarc;//弧尾相同的下一条弧

char*info;//该弧信息

}arcnode;

typedef struct vnode//邻接链表顶点头接点

{

char data;//结点信息

arcnode *firstarc;//指向第一条依附该结点的弧的指针

}vnode,adjlist;

typedef struct//图的定义

{

adjlist vertices[max];

int vexnum,arcnum;

int kind;

}algraph;

typedef struct acr

{

int pre;//弧的一结点

int bak;//弧另一结点

int weight;//弧的权

}edg;

int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图{

int i=0,j=0;

arcnode *arc,*tem,*p;

for(i=0;i!=G.vexnum;++i)

{

gra.vertices[i].data=G.vexs[i];

gra.vertices[i].firstarc=NULL;

}

for(i=0;i!=G.vexnum;++i)

{

for(j=0;j!=G.vexnum;++j)

{

if(gra.vertices[i].firstarc==NULL)

{

if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

arc=(arcnode *)malloc(sizeof(arcnode));

arc->adjvex=j;

gra.vertices[i].firstarc=arc;

arc->nextarc=NULL;

p=arc;

++j;

while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

tem=(arcnode *)malloc(sizeof(arcnode));

tem->adjvex=j;

gra.vertices[i].firstarc=tem;

tem->nextarc=arc;

arc=tem;

++j;

}

--j;

}

}

else

{

if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

arc=(arcnode *)malloc(sizeof(arcnode));

arc->adjvex=j;

p->nextarc=arc;

arc->nextarc=NULL;

p=arc;

}

}

}

}

gra.vexnum=G.vexnum;

gra.arcnum=G.arcnum;

return1;

}

int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点

//即以V为尾的第一个结点

{

if(v.firstarc!=NULL)

return v.firstarc->adjvex;

}

int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点

{

arcnode *p;

p=v.firstarc;

while(p!=NULL&&p->adjvex!=w)

{

p=p->nextarc;

}

if(p->adjvex==w&&p->nextarc!=NULL)

{

p=p->nextarc;

return p->adjvex;

}

if(p->adjvex==w&&p->nextarc==NULL)

return-10;

}

//**********************最小生成树PRIM算法******************* typedef struct

{

int adjvex;

int lowcost;

}closedge;

int prim(int g[][max],int n)//最小生成树PRIM算法

{

int lowcost[max],prevex[max];//LOWCOST[]存储当前集合U分别到剩余结点的最短路径

//prevex[]存储最短路径在U中的结点

int i,j,k,min;

for(i=2;i<=n;i++)//n个顶点，n-1条边

{

lowcost[i]=g[1][i];//初始化

prevex[i]=1;//顶点未加入到最小生成树中

}

lowcost[1]=0;//标志顶点1加入U集合

for(i=2;i<=n;i++)//形成n-1条边的生成树

{

min=inf;

k=0;

for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]

{

min=lowcost[j];

k=j;

}

printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);

lowcost[k]=0;//顶点k加入U

for(j=2;j<=n;j++)//修改由顶点k到其他顶点边的权值

if(g[k][j]

{

lowcost[j]=g[k][j];

prevex[j]=k;

}

printf("\n");

}

return0;

}

//**************************************************************

//**********************最小生成树kruscal算法*******************

int acrvisited[100];//kruscal弧标记数组

int find(int acrvisited[],int f)

{

while(acrvisited[f]>0)

f=acrvisited[f];

return f;

void kruscal_arc(MGraph_L G,algraph gra) {

edg edgs[20];

int i,j,k=0;

for(i=0;i!=G.vexnum;++i)

for(j=i;j!=G.vexnum;++j)

{

if(G.arcs[i][j].adj!=10000)

{

edgs[k].pre=i;

edgs[k].bak=j;

edgs[k].weight=G.arcs[i][j].adj;

++k;

}

}

int x,y,m,n;

int buf,edf;

for(i=0;i!=gra.arcnum;++i)

acrvisited[i]=0;

for(j=0;j!=G.arcnum;++j)

{

m=10000;

for(i=0;i!=G.arcnum;++i)

{

if(edgs[i].weight

{

m=edgs[i].weight;

x=edgs[i].pre;

y=edgs[i].bak;

n=i;

}

}

buf=find(acrvisited,x);

edf=find(acrvisited,y);

edgs[n].weight=10000;

if(buf!=edf)

{

acrvisited[buf]=edf;

cout<<"("<

cout<

}

}

//**************************************************************

//*********************主函数*********************************** int main()

{

algraph gra;

MGraph_L G;

int i,d,g[20][20];

char a='a';

d=creatMGraph_L(G);

creatadj(gra,G);

vnode v;

cout<<"*************菜单*************"<

cout<<"0、最小生成树PRIM算法"<

cout<<"1、最小生成树KRUSCAL算法"<

int s;

char y='y';

while(y='y')

{

cout<<"请选择菜单："<

cin>>s;

switch(s)

{

case0:

for(i=0;i!=G.vexnum;++i)

for(int j=0;j!=G.vexnum;++j)

g[i+1][j+1]=G.arcs[i][j].adj;

cout<<"prim:"<

prim(g,d);

break;

case1:

cout<<"kruscal:"<

kruscal_arc(G,gra);

break;

}

cout<

cin>>y;

if(y=='n')

break;

}

system("pause");

return0;

//**************************************************************四、输出结果

Kruskal算法结果

Prim算法

(完整版)离散数学作业答案一

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式

西安电子科技大学 数字电路基础 答案

习题4 4－3 解：该电路的输入为3x 2x 1x 0x ，输出为3Y 2Y 1Y 0Y 。真值表如下： 由此可得：1M =当时，33 2 321210 10 Y x Y x x Y x x Y x x =??=⊕?? =⊕??=⊕? 完成二进制至格雷码的转换。 0M =当时，33 2 32 132121 321010 Y x Y x x Y x x x Y x Y x x x x Y x =??=⊕?? =⊕⊕=⊕??=⊕⊕⊕=⊕? 完成格雷码至二进制的转换。

4－9 设计一个全加（减）器，其输入为A,B,C 和X(当X ＝0时，实现加法运算；当X ＝1时，实现减法运算)，输出为S(表示和或差)，P （表示进位或借位）。列出真值表，试用3个异或门和3个与非门实现该电路，画出逻辑电路图。 解：根据全加器和全减器的原理，我们可以作出如下的真值表： 由真值表可以画出卡诺图，由卡诺图得出逻辑表达式，并画出逻辑电路图： A B C X P 4－10 设计一个交通灯故障检测电路，要求红，黄，绿三个灯仅有一个灯亮时，输出F ＝0；

若无灯亮或有两个以上的灯亮，则均为故障，输出F ＝1。试用最少的非门和与非门实现该电路。要求列出真值表，化简逻辑函数，并指出所有74系列器件的型号。 解：根据题意，我们可以列出真值表如下： 对上述的真值表可以作出卡诺图，由卡诺图我们可以得出以下的逻辑函数： F AB AC BC A B C AB AC BC A B C =+++=??? 逻辑电路图如下所示： A F 4－13 试用一片3－8译码器和少量逻辑门设计下列多地址输入的译码电路。 （1） 有8根地址输入线7A ~1A ,要求当地址码为A8H,A9H ,…,AFH 时，译码器输出为 0Y ~7Y 分别被译中，且地电平有效。 （2） 有10根地址输入线9A ～0A ，要求当地址码为2E0H,2E1H, …,2E7H 时，译码器输 出0Y ~7Y 分别被译中，且地电平有效。

离散数学作业答案

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，

离散数学(大作业)与答案

一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}

{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)

电大 离散数学作业7答案

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨Q ）→R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) ． 4．设P (x )：x 是人，Q (x )：x 去上课，则命题“有人去上课．” 可符号化为 ?x(P(x) ∧Q(x)) ． 5．设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名：

吉林大学离散数学课后习题答案

第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每

一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故

G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G

吉林大学2019-2020学年第一学期期末考试《离散数学》大作业参考答案

吉林大学网络教育学院2019-2020学年第一学期期末考试《离散数学》大作业 学生姓名专业 层次年级学号 学习中心成绩 年月日

作业完成要求：大作业要求学生手写，提供手写文档的清晰扫描图片，并将图片添加到word 文档内，最终wod文档上传平台，不允许学生提交其他格式文件（如JPG，RAR等非word 文档格式），如有雷同、抄袭成绩按不及格处理。 一、简答题（每小题7分，共56分） 1、什么是命题公式的演绎？ 答：首先定义了消解复杂性的两种范式:最简范式和文字范式,在此基础上采用演绎方法证明了L中的可判定性定理,并设计了命题公式的演绎判定算法P(F).P(F)的时间复杂度为O(n3),远远小于基于真值表法的O(2n)和基于策略方案HAL的O(n5)。 2、什么是子句？请给出一例。 答：子句是一组包含一个主词和一个动词的关连字。子句与片语有明显的不同，后者为一组不含主词与动词关系的关连字，如"in the morning" 或"running down the street" 或"having grown used to this harassment." 3、什么是短语？请给出一例。 答：短语是由句法、语义和语用三个层面上能够搭配的语言单位组合起来的没有句调的语言单位，又叫词组。它是大于词而又不成句的语法单位。简单的短语可以充当复杂短语的句法成分，短语加上句调可以成为句子。由语法上能够搭配的词组合起来的没有句调的语言单位 例如：粮食//丰收（名//动）（什么//怎么样） 4、什么是命题逻辑中的文字？ 答：检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类。 5、什么是析取范式？请给出一例。 答：在离散数学中，仅由有限个文字构成的合取式称为简单合取式，而由有限个简单合取式构成的析取式称为析取范式。范式存在定理说明了它的存在性：任一命题公式都存在着与之等值的析取范式与合取范式。但它并不是惟一的。主析取范式是惟一的。

西安电子科技大学《电路基础》第三章部分习题解

习题三 3.3如题图3.3所示，求电压u，如果独立电压源的均值增至原值的2倍，独立电流源的值降为原值的一半，电压u变为多少？ Ω3 1 i A Ω 2 V1 图3.3 解：仅考虑电压源（电流源开路） Ω3 1 i Ω 2 V1 对节点a列写节点方程 （1/3+1/6） a u=1/3+10/6 所以 a u＝4V 3 1 i＋1＝4 则1i＝1A 1 u＋4?2＋（－1）＋3?（－1）＝0 则1u＝－4V 仅考虑电流源（电压源短路） Ω3 1 i Ω 2

1i ＝3?2/3＝2A i ＝4－21i ＝1A 2u ＋4?1－3?2－2?3＝0 故 2u ＝8V 所以 u ＝1u ＋2u ＝4V 当电压源增至2倍时，电流源降为原来的一半时，V u u 8211-==' V u u 421 22==' ='∴u V u u 421-=' +' 3.4如题图3.4所示电路，N 为不含独立源的线性电路，已知当s u ＝12V ，s i ＝4A 时，u ＝0V ；当s u ＝－12V ，s i ＝－2A 时，u ＝－1V ；求当s u ＝9V ，s i ＝－1A 时的电压u 。 s u 图3.4 解：u ＝1k s u ＋2k s i 根据题意列方程有： 121k ＋42k ＝0 －121k －22k ＝－1 解之有： 1k =1/6 2k ＝－1/2 即 u ＝1/6s u －1/2s i 故当s u ＝9V ，s i ＝－1A 时，u ＝2V 3.5当开关s 位置在1时，I ＝40mA,s 在位置2时，I ＝－60mA ，求s 在位置3时，I ＝？

V 图3.5 解：当开关s 位置在2时，电路图可以看成下图的叠加 V 4 所以，I '=I =40mA I ''=k 1s u I =I '+I ''=40mA+k 1s u =－60mA 所以k 1s u ＝－100mA 同理，若s 在位置3 I =I '+I ''=40mA+k 2s u 2 3 4621-=-=∴ s s u u k 2s u =150mA 故 I ＝190mA 3.8 N 为不含独立源的线性电阻电路，输出电压u ＝1/2s u ；若数处端 接5Ω电阻，u ＝1/3s u 问：输出端接3Ω电阻时，u 与s u 的关系。 +- u 图3.8 解：根据戴维南定理，电路等效为电压源和电阻串连

慕课 离散数学 电子科技大学 课后习题十 答案

作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G=，其中： V={a,b,c,d,e,f,g} E={(u,v)|u,v∈V,且u和v有共同语言} 从而图G如下图所示。 a b c d e f g 将这7个人围圆桌排位，使得每个人都能与他两边的人交谈，就是在图G 中找哈密顿回路，经观察上图可得到两条可能的哈密顿回路，即两种方案：abdfgeca和acbdfgea。 3.证明（法一）：根据已知条件，每个结点的度数均为n，则任何两个不相邻 的结点v i,v j的度数之和为2n，而图中总共有2n个结点，即deg(v i)+ deg(v j)?2n，满足哈密顿图的充分条件，从而图中存在一条哈密顿回路，当然，这就说明图G是连通图。 证明（法二）：用反证法，假设G不是连通图，设H是G的一个连通分支，由于图G是简单图且每个结点的度数为n，则子图H与G-H中均至少有n+1个结点。所以G的结点数大于等于2n+2，这与G中结点数为2n矛盾。所以假设不成立，从而G是连通图。 4.将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在 代表他们的结点之间连一条线，得到一个偶图G，假设它的互补结点子集V1、V2分别表示n位男士和n位女士，由题意可知V1中的每个结点度 1

数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2

离散数学作业答案完整版

离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，则R具有的性质是没有任何性质． 6．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，若在R中再增加两个元素{,} ，则新得到的关系就具有对 称性． 7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个． 8．设A={1, 2}上的二元关系为R={|x?A，y?A, x+y =10}，则R的自反闭 包为 {<1,1>,<2,2>} ． 9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含 <1,1>,<2,2>,<3,3> 等元素． 10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是 {<1,a>,<2,b>}或{<1,b>,<2,a>} ． 二、判断说明题（判断下列各题，并说明理由．）

离散数学作业答案

第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试

3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章

国开放大学离散数学本离散数学作业答案

国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021

离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题

1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {1,2,3}} ，A B= {< 1,1>，<1,2>，<2，1>，<2，2>，<3，1>，<3， 2> } ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {< 2,2>，<2,3>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，则R具有的性质是反自反性． 6．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，若在R中再增加两个元素 , ，则新得到的关系就具有对称性． 7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2 个．

华南理工网络教育2018年离散数学大作业参考答案#试题

华南理工大学网络教育学院 2018–2019学年度第一学期 《离散数学》作业 1、用推理规则证明?（P∧?Q），?Q∨R，? R??P 证（1）?Q∨R P （2）? R P （3）?Q（1）（2）析取三段论 （4）?（P∧?Q）P （5）?P ∨ Q （4）等价转换 （6）?P （3）（5）析取三段论 2、用推理规则证明Q，?P → R，P → S，? S?Q∧R 证（1）P → S P （2）? S P （3）?P（1）（2）拒取式 （4）?P → R P （5）R （3）（4）假言推理 （6）Q P （7）Q∧R（5）（6）合取 3．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解（1）真值表如下 P Q ?Q P→Q ?Q∧（P→Q）?P?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??（?Q∧（?P∨Q））∨?P ?（Q∨?（?P∨Q））∨?P??（?P∨Q）∨（Q∨?P）?1（析取范式）?（?P∧?Q）∨（?P∧Q）∨（P∧?Q）∨（P∧Q）（主析取范式） （3）该公式为重言式 4．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。

令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解前提：?x（F（x）→? G（x）），?x（G（x）∨H（x））， ? x? H（x）。 结论：? x ?F（x）。 证(1)? x ?H（x）P (2)?H（c）ES(1) (3)?x（G（x）∨H（x））P (4) G（c）∨H（c）US(3) (5) G（c）T(2，4)I (6)?x（F（x）→? G（x））P (7)F（c）→? G（c）US(6) (8)? F（c）T(5,7)I (9)（?x）? F（x）EG(8) 5．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证(1)（?x）（C（x）∧Q（x））P (2)C（c）∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P (4) C（c）→W（c）∧R（c）US(3) (5) C（c）T(2)I (6)W（c）∧R（c）T(4,5)I (7)R（c）T(6)I (8)Q（c）T(2)I (9)Q（c）∧R（c）T(7,8)I (10) （?x）（Q（x）∧R（x））EG(9) 6．设R是集合A = {1, 2, 3, 4, 5, 6, 7, 8, 9}上的整除关系。 （1）给出关系R；（2）画出关系R的哈斯图； （3）指出关系R的最大、最小元，极大、极小元。 解R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>，<1,7>,<1,8>,<1,9>,<2,4>,<2,6>，<2,8>，<3,6>，<3,9>，<4,8>}∪I A COV A={<1,2>,<1,3>,<1,5>,<1,7>,<2,4>,<2,6>，<3,6>，<3,9>，<4,8>} 作哈斯图如右： 极小元和最小元为1； 极大元为5,6,7,8,9, 无最大元 8

北京大学2017秋课件作业【离散数学】及答案

2017秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1设集合A={{2，3,4}，5，1}，下面命题为真是（选择题）[A] A．1∈A；B．2∈A；C．3∈A；D．{3，2,1}?A。 1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D] A．C；B．A；C．B；D．?。 1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题） （1）N?Q，Q∈S，则N?S，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］ 1-4设集合B={4，3}∩?，C={4，3}∩{?}，D={3，4，?}，E={x│x∈R并且x2-7x+12=0}，F={4，?，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A] A.C; B.D; C.E; D. F. 1-5用列元法表示下列集合：A={x│x∈N且3－x〈3}（选择题）[D] A.N; B.Z; C.Q; D.Z+ 1-6为何说集合的确定具有任意性?(简答题) 答：按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。 第二章二元关系 2-1设A={1，2，3}，A上的关系R={〈1，2〉，〈2，1〉}∪IA， 试求：（综合题） (1)domR=?;(2)ranR=?;(3)R的性质。 （4）商集A/R=？（5）A的划分∏=？（6）合成运算（R。R）=？ 答：R={<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}； (3)R的性质:自反,反对称,传递性质.这时，R不是等价关系。 （4）商集A/R={{1，2，3}，{2，3}，{3}}。由于R不是等价关系，所以，等价类之间出现交集。这是不允许的。请看下面的划分问题。 （5）A的划分∏={{1，2，3}，{2，3}，{3}}；也由于R不是等价关系，造成划分的荒谬结果：出现交集。试问：让“3”即参加第一组，又参加第二组，她该如何分配呢！！！ 所以，关系R必须是等价关系。至于作业中，此两题应说：因为R不是等价关系，此题无解。 2-2设R是正整数集合上的关系，由方程x+3y=12决定，即 R={〈x，y〉│x，y∈Z+且x+3y=12}， 试给出dom（R。R）。（选择题）[B] A.3； B.{3}； C.〈3，3〉； D.{〈3，3〉}。

离散数学 作业及答案

2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）：

离散数学作业答案

离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外） 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出 掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在 03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{3}，{1,3}，{2,3}， A B {1,2,3}} ，A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3,3> ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝ {<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，则R具有的性质是没有任何性质． 6．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，若在R中再增加两个元素{,} ，则新得到的关系就具 有对称性． 7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个． 8．设A={1, 2}上的二元关系为R={|x?A，y?A, x+y =10}，则R的自 反闭包为 {<1,1>,<2,2>} ． 9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少 包含 <1,1>,<2,2>,<3,3> 等元素． 10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是

离散数学作业标准答案

离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A )

吉大网院 离散数学 大作业及答案 201903

一、简要回答下列问题（每小题5分，共30分） 1、请给出集合的吸收率。 2、设A={1，2}，请给出A上的所有关系。 答：集合A上的全部关系有2^(2^2)=16种：空关系{}，全关系 {<1,1>,<1,2>,<2,1>,<2,2>}{<1,1>}{<2,2>}{<1,2>}{<2,1>}{<1,1>,<1,2>}{<1,1>,<2,1>}{<1,1> ,<2,2>}{<1,2>,<2,1>}{<1,2>,<2,2>}{<2,1>,<2,2>}{<1,1>,<1,2>,<2,1>}{<1,1>,<1,2>,<2,2>}{< 1,1>,<2,1>,<2,2>}{<1,2>,<2,1>,<2,2>} 3、什么是子句？请给出一例。 答：子句集S称为是可满足的，如果存在一个个体域和一种解释，使S中的每一个子句均为真，或者使得S的每一个子句中至少有一个文字为真。否则, 称子句集S是不可满足的 4、什么是前束范式？ 答：前束范式亦称前束式，一种谓词演算公式。指其一切量词都未被否定地处于公式的最前端且其辖域都延伸至公式的末端的谓词演算公式。设Q∈{?，?}，一个公式α是前束范式，当且仅当存在一个不含量词的公式β，使得 α=(Q?x?)(Q?x?)…(Q?x?)β. 5、什么是谓词逻辑中的项？ 答：谓词逻辑中的项指变项和常项，变项又分为自由变项和约束变项。 6、什么是命题公式的演绎？ 答：用A'表示非A,则 (A+B)'=A'B', (AB)'=A'+B'. 二、设A是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A={a，b}，B={1， 2}，试写出A到B上的全部二元关系。（8分） 答：解：A 到B 上共有2mn 个二元关系。本题中A×B 的全部子集φ，{(a,1)}，{(a,2)}，{(b,1)}， {(b,2)}， {(a,1),(a,2)}，{(a,1),(b,1)}，{(a,1),(b,2)}，{(a,1),(b,2)}，{(a,2),(b,1)}，{(a,2),(b,2)}， {(a,1),(a,2),(b,1)}，{(a,1),(a,2),(b,2)}，{(a,1),(b,1),(b,2)}，{(a,2),(b,1),(b,2)}，{(a,1),(a,2),(b,1),(b,2)}为A 到B 的全部二元关系。 三、R，S是集合A上的两个关系。试证明下列等式：（10分） （1）(R?S)-1= S-1?R-1 （2）(R-1)-1= R 证明：先证(R?S)--1?R-1，对任意(x，-1，则(y，，则存在，满足(y，且(a，，那么(x，-1且(a，-1，

吉林大学离散数学课后习题答案

第一章集合论基础 §1.1 基本要求 1. 掌握集合、子集、超集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系 的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。 2. 掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基 本算律，能够利用它们来证明更复杂的集合等式。 3. 掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质： 自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。 4. 掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。 5. 掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最 大元、最小元、极大元、极小元、上确界、小确界的定义。能画出有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。 6. 掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数 集合的判定方法。 7. 了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。

§1.2 主要解题方法 1.2.1 证明集合的包含关系 方法一.用定义来证明集合的包含关系是最常用也是最基本的一种方法。要证明A?B，首先任取x∈A，再演绎地证出x∈B成立。由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。当A是无限集时，因为我们不能对x∈A，逐一地证明x∈B成立，所以证明时的假设“x是任取的”就特别重要。 例1.2.1 设A，B，C，D是任意四个非空集合，若A?C，B?D，则A×B?C×D。 证明：任取(x，y) ∈A×B，往证(x，y) ∈C×D。 由(x，y) ∈A×B知，x∈A，且y∈B。又由A?C，B?D知，x∈C，且y∈D，因此，(x，y) ∈C×D。故，A×B?C×D。 方法二.还有一种证明集合包含关系的方法，基于集合的交和并运算的两个基本性质 A?B?A?B=A?A?B=B 以及一些已经证出的集合等式。现在我们就用此方法将上例再证一次。 由下面例1.2.2证明的结论有（A×B）?（C×D）=（A?C）×（B?D），若A?C，B?D，则A?C=A，B?D=B，因此，（A×B）?（C×D）=A×B。因此，A×B?C×D。 1.2.2 证明集合的相等 方法一.若A，B 是有限集，要证明集合A=B当然可以通过逐一比较两集合所有元素均一一对应相等即可，但当A，B 是无限集时，一般通过证明集合包含关系的方法证得A?B，B?A即可。 例1.2.2 设A，B，C，D是任意四个集合，求证（A×B）?（C×D）=（A?C）×（B?D）。 证明：首先证明（A×B）?（C×D）?（A?C）×（B?D）。任取（x,y）∈（A×B）?（C×D），则（x,y）∈（A×B），且（x,y）∈（C×D），故x∈A，y∈B，x∈C，y∈D，即x∈A?C，y∈B?D，因此，（x,y）∈（A?C）×（B?D）。 由于以上证明的每一步都是等价的，所以上述论证反方向进行也是成立的。故可证得（A?C）×（B?D）?（A×B）?（C×D）。 因此，（A×B）?（C×D）=（A?C）×（B?D）。 方法二. 还有一种证明集合相等的方法，可以通过已证出的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合。 例1.2.2 设A，B，C是三个集合，已知A?B=A?C，A?B=A?C，求证B=C。 证法1：使用反证法。假设B≠C，则必存在x，满足x∈B，且x?C，或者x?B，且x∈C。不妨设x∈B，且x?C，