(数理逻辑)离散数学习题参考答案1

习题参考解答习题1.11、（3）P：银行利率降低Q：股价没有上升P∧Q（5）P：他今天乘火车去了北京Q：他随旅行团去了九寨沟PQ（7）P：不识庐山真面目Q：身在此山中Q→P，或～P→～Q（9）P：一个整数能被6整除Q：一个整数能被3整除R：一个整数能被2整除T：一个整数的各位数字之和能被3整除P→Q∧R ，Q→T2、（1）T （2）F （3）F （4）T （5）F（6）T （7）F （8）悖论习题 1.31（3）)()()()()()(R P Q P R P Q P R Q P R Q P →∨→⇔∨⌝∨∨⌝⇔∨∨⌝⇔∨→（4）()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右2、不， 不， 能习题 1.41(3) (())~((~))(~)()~(~(~))(~~)(~)P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、主合取范式)()()()()()()()()()()()()()())(())(()()(())()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∧∧∨⌝∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∨⌝∧∧∨∨⌝∧⌝∧∨∨⌝∧∨⌝∧⌝=∧∨⌝∧∨⌝=∨⌝∧∨⌝=→∧→ ————主析取范式(2) ()()(~)(~)(~(~))(~(~))(~~)(~)(~~)P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨ 2、()~()(~)(~)(~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价3、解：根据给定的条件有下述命题公式：（A →（C ∇D ））∧～（B ∧C ）∧～（C ∧D ）⇔（～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ∧～C ）） ∧（～C ∨～D ）⇔（～A ∧～B ∧～C ）∨（C ∧～D ∧～B ∧～C ）∨（～C ∧D ∧～B ∧～C ）∨ （～A ∧～C ∧～C ）∨（～C ∧D ∧～C ∧～C ）∨（～A ∧～B ∧～D ）∨（C ∧～D ∧～B ∧～D ）∨（～C ∧D ∧～B ∧～D ）∨（～A ∧～C ∧～D ）∨ （～C ∧D ∧～C ∧～D ）（由题意和矛盾律）⇔（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ）∨（C ∧～D ∧～B ）⇔（～C ∧D ∧～B ∧A ）∨ （～C ∧D ∧～B ∧～A ）∨ （～A ∧～C ∧B ）∨ （～A ∧～C ∧～B ）∨ （～C ∧D ∧A ）∨ （～C ∧D ∧～A ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～A ∧～C ∧B ∧～D ）∨（～A ∧～C ∧～B ∧D ）∨ （～A ∧～C ∧～B ∧～D ）∨（～C ∧D ∧A ∧B ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ）∨ （～C ∧D ∧～A ∧～B ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ） ⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ） ∨（C ∧～D ∧～B ∧A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨（C ∧～D ∧～B ∧A ） 三种方案：A 和D 、 B 和D 、 A 和C习题 1.51、 （1）需证()(())P Q P P Q →→→∧为永真式()(())~(~)(~())~~(~)(()(~))~(~)(~)()P Q P P Q P Q P P Q P P P Q P Q TP Q P Q T P Q P P Q →→→∧=∨∨∨∧∨=∨∨∧∨=∨∨∨=∴→⇒→∧（3）需证S R P P →∧⌝∧为永真式SR P P T S F S R F S R P P ⇒∧⌝∧∴⇔→⇔→∧⇔→∧⌝∧3A B A B ⇒∴→ 、为永真式。

页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

《离散数学》习题一参考答案第一节 集合的基数1.证明两个可数集的并是可数集。

证明：设A ，B 是两可数集，},,,,,{321 n a a a a A =，},,,,,{321 n b b b b B = ⎪⎩⎪⎨⎧-→j b i a N B A f j i 212: ，f 是一一对应关系，所以|A ∪B|=|N|=0ℵ。

2．证明有限可数集的并是可数集证：设k A A A A 321,,是有限个可数集，k i a a a a A in i i i i ,,3,2,1),,,,,(321 ==⎪⎩⎪⎨⎧+-→==i k j a N A A f ij k i i )1(:1，f 是一一对应关系，所以|A|=| k i i A 1=|=|N|=0ℵ。

3.证明可数个可数集的并是可数集。

证：设 k A A A A 321,,是无限个可数集， ,3,2,1),,,,,(321==i a a a a A in i i i i⎪⎪⎩⎪⎪⎨⎧+-+-+→=∞=i j i j i a N A A f ij i i )2)(1(21:1 ， 所以f 是一一对应关系，所以|A|=| ∞=1i i A |=|N|=0ℵ。

4.证明整系数多项式所构成的集合是可数集。

证明：设整系数n 次多项式的全体记为}|{1110Z a a x a x a x a A i n n n n n ∈++++=--则整系数多项式所构成的集合 ∞==1N n A A ；由于k x 的系数k a 是整数，那么所有k x 的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得n A 是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合 ∞==1N n A A 也是可数集。

5.证明不存在与自己的真子集等势的有限集合.证明：设集合A 是有限集，则|A|=n ，若B 是A 的真子集，则|B|≤|A|=n ，A-B ≠φ，即|A-B|=|A|-|AB|＞0；又A=（A-B ）∪B ，（A-B ）B=φ，所以，，就是|A|＞|B|，即得结论。

离散数学习题答案习题一及答案：（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→⌝→⌝解：列出公式的真值表，如下所示：p qp⌝q⌝()p p →⌝()p p q→⌝→⌝001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。

20、求下列公式的成真赋值：（4）()p q q⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒0p 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。

§1.1 命题和逻辑连接词习题1.11. 下列哪些语句是命题，在是命题的语句中，哪些是真命题，哪些是假命题，哪些命题的真值现在还不知道？（1）中国有四大发明。

（2）你喜欢计算机吗？ （3）地球上海洋的面积比陆地的面积大。

（4）请回答这个问题！ （5）632=+。

（6）107<+x 。

（7）园的面积等于半径的平方乘以圆周率。

（8）只有6是偶数，3才能是2的倍数。

（9）若y x =，则z y z x +=+。

（10）外星人是不存在的。

（11）2020年元旦下大雪。

（12）如果311=+，则血就不是红的。

解是真命题的有：（1）、（3）、(7)、 (9) 、（12） ；是假命题的有：（5）、 (8) ；是命题但真值现在不知道的有： (10)、 (11)；不是命题的有：（2）、（4）、（6）。

2. 令p 、q 为如下简单命题：p ：气温在零度以下。

q ：正在下雪。

用p 、q 和逻辑联接词符号化下列复合命题。

（1）气温在零度以下且正在下雪。

（2）气温在零度以下，但不在下雪。

（3）气温不在零度以下，也不在下雪。

（4）也许在下雪，也许气温在零度以下，也许既下雪气温又在零度以下。

（5）若气温在零度以下，那一定在下雪。

（6）也许气温在零度以下，也许在下雪，但如果气温在零度以上就不下雪。

（7）气温在零度以下是下雪的充分必要条件。

解 （1）q p ∧；（2）q p ⌝∧；（3）q p ⌝∧⌝；（4）q p ∨； （5）q p →；（6）)()(q p q p ⌝→⌝∧∨；（7）q p ↔。

3. 令原子命题p ：你的车速超过每小时120公里，q ：你接到一张超速罚款单，用p 、q 和逻辑联接词符号化下列复合命题。

（1）你的车速没有超过每小时120公里。

（2）你的车速超过了每小时120公里，但没接到超速罚款单。

（3）你的车速若超过了每小时120公里，将接到一张超速罚款单。

（4）你的车速不超过每小时120公里，就不会接到超速罚款单。

《离散数学》第1章练习题参考答案2017年一、填空题1. 设命题公式)(r q p G ∨⌝∧=，则G 的成真赋值是 100 、 101 、 111 .2. 已知命题公式r q p G →∧⌝=)(，则G 的析取范式为r q p ∨⌝∨.3. 设B A ,为两个命题公式，B A ⇔当且仅当为重言式B A ↔，B A ⇒当且仅当为重言式B A →.4. 已知命题公式),,(r q p A 的主合取范式为530M M M ∧∧，则它的主析取范式为76421m m m m m ∨∨∨∨.5. 已知命题公式),,(r q p A 的成真赋值为000,001,010,100,110，则其主合取范式为357M M M ∧∧.二、选择题1. 设命题公式)(p q p G ⌝→∧=，则使G 的真值为1的p ，q 的取值是 （ C ）（A ） 00 （B ） 01 （C ） 10 （D ） 112. 与命题公式)(r q p →→等值的公式是 （ B ）（A ）r q p →∨)( （B ）r q p →∧)( （C ）)(r q p ∧→ （D ）)(r q p ∨→3. 命题公式p q p →∧)(是 （ A ）（A ）永真式 （B ）永假式 （C ）非永真式的可满足式 （D ）合取范式4. 设命题公式)(),(p q H q p G ⌝→=→⌝=，则G 与H 的关系是 （ D ）（A ）G H ⇔ （B ）G H → （C ）G H ⇒ （D ）H G ⇒5. 下列重言蕴涵式中，不正确的是 （ C ）（A ）Q P Q ∨⇒ （B ）Q P Q →⇒（C ）P Q P Q ⇒→∧⌝)( （D ）Q Q P ⌝⇒→⌝)(三、计算题1. 将下列命题符号化（1）李强不是不聪明，而是不用功 （2）如果天不下雨，我们就去郊游 解 （1）设p ：李强聪明，q ：李强用功.原命题符号化为：q p ⌝∧（2）设p ：天下雨，q ：我们去郊游.原命题符号化为：q p →⌝2.给出下列公式的真值表（1）r q p r q p ⌝∧∧→→∧)(（2）)()()(r p r q q p ⌝∧⌝→→∧∨⌝解略.3. 设命题变项q p ,为1， s r ,为0，试求出下列命题的真值（1）)(r q p ∧∨ （2）)()(s q r p →⌝∧→解 （1）101)01(1)(⇔∨⇔∧∨⇔∧∨r q p（2）010)00()01()()(⇔∧⇔→∧→⇔→⌝∧→s q r p4. 判断下列公式的类型（1）)(r q p p ∨∨→ （2）)()(q p q p ∨⌝→↔解 用真值表知（1）是重言式，（2）是可满足式.5. 求命题公式r q p →∨)(的主合取范式，并求其成假赋值. 解 用真值表可得642)(M M M r q p ∧∧⇔→∨.真值为0的赋值有三种：001，100，110.6. 求命题公式r q p ∨∧)(的主合取范式与主析取范式.解 用真值表法可知42076531)(M M M m m m m m r q p ∧∧⇔∨∨∨∨⇔∨∧四、证明题1. 用等值演算法证明q q p p →→∧)(为重言式. 证 原式q q p p q q p p →∨⌝∧⇔→→∧⇔)()( q q p q q p p ∨∧⌝⇔∨∨⌝∧⌝⇔)())((11⇔∨⌝⇔∨⌝∨⌝⇔p q q p2. 构造下列推理的证明（1）前提：q p q s s r q r →⌝→∨⌝→,,,，结论：p ⌝；（2）前提：s r s p q s r q p ,),)((),()(⌝∨→∧⌝→→⌝，结论：q p ↔；(3) 前提：)(,)(,t p r r q q p ∧⌝⌝⌝∧∨⌝→，结论：t ⌝. 证 （1）用归谬法证明①p 结论的否定引入 ②q p → 前提引入 ③q ①②假言推理 ④q s ⌝→ 前提引入 ⑤s ⌝ ③④拒取 ⑥ s r ∨ 前提引入⑦r ⑤⑥析取三段论 ⑧q r ⌝→ 前提引入 ⑨q ⌝ ⑦⑧假言推理 ⑩q q ⌝∧ ③⑨合取 ⑩得出矛盾，因此，p ⌝是前提的有效结论.（2）① s p q ⌝∨→)( 前提引入② s 前提引入 ③ p q → ①②析取三段论 ④ )()(s r q p ∧⌝→→⌝ 前提引入 ⑤ r 前提引入 ⑥ s r ∧ ②⑤合取 ⑦ q p → ④⑥拒取⑧)p→∧q→③⑦合取(q)(p⑨qp↔⑧置换（3）①r⌝)(前提引入∨∧q⌝r②rq∨⌝①化简③r⌝①化简④)⌝前提引入⌝p∧(t⑤tp⌝∨④置换⑥q⌝②③析取三段论⑦qp→前提引入⑧p⌝⑥⑦拒取⑨t⌝⑤⑧析取三段论。

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

b)不是命题。

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

d)不是命题。

