离散数学 习题答案

精品文档离散数学习题答案习题一及答案：（ P14-15 ）14、将下列命题符号化：（ 5）李辛与李末是兄弟解：设 p：李辛与李末是兄弟，则命题符号化的结果是p（ 6）王强与刘威都学过法语解：设 p：王强学过法语； q：刘威学过法语；则命题符号化的结果是p q （ 9）只有天下大雨，他才乘班车上班解：设 p：天下大雨； q：他乘班车上班；则命题符号化的结果是q p（ 11）下雪路滑，他迟到了解：设 p：下雪； q：路滑； r ：他迟到了；则命题符号化的结果是( p q)r15、设 p： 2+3=5.q：大熊猫产在中国 .r：太阳从西方升起 .求下列复合命题的真值：（ 4）(p q r )(( p q)r )解： p=1， q=1，r=0 ，(p q r )(110)1，((p q)r )((11)0)(00)1(p q r )(( p q)r ) 1 1119、用真值表判断下列公式的类型：（ 2）( p p)q解：列出公式的真值表，如下所示：p q p qp) ( p p)q( p001111011010100101110001由真值表可以看出公式有 3 个成真赋值，故公式是非重言式的可满足式。

20、求下列公式的成真赋值：精品文档（ 4）( p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( p q)1p0q0q0所以公式的成真赋值有： 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 )m3m7，此即公式的主析取范式，所以成真赋值为011， 111。

6、求下列公式的主合取范式，并求成假赋值：（ 2）( p q) ( p r )解：原式( pp r ) ( p q r )( p q r )M 4，此即公式的主合取范式，所以成假赋值为 100。

数理逻辑习题判断题1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →⌝→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧⌝∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →∃=→∀ （ √ ）6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）8．))()((x G x F x →∀是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ∃→∀是永真式（ √ ）11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）13．))()((x G x F x →∀是永假式 （ × ）14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨⌝ （ × ） 18．命题公式 )(r q p →∨⌝的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →∀是闭式（ × ）单项选择题1． 下述不是命题的是（ A ）A．花儿真美啊! B．明天是阴天。

C．2是偶数。

D．铅球是方的。

2．谓词公式（∀y）（∀x）（P（x）→R（x,y））∧∃yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）A．p→ （p∨q）B．（p∨┐p）→qC．q∧┐q D．p→┐q4．下列语句中不是．．命题的只有（A ）A．花儿为什么这样红？B．2+2=0C．飞碟来自地球外的星球。

1-1，1-2（1） 解：a) 是命题，真值为T。

b) 不是命题。

c) 是命题，真值要根据具体情况确定。

d) 不是命题。

e) 是命题，真值为T。

f) 是命题，真值为T。

g) 是命题，真值为F。

h) 不是命题。

i) 不是命题。

（2） 解：原子命题：我爱北京天安门。

A（3） 解：a) (┓P ∧R)→Qb) Q→Rc) ┓Pd) 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∧Qb) 设P：小李看书。

Q：小李听音乐。

P∧Qc) 设P：气候很好。

Q：气候很热。

P∨Qd) 设P： a和b是偶数。

Q：a+b是偶数。

P→Qe) 设P：四边形ABCD是平行四边形。

Q ：四边形ABCD的对边平行。

PQf) 设P：语法错误。

Q：程序错误。

R：停机。

（P∨ Q）→ R(6) 解：a) P:天气炎热。

Q:正在下雨。

P∧Qb) P:天气炎热。

R:湿度较低。

P∧Rc) R:天正在下雨。

S:湿度很高。

R∨Sd) A:刘英上山。

B:李进上山。

A∧Be) M:老王是革新者。

N:小李是革新者。

M∨Nf) L:你看电影。

M:我看电影。

┓L→┓Mg) P:我不看电视。

Q:我不外出。

R:我在睡觉。

P∧Q∧Rh) P:控制台打字机作输入设备。

Q:控制台打字机作输出设备。

P∧Q1-3（1）解：a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b) 是合式公式c) 不是合式公式（括弧不配对）d) 不是合式公式（R和S之间缺少联结词）e) 是合式公式。

（2）解：a） A是合式公式，(A∨B)是合式公式，(A→(A∨B)) 是合式公式。

