离散数学练习题.doc

《离散数学练习题.doc》由会员分享，可在线阅读，更多相关《离散数学练习题.doc（9页珍藏版）》请在三一办公上搜索。

1、离散数学题库一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=QP (2)Q=PQ (3)P=PQ (4)P(PQ)=P 2、下列公式中哪些是永真式？( )(1)(PQ)(QR) (2)P(QQ) (3)(PQ)P (4)P(PQ)3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=PQ (2) PQ=P (3) PQ=PQ (4)P(PQ)=Q (5) (PQ)=P (6) P(PQ)=P4、公式x(A(x)B(y，x) $z C(y，z)D(x)中，自由变元是( )，约束变元是( )。5、判断下列语句是不是命题。若是，给出命题的真值。( )(1) 北京是中华人

2、民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+818，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。(1)只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校8、设个体域为整数集，则下列公式的意义是( )。(1) x$y(x+y=0) (2) $yx(x+y=0)9、设全体域D是正整数集合，确定下列命题的真值：(1) x$

3、y (xy=y)()(2) $xy(x+y=y)()(3) $xy(x+y=x) ()(4) x$y(y=2x) ()10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 $x(P(x)Q(x)在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)-(3)均成立11、命题“2是偶数或-3是负数”的否定是（ ）。12、永真式的否定是（ ）(1) 永真式(2) 永假式(3) 可满足式(4) (1)-(3)均有可能13、公式(PQ)(PQ)化简为（ ），公式 Q(P(PQ)可化简为（ ）。14、谓词公式x(P(x) $yR(y)Q(x)中量词x的辖域是（ ）。15、

4、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。12指出下列公式哪些是恒真的哪些是恒假的：(1)P（P Q）Q(2)（P Q）（PQ）(3)（P Q） （QR）（P R ）(4)（P Q）（P QP Q）14证明下面的等价式：(1) (P(QR)(QR)(PR)=R(2) P(QP)=P(PQ)(3) P(QR)=(PQ)(PR)(4) (PQ)(RQ)=(PR)Q29试用演绎法证明PQ，QR，PM，M共同蕴涵R(PQ)一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=QP (2)Q=PQ (3)P=PQ (4)P(PQ

5、)=P 答：（1），（4）2、下列公式中哪些是永真式？( )(1)(PQ)(QR) (2)P(QQ) (3)(PQ)P (4)P(PQ) 答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=PQ (2) PQ=P (3) PQ=PQ (4)P(PQ)=Q (5) (PQ)=P (6) P(PQ)=P 答：（2），（3），（4），（5），（6）4、公式x(A(x)B(y，x) $z C(y，z)D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z5、判断下列语句是不是命题。若是，给出命题的真值。( )北京是中华人民共和国的首都。 (2) 陕西师大是

6、一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+818，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是（4） 是，T （5） 不是 （6） 不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。(1)只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） （2） （3） （4）12、永真式的否定是（ ）(1) 永真式(

7、2) 永假式(3) 可满足式(4) (1)-(3)均有可能 答：（2）11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。13、公式(PQ)(PQ)化简为（ ），公式 Q(P(PQ)可化简为（ ）。答：P ，QP1下列语句中不是命题的只有( )A鸡毛也能飞上天？ B或重于泰山，或轻于鸿毛。C不经一事，不长一智。 D牙好，胃口就好。5令p：张三做这件事，q：李四做这件事，则命题“这件事由张三和李四中的一人去做”可符号化为( )Ap q B(pq)(pq)C(pq)(pq) D(pq)(pq)6从真值角度看，命题公式的全部类型是( )A永真式 B永假式C永真式，永假式

8、 D永真式，永假式，可满足式7下述命题公式中，是重言式的为（ ）。A、 ； B、 ；C、 ； D、 。26下列语句中不是命题的只有( )A这个语句是假的。B1+1=2.0C飞碟来自地球外的星球。D凡石头都可练成金。27下列语句是命题的有（ ）。A、明年中秋节的晚上是晴天； B、；C、当且仅当x和y都大于0； D、我正在说谎。28设p：天下大雨，q：他在室内运动，命题“除非天下大雨，否则他不在室内运动”可符合化为( )A. pqB. pqC. pqD. pq29下列各命题中真值为真的命题有（ ）。A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当3不是奇数；C、2+24当且仅当3是奇数；

9、D、2+24当且仅当3不是奇数；30下列命题公式为重言式的是( )Aq（pq）Bp（pq）C（pq）pD（pq）q31下列等价式成立的有（ ）。A、 ； B、 ；C、 ； D、。54下列语句中是真命题的只有( )A宇宙间只有地球上有生命。 B我正在说谎。C大偶数都是两个素数之和。 D17只能被1和它本身整除。55命题“我不能一边听课，一边看小说”的符号化为（ ） ； ； ； 。56设p：我想睡，q：我去学习，命题：“除非我想睡，否则我就去学习”的符号化正确的是( )Apq BpqCpq Dpq57若公式的主析取范式为则它的主合取范式为（ ） ； ； 。59下列命题公式中不是重言式的是( )Ap

10、(qr) Bp(qp)C p(pp) D(p(qr) (q(pr)61下列表达式正确的有（ ） ； ； ； 。4n个命题变元可产生（ ）个互不等价的小项。 n ； n2 ； 2n ； 2n。27、判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。28、公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：（1）营业员A或B盗窃了钻石项链（2）若B作案，则作案时间不在营业时间（3）若A提供的证词正确，则货柜未上锁（4）若A提供的证词不正确，则作案发生在营业时间（5）货柜上了锁试问：

11、作案者是谁？要求写出推理过程。32、在自然推理系统P中，利用附加前提法证明下面推理： 前提：结论： S1设P：我将去市里，Q：我有时间命题“我将去市里，仅当我有时间时”符号化为( )A B C D 正确答案：B因为语句“仅当我有时间时”是“我将去市里”的必要条件，所以答案B是正确的。问：如果把“我将去市里”改成“我将去打球”、“我将去旅游”等，会符号化吗？2设命题公式G：,则使公式G取真值为1的P，Q，R赋值分别是 ( )A0, 0, 0 B0, 0, 1 C0, 1, 0 D1, 0, 0 正确答案：D 由教材162页的条件联结词“”运算的真值表可知，当P取真值时，P取假值，则无论后件QR取

12、真值还是假值，结果都是真的。因此答案D是正确的。3下列公式 ( )为重言式A(P(PQ) Q B(B(AB) (A(AB) C(P(QP)(P(PQ) DABAB正确答案：C 因为： P(PQ) P (PQ) P (PQ) P (P Q) P (Q P) P (Q P) P (Q P) 所以，C是重言式 4命题公式的主析取范式是( )A B C D正确答案：A复习主析取范式的定义：定义6.6.5 对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式而小项的定义是：定义6.6.4 n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存

13、在，但两者必须出现且仅出现一次由此可知，答案C和D是错的。又因为 (P Q ) (P Q) P Q所以，答案A是正确的。二、填空题1命题公式的真值是 应该填写：1因为P(QP) 1，所以应该填写：1。2设P：他生病了，Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 应该填写：(PQ)R一般地，当语句是由“如果，那么”，或“若，则”组成，它的符号化用条件联结词3含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 应该填写：(PQR) (PQR) 关于主析取范式的定义，在单选题的第4题已经复习了，由小项的定义知道，命题公式PQ中缺少命题变

14、项R与它的否定，因此，应该补上，即PQPQ (RR) (PQ R) (PQR)得到命题公式PQ的主析取范式。三、公式翻译题 1请将语句“今天不是天晴”翻译成命题公式解：设P：今天是天晴； 命题公式为： P 2请将语句“我去书店，仅当天不下雨”翻译成命题公式解：设 P：我去书店，Q：天不下雨， 命题公式为：P Q 3请将语句 “有人不去工作”翻译成谓词公式 解：设P(x)：x是人，Q(x)：x去工作， 谓词公式为： ($x)(P(x) Q(x)如果语句是“所有人都不去上课”,那么谓词公式应该怎样呢? 4请将语句“所有人都努力工作”翻译成谓词公式 解：设P(x)：x是人，Q(x)：x努力工作 谓词

15、公式为： (x)(P(x) Q(x)四、判断说明题（判断下列各题，并说明理由） 1命题公式为永假式 解：正确 因为，由真值表 PQQP( QP)( QP) P00100010101010011100可知，该命题公式为永假式 2下面的推理是否正确，请给予说明(1) xA(x)$ xB(x) 前提引入(2) A(y)B(y) US (1) 解：错推理过程应为：(1) xA(x)$xB(x) 前提引入(2) xA(x)$uB(u) T(1)（换名规则）(3) x$u(A(x)B(u) T(2)(4) x(A(x)B(y) ES(3)(5) A(y)B(y) US (4)如果把原题中的推理过程改为(1

16、) (x)A(x) B(x) 前提引入(2) A(y)B(y) US (1)更好些。这个推理的第2步也是错的，正确的应该是：A(y)B(z)，因为约束变元与自由变元不能混淆。五计算题1（1）求命题公式的主析取范式、主合取范式；（2）求该命题公式的成假赋值解：（1） (主析取范式) (主合取范式)（2）因为命题公式的成真赋值是(1, 0)，所以它的成假赋值是(0, 0)，(0, 1)，(1, 1)2求公式的析取、合取、主析取、主合取范式 解： （析取、合取、主合取范式）(P(QQ)(RR)(PP)Q(RR)(PP)(QQ)R) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR

17、) （主析取范式）问: 公式的析取、合取、主析取、主合取范式?六、证明题 1试证明命题公式 (P(QR)PQ与（PQ）等价 证：(P(QR)PQ(P(QR)PQ (PQR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ （吸收律） (PQ) （摩根律） 2试证明 xA(x)xB(x)x(A(x)B(x)分析：前提：xA(x)xB(x)结论：x(A(x)B(x)证：(1) xA(x)P(2) A(a) US(1) (3) xB(x) P(4) B(a) US(3)(5) A(a) B(a) T(2),(4) I (6) x(A(x)B(x) UG(5)下面对本课程的考核做

18、一些说明。 考核对象：本课程的考核是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的学生考核依据：以本课程的教学大纲（2007年6月审定）和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的离散数学 考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式其中终结性考核采用半开卷、笔试方式，试卷满分100分 半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考 考试时间：90分钟试题类型及结构：单项选择题的分数占15，填空题的分数占15，公式翻译题的分数占12，判断说明题的分数占14，计算题的分数占36；证明题的分数占8单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算单项选择题给出四个备选答案，其一是正确选项填空题只需填写正确结论，不写计算、推论过程或理由逻辑公式翻译题主要是利用命题逻辑和谓词逻辑的基本概念及命题联结词、谓词量词，将一个陈述句翻译成命题公式或谓词公式判断说明题是对给定的一个命题或结论作出对与错的判断，并给出简单的说明计算题主要考核学生的基本运算技能和速度，要求写出化简、计算过程证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程。