e)是命题，真值为T。

f)是命题，真值为T。

g)是命题，真值为F。

h)不是命题。

i)不是命题。

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

复合命题：如果不是练健美操，我就出外旅游拉。

（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的对边平行。

P Qf)设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-1，1-2指出下列哪些语句是命题，那些不是命题，如果是命题，指出它的真值。

离散数学是计算机科学系的一门必修课。

是命题，真值为T。

b)计算机有空吗？不是命题。

c)明天我去看电影。

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

d)请勿随地吐痰。

不是命题。

e)不存在最大的质数。

是命题，真值为T。

f)如果我掌握了英语，法语，那么学习其他欧洲语言就容易多了。

是命题，真值为T。

g)9+5≤12.是命题，真值为F。

h)X=3.不是命题。

i)我们要努力学习。

不是命题。

举例说明原子命题和复合命题。

原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。

设P表示命题“天下雪。

”Q表示“我将去镇上。

”R表示命题“我有时间。

”以符号形式写出下列命题a)如果天不下雪和我有时间，那么我将去镇上。

b)我将去镇上，仅当我有时间时。

c)天不下雪。

d)天下雪，那么我不去镇上。

用汉语写出一些句子，对应下列每一个命题。

a)Q?Q:我将去参加舞会。

R:我有时间。

