题目：输入n，随机生成一个n个顶点的无向图。再随机生成路径。最后判断该无向图是否是欧拉图或者半欧拉图。
输入一个1~20的值作为无向图的顶点个数。
程序代码
#include
#include
#include
#include
using namespace std;
int graph[100][100], n, m = 0; //用二维数组存图，节点数、边数初始化为0
int ans[50], count = 0; //记录欧拉路的路径，路径数
bool visted[50]; //标记点是否被访问
int begin; //判是否为连通图，搜索的起点
struct stack
{
int top, node[100];
}s; //定点的栈结构
//输出随机生成的无向图关系矩阵
void Print()
{
cout << endl;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout << graph[i][j] << " ";
cout << endl;
}
}
//初始化图
void Init()
{
bool flag = false; //标记是否生成图
memset(graph, 0, sizeof(graph)); //初始化为0
memset(visted, false, sizeof(visted)); //初始化都未被访问
memset(ans, 0, sizeof(ans)); //欧拉图初始化为0
srand((unsigned)time(NULL));
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
graph[i][j] = 0 + rand() % 2; //随机生成无向图
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(graph[i][j])
{
flag = true; //最少有一条边
m++; //记录边的条数
graph[j][i] = 1; //无向图的定义
begin = i; //有一条边则其任意一个端点设为起点}
while(!flag) //如果没有边则重新生成图：防止rand 随机值恰好生成不了图
Init();
}
//深度优先搜索
void DFS(int x)
{
visted[x] = true;
for(int i = 0; i < n; i++)
if(!visted[i] && graph[x][i])
DFS(i);
}
//从所设定的起点深度优先遍历图，若有一个点没被访问，则为非连通图
bool Judge()
{
DFS(begin);
for(int i = 0; i < n; i++)
if(!visted[i])
return false;
return true;
}
//深度优先搜索
void DFSGraph(int x)
{
s.top++;
s.node[s.top] = x;
for(int i = 0; i < n; i++)
{
if(graph[i][x] > 0)
{
graph[i][x] = 0; //删除该边
graph[x][i] = 0;
DFSGraph(i);
break;
}
}
}
//Fleury算法
void Fleury(int x)
{
int flag;
s.top = 0;
s.node[s.top] = x; //起点入栈
while(s.top >= 0)
{
flag = 0;
for(int i = 0; i < n; i++)
{
if(graph[s.node[s.top]][i] > 0)
{
flag = 1;
break;
}
}
if(flag == 0) //如果没有可扩展的点，则记录下该点并将其出栈
{
ans[count ++] = s.node[s.top] + 1;
s.top --;
}
else //如果有，则将其出栈并继续搜索
{
s.top --;
DFSGraph(s.node[s.top + 1]);
}
}
cout << endl;
}
//输出答案
void Answer()
{
for(int i = 0; i < count; i++)
cout << ans[i] << " ";
cout << endl;
}
int main()
{
int num = 0, start = 0, degree; //奇度顶点个数, 欧拉路的起点, 每个顶点的度
cout << "Please input n(1 <= n <= 20): ";
cin >> n;
Init();
cout << endl << "The generated undirected graph is: " << endl;
Print();
cout << endl;
if(!Judge())
{
cout << "Non-connected graph" << endl;
return 0;
}
//如果存在奇度顶点，则从奇度顶点出发，否则从0出发
for(int i = 0; i < n; i++)
{
degree = 0;
for(int j = 0; j < n; j++)
degree += graph[i][j];
if(degree % 2)
{
start = i;
num++;
}
}
//无向图具有一条欧拉路，当且仅当G是连通的，且有0个或2个奇数度结点
if(num == 0 || num == 2)
{
Fleury(start);
//欧拉路径的头和尾相等，则说明欧拉路是回路
if(ans[0] == ans[count - 1])
cout << "This graph is Euler Graph, its Euler Loop is: ";
else
cout << "This graph is Half-Euler Graph, its Euler Path is: ";
Answer();
}
else
cout << "This graph is Non-Euler Graph or Half-Euler Graph." << endl;
return 0;
}
实验结果
测试数据一
输入欧拉图结点为15：经过运行发现是非欧拉图或者半欧拉图。
测试数据二
输入欧拉图结点为8：经过运行发现是半欧拉图。
欧拉路径为：2,7,6,4,8,3,7,5,3,6,2,5,4,1,3,2,1,7。
测试数据三
输入欧拉图结点为6：经过运行发现是欧拉图。欧拉回路为：1,6,4,3,6,5,2,3,1。
2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19
D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项：
A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第（A）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下，放有本课程历年考试试卷的栏目名称是：（D ）． 选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标：
实验1 1实验内容 （1）求任意一个命题公式的真值表。 （2）利用真值表求任意一个命题公式的主范式。 （3）利用真值表进行逻辑推理。 注：（2）和（3）可在（1）的基础上完成。 2实验目的 真值表是命题逻辑中的一个十分重要的概念，利用它几乎可以解决命题逻辑中的所有问题。例如，利用命题公式的真值表，可以判断命题公式的类型、求命题公式的主范式、判断两命题公式是否等价，还可以进行推理等。 本实验通过编写一个程序，让计算机给出命题公式的真值表，并在此基础上进行命题公式类型的判定、求命题公式的主范式等。目的是让学生更加深刻地理解真值表的概念，并掌握真值表的求解方法及其在解决命题逻辑中其他问题中的应用。 3算法的主要思想 利用计算机求命题公式真值表的关键是：①给出命题变元的每一组赋值；②计算命题公式在每一组赋值下的真值。 真值表中命题变元的取值具有如下规律：每列中0 和1 是交替出现的，且0 和1 连续出现的个数相同。n 个命题变元的每组赋值的生成算法可基于这种思想。 含有n个命题变元的命题公式的真值的计算采用的方法为“算符优先法”。 为了程序实现的方便，约定命题变元只用一个字母表示，非、合取、析取、蕴含和等价联结词分别用！、&、|、－、＋来表示。 算符之间的优先关系如表1-1所示： 表1-1算符优先级
优先算法，我们采用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是： （1）首先设置操作数栈为空栈，符号“@”为运算符的栈底元素； （2）调用函数Divi（exp，myopnd）得到命题公式包含的命题变元序列myopnd （按字典序排列，同一个命题变元只出现一次）； （3）依次读入命题公式中的每个字符，若是命题变元则其对应的赋值进OPND 栈，若是运算符，则和OPTR栈的栈顶运算符比较后作相应操作，直至整个命题公式求值完毕。
离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D
(7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={
离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 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
离散数学(高起专)阶段性作业4 总分：100分得分：0分 一、单选题 1. 设Q是有理数集，
参考答案：B 二、多选题 1. 设R为实数集，函数f：R→R，f(x)=x-1，则f是_______(5分) (A) 满射函数 (B) 单射函数 (C) 双射函数 (D) 非单射非满射 参考答案：A,B,C 2. Q是有理数集, Q上的运算*为，则代数系统
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
实验一命题逻辑公式化简 【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。 【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。 实验用例：用化简命题逻辑公式的方法设计一个 5 人表决开关电路，要求 3 人以上（含 3 人）同意则表决通过（表决开关亮）。 【实验原理和方法】 （1）写出5人表决开关电路真值表，从真值表得出5 人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。 （2）上面公式中的每一个联结词是一个开关元件，将它们定义成 C 语言中的函数。 （3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。 （4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。 参考代码： #include
离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间
目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。
测 验 【一】 已知8阶群
的运算表见下，试完成以下要求： （1）填写表中的空缺部分。 （2 （3 ◇P 的子集。 （4）给出一条理由说明
的各个子群的左陪集就是右陪集。给出一条理由说明4阶子群 【二】 证明如果f 是由到的同态映射，g 是由到
【四】 设S 是30的因子集合，S 上关系“|”是整除关系。 a)请画出该关系所对应的格的Hasse 图; b)判断是否存在子格为布尔格; c)如果存在子格为布尔格，请给出这些子格并写出布尔格的原子。 解 （1）G={1，2，3，5，6，10，15，30}，其哈斯图见图7.4.1。 (2)〈G ，|〉的所有元素个数大于等于4的不同构的子格的Hasse 图见图7.4.2。 （3）所有的子格均是分配格、模格。图7.4.2（b ）、（f ）所示的格还是有补格。 （4）图（b ）、（f ）所示的格是布尔代数。其中，图（b ）的原子集合为{15，6}，图（f ）的原子集合为{2，3，5}。 【五】 假设当前有n 个人，其中任意两个人合起来认识所留下的n-2个人。 (a) 证明：当n ≥3时，n 个人能站成一排，使得中间每个人两旁站着自己的朋友，两端的两个人每个人旁边站着他的一个朋友。 (b) 证明：当n ≥4时，n 个人能站成一圈，使每个人的两旁站着自己的朋友。 由已知图G 中任意两个顶点u ，v 认识余下的n-2人，得 degn-2(u)+degn-2(v)≥n-2，且其余 n-2个顶点必与u 或v 相邻接 下面证明当n ≥3，必有 deg(u)+deg(v)≥ n-1， 则图G 中存在一条哈密尔顿通路。 (a) 若u ，v 相邻，则 deg(u)+deg(v)=(1+degn-2(u))+(1+degn-2(v)) ≥n (b) 若u ，v 不相邻，V-{u ，v}中恰有的n-2≥1个顶点。 如果 degn-2(u)+degn-2(v)= n-2，且其余 n-2个顶点必与u 或v 相邻接，则每一个顶点 3056 256 2 3110 51 65 306 1 5(a )(b )(c ) (f )(e )(d )
《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见
提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之
间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于{()∈A×}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足<>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的?(?x)((x∈A)→(<>∈R))=1 对称关系：对任意的∈A，如果<>∈R，那么<>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的? (?x)(?y)((x∈A)∧(y∈A)∧(<>∈R)→(<>∈R))=1 传递关系：对任意的∈A，如果<>∈R且<>∈R，那么<>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的? (?x)(?y)(?z)[(x∈A)∧(y∈A)∧(z ∈A)∧((<>∈R)∧(<>∈R)→(<>∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示：
离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。 （A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ?（B）0 ??（C）0∈?（D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） （A）自反性（B）有限性（C）对称性（D）传递性 7、集合A={1,2,…,10}上的关系R={
（C ）弱连通图 （D ）不连通图 9、具有6个顶点，12条边的连通简单平面图中，每个面都是由（ ）条边围成？ （A ）2 （B ）4 （C ）3 （D ）5 10．连通图G 是一棵树，当且仅当G 中（ ）。 （A ）有些边不是割边 （B ）每条边都是割边 （C ）无割边集 （D ）每条边都不是割边 二、 填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D 是正整数集合，则命题?x ?y(xy=y)的真值是______。 3、令R(x):x 是实数，Q(x):x 是有理数。则命题“并非每个实数都是有理数”的符号化表示为________。 4、公式(?P ∧Q)∨(?P ∧?Q)化简为________。 5、设A ∩B=A ∩C ，A ∩B=A ∩C ，则B________C 。 6、设A={2,4,6}，A 上的二元运算*定义为：a*b=max{a,b}，则在独异点
湖南工业大学 2009学年上学期考试试题 一、选择题.(每小题2分，总计30) 1.给定语句如下： （1）15是素数（质数）。 （2）10能被2整除，3是偶数。 （3）你下午有会吗？若无会，请到我这儿来！ （4）2x+3>0. （5）只有4是偶数，3才能被2整除。 (6)明年5月1日是晴天。 以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）, 是假命题的是（D）,真值待定的命题是（E） A: ①(1)(3)(4)(6) ②(1)(4)(6) ③(1)（6） B: ①(2)(4) ②(2)(4)(6) ③(2)(5) C: ①(1)(2)(5)(6) ②无真命题③（5） D: ①(1)(2) ②无假命题③（1）（2）（4）（5） E: ①(4)(6) ②（6）③无真值待定的命题 2.将下列语句符号化： （1）4是偶数或是奇数。（A） 设p：4是偶数，q：4是奇数 （2）只有王荣努力学习，她才能取得好成绩。（B） 设p：王荣努力学习，q：王荣取得好成绩 （3）每列火车都比某些汽车快。（C） 设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。 A: ① p∨q ② p∧q ③ p→q B: ① p→q ② q→p ③ p∧q C: ①?x?y ((F(x)∧G(y))→ (H(x,y)) ②?x (F(x)→?y(G(y)∧H(x,y))) ③?x (F(x)∧?y(G(y)∧H(x,y))) 3.设S={1,2,3},下图给出了S上的5个关系,则它们只具有以下性质:R1是 （A）,R2是(B),R3是(C)。
A B C:①自反的，对称的，传递的 ②反自反的，对称的 ③自反的 ④ 反对称的 ⑤对称的 ⑥自反的，对称的，反对称的，传递的 4. 设S={Ф，{1}，{1，2}}，则有 （1）（A ）∈S （2）(B)?S （3） P(S)有（C ）个元数。 （4）（D ）既是S 的元素，又是S 的子集 A: ① {1,2} ② 1 B: ③{{1,2}} ④{1} C: ⑤ 3 ⑥ 6 ⑦ 7 ⑧ 8 D: ⑨ {1} ⑩Ф 二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分） 1、用等值演算算法证明等值式 (p ∧q)∨(p ∧?q)?p 2、构造下面命题推理的证明 如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。 三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分， 总计30分） 1、设()(){}212,，，个体域为 为，整除为 2^m*n 选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→ Q （B）P∨Q （C）P∧Q （D）P∧Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→ P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是（A），而命题“所有的人都是要死的”的否定是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（） A ）永真式 （ B ）永假式 （ C ）可满足式 （ D ）以上均有可能 5、以下选项中正确的是（ ）。 （A ）0= ? （B ）0 ? （ C ）0∈ ? （D ）0?? 6、以下哪个不是集合 A 上的等价关系的性质？（ ） A ）自反性 （ B ）有限性 （ C ）对称性 （ D ）传递性 7、集合 A={1,2, ?,10}上的关系 R={ 离散数学上机实验报告 ————————————————————————————————作者：————————————————————————————————日期： ? 《离散数学》 实验报告 姓名: 学号: 班级： ? 实验一连结词逻辑运算 一.实验目的 实现二元合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则,利用程序语言实现逻辑这几种逻辑运算。 二.实验内容 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的真值。要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。 三．实验环境 使用Miｃroｓoft Visual C+＋6.０为编程软件，采用称C/C＋+语言为编程语言实现。 四.实验过程 １.算法分析: 合取：p，q都为1的时候为1,其他为0 析取：p,q都为0的时候为０，其他为1 蕴含：ｐ为1，q为0时为0,其他为１ 等价:p,q同真同假 2.程序代码： #iｎclｕdｅ 中国地质大学(武汉)远程与继续教育学院 离散数学课程作业2（共 4 次作业） 学习层次：专科涉及章节：第2-3章 1.指出下列命题公式那个不是重言式: A. Q→(P∨Q)； B.(P∧Q)→P； C.?（P∧?Q）； D.?（?P∧0）. 2. “每个大学生不是文科生就是理科生”写出下命题在一阶逻辑中符号形式. 3. 构造下面的推理的证明： 前提：R ∧ ?R Q P Q ? , ), (? ∨ ? 结论：P ? 4. 指出公式P→(Q ∨R)的值为0的真值指派P,Q,R: 5.写出公式:所有的人都会死,苏格拉底是人,所以苏格拉底是会死的.符号化形 式 6. 证明A∧(A→B) →B 是重言式. 7. 构造下面推理的证明: 前提:. ∨ ? ∧ A? ? ? B , (C ), B C 结论: A ? 8. 符号化命题并证明或推理:小李或者小张是三好学生.如果小李是三好学生,你 是知道的, .如果小张是三好学生, 小赵也是三好学生;你不知道小李是三 好学生,问谁是三好学生? P: 小李张是三好学生 Q:小张是三好学生 R: 小赵是三好学生 9.符号化命题并证明或推理:如果一个人怕困难,那么他就不会获得成功;每个人 或者获得成功,或者曾经失败过;有些人未失败过,所以有些人不怕困难. 10. 指出下列语句中何为真命题。 A.我正在说谎; B. 如果雪是黑的,那么1+2=5; C.严禁吸烟!; D.如果1+2=3,那么雪是黑的. 11. 用形式演绎法证明: },,{r q r s q p →?→?∨? 蕴涵p →s 。 前提：r , ,→?→?∨?q r s q p 结论：s p → 12. 用真值表或命题演算判断下列各命题（或公式）的真值： 1. (P ∧?P)?Q 。 2. ((P →Q) ∧(Q →R)) →(P →R) 。 3. Q →(P ∨Q) 。 4. ?)1(∨?q 。 参考答案 1. 答: C 不是重言式. 2. 解: 设F(x): x 是大学生,H(x): x 是理科生, H(x): x 是文科生,则命题的符号化形式为:))()()((x H x G x F x ∨→? 3. 证明： );(2).5). P 6) );(3).4). Q 5).); ( R 4).); ( R Q ).3); ( Q P 2).); ( )( ).1的析取三段论的析取三段论前提引入前提引入莫根律置换前提引入???∨?∨??∧?Q P 4. 答: 公式P →(Q ∨R)的值为0的真值指派P,Q,R 为(1,0,0) . 5. 解: P:人Q:会死; R:苏格拉底.符号化形式为: (P →Q) ∧(R →P)? (P →Q) 6. 证明: A ∧(A →B) →B ? A ∧(?A ∨B) →B ??A ∨(A ∧?B) ∨B ? (?A ∨A) ∧(?A ∨?B) ∨B ?(?A ∨?B) ∨B ?1 离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶 数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下：离散数学试题及解答
离散数学上机实验报告
离散数学阶段性作业21
离散数学试题与答案试卷一
相关主题
文本预览