习题二谓词逻辑一、选择题1、下列哪个式子不是谓词演算的合式公式( )A. (x)(A(x,2)∧B(y))B. (x)(A(x)∧B(x,y))C. ((x)∧(y))→(A(x,y)∧B(x,y))D. (x)(A(x)→B(y))2、设个体域是整数集，则下列命题的真值为真的是（）A.∀x∃y (xy=1)B. ∃x∀y(x+y=y)C.∃x∀y(x+y=x)D. ∀x∃y(y=2x)3、设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于( )A.(x)A(x)→BB. (x)A(x)→BC. A(x)→BD.(x)A(x)→(x)B4、谓词公式(x)(P(x)∨(y)R(y))→Q(x)中的x( ).A.只是约束变元B.只是自由变元C.既非约束变元又非自由变元D.既是约束变元又是自由变元5、谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z))中量词x的辖域是（）.A．(x)Q(x,z)→(x)(y)R(x,y,z))B．Q(x,z)→(y)R(x,y,z)C．Q(x,z)→(x)(y)R(x,y,z)D．Q(x,z)6、在论域D={a,b}中与公式（）A（x）等价的不含存在量词的公式是（）A. B.C. D.7、设M（x）：x是人；F（x）：x要吃饭.用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（）.A．B．C．D．8、设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（）.A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)9、按照约束变元的改名规则，∀xP(x) →∃yR(x,y)不可改写成（）. A．∀mP(m) →∃yR(x,y) B．∀xP(x) →∃zR(x,z)C．∀xP(x) →∃xR(x,x) D．∀xP(x) →∃nR(x,n)10、∀ x∀y(P(x,y)∧Q(y,z))∧(∃x)p(x,y),下面的描述中错误的是（）A.(∀ x)的辖域是（∀ y）（P（x,y）∧Q(y,z)）B．z是该谓词公式的约束变元C.(∃ x）的辖域是P（x,y）D. x是该谓词公式的约束变元二、填空题1、设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明和能干”的为谓词表达式为_______.2、使公式(x)( y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x.3、公式(x)A(x)→B(y)的前束范式为______.4、公式x(P(x)→Q(x,y)∨zR(y, z))→S(x)中的自由变元为________________，约束变元为________________.5、令R(x):x是实数，Q(x):x是有理数。

离散数学考试题及答案一、选择题（每题5分，共20分）1. 下列哪个选项不是离散数学的研究对象？A. 图论B. 组合数学C. 微积分D. 逻辑学答案：C2. 在逻辑学中，下列哪个命题是真命题？A. 如果今天是周一，那么明天是周二。

B. 如果今天是周一，那么明天是周三。

C. 如果今天是周一，那么明天是周四。

D. 如果今天是周一，那么明天是周五。

答案：A3. 在集合论中，下列哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 在图论中，下列哪个术语描述的是图中的顶点集合？A. 边B. 路径C. 子图D. 顶点答案：D二、填空题（每题5分，共20分）1. 如果一个集合A包含5个元素，那么它的子集个数是______。

答案：322. 在逻辑学中，如果命题P和命题Q都是真命题，那么复合命题“P且Q”的真值是______。

答案：真3. 在图论中，如果一个图的顶点数为n，那么它的最大边数是______。

答案：n(n-1)/24. 如果一个二叉树的深度为3，那么它最多包含______个节点。

答案：7三、简答题（每题10分，共30分）1. 请简述什么是图的连通性，并给出一个例子。

答案：图的连通性是指在图中任意两个顶点之间都存在一条路径。

例如，在一个完全图K3中，任意两个顶点之间都可以通过一条边直接连接，因此它是连通的。

2. 解释什么是逻辑蕴含，并给出一个例子。

答案：逻辑蕴含是指如果一个命题P为真，则另一个命题Q也必须为真。

例如，命题P：“如果今天是周一”，命题Q：“明天是周二”。

如果今天是周一，那么根据逻辑蕴含，明天必须是周二。

3. 请描述什么是二叉搜索树，并给出它的一个性质。

答案：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的数。

它的一个性质是中序遍历可以得到一个有序序列。

四、计算题（每题15分，共30分）1. 给定一个集合A={1, 2, 3, 4, 5}，请计算它的幂集，并列出所有元素。

第一章部分课后习题参考答案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⇔117．判断下面一段论述是否为真：“π是无理数。

并且，如果3是无理数，则2也是无理数。

另外6能被2整除，6才能被4整除。

”答：p: π是无理数 1q: 3是无理数0r: 2是无理数 1s:6能被2整除 1t: 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 10 1 1 0 1 1 11 0 0 1 0 0 11 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 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 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)解：（1）主析取范式(⌝p→q)→(⌝q∨p)⇔⌝(p ∨q)∨(⌝q ∨p)⇔(⌝p ∧⌝q)∨(⌝q ∨p) ⇔ (⌝p ∧⌝q)∨(⌝q ∧p)∨(⌝q ∧⌝p)∨(p ∧q)∨(p ∧⌝q)⇔(⌝p ∧⌝q)∨(p ∧⌝q)∨(p ∧q)⇔320m m m ∨∨⇔∑(0,2,3)主合取范式：(⌝p →q)→(⌝q ∨p)⇔⌝(p ∨q)∨(⌝q ∨p)⇔(⌝p ∧⌝q)∨(⌝q ∨p)⇔(⌝p ∨(⌝q ∨p))∧(⌝q ∨(⌝q ∨p)) ⇔1∧(p ∨⌝q)⇔(p ∨⌝q) ⇔ M 1⇔∏(1) (2) 主合取范式为： ⌝(p →q)∧q ∧r ⇔⌝(⌝p ∨q)∧q ∧r⇔(p ∧⌝q)∧q ∧r ⇔0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为：(p ∨(q ∧r))→(p ∨q ∨r)⇔⌝(p ∨(q ∧r))→(p ∨q ∨r)⇔(⌝p ∧(⌝q ∨⌝r))∨(p ∨q ∨r)⇔(⌝p ∨(p ∨q ∨r))∧((⌝q ∨⌝r))∨(p ∨q ∨r))⇔1∧1 ⇔1所以该式为永真式.永真式的主合取范式为 1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r) 前提引入②⌝q∨⌝r ①置换③q→⌝r ②蕴含等值式④r 前提引入⑤⌝q ③④拒取式⑥p→q 前提引入⑦￢p（3）⑤⑥拒取式证明（4）：①t∧r 前提引入②t ①化简律③q↔s 前提引入④s↔t 前提引入⑤q↔t ③④等价三段论⑥（q→t）∧(t→q) ⑤置换⑦（q→t）⑥化简⑧q ②⑥假言推理⑨q→p 前提引入⑩p ⑧⑨假言推理(11)p∧q ⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s 附加前提引入②s→p 前提引入③p ①②假言推理④p→(q→r) 前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p 结论的否定引入②p→﹁q 前提引入③﹁q ①②假言推理④￢r∨q 前提引入⑤￢r ④化简律⑥r∧￢s 前提引入⑦r ⑥化简律⑧r∧﹁r ⑤⑦合取由于最后一步r∧﹁r 是矛盾式,所以推理正确.第四章部分课后习题参考答案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)在两个个体域中都解释为)xF∀，在（a）中为假命题，在(b)中为真命题。

