离散数学习题答案
习题一及答案:(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、用真值表法求下面公式的主析取范式:
(1)()()p q p r ∨∨?∧
解:公式的真值表如下:
由真值表可以看出成真赋值的情况有7种,此7种成真赋值所对应的极小项的析取即为主析取范式,故主析取范式1234567m m m m m m m ?∨∨∨∨∨∨
习题三及答案:(P52-54)
11、填充下面推理证明中没有写出的推理规则。
前提:,,,p q q r r s p ?∨?∨→
结论:s
证明:
① p 前提引入
② p q ?∨ 前提引入
③ q ①②析取三段论
④ q r ?∨ 前提引入
⑤ r ③④析取三段论
⑥ r s → 前提引入
⑦ s ⑤⑥假言推理
15、在自然推理系统P 中用附加前提法证明下面推理:
(2)前提:()(),()p q r s s t u ∨→∧∨→
结论:p u →
证明:用附加前提证明法。
① p 附加前提引入
② p q ∨ ①附加
③ ()()p q r s ∨→∧ 前提引入
④ r s ∧ ②③假言推理
⑤ s ④化简
⑥ s t ∨ ⑤附加
⑦ ()s t u ∨→ 前提引入
⑧ u ⑥⑦假言推理
故推理正确。
16、在自然推理系统P 中用归谬法证明下面推理:
(1)前提:p q →?,r q ?∨,r s ∧?
结论:p ?
证明:用归谬法
① p 结论的否定引入
② p q →? 前提引入
③ q ? ①②假言推理
④ r q ?∨ 前提引入
⑤ r ? ③④析取三段论
⑥ r s ∧? 前提引入
⑦ r ⑥化简
⑧r r ∧? ⑤⑦合取
由于0r r ∧??,所以推理正确。
17、在自然推理系统P 中构造下面推理的证明:
只要A 曾到过受害者房间并且11点以前没离开,A 就是谋杀嫌犯。A 曾到过受害者房间。如果A 在11点以前离开,看门人会看见他。看门人没有看见他。所以,A 是谋杀嫌犯。
解:设p :A 到过受害者房间,q :A 在11点以前离开,r :A 是谋杀嫌犯,s :看门人看见过A 。
则前提:()p q r ∧?→,p ,q s →,s ?
结论:r
证明:
① q s → 前提引入
② s ? 前提引入
③ q ? ①②拒取式
④ p 前提引入
⑤ p q ∧? ③④合取引入
⑥ ()p q r ∧?→ 前提引入
⑦ r ⑤⑥假言推理
习题四及答案:(P65-67)
5、在一阶逻辑中将下列命题符号化:
(2)有的火车比有的汽车快。
解:设F(x):x 是火车,G(y):y 是汽车,H(x,y):x 比y 快;则命题符号化的结果是:
(()()(,))x y F x G y H x y ??∧∧
(3)不存在比所有火车都快的汽车。
解:方法一:
设F(x):x 是汽车,G(y):y 是火车,H(x,y):x 比y 快;则命题符号化的结果是:
(()(()(,)))x F x y G y H x y ??∧?→或(()(()(,)))x F x y G y H x y ?→?∧?
方法二:
设F(x):x 是火车,G(y):y 是汽车,H(x,y):x 比y 快;则命题符号化的结果是:
(()(()(,)))x G x y F y H x y ??∧?→或(()(()(,)))x y G x F y H x y ???∧→
9、给定解释I 如下:
(a) 个体域为实数集合R 。
(b) 特定元素0a
-=。
(c) 函数(,),,f x y x y x y R -=-∈。
(d) 谓词(,):,(,):,,F x y x y G x y x y x y R -
-
=<∈。 给出以下公式在I 下的解释,并指出它们的真值:
(2)(((,),)(,))x y F f x y a G x y ??→
解:解释是:(0)x y x y x y ??-
=→<,含义是:对于任意的实数x ,y ,若x-y=0则x 14、证明下面公式既不是永真式也不是矛盾式: (1)(()(()(,)))x F x y G y H x y ?→?∧ 解:取解释I 如下:个体域为全总个体域, ()F x :x 是兔子,()G y :y 是乌龟,(,)H x y :x 比y 跑得快,则该公式在解释I 下真值是1; 取解释'I 如下:(,)H x y :x 比y 跑得慢,其它同上,则该公式在解释' I 下真值是0; 故公式(1)既不是永真式也不是矛盾式。 此题答案不唯一,只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。 习题五及答案:(P79-81) 5、给定解释I 如下: (a) 个体域D={3,4} (b) ():(3)4,(4)3f x f f - -- == (c) (,):(3,3)(4,4)0,(3,4)(4,3)1F x y F F F F - ----==== 试求下列公式在I 下的真值: (1) (,)x yF x y ?? 解:方法一:先消去存在量词 (,)((,3)(,4))x yF x y x F x F x ????∨ ((3,3)(3,4))((4,3)(4,4))F F F F ?∨∧∨ (01)(10)?∨∧∨ 1? 15、在自然推理系统N ξ中,构造下面推理的证明: (3)前提:(()())x F x G x ?∨,()xG x ?? 结论:()xF x ? 证明: ① ()xG x ?? 前提引入 ② ()x G x ?? ①置换 ③ ()G c ? ②UI 规则 ④ (()())x F x G x ?∨ 前提引入 ⑤ ()()F c G c ∨ ④UI 规则 ⑥ ()F c ③⑤析取三段论 ⑦ ()xF x ? ⑥EG 规则 *22、在自然推理系统N 中,构造下面推理的证明: ξ (2)凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解:设F(x):x为大学生,G(x):x是勤奋的,c:王晓山 则前提:(()()) ? G c ?→,() x F x G x 结论:() ? F c 证明: ①(()()) ?→前提引入 x F x G x ②()() →①UI规则 F c G c ③() G c ?前提引入 ④() ?②③拒取式 F c 25、在自然推理系统N 中,构造下面推理的证明: ξ 每个科学工作者都是刻苦钻研的,每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者,并且是聪明的。所以,王大海在他的事业中将获得成功。(个体域为人类集合) 解:设F(x):x是科学工作者,G(x):x是刻苦钻研的,H(x):x是聪明的,I(x):x在他的事业中获得成功,c:王大海 则前提:(()()) F c H c ?∧→,()() ∧ x F x G x ?→,(()()()) x G x H x I x 结论:() I c 证明: ①()() ∧前提引入 F c H c ②() F c①化简 ③() H c①化简 ④(()()) x F x G x ?→前提引入 ⑤()() →④UI规则 F c G c ⑥() G c②⑤假言推理 ⑦()() ∧③⑥合取引入 G c H c ⑧(()()()) ?∧→前提引入 x G x H x I x ⑨ ()()()G c H c I c ∧→ ⑧UI 规则 ⑩ ()I c ⑦⑨假言推理 习题六及答案(P99-100) 28、化简下述集合公式: (3)(())(())(())(())A B C A B C A B C A B C --?-???-?? 解:(())(())(())(())A B C A B C A B C A B C --?-???-?? ()()A B A B =-?? A = 30、设A,B,C 代表任意集合,试判断下面命题的真假。如果为真,给出证明;如果为假,给出反例。 (6)()A B A B ?-= 解:该命题为假,()A B A B A ?-=-,如果B A ?=?,则B A B -=,否则 B A B -≠,故B A B -=为假。 举反例如下: {1,2},{1,3},A B ==则(){3}A B A B ?-=≠。 (8)A B A C B C ?=??= 解:该命题为假,举反例如下:如果B ,C 都是A 的子集,则A B A C ?= ?一定成立,但B C =不一定成立,例如:{ 1,2}A =,{1}B =, {2}C =,则A B A C A ?=?=, 但B C ≠。 33、证明集合恒等式: (1)()A B A B A ??=?: 证明:()A B A ??: ()()A B A A =???: ()A B =??? A B =?B A =? 习题七及答案:(P132-135) 26 设{}1,2,3,4,5,6A =,R 为A 上的关系,R 的关系图如图所示: (1)求23,R R 的集合表达式; (2)求r(R), s(R), t(R)的集合表达式。 解:(1)由R 的关系图可得{1,5,2,5,3,1,3,3,4,5R = 所以{}23,1,3,3,R R R =?=,{323,1,3,3,3,5R R R =?=, 可得{}3,1,3,3,3,5,n>=2n R =当; (2){}A r(R)=R I 1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6=U , {}1()R 1,5,5,1,2,5,,3,1,1,3,3,3,4,5,5,4s R R -==U {}232()R R ...R 1,5,2,5,3,1,3,3,3,5,4,5t R R R ===U U U U 41、设A={1,2,3,4},R 为A A ?上的二元关系,,,,a b c d A A ?<><>∈?,,,a b R c d a b c d <><>?+=+ (1)证明R 为等价关系; (2)求R 导出的划分。 (1)只需证明R 具有自反性、对称性和传递性即可,证明过程如下: (a )任取,a b A A ?<>∈?,有a b a b +=+,,,a b R a b ∴<><>,所以R 具有自反性; (b )任取,,,a b c d A A ?<><>∈?,若,,a b R c d <><>, 则有a b c d +=+,c d a b ∴+=+,,,c d R a b ∴<><>,所以R 具有对称性; (c )任取,,,,,a b c d e f A A ?<><><>∈?,若,,a b R c d <><>且,,c d R e f <><>, 则有a b c d +=+且c d e f +=+,a b e f ∴+=+,,,a b R e f ∴<><>,所以R 具有传递性, 综合(a )(b )(c )可知:R 为集合A A ?上的等价关系; (2)先求出集合A A ?的结果: {1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4}A A ?=<><><><><><><><><><><><><><><><> 再分别求集合A A ?各元素的等价类,结果如下: [1,1]{1,1},R <>=<> [1,2][2,1]{1,2,2,1},R R <>=<>=<><> [1,3][2,2][3,1]{1,3,2,2,3,1},R R R <>=<>=<>=<><><> [1,4][2,3][3,2][4,1]{1,4,2,3,3,2,4,1},R R R R <>=<>=<>=<>=<><><><> [2,4][3,3][4,2]{2,4,3,3,4,2},R R R <>=<>=<>=<><><> [3,4][4,3]{3,4,4,3},R R <>=<>=<><> [4,4]{4,4}R <>=<>。 等价关系R 导出的划分就是集合A 关于R 的商集/A R ,而集合A 关于R 的商集/A R 是由R 的所有等价类作为元素构成的集合,所以等价关系R 导出的划分是: {{1,1},{1,2,2,1},{1,3,2,2,3,1},{1,4,2,3,3,2,4,1},{2,4,3,3,4,2},{3,4,4,3},{4,4}}<><><><><><><><><><><><><><><><> 46、分别画出下列各偏序集,A R ≤的哈斯图,并找出A 的极大元、极小元、最大元和最小元。 (1){A ,,,,,,,,,,,,,I R a d a c a b a e b e c e d e ≤=U 解:哈斯图如下: A 的极大元为e 、f ,极小元为a 、f ; A 的最大元和最小元都不存在。 *22、给定{}1,2,3,4A =,A 上的关系{1,3,1,4,2,3,2,4,3,4R =,试 (1)画出R 的关系图; (2)说明解:(1) (2)R 是反自反的,不是自反的; R 的关系图中任意两个顶点如果有边的都是单向边,故R 是反对称的,不是对称 的; R 的关系图中没有发生顶点x 到顶点y 有边、顶点y 到顶点z 有边,但顶点x 到 顶点z 没有边的情况,故R 是传递的。 *48、设,B,S A R 和为偏序集,在集合A B ?上定义关系T 如下: 112211221212,,,A B, ,,a b a b a b T a b a Ra b Sb ?∈??∧ 证明T 为A B ?上的偏序关系。 证明:(1)自反性: 1111 11 1111 112212121111,A B R R S b Sb R b Sb ,,,,T a b a a a a a b T a b a Ra b Sb a b T a b ∈?∴∴∴∧?∧∴Q Q 任取,则: 为偏序关系,具有自反性,为偏序关系,具有自反性,又, ,故具有自反性 (2)反对称性: 1122112222111212 2121122112 122112 1122,,,A B ,,,,R S b b ,,T a b a b a b T a b a b T a b a Ra b Sb a Ra b Sb a Ra a Ra a a b Sb b Sb a b a b ∈?∧∧∴∧=∴∧=∴=任取,若且,则有: (1)(2),又为偏序关系,具有反对称性,所以,又为偏序关系,具有反对称性,所以,故具有反对称性 (3)传递性: 1122331122223311221212 22332323 122313 122313 13131133,,,,A B ,,,,,,,,,R ,S b Sb b Sb ,,T a b a b a b a b T a b a b T a b a b T a b a Ra b Sb a b T a b a Ra b Sb a Ra a Ra a Ra b Sb b Sb a Ra a b T a b ∈??∧?∧∴∧∴∧∴∧?任取,,若且又为偏序关系,具有传递性,所以又为偏序关系,具有传递性,所以,故具有传递性。 综合(1)(2)(3)知T 具有自反性、反对称性和传递性,故T 为A B ?上的偏序关系。 习题九及答案:(P179-180) 8、 S=Q Q,Q S a,b ,x,y a,b x,y ax,ay+b S ?*?∈*=为有理数集,为上的二元运算,有 (1)S *运算在上是否可交换、可结合?是否为幂等的? (2)S *运算是否有单位元、零元?如果有,请指出,并求出中所有可逆元素的逆元。 解:(1) ,a,b xa,xb+y ax,bx+y a,b ,x y x y *==≠*∴*运算不具有交换律 ()()(),a,b c,d ax,bx+y c,d acx,adx+bx+y ,a,b c,d ,*ac,ad+b xac,xad+xb+y acx,adx+bx+y ,a,b c,d x y x y x y x y **=*=**====**∴*而运算有结合律 2a,b s a,b a,b a ,a,b ab b ∈*=+≠∴*任取,则有:运算无幂等律 (2) ()()a,b *,a,b a,b s ax,ay+b a,b a,b s ax a a x 10a,b ay b b ay 0x 10x 1y 0y 0 101010 x y =?∈=?∈?=?-=?∴????+==???-==??∴???==??∴**∴*令对均成立 则有:对均成立 对成立必定有运算的右单位元为,,可验证,也为运算的左单位元, 运算的单位元为, ()()()a,b *,,,a,b s a,b *,,ax,ay+b ,a 1x 0ax x a 1y+b 0ay b y a 1y+b 0a,b s a,b *,,a,b s x y x y x y x y x y x y x y x y =?∈=?=?-=?=?????-=+=???? -=?∈=?∈令,若存在使得对上述等式均成立, 则存在零元,否则不存在零元。 由由于不可能对均成立, 故不可能对均成立,故不存在零元; a,b ,a,b *,e 10 1x ax 1a a ay b 0b y a a 0a,b 1b a a,b ,a a x y x y ==?=?=????≠??+=??=-?? ∴=≠-设元素的逆元为,则令,(当0) 当时,的逆元不存在; 当0时,的逆元是 11、{}S 12S S ?=***设,,...,10,问下面的运算能否与构成代数系统,如果能构成代数系统则说明运算是否满足交换律、结合律,并求运算的单位元和零元。 (3)x y x y *=大于等于和的最小整数; 解:(3)由*运算的定义可知:x y=max(x,y)*, x,y S,x y S S S ∈*∈**有,故运算在上满足封闭性,所以运算与非空集合能构成代数系统; x,y S,x y=max(x,y)=max(y,x)=y ,x ∈***任取有所以运算满足交换律; x,y,z S,x y)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x (y z),∈*****任取有(所以运算满足结合律;x S x 1=max(x,1)=x=max(1,x)=1x,∈***任取,有所以运算的单位元是1; x S x 10=max(x,10)=10=max(10,x)=10x,∈***任取,有所以运算的零元是10; 16、 }}1212V 1,2,3,,1,x y V 5,6,,6x y V V x y x y =??=**设其中表示取和之中较大的数。, 其中表示取和之中较小的数。求出和的所有的子代数。 指出哪些是平凡的子代数,哪些是真子代数。 {}{}{}}}}}}{}1111V 1 V 1,2,3,,1,1,,1,1,2,,1,1,3,,1 V 1,2,3,,1,1,,1 V 1,,1,1,2,,1,1,3,,1??????????解:(1)中运算的单位元是, 的所有的子代数是:; 的平凡的子代数是:; 的真子代数是:; }{}{}{}{}2222V 6V 5,6,,66,,6 V 5,6,,66,,6 V 6,,6******(2)中运算的单位元是, 的所有的子代数是:,; 的平凡的子代数是:,; 的真子代数是:。 习题十一及答案:(P218-219) 1、图给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由 解:(a )、(c )、(f )是格;因为任意两个元素构成的集合都有最小上界和最大下界; (b )不是格,因为{d,e}的最大下界不存在; (d )不是格,因为{b,c}的最小上界不存在; (e )不是格,因为{a,b}的最大下界不存在。 2、下列各集合低于整除关系都构成偏序集,判断哪些偏序集是格。 (1)L={1,2,3,4,5}; (2)L={1,2,3,6,12}; 解:画出哈斯图即可判断出:(1)不是格,(2)是格。 4、设L 是格,求以下公式的对偶式: (2)()()()a b c a b a c ∨∧≤∨∧∨ 解:对偶式为:()()()a b c a b a c ∧∨≥∧∨∧,参见P208页定义。 6、设L 为格,,,a b c L ∈,且a b c ≤≤,证明a b b c ∨=∧。 证明:,,a b a b b ≤∴∨=Q ,,b c b c b ≤∴∧=Q a b b c ∴∨=∧ 9、针对图中的每个格,如果格中的元素存在补元,则求出这些补元。 解: (a )图:a,d 互为补元,其中a 为全下界,d 为全上界,b 和c 都没有补元; (c )图:a,f 互为补元,其中a 为全下界,f 为全上界,c 和d 的补元都是b 和e ,b 和e 的补元都是c 和d ; (f )图:a,f 互为补元,其中a 为全下界,f 为全上界,b 和e 互为补元,c 和d 都没有补元。 10、说明图中每个格是否为分配格、有补格和布尔格,并说明理由。 解: (a )图:是一条链,所以是分配格,b 和c 都没有补元,所以不是有补格,所以不是布尔格; (c )图:a,f 互为补元,c 和d 的补元都是b 和e ,b 和e 的补元都是c 和d ,所以任何元素皆有补元,是有补格;(),c b d c a c ∨∧=∨=Q ()()c b c d f d d ∨∧∨=∧=()()()c b d c b c d ∴∨∧≠∨∧∨,所以∨对∧运算不满足分配律,所以不是分配格,所以不是布尔格; (f )图:经过分析知图(f )对应的格只有2个五元子格:L1={a,c,d,e,f}, L2={a,b,c,d,f}。画出L1和L2的哈斯图可知L1和L2均不同构于钻石格和五角格,根据分配格的充分必要条件(见P213页的定理)得图(f )对应的格是分配格;c 和d 都没有补元,所以不是有补格,所以不是布尔格。 《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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)均有可能 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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. 列出下述集合的全部元素: 1)A={x | x ∈N∧x是偶数∧x<15} 2)B={x|x∈N∧4+x=3} 3)C={x|x是十进制的数字} [解] 1)A={2,4,6,8,10,12,14} 2)B= 3)C={0,1,2,3,4,5,6,7,8,9} 2. 用谓词法表示下列集合: 1){奇整数集合} 2){小于7的非负整数集合} 3){3,5,7,11,13,17,19,23,29} [解] 1){n n∈I∧(?m∈I)(n=2m+1)}; 2){n n∈I∧n≥0∧n<7}; 3){p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性: 1) 2)∈ 3){} 4)∈{} 5){a,b}{a,b,c,{a,b,c}} 6){a,b}∈(a,b,c,{a,b,c}) 7){a,b}{a,b,{{a,b,}}} 8){a,b}∈{a,b,{{a,b,}}} [解]1)真。因为空集是任意集合的子集; 2)假。因为空集不含任何元素; 3)真。因为空集是任意集合的子集; 4)真。因为是集合{}的元素; 5)真。因为{a,b}是集合{a,b,c,{a,b,c}}的子集; 6)假。因为{a,b}不是集合{a,b,c,{a,b,c}}的元素; 7)真。因为{a,b}是集合{a,b,{{a,b}}}的子集; 8)假。因为{a,b}不是集合{a,b,{{a,b}}}的元素。 4. 对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B∈C,则A∈C。 2)如果A∈B∧B∈C,则A∈C。 3)如果A B∧B∈C,则A∈C。 [解] 1)假。例如A={a},B={a,b},C={{a},{b}},从而A∈B∧B∈C但A∈C。 2)假。例如A={a},B={a,{a}},C={{a},{{a}}},从而A∈B∧B∈C,但、A ∈C。 3)假。例如A={a},B={a,b},C={{a},a,b},从而ACB∧B∈.C,但A∈C。5.对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B C,则A∈C。 2)如果A∈B∧B C,则A C。 3)如果A B∧B∈C,则A∈C。 3)如果A B∧B∈C,则A C。 [解] 1)真。因为B C x(x∈B x∈C),因此A∈B A∈C。 2)假。例如A={a},B={{a},{b}},C={{a},{b},{c}}从而A∈B∧B C,但A C。 3)假。例如A={a},B={{a,b}},C={{a,{a,b}},从而A B∧B∈C,但A C。 4)假。例如A={a},B={{a,b}},C={{a,b},b},从而A B∧B∈C,但A C。 6.求下列集合的幂集: 1){a,b,c} 2){a,{b,c}} 3){} 4){,{}} 5){{a,b},{a,a,b},{a,b,a,b}} [解] 1){,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 2){,{a},{{b,c}},{a,{a,b}}} 3){,{}} 4){,{},{{}},{,{}}} 《离散数学》题库与答案 一、选择或填空 (数理逻辑部分) 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) 给我一杯水吧! 答:(1)是,T (2)是,F (3)不是(4)是,T (5)不是(6)不是(命题必须满足是陈述句,不能是疑问句或者祈使句。) 6、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。 答:所有人都不是大学生,有些人不会死(命题的否定就是把命题前提中的量词“换成存在,换成”,然后将命题的结论否定,“且变或或变且”) 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校(2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校答:(1)P ?(注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的)(2)Q P→ ? P? ?(4)Q P? →(3)Q 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 (反证法:假若存在,则(x- 1)*y=0 对所有的x都成立,显然这个与前提条件相矛盾) (2)F (同理)(3)F (同理)(4)T(对任一整数x存在整数y满足条件y=2x 很明显是正确的) 试卷二试题与参考答案 一、填空 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、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b 二、选择 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、下面偏序集( )能构成格。 离散数学试题及答案 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.下列句子中,哪些是命题?在是命题的句子中,哪些是简单命题?哪些是真命题?哪些命题的真值现在还不知道? (1)中国有四大发明. 答:此命题是简单命题,其真值为1. (2)5是无理数. 答:此命题是简单命题,其真值为1. (3)3是素数或4是素数. 答:是命题,但不是简单命题,其真值为1. x+< (4)235 答:不是命题. (5)你去图书馆吗? 答:不是命题. (6)2与3是偶数. 答:是命题,但不是简单命题,其真值为0. (7)刘红与魏新是同学. 答:此命题是简单命题,其真值还不知道. (8)这朵玫瑰花多美丽呀! 答:不是命题. (9)吸烟请到吸烟室去! 答:不是命题. (10)圆的面积等于半径的平方乘以π. 答:此命题是简单命题,其真值为1. (11)只有6是偶数,3才能是2的倍数. 答:是命题,但不是简单命题,其真值为0. (12)8是偶数的充分必要条件是8能被3整除. 答:是命题,但不是简单命题,其真值为0. (13)2008年元旦下大雪. 答:此命题是简单命题,其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:(1)p:中国有四大发明. (2)p:是无理数. (7)p:刘红与魏新是同学. (10)p:圆的面积等于半径的平方乘以π. (13)p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. (1)5是有理数. 答:否定式:5是无理数.p:5是有理数.q:5是无理数.其否定式q的真值为1. (2)25不是无理数. 答:否定式:25是有理数. p :25不是无理数. q :25是有理数. 其否定式q 的真值为1. (3)2.5是自然数. 答:否定式:2.5不是自然数. p :2.5是自然数. q :2.5不是自然数. 其否定式q 的真值为1. (4)ln1是整数. 答:否定式:ln1不是整数. p :ln1是整数. q :ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化,并指出真值. (1)2与5都是素数 答:p :2是素数,q :5是素数,符号化为p q ∧,其真值为1. (2)不但π是无理数,而且自然对数的底e 也是无理数. 答:p :π是无理数,q :自然对数的底e 是无理数,符号化为p q ∧,其真值为1. (3)虽然2是最小的素数,但2不是最小的自然数. 答:p :2是最小的素数,q :2是最小的自然数,符号化为p q ∧?,其真值为1. (4)3是偶素数. 答:p :3是素数,q :3是偶数,符号化为p q ∧,其真值为0. (5)4既不是素数,也不是偶数. 答:p :4是素数,q :4是偶数,符号化为p q ?∧?,其真值为0. 5.将下列命题符号化,并指出真值. (1)2或3是偶数. (2)2或4是偶数. (3)3或5是偶数. (4)3不是偶数或4不是偶数. (5)3不是素数或4不是偶数. 答: p :2是偶数,q :3是偶数,r :3是素数,s :4是偶数, t :5是偶数 (1) 符号化: p q ∨,其真值为1. (2) 符号化:p r ∨,其真值为1. (3) 符号化:r t ∨,其真值为0. (4) 符号化:q s ?∨?,其真值为1. (5) 符号化:r s ?∨?,其真值为0. 6.将下列命题符号化. (1)小丽只能从筐里拿一个苹果或一个梨. 答:p :小丽从筐里拿一个苹果,q :小丽从筐里拿一个梨,符号化为: p q ∨. (2)这学期,刘晓月只能选学英语或日语中的一门外语课. 答:p :刘晓月选学英语,q :刘晓月选学日语,符号化为: ()()p q p q ?∧∨∧?. 7.设p :王冬生于1971年,q :王冬生于1972年,说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表: 本科高等数学离散数学试题及答案 一、填空题 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变成完全图。 常熟理工学院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.设 《离散数学》期末复习题 一、填空题(每空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是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 离散数学试题及答案 一、填空题 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、下列哪些公式为永真蕴含式?( ) (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.公式) ∨ ? ∧的成真赋值为 01;10 ? p∧ ( (q ) p q 2.设p, r为真命题,q, s 为假命题,则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01;10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式,B为重言式,则B A∨的类型为重言式 5.设p, q均为命题,在不能同时为真条件下,p与q的排斥也可以写成p与q的相容或。 二.将下列命题符合化 1. 7不是无理数是不对的。 解:) ? ?,其中p: 7是无理数;或p,其中p: 7是无理数。 (p 2.小刘既不怕吃苦,又很爱钻研。 解:其中 ?p: 小刘怕吃苦,q:小刘很爱钻研 p∧ ,q 3.只有不怕困难,才能战胜困难。 解:p →,其中p: 怕困难,q: 战胜困难 q? 或q →,其中p: 怕困难, q: 战胜困难 p? 4.只要别人有困难,老王就帮助别人,除非困难解决了。 解:) → ?,其中p: 别人有困难,q:老王帮助别人,r: 困难解决了 p (q r→ 或:q ?) (,其中p:别人有困难,q: 老王帮助别人,r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解:q p?,其中p: 整数n是偶数,q: 整数n能被2整除 三、求复合命题的真值 P:2能整除5, q:旧金山是美国的首都, r:在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解:p, q 为假命题,r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r 离散数学课后答案 习题一 6.将下列命题符号化。 (1)小丽只能从框里那一个苹果或一个梨. (2)这学期,刘晓月只能选学英语或日语中的一门外语课. 答: (1)(p Λ?q )ν(?pΛq)其中p:小丽拿一个苹果,q:小丽拿一个梨(2)(p Λ?q )ν(?pΛq)其中p:刘晓月选学英语,q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答: (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学习题答案 习题一及答案:(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、用真值表法求下面公式的主析取范式:山东大学离散数学题库及答案
离散数学题库及答案
离散数学第三版课后习题答案
《离散数学》题库及答案
离散数学试题与答案
离散数学试题及答案精选版
离散数学习题解答
大学本科高等数学《离散数学》试题及答案
离散数学题库
中的幺元是,α的逆元是。 10.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>} = 。 = 。 三、判断题(每题1分,共10分) 1.命题公式是一个矛盾式。() 2.,若,则必有。() 3.设S为集合X上的二元关系,则S是传递的当且仅当(S S)S。() 4.任何一棵二叉树的结点可对应一个前缀码。() 5.代数系统中一个元素的左逆元一定等于该元素的右逆元。() 6.一个有限平面图,面的次数之和等于该图的边数。() 7.A′B = B′A () 8.设*定义在集合A上的一个二元运算,如果A中有关于运算*的左零元θl和右零θr,则A中 有零元。() 9.一个循环群的生成元不是唯一的。() 10.任何一个前缀码都对应一棵二叉树。() 四、解答题(5小题,共30分) 1.(5分)什么是欧拉路?如何用欧拉路判定一个图G是否可一笔画出? 2.(8分)求公式 (P∨Q)R 的主析取范式和主合取范式。中国石油大学大学《离散数学》期末复习题及答案
离散数学试题及答案(1)
山东大学离散数学题库及答案
离散数学章练习题及答案
离散数学课后答案
最新离散数学习题答案