离散数学1-6章练习题及答案
离散数学练习题
第一章
一．填空
1.公式)()(q p q p ∧?∨?∧的成真赋值为 01；10
2.设p, r 为真命题，q, s 为假命题，则复合命题)()(s r q p →??→的真值为 0
3.公式)()()(q p q p q p ∧∨?∧??与共同的成真赋值为 01；10
4.设A 为任意的公式，B 为重言式，则B A ∨的类型为 重言式
5．设p, q 均为命题，在 不能同时为真 条件下，p 与q 的排斥也可以写成p 与q 的相容或。
二．将下列命题符合化 1.
7不是无理数是不对的。
解：)(p ??，其中p:
7是无理数； 或p ，其中p:
7是无理数。
2.小刘既不怕吃苦，又很爱钻研。
解：其中,q p ∧?p: 小刘怕吃苦，q ：小刘很爱钻研
3.只有不怕困难，才能战胜困难。
解：p q ?→，其中p: 怕困难，q: 战胜困难
或q p ?→，其中p: 怕困难， q: 战胜困难
4.只要别人有困难，老王就帮助别人，除非困难解决了。
解：)(q p r →→?，其中p: 别人有困难，q:老王帮助别人 ，r: 困难解决了 或：q p r →∧?)(，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了
5.整数n 是整数当且仅当n 能被2整除。
解：q p ?，其中p: 整数n 是偶数，q: 整数n 能被2整除
三、求复合命题的真值
P ：2能整除5， q ：旧金山是美国的首都， r ：在中国一年分四季 1. ))(())((q p r r q p ∧→∧→∨
2.r q p p r p q ∧?∧?∨∨→→?)(())()(( 解：p, q 为假命题，r 为真命题
1.))(())((q p r r q p ∧→∧→∨的真值为0
2. r q p p r p q ∧?∧?∨∨→→?)(())()((的真值为1
四、判断推理是否正确 设x y 2=为实数，推理如下：
若y 在x=0可导，则y 在x=0连续。y 在x=0连续，所以y 在x=0可导。
解：x y 2=，x 为实数，令p: ｙ在ｘ=0可导，q: y 在x=0连续。P 为假命题，q 为真命题，推理符号化为：p q q p →∧→)(，由p ，q 得真值可知，推理的真值为0，所以推理不正确。
五、判断公式的类型
1，r q p q p p q ∨∧?∨∧→??)))()(()(( 2. )())((q r p q p ∧∧→?∧ 3. )()(r q r p ?→??
由上表可知A 为重言式，B 为矛盾式，C 为可满足式。
第二章练习题
一．填空
1.设A 为含命题变项p, q, r 的重言式，则公式))((→∧∨q p A 的类型为 重言式
2.设B 为含命题变项p, q, r 的重言式，则公式))((→∧∨q p B 的类型为矛盾式
3.设p, q 为命题变项，则)(q p ??的成真赋值为 01 ；10
4．设p,q 为真命题，r, s 为假命题，则复合函数)()(s q r p →???的成真赋值为__0___ 5.矛盾式的主析取范式为___0_____
6.设公式A 为含命题变项p, q, r 又已知A 的主合取范式为M
M M M 5
3
2
∧∧∧则A
的主合取范式为
m m m m 7
6
4
1
∨∨∨
二、用等值演算法求公式的主析取范式或主合取范式 1.求公式)())((p q q p ?→?∨→??的主合取范式。
解：
M q p q p q p q p p q q p 2
)()()())((?∨??→?→∨→??→?∨→??
2.求公式)())()((p q q p q p →?→∧∨的主析取范式，再由主析取范式求出主合取范式。 解：
M M M m q p q q p q p q p q q p q q p q q p q p p q q p q p 2
1030)()())(())(()()())()(()())()((∧∧??∨∧?∧?∨?→→∧→→?→??→?∨?∧∨?→?→∧∨ 三、用其表达式求公式r q p ?→)(的主析取范式。 解：真值表
由上 001；011；100；111
四、将公式)(r q p →→化成与之等值且仅含[]∧?,中连接词的公式 解：)()()()(r q p r q p r q p r q p ?∧∧??∨?∨??∨?→?→→ 五、用主析取范式判断))(()()(q p q p q p ∧?∧∨??与是否等值。 解：
))
(()())(())(()()()()())()(())()(()(p q q p p q q p q p p q q p p q q p p q q p p q q p q p ∧?∧∨??∧∨?∧?∧∨??∧∨?∧?∨??∨∨???∨?∧∨???→∧→????所以他们等值。
第四章 习题 一，填空题
1.设F(x): x 具有性质F ，G(x): x 具有性质G ，命题“对所有x 的而言，若x 具有性质F ，则x 具有性质G ”的符号化形式为 )()((x G x F x →?
2.设F(x): x 具有性质F ，G(x): x 具有性质G ，命题“有的x 既有性质F ，又有性质G ”的符号化形式为 )()((x G x F x ∧?
3. 设F(x): x 具有性质F ，G(y): y 具有性质G ，命题“对所有x 都有性质F ，则所有的y 都有性质G ”的符号化形式为 )()(y yG x xF ?→?
4. 设F(x): x 具有性质F ，G(y): y 具有性质G ，命题“若存在x 具有性质F ，则所有的y 都没有性质G ”的符号化形式为 )()(y G y x xF ??→?
5.设A 为任意一阶逻辑公式，若A 中__不含自由出现的个体项_____,则称A 为封闭的公式。
6.在一阶逻辑中将命题符号化时，若没有指明个体域，则使用 全总 个体域。 二．在一阶逻辑中将下列命题符号化
1.所有的整数，不是负整数就是正整数，或是0。
解：))()()(()(x R x H x G x xF ∨∨→?，其中x x F :)(是整数，
x x G :)(是负整数，x x H :)(是正整数，0:)(=x x R
2.有的实数是有理数，有的实数是无理数。
解：))()(())()((y H y F y x G x F x ∧?∧∧?，其中，x x F :)(是实数，x x G :)(是有理数，
y y H :)(是无理数
3.发明家都是聪明的并且是勤劳的，王进是发明家，所以王进是聪明的并且是勤劳的。 解：))()(())()))()(()(((a H a G a F x H x G x F x ∧→∧∧→?，其中：x x F :)(是发明家，
x x G :)(是聪明的，x x H :)(是勤劳的，:a 王前进
4.实数不都是有理数。
解：))()((x G x F x →??，其中x x F :)(是实数，x x G :)(是有理数 5.不存在能表示成分数的有理数。
解：)()(x G x xF ?→?，其中：x x F :)(是无理数，x x G :)(能表示成分数 6.若x 与y 都是实数且x>y ，则x+y>y+z
解：)),
(),()()(((z y z x H y x H y F x F y x ++→∧∧??，其中，x x F :)(是实数，
y x y x H ≥:),(
三．给定解释I 如下：
（a ）个体域为实数集合R ； (b)特定元素0=a ； (c)特定函数R y R x y x y x f ∈∈-=,,),(
(d)特定谓词R y R x y x y x G y x y x F ∈∈<=,
,
:),(,
:),(
给出下列公式在I 的解释，并指出他们的真值： 1.)),(),((y x F y x G y x ?→??
解：))()((y x y x y x ≠→
解：))(0(y x y x y x <→=-??，即对任意的实数y x ,若,0=-y x 则,y x <其真值为0 3.))),,((),((a y x f F y x G y x ?→??
解：))0()((≠-→
4.)),()),,((y x F a y x Gf y x →??
解：)))0((y x y x y x =→<-??，即对任意的实数y x ,若,0<-y x 则,y x =其真值为0 四．给定解释I 如下：
(a)个体域D=N; (b)特定元素2=a (c)N 上函数;),(,),(y x y x g y x y x f ?=+=
(d)N 上谓词y x y x F =:),(
给出下列公式在I 下的解释，并指出他们的真值： 1.)),,((x a x g xF ?
解：)2(x x x =?，即对任意的自然数x ，都有x x =2，真值为0 2.))),,(()),,(((x a y f F y a x f F y x →??
解：))2()2((x y y x y x =+→=+??，即对任意自然数y x ,若y x =+2，则x y =+2；其真值为0
3.)),,((z y x f zF y x ???
解：)(z y x z y x =+???，即对任意的自然数y x ,，都存在z ，使得z y x =+；真值为1 4.)),(),,((x x g x x f xF ? 解：)2(2
x
x x =?，即存在自然数x 使得x
x 2
2=
，其真值为1
第六章 习题 一，填空
1.设{}{}4,3,,2a A =， {}{}3,,4,a B Φ=，则=⊕B A ____{}{}Φ,3},{,3,,2a a ______
2.设{}{}{}{}2,1,1=A ，则=)(A P ____}}}2,1{{},1{{}}},2,1{{{}},1{{,{Φ_________
3.设{}{}{}2,11=A ，则=)(A P ____{Φ，{{1}}，{{1,2}}，{{1}，{1，,2}}}________
4. 设{
}2,1=A ，则=)(A P ____{Φ，{1}，{2}，{1,2}}_________ 5.设[a,b], (c,d)代表实数区间，那么=-?)3,1(])6,2[]4,0([____[3,4]________
6.设X,Y ,Z 为任意集合，且{
}3,2,1=⊕Y X ，{}4,3,2=⊕Z X ，若,Y Z ∈则一定有___Z Z ∈∈3;2_____
)4;3;2;1(Z Z Z Z ∈∈∈∈
7.设,A 则=-⊕A A A )(______Φ_______ 二，简答题
1.设{}12,2,1 =I ，{}11,9,7,5,3,1=A ，{}11,7,5,3,2=B ，{}12,6,3,2=C ，{}8,4,2=D ，计算：;B A ? C A ?; )(B A C ?-; B A -; D C -; D B ⊕;
=?B A {1,2,3,5,7,9,11} C A ?={3} )(B A C ?-={6, 12} B A -={1, 9}
D C -={3,6,12} D B ⊕={3,4,5,7,8,11}
2.设{}{}{}b a a A ,,=，求：A ?; A ?
A ?={a,b} A ?={a}
三、设{}6,5,4,3,2,1=A ，{}6,4,2=B ，{
}15,,|3
<∈=
=x N n x x C n ，求:
C A ?; A B -; )(B P
C={1,8}
C A ?={1,2,3,4,5,6,8} A B -=Φ
P(B)={ Φ,{2},{4},{6},{2,4},{2,6},{4,6},{2,4,6}}
四：一个班50个学生，在一次考试中有26人得5分，在第二次考试中有21人得5分，如果两次考试中没有得5分的有17人，那么两次考试中都得5分的有都少人？（提示：应用包含排斥原理）
答：设A 为第一次考试得5分的人，B 为第二次考试得5分的人。 A=26,B=21 ~（A ?B ）=17 A ?B=50-17=33 A ?B-A=7
A ?B=21-7=14
五，一个班25个学生，会打篮球的有12人，会打排球的有10人，两种球都不会打的有5人，那么两种球都会打的有多少人？（提示：应用包含排斥原理） 答：设A 为会打篮球的人数，B 为会打排球的人数。 A=12,B=10 ~（A ?B ）=5 A ?B=25-5=20 A ?B-A=8 A ?B=10-8=2
第七章 习题
设?-?=?+?x y y x 2,15,，求x,y 解：由有序相等的充要条件：
???=+-=x y y x 251 解得：?
?
?==76
y x 2.已知}{1,0=A ， {}2,1=B ，试确定下列集合(1)B A ?, (2){}B A ??1 (3)B A A ?? 解：(1){}>><<><><=?2,11,1,2,0,1,0B A
(2)
{}{}{}{}
><><><><=?><><=??2,1,1,1,1,1,2,1,0,1,1,02,11,1,1,01B A
(3)
{}{}
{}
><><><><><><><><=?><><><><=??2,0,1,2,1,1,2,1,0,2,0,0,1,0,1,1,1,1,1,1,0,1,0,02,10,1,1,1,1,0,0,0B A A
P143页13题
设 {}><><><=3,3,4,2,2,1A , {}><><><=2,4,4,2,3,1B 求：B A , B A , ranA B A dom domB domA ),(,,,
解：{}><>><<><><=2,4,3,34,2,3,1,2,1B A {}><=4,2B A {}3,2,1=d o m A {}4,2,1=d o m B {}4,3,2=r a n A
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。
离散数学1-6章练习题及答案
离散数学练习题 第一章 一?填空 1?公式(p q) ( p q)的成真赋值为01; 10 2?设p, r为真命题，q, s为假命题，则复合命题(p q) ( r s)的真值为0 3?公式(p q)与(p q) ( p q)共同的成真赋值为01 ；10 4?设A为任意的公式，B为重言式，则A B的类型为重言式 5. 设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二.将下列命题符合化 1. ■ 7不是无理数是不对的。 解：(p)，其中p：. 7是无理数；或p,其中p: . 7是无理数。 2?小刘既不怕吃苦，又很爱钻研。 解：p q,其中p:小刘怕吃苦，q :小刘很爱钻研 3?只有不怕困难，才能战胜困难。 解：q p，其中p:怕困难，q:战胜困难 或p q，其中p:怕困难，q:战胜困难 4?只要别人有困难，老王就帮助别人，除非困难解决了。 解：r (p q)，其中p:别人有困难，q:老王帮助别人，r:困难解决了 或：(r p) q，其中p：别人有困难，q:老王帮助别人，r:困难解决了 5?整数n是整数当且仅当n能被2整除。 解：p q，其中p:整数n是偶数，q:整数n能被2整除 三、求复合命题的真值 P：2能整除5, q：旧金山是美国的首都，r：在中国一年分四季
1. ((p q) r) (r (p q)) 2?((q p) (r p)) (( p q) r 解：p, q为假命题，r为真命题 1. (( p q) r) (r (p q))的真值为0 2. (( q p) (r p)) (( p q) r 的真值为1 四、判断推理是否正确 设y 2x为实数，推理如下： 若y在x=0可导，则y在x=0连续。y在x=0连续，所以y在x=0可导。 解：y 2x，x为实数，令p: y在x =0可导，q: y在x=0连续。P为假命题，q为真命题，推理符号化为：(p q) q p，由p, q得真值可知，推理的真值为0,所以推理不正确。 五、判断公式的类型 1，( (q p) ((p q) ( p q))) r 2. (p (q p)) (r q) 3. (p r) (q r)
(完整word版)离散数学期末练习题带答案
离散数学复习注意事项： 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为实数。命题“任何有理数都是实数”的符号化为（）
离散数学试题与答案
试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。
离散数学习题三 含答案
离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??
②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。
离散数学章练习题及复习资料
离散数学练习题 第一章 一．填空 1.公式)()(q p q p ∧?∨?∧的成真赋值为 01；10 2.设p, r 为真命题，q, s 为假命题，则复合命题)()(s r q p →??→的真值为 0 3.公式)()()(q p q p q p ∧∨?∧??与共同的成真赋值为 01；10 4.设A 为任意的公式，B 为重言式，则B A ∨的类型为 重言式 5．设p, q 均为命题，在 不能同时为真 条件下，p 与q 的排斥也可以写成p 与q 的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：)(p ??，其中p: 7是无理数； 或p ，其中p: 7是无理数。 2.小刘既不怕吃苦，又很爱钻研。 解：其中,q p ∧?p: 小刘怕吃苦，q ：小刘很爱钻研 3.只有不怕困难，才能战胜困难。 解：p q ?→，其中p: 怕困难，q: 战胜困难 或q p ?→，其中p: 怕困难， q: 战胜困难 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：)(q p r →→?，其中p: 别人有困难，q:老王帮助别人 ，r: 困难解决了 或：q p r →∧?)(，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了 5.整数n 是整数当且仅当n 能被2整除。 解：q p ?，其中p: 整数n 是偶数，q: 整数n 能被2整除 三、求复合命题的真值 P ：2能整除5， q ：旧金山是美国的首都， r ：在中国一年分四季 1. ))(())((q p r r q p ∧→∧→∨ 2.r q p p r p q ∧?∧?∨∨→→?)(())()(( 解：p, q 为假命题，r 为真命题
中国石油大学大学《离散数学》期末复习题及答案
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
16、设A、B为集合，如果集合A的元素都是集合B的元素，则称A是B 的。 17、集合上的三种特殊元是、 及。 18、设A={a, b}，则ρ(A) 的四个元素分别 是：，，，。 19、代数系统是指由及其上的或 组成的系统。 20、设
离散数学试题及答案(1)
离散数学试题及答案 一、填空题 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＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学复习题及标准答案
1. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学结构试题集5-7
第5章 一.填空题 1. 群中有唯一的（）。 2. 如果群运算是可交换的，则群为（）。 3. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y∈A，则称二元运算*在A上是（）。 4. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y*x，则称二元运算*在A上是（）。 5. 设★是定义在有理数集合Q上的二元运算，如果对于Q中任意的两个元素x,y，都有x★y=x+y-x*y，其中*表示普通乘法元算，则二元运算★在Q 上是（）。（填写可交互/不可交换） 6. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x,y,z，都有(x*y)*z=x*(y*z) ，则称二元运算*在A上是（）。 7. 设★是定义在非空集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y， 则二元运算★在A上是（）。（填写可结合/不可结合） 8. 设*，★是定义在集合A上的两个二元运算，如果对于A中任意的元素x,y,z，都有(x*y) ★z=（x★z）*(y★z)，z★(x*y)=(z★x)*(z★y),则称二元运算★对于*在A上是（）。 9. 设*，★是定义在集合A上的两个可交换的二元运算，如果对于A中任意的元素x,y，都有x*(x★y)=x, x★(x*y)=x,则称二元运算*对于★在A上满 足（）。 10. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x，都有x*x=x，则称二元运算*是（）。 11. 设*是定义在集合A上的二元运算，如果在A中存在元素el，对于A中任意的元素x，都有el*x=x，则称el为A中关于运算*的（）。 12. 设*是定义在集合A上的二元运算，如果在A中存在元素ol，对于A中任意的元素x，都有ol*x=x，则称ol为A中关于运算*的（）。 13. 设*是定义在集合A上的二元运算，如果在A中存在元素er，对于A中任意的元素x，都有x*erl =x，则称er为A中关于运算*的（）。 14. 设*是定义在集合A上的二元运算，如果在A中存在元素or，对于A中任意的元素x，都有x*or=x，则称or为A中关于运算*的（）。 15. 如果对于集合中的二元运算*，存在左零元和右零元，且左零元等于右零元，则零元是（）。 16. 如果对于集合中的二元运算*，存在左么元和右么元，且左么元等于右么元，则么元是（）。 17. 设*是定义在集合A上的二元运算，且e是A中关于运算*的么元，如果对于A中的元素x，存在A中的元素y，有y*x=e，则称y为x的 （）。 18. 对于实数域上的乘法元算，每个元素（）逆元。（填写一定有/不一定有） 19. 对于实数域上的加法运算，（）零元。（填写存在/不存在） 20. 对于整数域上的加法运算，（）么元。（填写存在/不存在） 21. 对于非空集合S上二元运算*，是封闭且可结合的，那么
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y 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、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (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设集合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.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题
离散数学王元元习题解答
第三篇图论 第八章图 图的基本知识 内容提要 8.1.1 图的定义及有关术语 定义图（graph）G由三个部分所组成： （1）非空集合V(G)，称为图G的结点集，其成员称为结点或顶点（nodes or vertices）。 （2）集合 E(G)，称为图G的边集，其成员称为边(edges)。 I （3）函数Ψ G ：E(G)→(V(G)，V(G))，称为边与顶点的关联映射（associatve mapping）。 这里（V(G)，V(G)）称为VG的偶对集，其成员偶对（pair）形如（u， v），u，v为结点，它们未必不同。Ψ G (e) = (u,v)时称边e关联端点u，v。当(u,v)用作序偶时(V(G)，V(G)) =V(G) ?V(G)，e称为有向边，e以u为起点,以v为终点, 图G称为有向图（directed graph）；当(u,v)用作无序偶对时，(u,v) = (v,u)，称e为无向边（或边），图G称为无向图（或图）。 图G常用三元序组< V(G)，E(G)，Ψ G >,或< V，E，Ψ>来表示。显然，图是一种数学结构，由两个集合及其间的一个映射所组成。 定义8. 2 设图G为< V，E，Ψ>。 （l）当V和E为有限集时，称G为有限图，否则称G为无限图。本书只讨论有限图。 （2）当Ψ G 为单射时，称G为单图；当Ψ G 为非单射时，称G为重图，
又称满足Ψ(e1) = Ψ(e2)的不同边e1,e2,为重边,或平行边。 （3）当Ψ(e)＝(v,v)（或
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！
最新离散数学习题答案
离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值：
（4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式：