离散数学自测题
离散数学第一部分 数理逻辑自测题
一、单选题
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．设()P x :x 是鸟，()Q x :x 会飞，命题“有的鸟不会飞”可符号化为（ ）。
A. ()(()())x P x Q x ??→
B. ()(()x P x ??∧())Q x
C. ()(()())x P x Q x ??→
D. ()(()x P x ??∧())Q x 5.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于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 ?∨→
D. ()p q p →∨
8．设()R x :x 为有理数；()Q x :x 为实数。命题“任何有理数都是实数”的符号化为（ ）
A ．()(()())x R x Q x ?∧
B ．()(()())?∧x R x Q x
C ．()(()())?→x R x Q x
D ．(()())x R x Q x ?→ 9.设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( )
A ．()()A a A b ∧
B ．()()A a A b →
C ．()()A a A b ∨
D ．()()A b A a →
10.下列等价式不正确的是（）。
A．(()())()()
?∨??∨?
x P x Q x xP x xQ x
B．(()())()()
?∧??∧?
x P x Q x xP x xQ x
C．(()())()()
x P x Q x xP x xQ x
?∨??∨?
D．(())()
?∧??∧
x P x Q xP x Q
11. 设个体域{,}
?等价的命题公式是( )
xA x
D a b
=，与公式()
A．()()
→
A a A b
A a A b
∧B．()()
C．()()
→
A a A b
A b A a
∨D．()()
12．在公式（x
?）F（x，y）→（?y）G（x，y）中变元x是（）A．自由变元B．约束变元
C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元二、填空题
1．命题公式()
p q
?→的成真赋值为，成假赋值为。
2. 命题公式()
∨→的成真赋值为，成假赋值为。
p q p
3．命题公式()
→∧的成真赋值为 , 成假赋值。
p p q
4．公式()()(()(,))()(,)
??→∧?约束变元为，自由变
x y P y Q x z y R x y
元为。
5．公式(()())(,)
x P x y R y Q x z
?∨?→约束变元为，自由变元为 , 。
6．n个命题变元的___________称为小项，其中每个变元与它的否定不能同时出现，但两者必须___________。
7．前提引入规则：在证明的任何步骤上都可以___________，简称___________ 规则。
8. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是________ ___ 。
9. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是。
10.请写出表示德摩根律的两个命题公式等价定理___________，___________。
三、判断题
1．p?q为真当且仅当p与q同时为真或同时为假。（）
2.(p→q)→r与(p∧q)→r 等值。（）
3．A为矛盾式当且仅当A ? 1.（）
4．任何公式的前束范式都存在，但不唯一。（）
5．一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式。（）
6．在不同个体域内，同一个命题的符号化形式也相同。（）
四、解答题
1．已知命题公式()()
∨→?∨
p q p r
（1）构造真值表；
（2）用等值演算法求公式的主析取范式。
2.证明(p→q)→r?(p∨r)∧(┐q∨r)
3. 构造下面推理的证明：
如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王
今天来开会了。小张今天看到小王。所以小王今天家里没事。
离散数学第二部分 集合论自测题
一、单选题
1．设,,｛｛｝｛｝｛｝｝=?X a b ，则下列陈述正确的是 A.{,}a b X ?
B.
a b X ∈｛｛｝,｛｝｝ C.
X ??｛｝ D.
a X ?｛｛｝｝ 2．设=A B A ，则
A.=A A B
B.=A B B
C.B A -=?
D.B A ?
3．设,,,｛｛｝｝=A a b a b ，则其幂集（）P A 的元素总个数为
A.2
B.3
C.4
D.8
4．集合A={1，2，…，10}上的关系R={
A ．自反的
B ．对称的
C ．传递的、对称的
D ．反自反的、传递的
5. R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t （R ）中元素的是（ ）
A ．<1，1>
B ．<1，2>
C ．<1，3>
D ．<1，4> 6. 设集合A={1，2，3}，下列关系R 中不是等价关系的是（ ）
A.R={<1,1>,<2,2>,<3,3>}
B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}
C.R={<1,1>,<2,2>,<3,3>,<1,2>}
D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 7.设P={x|(x+1)2≤4}，Q={x|x 2+16≥5x},则下列选项正确的是（ ）
A.P ?Q
B.P ?Q
C.Q ?P
D.Q=P 8．设A-B=?，则有（ ）
A ．B=?
B ．B ≠?
C ．A ?B
D ．A ?B
9.A，B是集合，P（A），P（B）为其幂集，且A∩B=?，则P(A)∩P(B)为（）A．?B．{?}
C．{{?}} D．{?，{?}}
10.若R和S是集合A上的两个关系，则下述结论正确的是（）
A．若R和S是自反的，则R∩S是自反的
B．若R和S是对称的，则R S是对称的
C．若R和S是反对称的，则R S是反对称的
D．若R和S是传递的，则R∪S是传递的
二、填空题
1．设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; P(A) - P(B)＝ __________________________ .
2. 设有限集合A, |A| = n, 则 |P(A×A)| = __________________________.
3.设集合 A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________, 其中双射的是__________________________.
4.设A={1，2}，B={2，3}，则A⊕A=__________，A⊕B=__________。
5．设A、B为两个集合, A={1,2,4},B= {3,4}, 则从A?B＝_________________；A?B＝_______________________；A－B＝ _____________________。
6. 设R是集合A上的等价关系，则R所具有的关系的三个特性是___ __ _________, ____________________, _____________________。
7． A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵M R 中m24=______,m34=_____
8. 集合X={a，b，c，d}上二元关系R={ d>， 9. 设有限集A, B，|A| = m, |B| = n, 则| |P(A?B)| = ______________________ 。 10.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为____________________________________。 三、判断题 1．自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是。（） 2.设f：Z+→R，f(x)=ln x，Z+为正整数集，则f既是单射又是满射。（）3．若R是自反的，则s(R)与t(R)也是自反的.（） 4．A×B＝A×C B＝C。（） 5．A-(B×C)＝(A-B)×(A-C)。（） 6．若R1和R2是传递的，则R1∩R2也是传递的。（） 四、解答题 1．若集合A={a，{b，c}}的幂集为P(A)，集合B={ O/，{ O/}}的幂集为P(B)， 求P(A)∩P(B)。 2.设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}. (1) 试写出R和S的关系矩阵； (2) 计算R?S, R∪S, R－1, S－1?R－1. 3. 设X={1，2，3，4}，R是X上的二元关系， R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。 （1）画出R的关系图； （2）写出R的关系矩阵； （3）说明R是否具有自反、反自反、对称、传递性质。 4.设A ＝{a ，b ，c}，R 是A 上的二元关系，且R ＝{，}，求r(R)、s(R)和t(R)。 5.设集合}654321{，，，，，A 上的关系{(1,1,1,3,1,6,2,2,R =><><><> 2,5,3,1,3,3,3,6,4,4,5,2,5,5,6,1,6,3),6,6} <><><><><><><><><<>（1）画出R 的关系图，并写出R 的关系矩阵； （2）R 是否为等价关系？若是，写出R 的所有等价类。 离散数学第三部分代数系统 离散数学第四部分图论 一、单选题 1．设简单图G所有结点的度数之和为50，则G的边数为（）。 A. 50 B. 25 C. 10 D. 5 2．设简单无向图G是一个有5个顶点的4－正则图，则G有（）条边。 A. 4 B. 5 C. 10 D. 20 3．设Z为整数集，A为集合，A的幂集为P(A)，+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 4．下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z， Z是整数集， 定义为x xy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 5.下列集合对所给的二元运算封闭的是（） A.正整数集上的减法运算 B.在正实数的集R+上规定*为a*b=ab-a-b ?a,b∈R+ C.正整数集Z+上的二元运算*为x*y=min(x,y) ?x,y∈Z+ D.全体n×n实可逆矩阵集合R n×n上的矩阵加法 6.设集合A={1，2，3，……，10}，下列定义的运算关于集合A是不封闭的是 （） A．x*y=max{x,y} B．x*y=min{x,y} C．x*y=GCD{x,y},即x,y的最大公约数 D．x*y=LCM{x,y},即x,y的最小公倍数 7.设H，K是群（G， ）的子群，下面代数系统是（G， ）的子群的是（） A．（H∩K， ）B．（H∪K， ） C．（K-H， ）D．（H-K， ） 8. 设A是整数集，下列说法正确的是( ) A. B. C. D. 9.设简单图G所有结点的度数之和为12，则G一定有（） A．3条边B．4条边 C．5条边D．6条边 10. .设简单无向图G是一个有6个顶点的5－正则图，则G有( )条边。 A. 5 B. 6 C. 15 D. 30 11. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（）。 A. (1,2,2,3,4,5) B. (1,2,3,4,5,5) C. (1,1,1,2,3) D. (2,3,3,4,5,6) 12．设G为任意n阶无向简单图，则有（） A．Δ(G)＜n+1 B．Δ(G)≤n－1 C．Δ(G)＞n D．Δ(G)≥n 13.右图的最小入度是( ) A.0 B.1 C.2 D.3 14.右图的最大出度是（） A．0 B．1 C．2 D．3 15.设*是集合A上的二元运算，下列说法正确的是（） A．在A中有关于运算*的左幺元一定有右幺元 B．在A中有关于运算*的左右幺元一定有幺元 C．在A中有关于运算*的左右幺元，它们不一定相同 D．在A中有关于运算*的幺元不一定有左右幺元 二、填空题 1．对代数系统 2. 有理数集Q 中的*运算定义如下：a*b=a+b-ab ，则*运算的单位元是__________，设a 有逆元，则其逆元1a - =__________。 3．设S 是非空有限集，代数系统 中，其中P （S ）为集合S 的幂集，则P （S ）对∪运算的单位元是________，零元是________。 4．无向图G= 度δ(G)=_____________。 5．在实数集R 上定义运算a b=a+b+ab ，则幺元为________，元素2的逆元为________。 6．K n 是个结点的完全图，则K 5有_______条边，每个结点的度数为__________。 7.如右图中，结点v2的度数是________。 8.如右图中，结点v2的度数是________整数集Z 中的运算*定义如下：,,*4a b z a b a b ab ?∈=+-，则Z 中关于*运算的幺元为______；设a 有逆元，则其逆元1 a -为______。 三、判断题 1．任何无向图中，各顶点度数之和等于边数的两倍。（ ） 2. 设非负整数列d ＝(d 1，d 2，…，d n )，则d 是可图化的当且仅当1为奇数。n i i d =∑ （ ） 3．G 为任意n 阶无向简单图，则△(G)≤n+1.（ ） 4．n 阶k-正则图中，边数m ＝（kn+1）/2。（ ） 5．对于顶点标定的无向图，它的度数列可以不唯一的。（ ） 6．积代数一定能保留因子代数中的消去律性质。（ ） 四、解答题 1．给定下列4个图（前两个为无向图，后二个为有向图）的集合表示，试画出它们的图形表示。 ,,111>= 222,,G V E =<>其中21V V =，21223344551{(,),(,),(,),(,),(,)}E v v v v v v v v v v = ； 133,,D V E =<>其中31V V =，31223324551{(,), (,),(,),(,),(,)}E v v v v v v v v v v =； 244,,D V E =<>其中41V V =，41225523443{(,),(,),(,),(,),(,)}E v v v v v v v v v v = 2. 判断下列各非负整数列哪些是可图化的，哪些是可简单图化的。 (1) (5,5,4,4,2,1) (2) (5,4,3,2,2) (3) (4,4,3,3,2,2) 3．（1）设{0,1,2}A =，给出幂集合()P A 对称差运算的运算表。 （2）设6{0,1,2,3,4,5}Z =，给出模6加运算的运算的运算表。 4.设S={1,2,3,4}，定义S 上的二元运算*如下： x*y=(xy) mod 5任意x,y 属于S 求运算*的运算表. 5.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元. 离散数学试题库——填空题 （每空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分） 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={ 离散数学考试题(后附详细答案) 一、命题符号化（共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分） 离散数学试题及答案 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)},则 湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：[ ] 考试科目名称：离散数学 一、试卷结构 1) 试卷成绩及考试时间 考试时间为180分钟。 2)答题方式：闭卷，笔试 3)试卷内容结构 （一）数理逻辑约30% （二）集合论约30% （三）图论约20% （四）代数结构约20% 4)题型结构 a: 选择题约30% b: 计算题约20% c: 证明题约20% d: 应用题约30% 二、考试内容与考试要求 (一)数理逻辑（30%） 考试内容： 命题与命题的真值，五个基本联结词，命题符号化，合式公式真值表，合式公式的类型，等价式、蕴含式的证明，范式和判定问题，求主范式的方法，变元、谓词和量词，量词的辖域、前束范式，合式公式的解释、求合式公式在给定解释下真值的方法。 考试要求： （1）理解命题与命题的真值、联结词、合式公式与真值表、变元、谓词和量词等概念．（2）掌握合式公式的类型、等价式、蕴含式的证明、求主范式的方法、合式公式的解释、以及求在给定解释下真值的方法． （3）了解量词的辖域、前束范式． (二)集合论（30%） 考试内容： 集合及其表示，集合的运算与性质，二元关系的概念，二元关系的五种性质，关系矩阵与关系图，关系的各种运算与性质，关系闭包与性质，相容关系，等价关系，序关系，部分函数、满射、内射、双射的概念，可逆、左可逆、右可逆函数，特征函数，集合的基数与性质。 考试要求： （1）熟练进行集合的并交差补运算，集合之间的关系判定，幂集运算，二元关系的自反、对称、传递性质判定，熟练求解二元关系的自反、对称、传递闭包，熟练求解偏序集中的特殊元素； （2）熟练进行函数的判定，函数的性质判定，函数的复合运算。 (三)图论（20%） 考试内容： 图的基本概念路与回路和连通性图的矩阵表示欧拉图和哈密顿图平面图对偶图与着色树与生成树根树及其应用 考试要求： （1）理解图、路、回路和连通性等基本概念，熟练运用图的结点、边、补图的性质，（2）掌握一些特殊图类的性质，树的特征与应用． (四)代数结构（20%） 考试内容： 二元运算及其性质，代数系统，群、半群、环、格4种典型的代数系统 考试要求： （1）熟练掌握二元运算的性质，理解代数系统概念； （2）了解群、环和格的概念并能进行判定。 离散数学考试试题（A卷及答案） 一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。 证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。 所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。 三、（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 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。 正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。 解设R＝{ 常熟理工学院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．设 2003: 离散部分 1)R是A上的一个对称和传递的关系,对于任意a属于A,都存在一个b属于A,使得 离散数学复习注意事项： 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 )。 离散数学2012年12月28 日 √√计科21101、21102、信科11001、11002 一二三四五六七八 一、单选题: (2分×10=20分) 1.设p:我们听课,q:我们打球.命题“我们不能既听课又打球”符号化为( ). A．┓p→┓q B．┓p∨┓q C．┓(p→q) D．p?┓q 2.设个体域A={a,b},公式?xP(x)∧?yQ(y)消去量词后为( ) A.P(x)∧Q(y) B.P(a)∧P(b)∧(Q(a)∨Q(b)) C.P(a)∧Q(b) D. P(a)∧P(b)∧Q(a)∨Q(b) 3．设A={1,2,3}, 则A上的等价关系有( ) A．3个B．4个C．5个D．6个 4．设Z是整数集，+，·分别是普通加法和乘法，则〈Z，+，·〉是（）A．域B．整环和域C．整环D．含零因子环 5．Q为有理数集，·是普通乘法,则代数系统〈Q，*〉不能构成（）A．群B．独异点C．半群D．交换半群 6．N是自然数集，≤是小于等于关系，则〈N，≤〉是（） A．有界格B．有补格C．分配格D．有补分配格 7．有限布尔代数的元素个数必定等于（） A．2n B．2n C．n2D．3n 8．给定下列序列，可构成无向简单图的度数序列的是（） A．1,1,2,2,3 B．1,1,2,2,2 C．0,1,3,3,3 D．1,3,4,4,5 9．任何无向图中顶点间的连通关系是（） A．偏序关系B．等价关系C．非偏序关系D．非等价关系10．设D=〈V，E〉为有向图，V={a,b,c,d}， E={ 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={ 离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是 （１）（１）写出 和 的关系矩阵。（２）求 及 （1２分） 五、求 的主析取范式和主合取范式。（１０分） 六、设 是 到 的关系， 是 到 的关系，证明： （8分） 七、设 是一个等价关系，设 对某一个 ,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分） 《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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 离散数学考研试题 2009-12-30 19:56:33| 分类：考试类| 标签：|字号大中小订阅 复习题 一、单项选择题 1．下列语句中是真命题的是（D） A．我正在说谎B．严禁吸烟 C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的 2．设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( B ) A. B. C. D. 3．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（D） 4．在公式（）F（x，y）→（y）G（x，y）中变元x是（C） A．自由变元B．约束变元 C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元 5．设个体域是整数集，则下列命题的真值为真的是（C） A．y x(x·y=1) B．x y (x·y≠0) C．x y (x·y=y2) D．y x(x·y=x2) 6．设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( C ) A.R∪IA B.R C.R∪{〈c,a〉} D.R∩IA 7．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（B） A．B．C．D． 8．设R为实数集，函数f：R→R，f(x)=2x，则f是（B） A．满射函数B．入射函数C．双射函数D．非入射非满射 9．设集合A={1，2，3，……，10}，下列定义的运算关于集合A是不封闭的是（D ） A．x*y=max{x,y} B．x*y=min{x,y} C．x*y=GCD{x,y},即x,y的最大公约数D．x*y=LCM{x,y},即x,y的最小公倍数 10．设 离散数学 1.在自然推理系统P 中构造下面推理的证明： 前提：,,p q r q r s ?∨∨?→ 结论：p s →. 3设一阶逻辑公式 ((,)(()()))G x yP x y zQ z R x =???→?→ 试将G 化成与其等价的前束范式。 4.判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。 如果小张今天看到小王，则小王今天来开会了。 小张今天看到小王。所以小王今天家里没事。 5、构造下面推理的证明 前提： ))()(()),()()((x R x F x x H x G x F x ∧?∧→? 结论: ))()()((x G x R x F x ∧∧? 6用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类型。 7分别用真值表法和公式法求(P →(Q ∨R ))∧(?P ∨(Q ?R ))的主析取范式 ，并写出其相应的成真赋值和成假赋值。 8用逻辑推理证明： 所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 9、设A ＝{?，1，{1}}，B ＝{0，{0}}，求P (A )、P (B )－{0}、P (B )⊕B 。 10、设X ＝{1，2，3，4}，R 是X 上的二元关系，R ＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R 的关系图。 (2)写出R 的关系矩阵。 (3)说明R 是否是自反、反自反、对称、传递的。 11、集合X={<1,2>, <3,4>, <5,6>,… }，R={<，其中*是S 上的二元运算，若a ，b ∈S ，且对任意的x ∈S ，都有a*x=x*a=x ，b*x=x*b=b ，则称a 为运算“*”的______________，称b 为运算“*”的______________。100道离散数学填空题分解
离散数学期末考试试题(有几套带答案)
离散数学考试题详细答案
离散数学试题及答案精选版
2020年湖南师范大学029_离散数学-复试
离散数学考试试题(A卷及答案)
离散数学题库
中大复试离散数学
离散数学期末练习题-(带答案)
离散数学题库及答案
离散数学试卷(2012年)
离散数学 练习题七
离散数学期末考试试卷(A卷)
《离散数学》练习题和参考答案
山东大学离散数学题库及答案
离散数学
离散数学题库