P:天下雨。

Q?:我将去参加舞会当且仅当我有时间和天不下雨。

→QQ→R ┓PP→┓Qb)R∧QR:我在看电视。

[)Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。

c)∧Q:一个数是奇数。

R:一个数不能被2除。

∧:一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。

将下列命题符号化。

a)王强身体很好，成绩也很好。

设P：王强身体很好。

Q：王强成绩很好。

P∧Qb)小李一边看书，一边听音乐。

设P：小李看书。

Q：小李听音乐。

P∧Qc)气候很好或很热。

设P：气候很好。

Q：气候很热。

P∨Qd)如果a和b是偶数，则a+b是偶数。

设P：a和b是偶数。

Q：a+b是偶数。

P→Qe)四边形ABCD是平行四边形，当且仅当它的对边平行。

设P：四边形ABCD是平行四边形。

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

P?Qf)停机的原因在于语法错误或程序错误。

北京科技大学远程教育学院《离散数学》综合练习(一)参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。

1、今天天气真好！解：不是命题。

2、王华和张民是同学。

解：是命题。

真值视实际情况而定。

p：王华和张民是同学。

3、我一边吃饭，一边看电视。

解：是命题。

真值视实际情况而定。

p：我吃饭。

q：我看电视。

p∧q 4、没有不呼吸的人。

