国防科技大学研究生院1999年硕士生入学考试
软件基础试题(可不抄题)
离散数学部分命题标准答案、评分标准
三、离散数学部分(30分)(6分，必要性和充分性各3分)证明
o 1
充分性：
(8分，证出为双射得4分，证出为同态得4分)
o 2a f a f 证明：
i ) 若x ，y G 使 (x) = (y), 即显然有x = y ，这表明为内射。a f a f a f
(8分，证出a GF(a)得4分，证出a GF(a)得4分，证出GFGF(a) GF(a)得4分)。 o 3证明：
因为A 上的半序自反，所以对每个a A 皆有a a ，故由G 和F 保序得F(a) F(a) 且
GF(a) GF(a)。这时取b = F (a) B
i )根据题设，由F(a) b 得a G(b)即a GF(a)。
i i )因为GF(a) A ，所以由题设及GF(a) G(b)得
FGF(a) b 即FGF(a) F(a) 从而再由G 保序得GFGF(a) GF(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 ＝{，，，，，，，，
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
第四章部分课后习题参考答案 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)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):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、下面偏序集( )能构成格。 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每 一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故 G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G 安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设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 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈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 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G= 数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 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) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 一、填空 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 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 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 p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {1,2,3}} ，A B= {< 1,1>，<1,2>，<2，1>，<2，2>，<3，1>，<3， 2> } ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {< 2,2>，<2,3>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷） （时间120分钟） 开课院（系、部）姓名学号. 一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、 4 2= + x； B、我们要努力学习； C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（） A、P Q P→ →) (； B、P P Q∧ → ?) (； C、Q P P? ? ∧) (； D、) (Q P P∨ →。3．在谓词逻辑中，令) (x F表示x是火车；) (y G表示y是汽车；) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的（） I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ； B 、仅III ； C 、I 和II ； D 、都不对。 4．下列结论正确的是：（ ） A 、若C A B A =，则 C B =； B 、若B A B A ?，则B A =； C 、若C A B A =，则C B =； D 、若B A ?且D C ?，则D B C A ?。 5．设φ=1A ，}{2φ=A ，})({3φρ=A ，)(4φρ=A ，以下命题为假的是（ ） A 、42A A ∈； B 、31A A ?； C 、24A A ?； D 、34A A ∈。 6．设R 是集合},,,{d c b a A =上的二元关系， },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真（ ） I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ； B 、仅II ； C 、I 和II ； D 、全真。离散数学试题与答案
(完整版)离散数学作业答案一
离散数学期末试卷A卷及答案
离散数学答案解析屈婉玲版第二版高等教育出版社课后答案解析
离散数学期末试题及答案完整版
吉林大学离散数学课后习题答案
安徽大学期末试卷离散数学上卷及参考答案.doc
离散数学期末试卷及答案
慕课 离散数学 电子科技大学 课后习题十 答案
离散数学试卷及答案
离散数学作业答案
离散数学试卷及答案(1)
国开放大学离散数学本离散数学作业答案
大学《离散数学》期末考试试卷及答案-(1)
相关主题
文本预览