离散数学数理规律部分期末复习题

本文格式为Word版，下载可任意编辑——离散数学数理规律部分期末复习题个人收集整理仅供参考学习

离散数学数理规律部分综合练习辅导

一、单项选择题

1．设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时〞符号化为()．

A．Q?PB．P?QC．P?QD．?P??Q由于语句“仅当我有时间时〞是“我将去打球〞的必要条件，所以选项B是正确的．正确答案：B

一般地，当语句是由“……，仅当……〞组成，它的符号化用条件联结词?．问：假使把“我将去打球〞改成“我将去学习〞、“我将去旅游〞等，会符号化吗？

2．设命题公式G：?P?(Q?R)，则使公式G取真值为1的P，Q，R赋值分别是()．

A．0,0,0B．0,0,1C．0,1,0D．1,0,0个人收集整理勿做商业用途当P为真值为1时，?P的真值为0，无论(Q?R)的真值是1还是0，命题公式G的真值为1．所以选项D是正确的．正确答案：D

3．命题公式P?Q的合取范式是()．

A．P?QB．（P?Q）?（P?Q）C．P?QD．?（?P??Q）复习合取范式的定义：

定义6.6.2一个命题公式称为合取范式，当且仅当它具有形式：

A1∧A2∧…∧An，（n?1）

其中A1，A2，…，An均是由命题变元或其否定所组成的析取式．

由此可知，选项B和D是错的．又由于P?Q与P?Q不是等价的，选项A是错的．所以，选项C是正确的．正确答案：C

4．命题公式?(P?Q)的析取范式是()．A．P??QB?P?QC．?P?QD．P??Q

复习析取范式的定义：

定义6.6.3一个命题公式称为析取范式，当且仅当它具有形式：

A1∨A2∨…∨An，（n?1）

其中A1，A2，…，An均是有命题变元或其否定所组成的合取式．

公式?(P?Q)与P??Q是等价的，P??Q满足析取范式的定义，所以，

0/6

个人收集整理仅供参考学习

选项A是正确的．正确答案：A

5．以下公式成立的为()．

A．?P??Q?P?QB．P??Q??P?QC．Q?P?PD．?P?(P?Q)?Q由于：?P?(P?Q)?Q所以，选项D是正确的．正确答案：D

6．以下公式()为重言式．

A．?P??Q?P?QB．(Q?(P?Q))?(?Q?(P?Q))C．(P?(?Q?P))?(?P?(P?Q))D．(?P?(P?Q))?Q

(P?(?Q?P))??P?(Q?P)，(?P?(P?Q))?P?(?P?Q)

所以，C是重言式，也就是永真式．正确答案：C

说明：假使题目改为“以下公式()为永真式〞，应当是一样的．7．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生〞可符号化为（）．

A．(?x)(A(x)?B(x))B．?(?x)(A(x)?B(x))C．?(?x)(A(x)?B(x))D．?(?x)(A(x)??B(x))

由题设知道，A(x)?B(x)表示只要是人，就是学生，而“不是所有〞应当用全称量词的否定，即??x，得到公式C．个人收集整理勿做商业用途正确答案：C

8．设C(x)：x是国家级运动员，G(x)：x是顽强的，则命题“没有一个国家级运动员不是顽强的〞可符号化为()．个人收集整理勿做商业用途A．??x(C(x)??G(x))B．??x(C(x)??G(x))

C．??x(C(x)??G(x))D．??x(C(x)??G(x))

由题设知道，C(x)??G(x)表示国家级运动员不是顽强的，而“没有一个〞就是“不存在一个〞，因此用存在量词的否定，即??x，得到公式D．个人收集整理勿做商业用途正确答案：D

9．表达式?x(P(x,y)?Q(z))??y(R(x,y)??zQ(z))中?x的辖域是()．A．P(x,y)B．P(x,y)?Q(z)C．R(x,y)D．P(x,y)?R(x,y)个人收集整理勿做商业用途所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域〞．那么看题中紧接于量词?x之后最小的子公式是什么呢？显然是P(x,y)?Q(z)，因此，选项B是正确的．个人收集整理勿做商业用途1/6

个人收集整理仅供参考学习

正确答案：B

10．在谓词公式(?x)(A(x)→B(x)?C(x，y))中，（）．A．x，y都是约束变元B．x，y都是自由变元

C．x是约束变元，y都是自由变元D．x是自由变元，y都是约束变元约束变元就是受相应的量词约束的变元．而自由变元就是不受任何量词约束的变元．所以选项C是正确的．正确答案：C

注：假使该题改为填写约束变元或自由变元的填空题，大家也应当把握．二、填空题

1．命题公式P?(Q?P)的真值是．

由于P?(Q?P)??P?(Q?P)?1，所以应当填写：1．应当填写：1

问：命题公式Q?Q、Q??Q的真值是什么？

2．设P：他生病了，Q：他出差了．R：我同意他不参与学习.则命题“假使他生病或出差了，我就同意他不参与学习〞符号化的结果为．个人收集整理勿做商业用途一般地，当语句是由“假使……，那么……〞，或“若……，则……〞组成，它的符号化用条件联结词?．应当填写：(P?Q)?R