解：是命题。

真值为1。

M(x)：x是人。

F(x)：x呼吸。

∀x(M(x)→F(x))二、求命题公式的真值表和成真赋值、成假赋值。

p→∧qr∧→(p])[(r)解：成真赋值：000，001，010，011，101，111；成假赋值100，110三、用真值表、等值演算两种方法判别公式类型。

1、r q q p →∧→])[( 解：rq q p r q q q p r q q p rq q p r q q p r q q p ∨⌝∧⌝∨⇔∨⌝∨⌝∧⌝∨⇔∨⌝∨⌝∧⇔∨⌝∨∨⌝⌝⇔∨∧∨⌝⌝⇔→∧→])[()]()[()()(])[(])[(可满足式2、))((p q p q ∧∨⌝⌝∨ 解：))((p q p q A ∧∨⌝⌝∨=1)()()())((⇔∨⌝∨∨⌝⌝⇔⌝∨∨⌝⌝∨⇔∧∨⌝⌝∨q p q p p q p q p q p q永真式四、求命题公式的主析取范式和成真赋值、成假赋值。

)(r q p →→ 解：∑=→→），，，，，，7543210()(r q p 成真赋值：000，001，010，011，100，101，111；成假赋值110 五、解释I 如下：D 是实数集，特定元素a =0；特定函数f (x ，y )=x -y ；特定谓词F (x ，y )：x<y 。

在解释I 下判别公式真、假。

1、)])(([x y x f F y x ，，⌝∀∀ 解：)])[()])(([)]([)])(([x y x y x x y x y x x y x F y x x y x f F y x ≥-∀∀⇔<-⌝∀∀⇔-⌝∀∀⇔⌝∀∀，，，真值为假2、)]()([)({z y f z x f F y x F z y x ，，，，→∀∀∀ 解：)]()()[()]}()([)({z y z x y x z y x z y f z x f F y x F z y x -<-→<∀∀∀⇔→∀∀∀，，，，真值为真 六、1、求前束范式)()(y x yG x xF ，∀→⌝∃ 解：)]()([)()()()()()(y t G x F y x y t yG x xF y x yG x xF y x yG x xF ，，，，∨∀∃⇔∀∨∃⇔∀∨∃⇔∀→⌝∃2、证明：B x xA B x A x →∀⇔→∃)())(( 证明：Bx xA Bx xA B x A x B x A x B x A x →∀⇔∨⌝∀⇔∨⌝∃⇔∨⌝∃⇔→∃)()()())(())((七、写出下面推理的证明，要求写出前提、结论，并注明推理规则。

可编辑修改精选全文完整版离散数学习题答案习题一：P121.判断下列句子哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？(1)中国有四大发明。

(2)5是无理数。

(3)3是素数或4是素数。

(4)x2+3<5，其中x是任意实数。

(5)你去图书馆吗？(6)2与3都是偶数。

(7)刘红与魏新是同学。

(8)这朵玫瑰花多美丽呀！(9)吸烟请到吸烟室去！(10)圆的面积等于半径的平方乘π。

(11)只有6是偶数，3才能是2的倍数。

(12)8是偶数的充分必要条件是8能被3整除。

(13)2025年元旦下大雪。

1、2、3、6、7、10、11、12、13是命题。

在上面的命题中，1、2、7、10、13是简单命题；1、2、10是真命题；7的真值现在还不知道。

2.将上题中是简单命题的命题符号化。

(1)p：中国有四大发明。

(2)q：5是无理数。

(7)r：刘红与魏新是同学。

(10)s：圆的面积等于半径的平方乘π。

(1)t：2025年元旦下大雪。

3.写出下列各命题的否定式，并将原命题及其否定式都符号化，最后指出各否定式的真值。

“5是有理数”的否定式是“5不是有理数”。

解：原命题可符号化为：p：5是有理数。

其否定式为：非p。

非p的真值为1。

4.将下列命题符号化，并指出真值。

(1)2与5都是素数。

(2)不但π是无理数，而且自然对数的底e也是无理数。

(3)虽然2是最小的素数，但2不是最小的自然数。

(4)3是偶素数。

(5)4既不是素数，也不是偶数。

a：2是素数。

b：5是素数。

c：π是无理数。

d：e是无理数。

f：2是最小的素数。

g：2是最小的自然数。

h：3是偶数。

i：3是素数。

j：4是素数。

k：4是偶数。

解：（1）到（5）的符号化形式分别为a∧b，c∧d，f∧非g，h∧i，非j∧非k。

这五个复合命题的真值分别为1，1，1，0，0。

5.将下列命题符号化，并指出真值。

a：2是偶数。

b：3是偶数。

c：4是偶数。

作业答案：数理逻辑部分P14：习题一1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（3 答：简单命题，真命题。

（9）吸烟请到吸烟室去！ 答：不是命题。

（12）8是偶数的充分必要条件是8能被3整除。

答：复合命题，假命题。

14、讲下列命题符号化。

（6）王强与刘威都学过法语。

答：:p 王强学过法语；:q 刘威学过法语。

符号化为：p q ∧（10）除非天下大雨，他就乘班车上班。

答：:p 天下大雨；:q 他乘班车上班。

符号化为：p q →（13）“2或4是素数，这是不对的”是不对的。

答：:p 2是素数；:q 4是素数。

符号化为：(())p q ⌝⌝∨15、设:p 2+3=5. :q 大熊猫产在中国。

:r 太阳从西方升起。

求下列复合命题的真值。

（2）(())r p q p →∧↔⌝（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→ 解答： p 真值为1；q 真值为1；r 真值为0.（2）p q ∧真值为1；()r p q →∧真值为1；p ⌝真值为0；所以(())r p q p →∧↔⌝真值为0.（4）p q r ∧∧⌝真值为1，p q ⌝∨⌝真值为0，()p q r ⌝∨⌝→真值为1；所以()(())p q r p q r ∧∧⌝↔⌝∨⌝→真值为1.19、用真值表判断下列公式的类型。

（4）()()p q q p →→⌝→⌝所以为重言式。

（7）所以为可满足式。

P36:习题二3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。

（1）()p q q ⌝∧→ 解答：()(())(())()10p q q p q q p q q p q q ⌝∧→⇔⌝⌝∧∨⇔⌝⌝∨⌝∨⇔⌝⌝∨⌝∨⇔⌝⇔所以为永假式。

（2）(())()p p q p r →∨∨→ 解答：(())()(())()()()1()1p p q p r p p q p r p p q p r p r →∨∨→⇔⌝∨∨∨⌝∨⇔⌝∨∨∨⌝∨⇔∨⌝∨⇔ 所以因为永真式。

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1）设：p：派小王去开会。

q：派小李去开会。

则命题：“派小王或小李中的一人去开会”可符号化为：(p∨⌝q) ∧ (⌝p∨q) 。

（2）设A，B都是命题公式，A⇒B，则A→B的真值是T。

（3）设：p：刘平聪明。

q：刘平用功。

在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p∧q。

（4）设A , B 代表任意的命题公式，则蕴涵等值式为A → B⇔⌝A∨B。

（5）设，p：径一事；q：长一智。

在命题逻辑中，命题：“不径一事，不长一智。

”可符号化为：⌝ p→⌝q 。

（6）设A , B 代表任意的命题公式，则德•摩根律为⌝（A ∧ B）⇔⌝A ∨⌝B）。

（7）设，p：选小王当班长；q：选小李当班长。

则命题：“选小王或小李中的一人当班长。

”可符号化为：(p∨⌝q) ∧ (⌝p∨q) 。

（8）设，P：他聪明；Q：他用功。

在命题逻辑中，命题：“他既聪明又用功。

”可符号化为：P∧Q 。

（9）对于命题公式A，B，当且仅当 A → B 是重言式时，称“A蕴含B”，并记为A⇒B。

（10）设：P：我们划船。

Q：我们跑步。

在命题逻辑中，命题：“我们不能既划船又跑步。

”可符号化为：⌝ (P∧Q) 。

（11）设P , Q是命题公式，德·摩根律为：⌝（P∨Q）⇔⌝P∧⌝Q）。

（12）设P：你努力。

Q：你失败。

在命题逻辑中，命题：“除非你努力，否则你将失败。

”可符号化为：⌝P→Q。

（13）设p：小王是100米赛跑冠军。

q：小王是400米赛跑冠军。

在命题逻辑中，命题：“小王是100米或400米赛跑冠军。

”可符号化为：p∨q。

（14）设A，C为两个命题公式，当且仅当A→C为一重言式时，称C可由A逻辑地推出。

二．判断题1.设A，B是命题公式，则蕴涵等值式为A→B⇔⌝A∧B。

（⨯）2.命题公式⌝p∧q∧⌝r是析取范式。

（√）3.陈述句“x + y > 5”是命题。

第一章部分习题及参考答案1 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)（2）（p↔r）∧(﹁q∨s)（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r)(4)（⌝r∧s）→(p∧⌝q)2．判断下面一段论述是否为真：“π是无理数。

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

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

”3．用真值表判断下列公式的类型：（1）(p→q) →(⌝q→⌝p)（2）(p∧r) ↔(⌝p∧⌝q)（3）((p→q) ∧(q→r)) →(p→r)4.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) ⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)5.用等值演算法证明下面等值式：(1)(p→q)∧(p→r)⇔(p→(q∧r))(2)(p∧⌝q)∨(⌝p∧q)⇔(p∨q) ∧⌝(p∧q)6.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)7.在自然推理系统P中构造下面推理的证明：(1)前提：p→q,⌝(q∧r),r结论：⌝p(2)前提：q→p,q↔s,s↔t,t∧r结论：p∧q8.在自然推理系统P中用附加前提法证明下面推理：前提：p→(q→r),s→p,q结论：s→r9.在自然推理系统P中用归谬法证明下面各推理：前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p参考答案: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⇔12.p: π是无理数 1q: 3是无理数0r: 2是无理数 1s: 6能被2整除 1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。