离散数学试题及答案解析一、选择题1. 在集合{1,2,3,4}中，含有3个元素的子集有多少个？A. 4B. 8C. 16D. 32答案：B解析：含有3个元素的子集可以通过组合数公式C(n, k) = n! / [k!(n-k)!]来计算，其中n为集合的元素个数，k为子集中的元素个数。

在本题中，n=4，k=3，所以C(4, 3) = 4! / [3!(4-3)!] = 4。

2. 下列哪个命题是真命题？A. 所有偶数都是整数。

B. 所有整数都是偶数。

C. 所有整数都是奇数。

D. 所有奇数都是整数。

答案：A解析：偶数是指能被2整除的整数，因此所有偶数都是整数，选项A是真命题。

选项B、C和D都是错误的，因为并非所有整数都是偶数或奇数。

二、填空题1. 逻辑运算符“非”（NOT）的真值表是：当输入为真时，输出为______；当输入为假时，输出为真。

答案：假解析：逻辑运算符“非”（NOT）是一元运算符，它将输入的真值取反。

如果输入为真，则输出为假；如果输入为假，则输出为真。

2. 命题逻辑中，合取词“与”（AND）的真值表是：当两个命题都为真时，输出为真；否则输出为______。

答案：假解析：合取词“与”（AND）是二元运算符，只有当两个命题都为真时，输出才为真；如果其中一个或两个命题为假，则输出为假。

三、简答题1. 解释什么是等价关系，并给出一个例子。

答案：等价关系是定义在集合上的一个二元关系，它满足自反性、对称性和传递性。

例如，考虑整数集合上的“同余”关系。

对于任意整数a，b，如果a和b除以同一个正整数n后余数相同，则称a和b模n同余。

这个关系是自反的（a同余a），对称的（如果a同余b，则b同余a），并且是传递的（如果a同余b且b同余c，则a同余c）。

2. 什么是图的连通性？一个图是连通的需要满足什么条件？答案：图的连通性是指在无向图中，任意两个顶点之间都存在一条路径。

一个图是连通的需要满足以下条件：图中的任意两个顶点v和w，都可以通过图中的边相互到达。

第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法等证明方法。

教学目的：1. 熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。

2. 熟练掌握常用的基本等价式及其应用。

3. 熟练掌握（主）析/合取范式的求法及其应用。

4. 熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。

5. 熟练掌握形式演绎的方法。

教学重点：1 .命题的概念及判断2 .联结词，命题的翻译3. 主析（合）取范式的求法4. 逻辑推理教学难点：1. 主析（合）取范式的求法2. 逻辑推理1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母 A , B,…，Z或带下标的大写字母或数字表示,如A i, [10], R等，例如A1：我是一名大学生。

A1：我是一名大学生.[10]:我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1否定联结词「P1.2.2合取联结词A1.2.3 析取联结词V1.2.4 条件联结词—125126 与非联结词T性质：(1)P T P=「( PAP)二「P；(2)(P T Q)T( P T Q) -「( P T Q) - PAQ；(3)( P T P)T( Q TQ) -「P T「Q= P V Q。

127 或非联结词J性质:(1) P J P=「( P V Q) =「P;(2)( P J Q )；( P J Q) =「( P J Q) = P V Q;(3)( P J P)J( Q J Q) =「P Q=P V-Q) = PAQ1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2 ）如果P是公式，则「P是公式；（3）如果P、Q是公式,则PAQ、PVQ、P > Q、P Q都是公式；（4）当且仅当能够有限次的应用（1）、（2）、（3）所得到的包括命题变元、联结词和括号的符号串是公式。