3．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是．复习主析取范式的定义：

定义6.6.5对于给定的命题变元，假使有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式．个人收集整理勿做商业用途而小项的定义是：

定义6.6.4n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必需出现且仅出现一次．个人收集整理勿做商业用途由小项的定义知道，命题公式P?Q中缺少命题变项R与它的否定，因此，应当补上，即

P?Q?P?Q?(R??R)?(P?Q?R)?(P?Q??R)

得到命题公式P?Q的主析取范式．应当填写：(P?Q?R)?(P?Q??R)

4．设个体域D＝{a,b},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为．由于在有限个体域下，消除量词的规则为：设D＝{a1,a2,…,an}，则所以，应当填写：(A(a)?A(b))?(B(a)?B(b))应当填写：(A(a)?A(b))?(B(a)?B(b))

假使个体域是D＝{1,2}，D={a,b,c},或谓词公式变为?x(A(x)?B(x))，怎么做?

2/6

个人收集整理仅供参考学习

5．设个体域D＝{1,2,3}，A(x)为“x小于3〞，则谓词公式(?x)A(x)的真值为．

由于(?x)A(x)?A(1)?A(2)?A(3)?1?1?0?1应当填写：1

6．谓词命题公式(?x)((A(x)?B(x))?C(y))中的自由变元为．

由于自由变元就是不受任何量词约束的变元，在公式(?x)((A(x)?B(x))?C(y))中，y是不受全称量词?约束的变元．所以应当填写：y．个人收集整理勿做商业用途应当填写：y

问:公式中的约束变元是什么?

三、公式翻译题

1．请将语句“今天是天晴〞翻译成命题公式．

解：设P：今天是天晴；

则命题公式为：P．

问：“今天不是天晴〞的命题公式是什么？

2．请将语句“小王去旅游，小李也去旅游．〞翻译成命题公式．

解：设P：小王去旅游，Q：小李去旅游，则命题公式为：P?Q．

注：语句中包含“也〞、“且〞、“但〞等连接词，命题公式要用合取“?〞3．请将语句“他去旅游，仅当他有时间．〞翻译成命题公式．

解：设P：他去旅游，Q：他有时间，则命题公式为：P?Q．

4．请将语句“所有人都努力工作．〞翻译成谓词公式．解：设P(x)：x是人，Q(x)：x努力工作．谓词公式为：(?x)(P(x)?Q(x))．

四、判断说明题（判断以下各题，并说明理由．）1．命题公式?P?P的真值是1．

解错误．

由于?P?P是永假式（教材167页的否定律）．2．命题公式?P∧(P??Q)∨P为永真式．解：正确由于，由真值表

PQ?P?QP??Q?P∧(P→?Q)∨P0011110110113/6

．个人收集整理仅供参考学习

110100101011可知，该命题公式为永真式．注：假使题目改为该命题公式为永假式，如何判断并说明理由？3．下面的推理是否正确，请给予说明．

(1)(?x)A(x)?B(x)前提引入

(2)A(y)?B(y)US(1)第2步应为：A(y)?B(x)

由于A(x)中的x是约束变元，而B(x)中的x是自由变元，换名时，约束变元与自由变元不能混淆．

五．计算题

1．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式．解P?Q?R??P?Q?R（析取范式、合取范式、主合取范式）?(?P?(Q??Q)?(R??R))?((P??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)?(?P??Q?R)（?对?的分派律）

个人收集整理勿做商业用途?(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(?P?Q?R)

?(P??Q?R)?(P?Q??R)?(P?Q?R)（主析取范式）

个人收集整理勿做商业用途注：假使题目只是求“析取范式〞或“合取范式〞，大家一定不要再进一步求“主析取范式〞或“主合取范式〞．

2．设谓词公式(?x)(P(x,y)?(?z)Q(y,x,z))?(?y)R(y,z)．（1）试写出量词的辖域；

（2）指出该公式的自由变元和约束变元．解（1）量词?x的辖域为P(x,y)??zQ(y,x,z)，

?z的辖域为Q(y,x,z)，

?y的辖域为R(y,z)．

（2）自由变元为P(x,y)??zQ(y,x,z)中的y，R(y,z)中的z．

约束变元为P(x,y)??zQ(y,x,z)中的x，Q(y,x,z)中的z，R(y,z)中的y．3．设个体域为D={a1,a2}，求谓词公式?y?xP(x,y)消去量词后的等值式．

解：?y?xP(x,y)?(?xP(x,a1))?(?xP(x,a2))?(P(a1,a1)?P(a2,a1))?(P(a1,a2)?P(a2,a2))

4/6

个人收集整理仅供参考学习

六、证明题

1．试证明命题公式(P?(Q??R))??P?Q与?（P??Q）等价．证：(P?(Q??R))??P?Q?(?P?(Q??R))??P?Q?((?P?Q??R)??P)?Q

??P?Q（吸收律）??(P??Q)（摩根律）

2．试证明(?x)(P(x)?R(x))?(?x)P(x)?(?x)R(x)．分析：前提：(?x)(P(x)?R(x))，

结论：(?x)P(x)?(?x)R(x)．证明(1)(?x)(P(x)?R(x))P

(2)P(a)