《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式?x((A(x)?B(y，x))??z C(y，z))?D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。

在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。

）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

《离散数学》题库答案第2，3章(数理逻辑)1.答：（2），（3），（4）2.答：（2），（3），（4），（5），（6）3.答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是4.答：（1）P↔（4）QP→⌝P⌝Q→⌝（2）QP⌝→（3）Q5.答：（1）6.答：2不是偶数且-3不是负数。

7.答：（2）8.答：⌝P ，Q→P9.答：P(x)∨∃yR(y)10.答：⌝∀x(R(x)→Q(x))11、a、(P→Q)∧R解：(P→Q)∧R⇔(⌝P∨Q )∧R⇔(⌝P∧R)∨(Q∧R) （析取范式）⇔(⌝P∧(Q∨⌝Q)∧R)∨((⌝P∨P)∧Q∧R)⇔(⌝P∧Q∧R)∨(⌝P∧⌝Q∧R)∨(⌝P∧Q∧R)∨(P∧Q∧R)⇔(⌝P∧Q∧R)∨(⌝P∧⌝Q∧R)∨(P∧Q∧R)⇔m3∨ m1∨m7 （主析取范式）⇔m1∨ m3∨m7⇔M0∧M2∧M4∧M5∧M6 （主合取范式）b、Q→(P∨⌝R)解：Q→(P∨⌝R)⇔⌝Q∨P∨⌝R⇔M5（主合取范式）⇔ m0∨ m1∨ m2∨m3∨ m4∨m6 ∨m7 （主析取范式）c、P→(P∧(Q→P))解：P→(P∧(Q→P))⇔⌝P∨(P∧(⌝Q∨P))⇔⌝P∨P⇔ 1 (主合取范式)⇔ m0∨ m1∨m2∨ m3 （主析取范式）d、P∨(⌝P→(Q∨(⌝Q→R)))解：P∨(⌝P→(Q∨(⌝Q→R)))⇔ P∨(P∨(Q∨(Q∨R)))⇔ P∨Q∨R⇔ M0 (主合取范式)⇔ m1∨ m2∨m3∨ m4∨ m5∨m6 ∨m7 (主析取范式)12、a、P→Q，⌝Q∨R，⌝R，⌝S∨P=>⌝S证明：(1) ⌝R 前提(2) ⌝Q∨R 前提(3)⌝Q （1），（2）析取三段论(4) P→Q 前提(5)⌝P （3），（4）拒取式(6)⌝S∨P 前提(7) ⌝S （5），（6）析取三段论b、P→(Q→R)，R→(Q→S) => P→(Q→S)证明：（1） P 附加前提（2） Q 附加前提（3） P→(Q→R) 前提（4） Q→R （1），（3）假言推理（5） R （2），（4）假言推理（6） R→(Q→S) 前提（7） Q→S （5），（6）假言推理（8） S （2），（7）假言推理c、A，A→B， A→C， B→(D→⌝C) => ⌝D证明：（1） A 前提（2） A→B 前提（3） B (1)，(2) 假言推理（4） A→C 前提（5） C (1)，(4) 假言推理（6） B→(D→⌝C) 前提（7） D→⌝C (3)，(6) 假言推理（8）⌝D (5)，(7) 拒取式d、P→⌝Q，Q∨⌝R，R∧⌝S⇒⌝P证明、(1) P 附加前提（2） P→⌝Q 前提（3）⌝Q （1），（2）假言推理（4） Q∨⌝R 前提(5) ⌝R （3），（4）析取三段论(6 ) R∧⌝S 前提（7） R （6）化简（8） R∧⌝R 矛盾（5），（7）合取所以该推理正确13.写出∀x(F(x)→G(x))→(∃xF(x) →∃xG(x))的前束范式。