离散实验报告
实验一真值计算
1、实验目的
熟悉五个常用联结词合取、析取、条件和双条件的概念，掌握真值表技术。
2、实验内容与要求
定义1 设P表示一个命题，由命题联结词┐和命题P连接成┐P，称┐P为P的否定式复合命题，┐P读“非P”。称┐为否定联结词。┐P是真，当且仅当P为假；┐P是假，当且仅当P为真。
定义2 设P和Q为两个命题，由命题联结词∧将P和Q连接成P∧Q，称P∧Q为命题P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P且Q”。称∧为合取联结词。当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。
定义3 设P和Q为两个命题，由命题联结词∨把P和Q连接成P∨Q，称P∨Q为命题P和Q的析取式复合命题，P∨Q读做“P或Q”。称∨为析取联结词。当且仅当P和Q的真值同为假，P∨Q的真值为假；否则，P∨Q的真值为真。
定义4 设P和Q为两个命题，由命题联结词→把P和Q连接成P→Q，称P→Q为命题P和Q的条件式复合命题，简称条件命题。P→Q读做“P条件Q”或者“若P则Q”。称→为条件联结词。当P的真值为真而Q的真值为假时，命题P→Q的真值为假；否则，P→Q 的真值为真。
定义5 令P、Q是两个命题，由命题联结词?把P和Q连接成P ? Q，称P ? Q为命题P和Q的双条件式复合命题，简称双条件命题，P ?Q读做“P当且仅当Q”，或“P等价Q”。称?为双条件联结词。当P和Q的真值相同时，P ? Q的真值为真；否则，P ? Q 的真值为假。
本实验要求从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值。用C语言或MATLAB实现。
3、源程序
#include
void main()
{
printf("请输入P、Q的真值\n");
int a,b;
scanf("%d%d",&a,&b);
int c;
if(a==1&&b==1)
c=1;
else c=0;
printf("合取结果为%d\n",c);
int d;
if(a==0&&b==0)
d=0;
else d=1;
printf("析取结果为%d\n",d);
int e;
if(a==1&&b==0)
e=0;
else e=1;
printf("单条件为%d\n",e);
int f;
if(a==b)
f=1;
else f=0;
printf("双条件为%d\n",f);
}
4、实验结果
请输入P、Q的真值
1 0
合取结果为0
析取结果为1
单条件为0
双条件为0
Press any key to continue
实验二关系闭包计算
1、实验目的
熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。
2、实验内容与要求
定义6 设R是A上的二元关系，R的自反（对称、传递）闭包是关系R1，则
①R1是自反的（对称的、传递的）
②R?R1
③对任何自反的（对称的、传递的）关系R2，若R?R2，则R1?R2。
R的自反、对称和传递闭包分别记为r(R)、s(R)和t(R)。
定理1 令R?A?A，则
①r(R)=R∪IA
②s(R)=R∪R-1
③t(R)=R∪R2∪R3…
Warshall算法：设R是n个元素集合上的二元关系，M是R的关系矩阵；
(1)置新矩阵A:=M
(2)置i:=1；
(3)for j=1 to n do
if A[j,i]=1 then do
for k=1 to n do
A[j,k]:=A[j,k]+A[i,k]
(4)i=i+1；
(5)if i<=n then to (3)
else stop
本实验要求从键盘输入一个关系的关系矩阵，计算其自反闭包、对称闭包和传递闭包，计算传递闭包时使用Warshall算法。用C语言或MA TLAB实现。
3、源程序
#include
int xiqu(int,int);
void main()
{
int
a[100][100],b[100][100],c[100][100],d[100][100],e[100][100],i,j,k,n,x,y,z;
printf("请输入关系矩阵的阶数\n");
scanf("%d",&n);
printf("请输入此关系矩阵\n");
for(i=0;i for(j=0;j scanf("%d",&a[i][j]); for(i=0;i { e[i][i]=1; } printf("自反闭包为\n"); for(i=0;i { for(j=0;j { b[i][j]=xiqu(a[i][j],e[i][j]),printf(" %4d",b[i][j]); } printf("\n"); } for(i=0;i { for(j=0;j b[j][i]=a[i][j]; } printf("对称闭包为\n"); for(i=0;i { for(j=0;j { c[i][j]=xiqu(a[i][j],b[i][j]),printf(" %4d",c[i][j]); } printf("\n"); } for(j=0;j for(k=0;k { if(a[k][j]==1) { for(i=0;i a[k][i]=a[k][i]||a[j][i]; } } printf("传递闭包为\n"); for(i=0;i { for(j=0;j { printf(" %4d",a[i][j]); } printf("\n"); } } int xiqu(int x,int y) { int z; if(x==1&&y==1) z=1; else z=0; return (z); } 4 、实验结果 实验三 计算两结点间长度为m 的路的数目 1、实验目的 熟悉邻接矩阵和两结点间长度为m 的路的数目的关系并编程计算。 2、实验内容与要求 定义7 给定简单图G= 10i j ij i j v adj v a v nadj v ori j ?=?=? i ，j=1，2，…，n 。 定理2 设A 为简单图G 的邻接矩阵，则A m 中的i 行j 列元素a m ij 等于G 中联结v i 到v j 的长度为m 的链(或路)的数目。 本实验要求从键盘输入图的邻接矩阵和一正整数m ，计算结点两两之间长度为m 的路的数目。考虑有向图和无向图。用C 语言或MA TLAB 实现。 3、源程序 #include void main() { int a[100][100],b[100][100],c[100][100],d[100][100],i,j,k,t,p,q,n,m; printf("请输入关系矩阵的阶数\n"); scanf("%d",&n); printf("请输入路的长度\n"); scanf("%d",&m); printf("请输入此关系矩阵\n"); for(i=0;i { for(j=0;j { scanf("%d",&a[i][j]); c[i][j]=a[i][j]; d[i][j]=a[i][j]; b[i][j]=0; } } for(t=0;t { for(i=0;i { for(j=0;j { for(k=0;k b[i][j]+=c[i][k]*a[k][j]; } } for(p=0;p { for(q=0;q { c[p][q]=b[p][q]; b[p][q]=0; } } } for(i=0;i { for(j=0;j { if(c[i][j]==m) k=k+1; } } printf("结点两两之间长度为%d的路的数目为%d\n",m,k); } 4、实验结果 实验四 最优树的构造 1、实验目的 熟悉最优树的构造算法，掌握最优树的构造过程。 2、实验内容与要求 定义8 在权分别为w 1，w 2，…，w t 的加权二叉树T 中，若权是w i 的叶结点，其级为L(w i )，则 1()()t i i i w T w L w ==∑称为加权二叉树T 的权，并记为w(T)。已知w 1，w 2，…，w t 为权，T 0为加权二叉树，其权为w(T 0)，如果对任意加权二叉树T ，它的权是w(T)，均有w(T 0)≤w(T)，则称T 0是最优树或Huffman 树。 定理3 设T 为加权w 1，w 2，…，w t 且w 1≤w 2≤…≤w t 的最优树，则 (1) 加权w 1和w 2的叶结点v w1和v w2是兄弟。 (2) 以叶结点v w1和v w2为儿子的分枝结点，它是所有分枝结点的级最高者。 定理4 设T为加权w1，w2，…，w t且w1≤w2≤…≤w t的最优树，若将以加权w1和w2的叶结点为儿子的分枝结点改为加权w1+w2的叶结点而得到一棵新树T1，则T1是最优树。 根据上述两个定理，求一棵有t个权的最优树，可简化为求一棵有t-1个权的最优树，而这又可简化为求一棵有t-2个权的最优树，依此类推。具体作法是：首先找出两个最小的权值，设w1和w2。然后对t-1个权w1+w2，w3，…，w t求作一棵最优树，并且将这棵树中的结w1+w2代之以w1 w2，依此类推。 本实验要求从键盘输入一组权值，构造出对应的最优树，列出构造过程。用C语言或MATLAB实现。 3、源程序 #include using namespace std; int M[100]; int N[100][100]; int P[100][100][100]; int x; void shuru(); void paixu(int h); void shuchu(); void main() { int i,j,k,l,linshi; shuru(); shuchu(); paixu(x); shuchu(); for (i=1;i<=x;i++) { paixu(i); cout< M[i+1]=M[i]+M[i+1]; } } void shuru() { int s; cout<<"请输入权值个数：\n"; cin>>x; cout<<"请输入权值：\n"; for (s=1;s<=x;s++) cin>>M[s]; } void paixu(int h) { int i,j,linshi; for (i=1;i<=h-1;i++) { for (j=i+1;j<=h;j++) { if (M[i]>=M[j]) { linshi=M[i]; M[i]=M[j]; M[j]=linshi; } } } } void shuchu() { int i; for(i=1;i<=x;i++) { cout< } cout<<"\n"; } 4、实验结果 实验总结 通过这次离散的实验，使我了解到我对离散的很多知识没有掌握好，很多知识点都忘了，写程序时还要查书，还有我的C语言编程能力非常差，第二个实验就用了很长时间，后面的实验更是花费了好多时间，经过无数次改正，才勉强可以达到要求，看来以后要多在这些方面下功夫。 第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 - 四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 - 第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 - 《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 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 一、请给出一个集合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) 北京邮电大学 离散数学 第一次阶段作业 判断题 1. 如果A∪B=B，则A?B。【答案：A】 A. 正确 B. 错误 2. 如果a∈A∪B，则a?A或a?B。【答案：B】 A. 正确 B. 错误 3. a∈{a,a}。【答案：A】 A. 正确 B. 错误 4.{?}是空集。【答案：B】 A. 正确 B. 错误 5.设ρ是集合A上的等价关系，则当a,b∈ρ时，aρ=bρ。【答案：A】 A. 正确 B. 错误 单项选择题 1. 设A={a,a}，则下列各式中错误的是【答案：B】 A. a∈2A B. {a}?2A C. {a}∈2A D. {a}?2A 解：2A={?,a,a, a,a} 2. 下列各式中不正确的是【答案：C】 A. ??? B. ?∈{?} C. ??? D. ?∈{?,?} 3. 设ρ是集合A上的关系，则（）不是ρ为反对称关系的充分必要条件【答案：D】 A. ρ是反对称关系 B. ρ∩ρ?i A C. 对任意x,y∈A，当x,y∈ρ且x≠y时y,x?ρ D. 对A的某两个元素x, y，当x,y,y,x∈ρ时有x=y 4. 设A，B，C是集合，ρ,μ分别是A到B，B到C的关系，x∈A，z∈C，则存在y∈B使得x,y∈ρ且y,z∈μ是x,z∈ρ°μ的（）条件【答案：C】 A. 充分而非必要 B. 必要而非充分 C. 充分必要 D. 既非充分又非必要 5. 设A={0,b}，B={1,b,3}，则A∪B的恒等关系为【答案：A】 A.{0,0,1,1,b,b,3,3} B. {0,0,1,1,3,3} C. {0,0,b,b,3,3} D. {0,1,1,b,b,3,3,0} 离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间 目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。 离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 第一次 第1题 空集不是任何集合的真子集 您的答案：错误 题目分数：0.5 此题得分：0.5 批注：本题考查空集的基本概念 第2题 一个集合可以是另一个集合的元素 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查集合的基本概念 第3题 设A、B为集合，如果集合A的元素都是集合B的元 素，则称A是B的子集 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查子集的基本概念 第4题 如果一个集合包含了所要讨论的每一个集合，则称该 集合为全集，记为U 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查全集的基本概念 第5题 在笛卡儿坐标系中，平面上点的坐标< 1,2> 与< 2,1> 代表不同的点 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查笛卡儿坐标系的基本概念 第6题 复合运算不满足交换律，但复合运算满足结合律您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查复合运算的是否满足交换律和结合律 第7题 映射也可以称为函数，是一种特殊的二元关系 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查映射的基本概念 第8题 映射的复合运算不满足交换律 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题为映射的基础知识 第9题 空集是唯一的 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查空集的唯一性 第10题 对任意的集合A，A包含A 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查集合的包含概念 第11题 集合上的三种特殊元是单位元、零元及可逆元 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查集合上的三种特殊元 第12题 集合A上的偏序关系的三个性质是自反性、反对称性和传递性 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查集合偏序关系的三个性质 第13题 设f:A→B, g:B→C。若f, g都是满射，则gf也是满射 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查复合关系的满射概念 第14题 设f:A→B, g:B→C。若f, g都是双射，则gf也是双射 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查复合关系的双射概念 第15题 设f:A→B, g:B→C。若f, g都是单射，则gf也是单射 您的答案：正确 题目分数：0.5 此题得分：0.5 命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。 2013年9月份考试离散数学第一次作业 一、单项选择题（本大题共40分，共20 小题，每小题2 分） 1. 下列语句中不是命题的只有（）。A. 鸡毛也能飞上天？B. 人的死或重于泰山，或轻于鸿毛。C. 不经一事，不长一智。 D. 牙好，胃口就好。 2. 设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1oR-1的运算结果是（）。 A. {〈4，1〉，〈2，3〉，〈4，2〉} B. {〈2，4〉，〈2，3〉，〈4，2〉} C. {〈4，1〉，〈2，3〉，〈2，4〉} D. {〈2，2〉，〈3，1〉，〈4，4〉} 3. 下列集合关于所给定的运算成为群的是（）。 A. 已给实数a的正整数次幂的全体，且a∈{0，1，-1}，关于数的乘法 B. 所有非负整数的集合，关于数的加法 C. 所有正有理数的集合，关于数的乘法 D. 实数集，关于数的除法 4. 在有n个结点的连通图中，其边数（） A. 最多有n-1条 B. 至少有n-1条 C. 最多有n条 D. 至少有n条 5. 一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条（） A. 汉密尔顿回路 B. 欧拉回路 C. 汉密尔顿通路 D. 初级回路 6. .以下命题公式中，为永假式的是（） A. .p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) 7. 在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是（）。 A. b∧(a∨c) B. (a∧b)∨(a∧b) C. (a∨b)∧(a∨b∨c)∧(b∨c) D. (b∨c)∧(a∨c) 8. 所有使命题公式为真的赋值为（）。 A. 010，100，101，110，111 B. 010，100，101，111 C. 全体赋值 D. 不存在 9. 设i是虚数，·是复数乘法运算，则G=<{i,-i,1,-1},?>是群，下列是G的子群是（）。 A. 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以 根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足 离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元. 解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。 3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素. 离散数学第一次作业（命题逻辑） 1、证明下列各式是重言式 （1）（（P∧Q）→P）?T ù((?(P∧Q) ∨ P) ?T ù(?P∨?Q∨P) ?T ù（T∨?Q）?T ùT?T 所以此式为重言式 （2）?（?（P∨Q）→? P）?F ù?（（P∨Q）∨? P）?F ù?（T∨Q）?F ù?T?F ùF?F 所以此式为重言式 （3）（Q→P）∧（? P→Q）∧（Q?Q）? P ù（? Q∨P）∧（P∨Q）∧T? P ù（(? Q∨P）∧P) ∨(（? Q∨P）∧Q) ? P ù(P∨((? Q∨P）∧Q) ? P ù(P∨P) ? P ùP? P 所以此式为重言式 （4）（P→? P）∧（? P→P）?F ù（? P∨? P）∧（P∨P）?F ù（? P∧P）?F ùF?F 所以此式为重言式 2、求出下列公式的最简等价式：（1）（（P→Q）?（? Q→? P））∧R ù（（P→Q）?（P→Q））∧R ùT∧RùR （2）P∨? P∨（Q∧?Q） ùT∨FùT （3）（P∧（Q∧S））∨（? P∧（Q∧S））ù（（P∨? P ）∧（Q∧S））） ùT∧（Q∧S） ù（Q∧S） 3、（1）与非运算符↑（又叫悉菲（Sheffer）记号）用下述真值表定义，可以看出P↑Q??（P∧Q），试证明： （a）P↑P?? P；（b）（P↑P）↑（Q↑Q）? P∨Q； （c）（P↑Q）↑（P↑Q）? P∧Q 证明： （a）P↑P??（P∧P）??P (b) （P↑P）↑（Q↑Q）??P↑?Q??(?P∧?Q) ? P∨Q (c) （P↑Q）↑（P↑Q）??（P∧Q）↑?（P∧Q） ??(?（P∧Q）∧?（P∧Q）) ???（P∧Q） ? P∧Q （2）或非运算符↓（又叫皮尔斯（Peirce）箭头）用下述真值表定义，它与?（P∨Q）逻辑等价。对下述每一式，找出仅用↓表示的等价式。（a）? P；（b）P∨Q；（c）P∧Q。 P Q P↑Q P↓Q 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 证明： （a）? Pù? P∧Tù? P∧?Fù?（P∨F）ùP↓ F （b）P∨Qù??（P∨Q）ù?（P↓Q）ù（P↓Q）↓ F （c）P∧Qù?(?P∨?Q) ù??（? P↓? Q）ù? P↓? Qù（P↓ F）↓（Q↓ F） 《离散数学》实验报告 专业网络工程 班级 姓名 学号 授课教师 二 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 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共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={ 大连民族学院 计算机科学与工程学院实验报告 实验题目：判断关系的性质 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性 专业：班级：学生姓名：学号： 实验日期：年月日实验地点： 实验学时：实验成绩： 指导教师签字：年月日 实验报告正文部分（具体要求详见实验报告格式要求） 实验报告格式 [实验题目] 判断关系的性质 [实验目的] 使学生掌握利用计算机语言实现判断关系性质的基本方法。[实验环境] Microsoft Visual C++6.0 [实验原理] 实验内容与要求：对给定表示有穷集上关系的矩阵，确定这个关系是否是自反的或反自反的；对称的或反对称的；是否传递的。 通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示： 程序源代码： #include scanf("%d",&M[i][j]); for(i=0;i 华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?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）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P (5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令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 ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(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) 4．用直接证法证明： 前提：（?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 注意看参考答案 1. A．明年国庆节是晴天。 B．在实数范围内，x+y〈3。 C．请回答这个问题！ D．明天下午有课吗？ 在上面句子中，是命题的只有（） 答题： A. B. C. D. 参考答案：A 2. 在上面句子中，是命题的是( ) A．雪是黑色的。 B．这朵花多好看呀！。 C．请回答这个问题！ D．明天下午有会吗？ 答题： A. B. C. D. 参考答案：A 3. A．现在开会吗？ B．在实数范围内，x+y >5。 C．这朵花多好看呀！ D．离散数学是计算机科学专业的一门必修课。 在上面语句中，是命题的只有( ) 答题： A. B. C. D. 参考答案：D 4. A．1＋101＝110 B．中国人民是伟大的。 C．全体起立！ D．计算机机房有空位吗？ 在上面句子中，是命题的是( ) 答题： A. B. C. D. 参考答案：B 5.下面的命题不是简单命题的是( ) A．3是素数或4是素数 B．2018年元旦下大雪 C．刘宏与魏新是同学 D．圆的面积等于半径的平方与之积 答题： A. B. C. D. 参考答案：A 6.设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会” 可符号化为：（） A． B． C． D． 答题： A. B. C. D. 参考答案：B 7.下面“”的等价说法中，不正确的为 A．p是q的充分条件 B． q是p的必要条件 C．q仅当p D．只有q才p 答题： A. B. C. D. 参考答案：C 8. p,q都是命题，则p→q的真值为假当且仅当( ) A．p为假，q为真 B．p为假，q也为假 C．p为真，q也为真 D．p为真，q也为假 答题： A. B. C. D. 参考答案：D 9.个命题变元组成的命题公式，有( )种真值情况 A． B． C． D．2 答题： A. B. C. D. 参考答案：C 10. 答题： A. B. C. D. 参考答案：C 11.设F（x）：x是火车，G（x）：x是汽车，H（x，y）：x比y快。命题“说 离散数学实验报告 姓名： 学号： 班级： 实验地点： 实验时间： 1 实验目的和要求 运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下： 八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km 。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？ 2 实验环境和工具 实验环境：Windows 7 旗舰版 工具：Dev-C++ 5.8.3 3 实验过程 3.1 算法流程图 3.2程序核心代码 //油管铺设问题Prim算法实现 #include /*输出邻接矩阵g*/ void DispMat(MGraph g){ int i,j; for (i=0;i 离散数学作业7 离散数学数理逻辑部分形成性考核书 面作业 本课程形成性考核书面作业共3次,内容主要分别就是集合论部分、图论部分、数理逻辑部分的综合练习,基本上就是按照考试的题型(除单项选择题外)安排练习题目,目的就是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业就是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”与“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值就是 T 或1 . 2.设P :她生病了,Q :她出差了.R :我同意她不参加学习、 则命题“如果她生病或出差了,我就同意她不参加学习”符号化的结果为 (P ∨Q)→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式就是 )()(R Q P R Q P ?∧∧∨∧∧ . 4.设P (x ):x 就是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ))()((x Q x P x ∧? . 5.设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 ))()(())()((b B a B b A a A ∧∨∨ . 6.设个体域D ＝{1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 F 或0 . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天就是天晴”翻译成命题公式. P 。，P 则今天是天晴设答:: 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. Q 。P ；，Q P ∧则小李去旅游小王去旅游设答::: 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. Q 。P ；，Q P →则我去滑雪明天下雪设答;:: 4.请将语句“她去旅游,仅当她有时间.”翻译成命题公式. 份考试离散数学第一次 作业精选文档 TTMS system office room 【TTMS16H-TTMS2A-TTMS8Q8- 2014年9月份考试离散数学第一次作业 一、单项选择题（本大题共42分，共 21 小题，每小题 2 分） 1. 下列语句中是命题的只有（） A. 在实数范围内，x2+y2>=0 B. 在实数范围内，x+y C. 请回答这个问题 D. 真正有学问的人怎么回不关心政治呢？ 2. 设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算， 4. 下述是命题且真值为真的是（） A. 下个月8日是晴天 B. 他真年轻啊！ C. 长方形面积等于长乘以宽 D. 每个月至少有29天 5. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 6. .以下命题公式中，为永假式的是（） A. .p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) 7. 设A={Φ}，B=P（P（A）），以下不正确的式子是（）。 A. {{Φ}，{{Φ}}，{Φ，{Φ}}}包含于B B. {{{Φ}}}包含于B C. {{Φ，{Φ}}}包含于B D. {{Φ}，{{Φ，{Φ}}}}包含于B 8. 无向图结点之间的连通性，是结点集之间的一个（） A. 连通关系 B. 偏序关系 C. 等价关系 D. 函数关系 9. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射离散数学作业
离散数学实验报告
离散数学(大作业)与答案
北邮离散数学第一次阶段作业
离散数学实验报告
离散数学作业(2)
《离散数学》第一次在线作业
离散数学作业
2013年9月份考试离散数学第一次作业
离散数学实验报告--四个实验!!!
离散数学作业
离散数学第一次作业(命题逻辑) 1、证明下列各式是重言式
离散数学实验报告()
离散数学作业答案
离散数学实验报告
华南理工离散数学作业题2017版
2013华工离散数学作业
离散数学实验报告
离散数学作业答案一
份考试离散数学第一次作业精选文档
相关主题
文本预览