离散数学及其应用(徐凤生版)数学习题答案
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t 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 ?∧∧?∨) ()(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 ∨∧∧?
①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 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. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
离散数学图论与系中有图题目
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 The Foundations: Logic and Proofs（逻辑与证明） 1.1 Propositional Logic（命题逻辑） Propositions（命题）——declarative sentence that is either true or false, but not both.判断性语句，正确性唯一。 Truth Table（真值表） Conjunction（合取，“与”，and），Disjunction（析取，or，“相容或”），Exclusive（异或），Negation（非，not），Biconditional（双条件，双向，if and only if） Translating English Sentences 1.2 Propositional Equivalences（命题等价） Tautology（永真式、重言式），Contradiction（永假式、矛盾式），Contingency（偶然式） Logical Equivalences（逻辑等价）——Compound propositions that have the same truth values in all possible cases are called logical equivalent.（真值表相同的式子，p<->q是重言式） Logical Equivalences——Page24 Disjunctive normal form(DNF，析取范式) Conjunctive normal form(CNF，合取范式) 见Page27～29 1.3 Predicates and Quantifiers（谓词和量词） Predicates——谓词，说明关系、特征的修饰词 Quantifiers——量词 ? Universal Quantifier(全称量词) "
离散数学复习题参考带答案
一、选择题：（每题2’） 1、下列语句中不是命题的有（ ）。 A ．离散数学是计算机专业的一门必修课。 B ．鸡有三只脚。 C ．太阳系以外的星球上有生物 。 D ．你打算考硕士研究生吗? 2、命题公式A 与B 是等价的，是指（ ）。 A ． A 与B 有相同的原子变元 B ． A 与B 都是可满足的 C ． 当A 的真值为真时，B 的真值也为真 D ． A 与B 有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（ ）。 A ． 010，100，101，110，111 B ． 010，100，101，111 C ． 全体赋值 D ． 不存在 4、合式公式 (P∧Q)R 的主析取范式中含极小项的个数为（ ）。 A ．2 B ．3 C ．5 D ．0 5、一个公式在等价意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 6、下述公式中是重言式的有（ ）。 A ．(P ∧Q) (P ∨Q) B ．(P Q) (( P Q)∧(Q P)) C ．(P Q)∧Q D ．P (P ∧Q) 7、命题公式 (P Q) ( Q ∨P) 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0 B ．1 C ．2 D ．3 8、若公式 (P∧Q)∨(P∧R) 的主析取范式为 m 001∨m 011∨m 110∨m 111 则它的主合取范式为（ ）。 A ．m 001∧m 011∧m 110∧m 111 B ．M 000∧M 010∧M 100∧M 101 C ．M 001∧M 011∧M 110∧M 111 D ．m 000∧m 010∧m 100∧m 101 9、下列公式中正确的等价式是（ ）。 A ．(x)A(x) ( x)A(x) B ．(x) (y)A(x, y) (y) (x) A(x, y) C ．(x)A(x) (x)A(x) D ．(x) (A(x) ∧B(x)) ( x) A(x) ∨(x) B(x) 10、下列等价关系正确的是（ ）。 A ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) B ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) C ．x ( P(x) Q ) x P(x) Q D ． x ( P(x) Q ) x P(x) Q 11、设个体域为整数集，下列真值为真的公式是（ ）。 A ．x y （x·y=1） B ．x y （x·y=0） C ． x y （x·y=y） D ．x y （x+y=2y ） 12、设S={,{1},{1,2}}，则有（ ）S 。 A ．{{1,2}} B ．{1,2 } C ．{1} D ．{2} 13、下列是真命题的有（ ）。 A ．{a}{{a}} B ．{{}}{,{}} C ．{,{}} D ．{}{,{}}
离散数学测验题--图论部分(优选.)
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
离散数学试题与答案
试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。
离散数学课后习题答案(左孝凌版)
离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。
R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解：
(完整版)离散数学及其应用(课后习题)
习题1.1 2. 指出下列命题是原子命题还是复合命题。 （3）大雁北回，春天来了。 （4）不是东风压倒西风，就是西风压倒东风。 （5）张三和李四在吵架。 解：（3）和（4）是复合命题，（5）是原子命题。 习题1.2 1. 指出下列命题的真值： （1）若224+>，则太阳从西方升起。 解：该命题真值为T （因为命题的前件为假）。 （3）胎生动物当且仅当是哺乳动物。 解：该命题真值为F （如鸭嘴兽虽是哺乳动物，但不是胎生动物）。 2. 令P ：天气好。Q ：我去公园。请将下列命题符号化。 （2）只要天气好，我就去公园。 （3）只有天气好，我才去公园。 （6）天气好，我去公园。 解：（2）P Q →。 （3）Q P →。 （6）P Q ?。 习题1.3 2. 将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）： （1）我去新华书店（P ），仅当我有时间（Q ）。 （3）只要努力学习（P ），成绩就会好的（Q ）。 （6）我今天进城（P ），除非下雨（Q ）。 （10）人不犯我（P ），我不犯人（Q ）；人若犯我，我必犯人。 解：（1）P Q →。 （3）P Q →。 （6）Q P ?→。 （10）()()P Q P Q ?→?∧→。 习题1.4 1. 写出下列公式的真值表： （2）()P Q R ∨→。
解：该公式的真值表如下表： 2. 证明下列等价公式： （2）()()()P Q P Q P Q ∨∧?∧???。 证明： ()(()()) ()()) ()() ()() P Q P Q P Q P Q P Q P Q P Q P Q P Q ????∧∨?∧???∧∧??∧???∧∧∨?∨∧?∧ （4）()()()P Q P R P Q R →∧→?→∧。 证明： ()()()() () () P Q P R P Q P R P Q R P Q R →∧→??∨∧?∨??∨∧?→∧ 3. 甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。乙说：是丁。丙说：是乙。丁说：不是我。已知4个人的回答只有一个人符合实际，问成绩最好的是谁？ 解：设A ：甲成绩最好。B ：乙成绩最好。C ：丙成绩最好。D ：丁成绩最好。 四个人所说的命题分别用P Q R S 、、、表示，则 P A ??；Q A B C D ??∧?∧?∧；R A B C D ??∧∧?∧?；S D ??。 则只有一人符合实际的命题K 符号化为 ()()()() K P Q R S P Q R S P Q R S P Q R S ?∧?∧?∧?∨?∧∧?∧?∨?∧?∧∧?∨?∧?∧?∧
离散数学课后习题答案第二章
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R.
离散数学试题及答案(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变成完全图。
离散数学部分答案
第十四章部分课后习题参考答案 5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(G G δ、?。 解：由握手定理图G 的度数之和为：20102=? 3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2, 所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==?G G δ. 7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求)(),(D D δ?， )(),(D D ++?δ,)(),(D D --?δ. 解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2. 2)(,3)(==?D D δ,1)(,2)(==?++D D δ,1)(,2)(==?--D D δ 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 解：由握手定理图G 的度数之和为：1262=? 设2度点x 个，则1221513=+?+?x ，2=x ，该图有4个顶点. 14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化； 18、设有3个4阶4条边的无向简单图G 1、G 2、G 3，证明它们至少有两个是同构的。 证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以
离散数学章练习题及答案
离散数学练习题 第一章 一．填空 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
离散数学复习题参考带答案
. 一、选择题：（每题2’） 1、下列语句中不是命题的有（）。 A．离散数学是计算机专业的一门必修课。B．鸡有三只脚。 C．太阳系以外的星球上有生物。D．你打算考硕士研究生吗? 2、命题公式A与B是等价的，是指（）。 A．A与B有相同的原子变元B．A与B都是可满足的 C．当A的真值为真时，B的真值也为真D．A与B有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（）。 A．010，100，101，110，111 B．010，100，101，111 C．全体赋值D．不存在 4、合式公式?(P∧Q)→R的主析取范式中含极小项的个数为（）。 A．2 B．3 C．5 D．0 5、一个公式在等价意义下，下面哪个写法是唯一的（）。 A．析取范式B．合取范式C．主析取范式D．以上答案都不对 6、下述公式中是重言式的有（）。 A．(P∧Q) → (P∨Q) B．(P?Q) ? (( P→Q)∧(Q→P)) C．?(P →Q)∧Q D．P →(P∧Q) 7、命题公式(?P→Q) →(?Q∨P)中极小项的个数为（），成真赋值的个数为（）。 A．0 B．1 C．2 D．3 8、若公式(P∧Q)∨(?P∧R) 的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为（）。 A．m001∧m011∧m110∧m111B．M000∧M010∧M100∧M101 C．M001∧M011∧M110∧M111D．m000∧m010∧m100∧m101 9、下列公式中正确的等价式是（）。 A．?(?x)A(x) ? (?x)?A(x) B．(?x) (?y)A(x, y) ? (?y) (?x) A(x, y) C．?(?x)A(x) ? (?x)?A(x) D．(?x) (A(x) ∧B(x)) ? (?x) A(x) ∨(?x) B(x) 10、下列等价关系正确的是（）。 A．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) B．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) C．?x ( P(x) →Q ) ??x P(x) → Q D．?x ( P(x) →Q ) ??x P(x) → Q 11、设个体域为整数集，下列真值为真的公式是（）。 A．?x?y（x·y=1）B．?x?y（x·y=0）C．?x?y（x·y=y）D．?x?y（x+y=2y） 12、设S={?,{1},{1,2}}，则有（）?S。 A．{{1,2}} B．{1,2 } C．{1} D．{2} 13、下列是真命题的有（）。 A．{a}?{{a}} B．{{?}}∈{?,{?}} C．?∈{?,{?}} D．{?}∈{?,{?}} 14、设S={?,{1},{1,2}}，则2S有（）个元素。 A．3 B．6 C．7 D．8
离散数学图论练习题
图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12
离散数学习题答案
离散数学习题答案 习题一及答案：（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 ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567 m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式：
离散数学及应用课后习题答案
离散数学及应用课后习题答案 【篇一：离散数学及其应用图论部分课后习题答案】 p165:习题九 1、给定下面4个图（前两个为无向图，后两个为有向图）的集合 表示，画出它们的图形表 示。 （1）g1??v1,e1?，v1?{v1,v2,v3,v4,v5}， e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)} （2）g2??v2,e2?， v2?v1，e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)} （3） d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v 1?} （4） d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v 3?} 解答：（1） （2） 10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样 的图。 （1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个 奇度顶点 。 14、设g是n(n?2)阶无向简单图，g是它的补图，已 知?(g)?k1,?(g)?k2，求?(g)， ?(g)。 解答：?(g)?n?1?k2；?(g)?n?1?k1。 15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双 射函数。 解答： （c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d）同构，同构函数为 ?1?2??f(x)??3 ?4???5 解答： （1）三条边一共提供6度；所以点度序列可能是
离散数学课后习题答案_(左孝凌版)
1-1，1-2 （1）解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解：、- a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q? (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P?Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式） b)是合式公式 c)不是合式公式（ d)） e)不是合式公式（R和S之间缺少联结词） f)是合式公式。 （2）解： a）A是合式公式，(A∨B)是合式公式，(A→(A∨B))是合式公式。这个过程可以简记为：A；(A∨B)；(A→(A∨B)) 同理可记 b）A；┓A ；(┓A∧B) ；((┓A∧B)∧A) c）A；┓A ；B；(┓A→B) ；(B→A) ；((┓A→B)→(B→A)) d）A；B；(A→B) ；(B→A) ；((A→B)∨(B→A)) （3）解： a）((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b）((B→A)∨(A→B))。 （4）解： a) 是由c) 式进行代换得到，在c) 中用Q代换P, (P→P)代换Q. d) 是由a) 式进行代换得到，在a) 中用P→(Q→P)代换Q. e) 是由b) 式进行代换得到，用R代换P, S代换Q, Q代换R, P代换S.
离散数学(左孝凌)课后习题解答(详细)
离散数学~ 习题1.1 1.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗? ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以 。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。
3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。 ⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：?p→?q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：p?q ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p?q。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：?p→q；该命题是真命题。 ⑶原命题符号化为：p→?q；该命题是假命题。 ⑷原命题符号化为：?p→?q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：p?q；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：p?q；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：p?q；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：p?q；该命题是真命题。