一、填空题（10分，每空1分，请将本题答案填在原题横线．．．．上！） 1、设集合X={0，1，2}，R 是X 上的二元关系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，则R 的关系矩阵M R = 。
2、66,Z <⊕>为模6整数加群， 则由2生成的子群<2>= ，右陪集
<2>⊕65= 。
3、设A 和B 为有限集，|A|=m ，|B|=n ，则有 个从A 到B 的关系，有 个从A 到B 的函数。
4、无向图G 如下图所示，G 的点连通度κ为 ，边连通度λ为 。
5、在上面无向图中，已给出了一棵生成树T （粗边所示），则树枝d 对应的基本割集是 ，弦b 对应的基本回路是 。
6、令F(x)： x 是整数，G(x)：x 是奇数，则“不存在不是奇数的整数”符号化为 。
7、含有三个命题变项P ，Q ，R 的命题公式P?Q 的主析取范式是 （用m i 形式表示最小项）。
二、单选题（20分，每题1分，请将本题答案写在下方表格
中！） A 、{}1111,110,10,0 B 、{}01,001,000,10
C 、{}1101,1001,101,110,
D 、{}abc aba ac aa c b ,,,,, 2、下列( )组赋值不是命题公式C ()A B →∨?的成真赋值。
A 、010
B 、011
C 、110
D 、101
3、设A={a ，b ，c ，d}，A 上的等价关系R={，，
A 、{{a ，b}，{c ，d}}
B 、{{a ，b ，d}，{c}}
C 、{{a}，{b}，{c}，{d}}
D 、{{a}，{b ，c}，{d}} 4、二部图3,3K 是( ) 。
A 、欧拉图
B 、 哈密顿图
C 、 非连通图
D 、完全图 5、令p: 我将去上网，q: 我有时间，则“我将去上网，仅当我有时间”可符号化为( )。 (A) q p → (B) q p ? (C)p q → (D)q p ?∨? 6、下面（ ）图不一定是树。
A 、每对结点间都有路的图
B 、无回路的连通图
C 、连通但删去一条边则不连通的图
D 、有n 个顶点n —1条边的连通图
7、集合A = {1, 2, …, 10}上的关系R ={
8、设G 如右图，那么G 不是( )。(A)哈密顿图 (B)完全图 (C)欧拉图
(D)树
9、设图D 的邻接矩阵为???
?
??
?
??????
???01101
101011101100101
11110，则D 的顶点数与边数分别为( ) 。
A 、4， 5
B 、5， 16
C 、4， 10
D 、5， 8
10、下列式子中正确的是（ ）。 A 、?＝1 B 、??? C 、??｛?｝ D 、?＝{?}
11、由2个命题变元p 和q 组成的不等值的命题公式的个数有( )。 (A)2 (B)4 (C) 16 (D) 8
12、给定下列非负整数序列，可构成简单无向图的节点度数序列的为( )。 (A) (1， 3， 4， 4， 5) (B) (1， 1， 2， 2， 2) (C) (0， 1， 3， 3， 5) (D) (1， 1， 2， 2， 3)
13、 4阶完全无向图4K 中含3条边的不同构的生成子图有( )。 (A)5 (B)4 (C)3 (D)2
14、任意12阶群的子群的阶一定不为 ( )。 (A)3 (B)6 (C)8 (D)4 15、在公式x ?F(x ， y)→ ? yG(x ，y)中变元x 是( )。
(A) 既是自由变元，又是约束变元 (B) 既不是自由变元，又不是约束变元 (C) 自由变元 (D) 约束变元
16、设图G=
17、给定公式)()(x xP x xP ?→?，当D={a,b}时，解释( )使该公式真值为0。 (a)=0、P(b)=0 (a)=0、P(b)=1 (a)=1、P(b)=1
18、设A={1 ,2 ,3 }，则A 上有（ ）个二元关系。
A 、23
B 、32
C 、 322
D 、2
32
19、设Z 是整数集合，“+”是数的加法运算，则
20、设R 和S 是集合A={1，2，3，4}上的二元关系，则S 是R 的（ ）闭包。 R = {<1 ，1>，<1 ，2>，<2 ，2>，<2 ，3>，<4 ，4>}
S = {<1 ，1>，<1 ，2>，<2 ，2>，<2 ，3>，<3 ，3>，<4 ，4>} A 、对称 B 、自反 C 、传递 D 、以上都不对 三、求解题（40分，每题8分，请将本题答案写在后面答题纸上！） 1、在自然推理系统中构造证明：
已知张三或李四的彩票中奖了。如果张三的彩票中奖了，那么你会知道张三的彩票中奖了。如果李四的彩票中奖了，那么王五的彩票也中奖了。你不知道张三的彩票中奖了。所以，李四和王五的彩票都中奖了。
2、设A={a,b,c,d,e}，A 上的偏序关系R ＝{
(1) 画出偏序集的哈斯图；
(2) 求子集B={c,d,e}的极大元，极小元，最大元，最小元。
3、求一阶逻辑公式的前束范式：(?xF(x,y) →?yG(y)) → ?xH(x,y,z)。
4、设7个字母在通信中出现的频率如下：a: 35%，b: 20%，c: 15%，d: 10%，e: 10%，
f: 5%，g: 5%，用Huffman 算法求传输它们的最佳前缀码。要求画出最优二叉树，并指出传输100个按上述频率出现的字母，需要多少个二进制数字。
5、
四、证明题（30分，每题7、7、8、8分，请将本题答案写在后面答题纸上！） 1、例如，f 和g 都是群
2、要在七天安排七场考试，同一个老师监的任何两场考试不能安排在接连的两天内进行。假如每个教师最多监四场考试，请证明：安排这样的考试日程表是可以的。
3、设R 是集合A 上一个等价关系，
{,|,(,,)}S x y x y A z x z R z y R =<>∈∧?<>∈∧<>∈，试证明S 也是A 上的一
个等价关系。
4、
参考答案
一、
1、101001110??????????
2、{0，2，4}，{5，1，3}
3、2mn ，n m
4、2，3
5、d,b,c ，bade
6、(F()(x))
或(F()(x))x x G x x G ??∧??→ 7、m6?m7
二、
离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) 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))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (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))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分）
离散数学试题库——填空题 （每空2分） 1 命题: ? ? {{a }} ? {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ . 4. 无孤立点的有限有向图有欧拉路的充分必要条件为: 5.公式))(),(()),()((x S z y R z y x Q x P x →?∨→?的自由变元是 , 约束变元是 . 6.)))()()(()),()(()((x R z Q z y x P y x →?→???的前束范式是 . 7．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶 数） 则 =?B A 。 8．A ，B ，C 。 9．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 10．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 12．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为
则 R= 。 14．图的补图为。15．设A={a，b，c，d} ，A上二元运算如下： 那么代数系统
离散数学试题（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) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（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 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】
一、填空题 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.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则
2016注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．令p : 今天下雪了，q :路滑，r :他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。 A. p q r ∧→ B. p q r ∨→ C. p q r ∧∧ D. p q r ∨? 2.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于0”可符号化为（ B ）。 A. (()((),0))x P x L f x ?∧ B. (()((),0))x P x L f x ?→ C. ()((),0)xP x L f x ?∧ D. ()((),0)xP x L f x ?→ 3.设()F x :x 是人，()G x :x 犯错误，命题“没有不犯错误的人”符号化为（D ）。 A ．(()())x F x G x ?∧ B ． (()())x F x G x ??→? C ．(()())x F x G x ??∧ D ． (()())x F x G x ??∧? *4.下列命题公式不是永真式的是（ A ）。 A . ()p q p →→ B . ()p q p →→ C . ()p q p ?∨→ D . ()p q p →∨ 5．设p ：我们划船，q ：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。 A. p q ∧ B. ()p q ?∧ C. p q ?∧? D. p q ?∧ 6．设()R x :x 为有理数；()Q x :x 为实数。命题“任何有理数都是实数”的符号化为（ A ） A ．()(()())?→x R x Q x B ．()(()())?∧x R x Q x C ．()(()())x R x Q x ?∧ D ．(()())x R x Q x ?→ 7. 设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( C ) A ．()()A a A b ∧ B ．()()A a A b → C ．()()A a A b ∨ D ．()()A b A a → 8．无向图G 有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点， 则G 一共有（ C ）个顶点。
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数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) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 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 的关系图为 离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（） 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。 离散数学试题与答案试卷一 一、填空 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 = 。 8．图的补图为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A B C ?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 3、设A={1，2，3}，则A上的二元关系有（）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） Rο是自反的； A．若R，S 是自反的，则S Rο是反自反的； B．若R，S 是反自反的，则S Rο是对称的； C．若R，S 是对称的，则S Rο是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（ ）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（ ），??x T(x)表示（ ），?x ? T(x)表示（ ），?x(S(x)→P(x))表示（ ），?x(S(x)∧G(x))表示（ ），?x(S(x)∧P(x))表示（ ），?x(S(x)→G(x))表示（ ）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。 二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={ 《离散数学》题库答案 第2，3章(数理逻辑) 1.答：（2），（3），（4） 2.答：（2），（3），（4），（5），（6） 3.答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 4.答：（1）P ?（4）Q P→ ? P? Q→ ?（2）Q P? →（3）Q 5.答：（1） 6.答：2不是偶数且-3不是负数。 7.答：（2） 8.答：?P ，Q→P 9.答：P(x)∨?yR(y) 10.答：??x(R(x)→Q(x)) 11、 a、(P→Q)∧R 解：(P→Q)∧R?(?P∨Q )∧R ?(?P∧R)∨(Q∧R) （析取范式） ?(?P∧(Q∨?Q)∧R)∨((?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) ?m3∨ m1∨m7 （主析取范式） ?m1∨ m3∨m7 ?M0∧M2∧M4∧M5∧M6 （主合取范式） b、Q→(P∨?R) 解：Q→(P∨?R) ??Q∨P∨?R ?M5（主合取范式） ? m0∨ m1∨ m2∨m3∨ m4∨m6 ∨m7 （主析取范式）c、P→(P∧(Q→P)) 解：P→(P∧(Q→P)) ??P∨(P∧(?Q∨P)) ??P∨P ? 1 (主合取范式) ? m0∨ m1∨m2∨ m3 （主析取范式） d、P∨(?P→(Q∨(?Q→R))) 解：P∨(?P→(Q∨(?Q→R))) ? P∨(P∨(Q∨(Q∨R))) ? P∨Q∨R ? M0 (主合取范式) ? m1∨ m2∨m3∨ m4∨ m5∨m6 ∨m7 (主析取范式) 12、 a、P→Q，?Q∨R，?R，?S∨P=>?S 证明： (1) ?R 前提 (2) ?Q∨R 前提 (3)?Q （1），（2）析取三段论 (4) P→Q 前提 (5)?P （3），（4）拒取式 (6)?S∨P 前提 一、判断正误20% （每小题2分） 1、设A.B. C是任意三个集合。 （1）若A∈B且B?C，则A?C。（） （2）若A?B且B∈C，则A?C。（） （3）若A?B且B∈C，则A?C。（） （4）A) ( ) ( ) (C A B A C B ⊕ = ⊕。（） （5）(A–B)?C=(A?C)-(B?C)。（） 2、可能有某种关系，既不是自反的，也不是反自反的。（） ３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（） ４、一个图是平面图，当且仅当它包含与Ｋ 3， 3 或Ｋ 5 在２度结点内同构的子图。（） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（） ６、群是每个元素都有逆元的半群。（） 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．F A F E D D C B A →?→∨∧→∨,。 ２．?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论：?→?)()((x F x S ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%（每小题2分） 《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P 离散数学练习题 1、图中度为零的结点称为孤立结点。 A. 正确 B. 错误 正确：【A】 2、域是整环。 A. 正确 B. 错误 正确：【A】 3、有限格都是有界格。 A. 正确 B. 错误 正确：【A】 4、连通且不含圈的图称为树。 A. 正确 B. 错误 正确：【A】 5、“如果1+1≠3，则2+2≠4”是真命题。 A. 正确 B. 错误 正确：【B】 6、无向图G为欧拉图，则G是连通的。 A. 正确 B. 错误 正确：【A】 7、若A和B都是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A<->B)都是谓词公式。 A. 正确 B. 错误 8、设A, B, C是命题公式，则AVBV﹁C 也是命题公式。 A. 正确 B. 错误 正确：【A】 9、设〈L，≤〉是格，则格的交∧和并∨运算满足等幂律。 A. 正确 B. 错误 正确：【A】 10、“x+3>1。”是命题。 A. 正确 B. 错误 正确：【B】 11、半群满足交换律。 A. 正确 B. 错误 正确：【B】 12、在任何图中，奇数度的结点数必是偶数。 A. 正确 B. 错误 正确：【A】 13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。 A. 正确 B. 错误 正确：【A】 14、完全图Kn没有割集，它的连通性能是最好的。 A. 正确 B. 错误 15、对任意集合A，都有??A。 A. 正确 B. 错误 正确：【A】 17、强连通图一定是单向连通图。 A. 正确 B. 错误 正确：【A】 18、代数系统〈G，°〉为群的条件是存在零元素。 A. 正确 B. 错误 正确：【B】 19、对应日常生活中的“任意的”，“所有的”，“一切的”等词，用符号“任意”表示。 A. 正确 B. 错误 正确：【A】 20、如果a是集合A中的元素，则称a属于A，记作a?A。 A. 正确 B. 错误 正确：【B】 21、A,B是集合,P（A），P（B）为其幂集,且,则P(A)∩P(B)为（） A. B. C. D. 正确：【B】 22、设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)?f2(x)=0的解离散数学题库
离散数学试卷及答案(2)
离散数学期末练习题-(带答案)
离散数学题库及答案
离散数学全部试卷
离散数学 练习题七
离散数学(1-4章)自测题(答案)
离散数学试卷及答案(17)
《离散数学》练习题和参考答案
山东大学离散数学题库及答案
离散数学练习题
相关主题
文本预览