离散数学-屈婉玲-耿素云-张立昂-主编-高等教育出版社-课后最全答案

离散数学习题答案习题二及答案：（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。

7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())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 ⇔⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧⌝∨∧∧ 13567m m m m m ⇔∨∨∨∨，此即主析取范式。

主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ⇔∧∧。

9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨⌝∧ 解：公式的真值表如下：由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式1234567m m m m m m m ⇔∨∨∨∨∨∨习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。

前提：,,,p q q r r s p ⌝∨⌝∨→结论：s 证明：① p 前提引入 ② p q ⌝∨ 前提引入 ③ q ①②析取三段论 ④ q r ⌝∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入⑦ s ⑤⑥假言推理15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论：p u →证明：用附加前提证明法。

第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(1)证明：① S结论否定引入② S→P前提引入③ P①②假言推理④ P→(q→r)前提引入⑤ q→r③④假言推论⑥ q前提引入⑦ r⑤⑥假言推理（2）证明：① p附加前提引入② p∨q①附加③ (p∨q)→(r∧s)前提引入④ r∧s②③假言推理⑤ s④化简⑥ s∨t⑤附加⑦ (s∨t)→u前提引入⑧ u⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

第一章部分课后习题参考答案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) ⇔ M1⇔∏(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,均有错误!未找到引用源。

离散数学习题答案习题二及答案：（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。

7、求下列公式的主析取式，再用主析取式求主合取式： （1）()p q r ∧∨ 解：原式()(()())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 ⇔⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧⌝∨∧∧13567m m m m m ⇔∨∨∨∨，此即主析取式。

主析取式中没出现的极小项为0m ，2m ，4m ，所以主合取式中含有三个极大项0M ，2M ，4M ，故原式的主合取式024M M M ⇔∧∧。

9、用真值表法求下面公式的主析取式： （1）()()p q p r ∨∨⌝∧ 解：公式的真值表如下：由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取式，故主析取式1234567m m m m m m m ⇔∨∨∨∨∨∨习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。

前提：,,,p q q r r s p ⌝∨⌝∨→结论：s 证明：① p 前提引入 ② p q ⌝∨ 前提引入 ③ q ①②析取三段论 ④q r ⌝∨ 前提引入⑤ r ③④析取三段论 ⑥ r s → 前提引入⑦ s ⑤⑥假言推理15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论：p u →证明：用附加前提证明法。

屈婉玲⾼教版离散数学部分答案第七章部分课后习题参考答案7.列出集合A={2,3,4}上的恒等关系I A ,全域关系E A ,⼩于或等于关系L A ,整除关系D A .解：I A ={<2，2>,<3,3>,<4,4>}E A ={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}L A ={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} D A ={<2,4>}13.设A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>}求A ?B,A ?B, domA, domB, dom(A ?B), ranA, ranB, ran(A ?B ), fld(A-B). 解：A ?B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A ?B= {<2,4>}domA={1,2,3} domB={1,2,4} dom(A ∨B)={1,2,3,4}ranA={2,3,4} ranB={2,3,4} ran(A ?B)={4}A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R οR, R -1, R ↑{0,1,}, R[{1,2}] 解：R οR={<0,2>,<0,3>,<1,3>}R -1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}R ↑{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3}16．设A={a,b,c,d}，1R ，2R 为A 上的关系，其中1R ={},,,,,a a a b b d{2,,,,,,,R a d b c b d c b=求23122112,,,R R R R R R o o 。

1.1．略1.2．略1.3．略1.4．略1.5．略1.6．略1.7．略1.8．略1.9．略1.10．略1.11．略1.12．将下列命题符号化,并给出各命题的真值:<1>2+2＝4当且仅当3+3＝6.<2>2+2＝4的充要条件是3+3≠6.<3>2+2≠4与3+3＝6互为充要条件.<4>若2+2≠4, 则3+3≠6,反之亦然.<1>p↔q,其中,p: 2+2＝4,q: 3+3＝6, 真值为1.<2>p↔⌝q,其中,p:2+2＝4,q:3+3＝6,真值为0.<3>⌝p↔q,其中,p:2+2＝4,q:3+3＝6,真值为0.<4>⌝p↔⌝q,其中,p:2+2＝4,q:3+3＝6,真值为1.1.13．将下列命题符号化, 并给出各命题的真值:<1>若今天是星期一,则明天是星期二.<2>只有今天是星期一,明天才是星期二.<3>今天是星期一当且仅当明天是星期二. <4>若今天是星期一,则明天是星期三.令p: 今天是星期一;q:明天是星期二;r:明天是星期三.<1>p→q ⇔ 1.<2> q→p ⇔ 1.<3> p↔q⇔ 1.<4>p→r当p ⇔ 0时为真; p ⇔ 1时为假.1.14．将下列命题符号化. <1>刘晓月跑得快,跳得高.<2>老王是XX人或XX人.<3>因为天气冷, 所以我穿了羽绒服. <4>王欢与李乐组成一个小组.<5>李辛与李末是兄弟.<6>王强与刘威都学过法语. <7>他一面吃饭, 一面听音乐. <8>如果天下大雨,他就乘班车上班.<9>只有天下大雨,他才乘班车上班.<10>除非天下大雨,他才乘班车上班.<11>下雪路滑, 他迟到了.<12>2与4都是素数,这是不对的.<13>"2或4是素数,这是不对的"是不对的.<1>p∧q,其中, p:刘晓月跑得快, q: 刘晓月跳得高.<2>p∨q,其中, p:老王是XX人, q: 老王是XX 人.<3>p→q, 其中,p:天气冷, q:我穿了羽绒服.<4>p, 其中,p:王欢与李乐组成一个小组,是简单命题.<5>p, 其中,p:李辛与李末是兄弟.<6>p∧q,其中, p:王强学过法语, q: 刘威学过法语.<7>p∧q,其中, p:他吃饭,q:他听音乐.<8>p→q, 其中,p:天下大雨, q:他乘班车上班.<9>p→q, 其中,p:他乘班车上班, q: 天下大雨.<10>p→q, 其中,p: 他乘班车上班,q:天下大雨.<11>p→q, 其中,p: 下雪路滑, q:他迟到了.12>⌝ <p∧q>或⌝p∨⌝q,其中,p:2是素数,q:4是素数.<13>⌝⌝ <p∨q>或p∨q,其中,p:2 是素数,q:4是素数.1.15．设p:2+3=5.q: 大熊猫产在中国.r: 复旦大学在XX.求下列复合命题的真值:<1><p↔q>→r<2><r→ <p∧q>>↔ ⌝p<3>⌝r→ <⌝p∨⌝q∨r><4><p∧q∧⌝r>↔ <<⌝p∨⌝q>→r><1>真值为0.<2>真值为0.<3>真值为0.<4>真值为1.注意:p, q是真命题,r是假命题.1.16．略1.17．略1.18．略1.19．用真值表判断下列公式的类型:<1>p→ <p∨q∨r><2><p→⌝q>→⌝q<3>⌝ <q→r>∧r<4><p→q>→ <⌝q→⌝p><5><p∧r>↔ <⌝p∧⌝q><6><<p→q>∧ <q→r>>→ <p→r><7><p→q> ↔ <r↔s><1>, <4>,<6>为重言式.<3>为矛盾式.<2>, <5>,<7>为可满足式.1.20．略1.21．略1.22．略1.23．略1.24．略1.25．略1.26．略1.27．略1.28．略1.29．略1.30．略1.31．将下列命题符号化,并给出各命题的真值:<1>若3+＝4,则地球是静止不动的.<2>若3+2＝4,则地球是运动不止的. <3>若地球上没有树木,则人类不能生存.<4>若地球上没有水,则3是无理数.<1>p→q,其中, p: 2+2＝4,q:地球静止不动,真值为0.<2>p→q,其中, p: 2+2＝4,q:地球运动不止,真值为1.<3>⌝p→⌝q,其中,p:地球上有树木,q:人类能生存,真值为1.<4>⌝p→q,其中,p:地球上有水,q: 3 是无理数,真值为1.习题二2.1.设公式A=p→q,B=p⌝∧q,用真值表验证公式A和B适合德摩根律:⌝<A∨B>⇔ ⌝A⌝∧B.p q A =p→q B=p⌝∧q⌝<A∨B>⌝A⌝∧B0 0 1 0 0 00 1 1 0 0 01 0 0 1 0 01 1 1 0 0 0因为⌝<A∨B>和⌝A⌝∧B的真值表相同,所以它们等值.2.2. 略2.3. 用等值演算法判断下列公式的类型, 对不是重言式的可满足式,再用真值表法求出成真赋值.<1>⌝ <p∧q→q><2><p→ <p∨q>>∨ <p→r><3><p∨q>→ <p∧r><1>⌝ <p∧q→q>⇔ ⌝ <⌝<p∧q>∨ q>⇔ ⌝ <⌝p∨ ⌝q∨ q>⇔ p∧q∧⌝q⇔ p∧0⇔ 0⇔ 0.矛盾式.<2>重言式.<3> <p∨q>→ <p∧r>⇔ ⌝<p∨q>∨ <p∧r>⇔ ⌝p⌝∧q∨ p∧r易见,是可满足式,但不是重言式.成真赋值为:000,001, 101, 111p q r←p∍ ←q(p∍r0 0 0 1 1 1 1 00 0 1 1 1 1 1 00 1 0 1 0 0 0 00 1 1 1 0 0 0 01 0 0 0 0 1 0 01 0 1 0 0 1 1 11 1 0 0 0 0 0 01 1 1 0 0 0 1 12.4.用等值演算法证明下面等值式:<1>p⇔ <p∧q>∨ <p∧⌝q><3>⌝ <p↔q>⇔ <p∨q>∧⌝ <p∧q><4><p∧⌝q>∨ <⌝p∧q>⇔ <p∨q>∧⌝ <p∧q><1><p∧q>∨ <p∧⌝q>⇔ p∧ <q⌝∨q>⇔ p∧ 1⇔ p.<3>⌝<p↔q>⇔⌝ <<p→q>∧ <q→p>>⇔⌝ <<⌝p∨q>∧ <⌝q∨p>>⇔ <p∧⌝q>∨ <q∧⌝p>⇔ <p∨q>∧ <p∨⌝p>∧ <⌝q∨q>∧ <⌝p∨⌝q>⇔ <p∨q> ∧⌝ <p∧q><4><p∧⌝q>∨ <⌝p∧q>⇔ <p∨⌝p>∧ <p∨q>∧ <⌝q∨⌝p>∧ <⌝q∨q>⇔ <p∨q> ∧⌝ <p∧q>2.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<吸收律>⇔ <p⌝∨p>⌝∧q∨ p∧<q⌝∨q>⇔ p⌝∧q⌝∨p⌝∧q∨ p∧q∨ p⌝∧q⇔ m10∨ m00∨ m11∨ m10⇔ m0∨ m2∨ m3⇔ ∑<0, 2,3>.成真赋值为00,10, 11.<2>主析取范式为0, 无成真赋值,为矛盾式.<3>m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7,为重言式.2.6. 求下列公式的主合取范式, 并求成假赋值:<1>⌝ <q→⌝p>∧⌝p<2><p∧q>∨ <⌝p∨r><3><p→ <p∨q>>∨r<1> ⌝ <q⌝→p>∧ ⌝p⇔ ⌝<⌝q⌝∨p>∧ ⌝p⇔ q∧p∧ ⌝p⇔ q∧0⇔ 0⇔ M0∧M1∧M2∧M3这是矛盾式.成假赋值为00, 01,10,11.<2>M4,成假赋值为100.<3>主合取范式为1, 为重言式.2.7.求下列公式的主析取范式,再用主析取范式求合取范式:<1><p∧q> ∨r<2><p→q> ∧ <q→r><1>m1∨m3∨m5∨m6∨m7⇔M0∧M2∧M4<2>m0∨m1∨m3∨m7⇔M2∧M4∧M5∧M62.8. 略2.9. 用真值表求下面公式的主析取范式.<2><p→q>→ <p⌝↔q>p q<p q> <p←  q>0 0 1 0 0 10 1 1 1 1 01 0 0 1 1 11 1 1 0 0 0<2>从真值表可见成真赋值为01,10.于是<p→ q>→ <p⌝ ↔ q>⇔ m1∨ m2.2.10.略2.11.略2.12.略2.13.略2.14.略2.15. 用主析取范式判断下列公式是否等值:<1> <p→q> →r与q→ <p→r><2><p→q> →r⇔ ⌝<⌝p∨q>∨ r⇔ ⌝<⌝p∨q>∨ r⇔ p⌝∧q∨ r⇔ 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= m101∨ m100∨ m111∨ m101∨ m011∨ m001⇔ m1∨ m3∨ m4∨ m5∨ m7= ∑<1,3,4,5,7>.而q→<p→r>⇔ ⌝q∨ <⌝p∨r>⇔ ⌝q∨ ⌝p∨r⇔ <⌝p∨p>⌝∧q∧<⌝r∨r>∨ ⌝p∧<⌝q∨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>= m0∨ m1∨ m4∨ m5∨ m0∨ m1∨ m2∨ m3∨ m1∨ m3∨ m5∨ m7⇔ m0∨ m1∨ m2∨ m3∨ m4∨ m5∨ m7⇔ ∑<0,1,2,3,4,5,7>.两个公式的主吸取范式不同,所以<p→q>→rœq→ <p→r>.2.16.用主析取范式判断下列公式是否等值:<1><p→q>→r与q→ <p→r><2>⌝ <p∧q>与⌝ <p∨q><1><p→q>→r> ⇔m1∨m3∨m4∨m5∨m7q→ <p→r>⇔m0∨m1∨m2∨m3∨m4∨m5∨m7所以<p→q>→r>œq→ <p→r><2>⌝ <p∧q>⇔m0∨m1∨m2⌝ <p∨q>⇔m0所以⌝ <p∧q>œ⌝ <p∨q>2.17.用主合取范式判断下列公式是否等值:<1>p→ <q→r>与⌝ <p∧q>∨r<2>p→ <q→r>与<p→q>→r<1>p→ <q→r>⇔M6⌝ <p∧q>∨r⇔M6所以p→ <q→r>⇔ ⌝ <p∧q>∨r<2>p→ <q→r>⇔M6<p→q>→r⇔M0∧M1∧M2∧M6所以p→ <q→r>œ<p→q>→r2.18.略2.19.略2.20.将下列公式化成与之等值且仅含{⌝,→}中联结词的公式.<3> <p∧q>↔r.注意到A↔B⇔ <A→B>∧<B→A>和A∧B⇔ ⌝<⌝A⌝∨B>⇔ ⌝<A⌝→B>以及A∨B⇔ ⌝A→B.<p∧q>↔r⇔ <p∧q → r> ∧ <r → p∧q>⇔ <⌝<p⌝→q>→ r>∧ <r→ ⌝<p⌝→q>>⇔ ⌝<<⌝<p⌝→q>→ r>→ ⌝<r→ ⌝<p⌝→q>>>注 联结词越少,公式越长.2.21.证明:<1> <p↑q>⇔ <q↑p>,<p↓q>⇔ <q↓p>.<p↑q>⇔ ⌝<p∧q>⇔ ⌝<q∧p>⇔ <q↑p>.<p↓q>⇔ ⌝<p∨q>⇔ ⌝<q∨p>⇔ <q↓p>.2.22.略2.23.略2.24.略2.25.设A,B,C为任意的命题公式.<1>若A∨C⇔B∨C,举例说明A⇔B不一定成立.<2>已知A∧C⇔B∧C,举例说明A⇔B不一定成立.<3>已知⌝A⇔⌝B,问:A⇔B 一定成立吗?<1>取A=p,B=q,C = 1 <重言式>, 有A∨C⇔ B∨C,但AœB.<2>取A=p,B=q,C = 0 <矛盾式>, 有A∧C⇔ B∧C,但AœB.好的例子是简单,具体,而又说明问题的.<3>一定.2.26.略2.27.某电路中有一个灯泡和三个开关A,B,C.已知在且仅在下述四种情况下灯亮:<1>C的扳键向上, A,B的扳键向下.<2>A的扳键向上, B,C的扳键向下.<3>B,C的扳键向上,A的扳键向下.<4>A,B的扳键向上,C的扳键向下.设F为1表示灯亮,p,q,r分别表示A,B,C的扳键向上.<a>求F的主析取范式.<b>在联结词完备集{⌝,∧}上构造F.<c>在联结词完备集{⌝,→,↔}上构造F.<a>由条件<1>-<4>可知, F的主析取范式为F⇔ <⌝p∧⌝q∧r>∨ <p∧⌝q∧⌝r>∨ <⌝p∧q∧r>∨ <p∧q∧⌝r>⇔m1∨m4∨m3∨m6⇔m1∨m3∨m4∨m6<b>先化简公式F⇔ <⌝p∧⌝q∧r>∨ <p∧⌝q∧⌝r>∨ <⌝p∧q∧r>∨ <p∧q∧⌝r>⇔⌝q∧ <<⌝p∧r>∨ <p∧⌝r>>∨q∧ <<⌝p∧r>∨ <p∧⌝r>>⇔ <⌝q∨q>∧ <<⌝p∧r>∨ <p∧⌝r>>⇔ <⌝p∧r>∨ <p∧⌝r>⇔⌝ <⌝ <⌝p∧r>∧⌝ <p∧⌝r>><已为{⌝,∧}中公式><c>F⇔ <⌝p∧r>∨ <p∧⌝r>⇔⌝⌝ <⌝p∧r>∨ <p∧⌝r>⇔⌝ <⌝p∧r>→ <p∧⌝r>⇔ <p∨⌝r>→⌝ <⌝p∨r>⇔ <r→p>→⌝ <p→r> <已为{⌝,→,↔}中公式>2.28.一个排队线路, 输入为A,B,C,其输出分别为F A,F B,F C.本线路中,在同一时间内只能有一个信号通过,若同时有两个和两个以上信号申请输出时,则按A,B,C的顺序输出.写出F A,F B,F C在联结词完备集{⌝,∨}中的表达式.根据题目中的要求,先写出F A,F B,F C的真值表<自己写>由真值表可先求出他们的主析取范式,然后化成{⌝,∧}中的公式F A⇔m4∨m5∨m6∨m7⇔p <已为{⌝,∧}中公式>F B⇔m2∨m3⇔⌝p∧q <已为{⌝,∧}中公式>F C⇔m1⇔⌝p∧⌝q∧r <已为{⌝,∧}中公式>2.29.略2.30.略习题三3.1.略3.2.略3.3.略3.4.略3.5.略3.6.判断下面推理是否正确.先将简单命题符号化,再写出前提,结论, 推理的形式结构<以蕴涵式的形式给出>和判断过程<至少给出两种判断方法>:<1>若今天是星期一,则明天是星期三；今天是星期一.所以明天是星期三.<2>若今天是星期一,则明天是星期二；明天是星期二.所以今天是星期一.<3>若今天是星期一,则明天是星期三；明天不是星期三.所以今天不是星期一.<4>若今天是星期一,则明天是星期二；今天不是星期一.所以明天不是星期二.<5>若今天是星期一,则明天是星期二或星期三.<6>今天是星期一当且仅当明天是星期三；今天不是星期一.所以明天不是星期三.设p: 今天是星期一,q:明天是星期二,r:明天是星期三.<1>推理的形式结构为<p→r>∧p→r此形式结构为重言式,即<p→r>∧p⇒r所以推理正确. <2>推理的形式结构为<p→q>∧q→p 此形式结构不是重言式,故推理不正确.<3>推理形式结构为<p→r>∧⌝r→⌝p此形式结构为重言式,即<p→r>∧⌝r⇒⌝p故推理正确. <4>推理形式结构为<p→q>∧⌝p→⌝q此形式结构不是重言式, 故推理不正确.<5>推理形式结构为p→ <q∨r>它不是重言式, 故推理不正确. <6>推理形式结构为<p⇒r>∧⌝p→⌝r.此形式结构为重言式,即<p⇒r>∧⌝p⇒⌝r故推理正确.推理是否正确, 可用多种方法证明.证明的方法有真值表法,等式演算法.证明推理正确还可用构造证明法.下面用构造证明法证明<6>推理正确.前提:p⇒r,⌝p结论:⌝r证明:①p⇒r 前提引入②<p→r>∧ <r→p> ①置换③r→p ②化简律④⌝p 前提引入⑤⌝r ③④拒取式所以,推理正确.3.7.略3.8.略3.9.用三种方法<真值表法,等值演算法,主析取范式法>证明下面推理是正确的:若a 是奇数,则a 不能被2 整除.若a 是偶数,则a 能被2 整除.因此,如果a是偶数, 则a不是奇数.令p: a是奇数;q:a 能被2 整除; r:a是偶数.前提:p→ ⌝q,r→ q.结论:r→ ⌝p.形式结构:<p→ ⌝q>∧ <r→ q>→ <r→ ⌝p>.……3.10.略3.11.略3.12.略3.13.略3.14.在自然推理系统P中构造下面推理的证明:<1>前提: p→ <q→r>,p, q结论: r∨s<2>前提:p→q,⌝ <q∧r>,r结论:⌝p<3>前提: p→q结论: p→ <p∧q><4>前提: q→p, q⇒s,s⇒t,t∧r结论: p∧q<5>前提: p→r,q→s,p∧q.结论: r∧s<6>前提:⌝p∨r,⌝q∨s,p∧q结论:t→ <r∨s><1>证明:①②p→<q→r>p前提引入前提引入③④q→rq①②假言推理前提引入⑤r③④假言推理⑥r∨s⑤附加律<2>证明:①②③⌝ <q∧r>⌝q∨⌝rr前提引入①置换前提引入④⑤⑥⌝qp→q⌝p②③析取三段论前提引入④⑤拒取式<3>证明:①p→q前提引入②⌝p∨q①置换③<⌝p∨q>∧ <⌝p∨p>②置换④⌝p∨ <p∧q>③置换⑤p→ <p∧q> ④置换也可以用附加前提证明法,更简单些.<4>证明:①②③④⑤s⇒t<s→t> ∧ <t→s>t→st∧rt前提引入①置换②化简前提引入④化简⑥s③⑤假言推理⑦⑧⑨⑩q⇒s<s→q>∧ <q→s>s→qq前提引入⑦置换⑧化简⑥⑥假言推理○11 q →p前提引入○12 ○13 pp∧q⑩○11 假言推理⑩○12 合取<5>证明:①②p→rq→s前提引入前提引入③④p∧qp前提引入③化简⑤q③化简⑥r①④假言推理⑦s②⑤假言推理⑧r∧s⑥⑦合取<6>证明:①②t⌝p∨r附加前提引入前提引入③④p∧qp前提引入③化简⑤r②④析取三段论⑥r∨s⑤附加说明:证明中,附加提前t,前提⌝q∨s没用上.这仍是正确的推理.3.15.在自然推理系统P中用附加前提法证明下面各推理:<1>前提: p→ <q→r>,s→p,q结论: s→r<2>前提: <p∨q> → <r∧s>,<s∨t>→u结论: p→u<1>证明:①②ss→p附加前提引入前提引入③p①②假言推理④⑤⑥p→ <q→r>q→rq前提引入③④假言推理前提引入⑦r⑤⑥假言推理<2>证明:①②Pp∨q附加前提引入①附加③<p∨q> → <r∧s> 前提引入④⑤r∧sS②③假言推理④化简⑥⑦⑧s∨t<s∨t>→uu⑤附加前提引入⑥⑦假言推理3.16.在自然推理系统P中用归谬法证明下面推理:<1>前提:p→⌝q,⌝r∨q,r∧⌝s结论:⌝p<2>前提: p∨q,p→r,q→s结论: r∨s<1>证明:①②Pp→⌝q结论否定引入前提引入③④⑤⑥⑦⌝q⌝r∨q⌝rr∧⌝sr①②假言推理前提引入③④析取三段论前提引入⑥化简⑧⌝r∧r⑤⑦合取⑧为矛盾式,由归谬法可知, 推理正确.<2>证明:①⌝ <r∨s>结论否定引入②p∨q前提引入③p→r前提引入④q→s前提引入⑤r∨s②③④构造性二难⑥⌝ <r∨s>∧ <r∨s>①⑤合取① ② ③ ④ ⑤ ⑥ ⑦ pp q (rq (rss ←q←qr ①②假言推理 前提引入 前提引入⑥为矛盾式,所以推理正确.3.17.P53 17. 在自然推理系统P 中构造下面推理的证明:只要A 曾到过受害者房间并且11点以前没用离开,A 就犯了谋杀罪.A 曾到过受害者房间.如果A 在 11点以前离开, 看门人会看到他.看门人没有看到他.所以A 犯了谋杀罪.令p :A 曾到过受害者房间;q :A 在11点以前离开了; r : A 就犯了谋杀罪;s :看门人看到A.前提:p ⌝∧q → r ,p ,q → s ,⌝s.结论:r .前提:p ⌝∧q → r ,p ,q → s ,⌝s;结论:r . 证明:①⌝s前提引入 ②q → s前提引入 ③⌝q①②拒取 ④p前提引入 ⑤p ⌝∧q③④合取 ⑥p ⌝∧q → r前提引入 ⑦r ⑤⑥假言推理3.18.在自然推理系统P 中构造下面推理的证明. <1>如果今天是星期六,我们就要到颐和园或圆明园去玩.如果颐和园游人太多,我们就不去颐和园玩.今天是星期六. 颐和园游人太多.所以我们去圆明园玩.<2>如果小王是理科学生,他的数学成绩一定很好.如果小王不是文科生,他必是理科生.小王的数学成绩不好.所以小王是文科学生.<3>明天是晴天, 或是雨天；若明天是晴天,我就去看电影；若我看电影,我就不看书.所以,如果我看书,则明天是雨天.<1>令p : 今天是星期六;q :我们要到颐和园玩;r :我们要到圆明园玩;s :颐和园游人太多.前提:p → <q ∨r >,s → ⌝q ,p ,s.结论:r .前提引入前提引入 p p →q ∨rq ∨r s s → ⌝q ⌝q r ④⑤假言推理 <1>的证明树③⑥析取三段论① p →r前提引入 ② ⌝r前提引入 ③ ⌝p ①②拒取式 ④ ⌝q →p 前提引入 ⑤ q③④拒取式 <2>令p : 小王是理科生,q :小王是文科生,r :小王的数学成绩很好.前提:p →r ,⌝q →p ,⌝r结论:q证明:⌝q p →q ⌝p ⌝r →p <2> 的证明树 r <3>令p : 明天是晴天,q :明天是雨天,r :我看电影,s :我看书. 前提: p ∨q ,p →r ,r →⌝s 结论: s →q证明:① ② sr →⌝s附加前提引入 前提引入 ③ ⌝r①②拒取式 ④ p →r前提引入 ⑤ ⌝p③④拒取式 ⑥ p ∨q前提引入 ⑦ q ⑤⑥析取三段论习题四4.1.将下面命题用0元谓词符号化:<1>小王学过英语和法语. <2>除非李建是东北人,否则他一定怕冷.<1>令F<x>: x学过英语;F<x>: x学过法语; a:小王.符号化为F<a>∧F<b>.或进一步细分,令L<x,y>: x学过y;a:小王; b1: 英语;b2:法语.则符号化为L<a,b1>∧L<a,b2>.<2>令F<x>: x是东北人;G<x>: x怕冷; a:李建.符号化为⌝F<a>→G<a>或⌝G<a>→F<a>.或进一步细分,令H<x,y>: x是y 地方人;G<x>:x 怕冷;a:小王;b: 东北. 则符号化为⌝H<a,b>→G<a>或⌝G<a>→ H<a,b>.4.2.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为<a>,<b>时命题的真值:<1>凡有理数都能被2整除.<2>有的有理数能被2整除. 其中<a>个体域为有理数集合,<b>个体域为实数集合.<1><a>中, ∀xF<x>,其中,F<x>: x能被2整除, 真值为0.<b>中, ∀x<G<x> ∧F<x>>,其中, G<x>:x为有理数,F<x>同<a>中,真值为0.<2><a>中, ∃xF<x>,其中,F<x>: x能被2整除, 真值为1.<b>中, ∃x<G<x> ∧F<x>>, 其中,F<x>同<a>中,G<x>:x为有理数,真值为1.4.3.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为<a>,<b>时命题的真值:<1>对于任意的x,均有x2-2=<x+2><x- 2>.<2>存在x, 使得x+5=9.其中<a>个体域为自然数集合,<b>个体域为实数集合.<1><a>中,∀x<x2-2=<x+2><x- 2>>,真值为1.<b>中, ∀x<F<x>→ <x2-2=<x+2><x- 2>>>>, 其中,F<x>:x为实数,真值为1.<2><a>中,∃x<x+5=9>,真值为1.<b>中, ∃x<F<x> ∧ <x+5=9>>,其中,F<x>: x为实数,真值为1.4.4.在一阶逻辑中将下列命题符号化:<1>没有不能表示成分数的有理数. <2>在北京卖菜的人不全是外地人.<3>乌鸦都是黑色的. <4>有的人天天锻炼身体.没指定个体域, 因而使用全总个体域.<1>⌝∃x<F<x>∧⌝G<x>>或∀x<F<x>→G<x>>,其中,F<x>:x为有理数,G<x>:x能表示成分数.<2>⌝∀x<F<x>→G<x>>或∃x<F<x>∧⌝G<x>>,其中,F<x>:x在北京卖菜,G<x>:x是外地人.<3>∀x<F<x> →G<x>>,其中,F<x>: x是乌鸦,G<x>: x是黑色的.<4>∃x<F<x> ∧G<x>>,其中,F<x>:x是人,G<x>:x天天锻炼身体.4.5.在一阶逻辑中将下列命题符号化:<1>火车都比轮船快. <2>有的火车比有的汽车快. <3>不存在比所有火车都快的汽车. <4>"凡是汽车就比火车慢"是不对的.因为没指明个体域,因而使用全总个体域<1>∀x∀y<F<x> ∧G<y>→H<x,y>>,其中,F<x>: x是火车,G<y>:y是轮船,H<x,y>:x比y快.<2>∃x∃y<F<x> ∧G<y>∧H<x,y>>, 其中, F<x>:x是火车,G<y>:y是汽车,H<x,y>:x比y快.<3>⌝∃x<F<x>∧∀y<G<y>→H<x,y>>>或∀x<F<x>→∃y<G<y>∧⌝H<x,y>>>,其中,F<x>:x是汽车,G<y>:y是火车,H<x,y>:x比y快.<4>⌝∀x∀y<F<x>∧G<y>→H<x,y>>或∃x∃y<F<x>∧G<y>∧⌝H<x,y>>,其中,F<x>:x是汽车,G<y>:y是火车,H<x,y>:x比y慢. 4.6.略4.7.将下列各公式翻译成自然语言,个体域为整数集®,并判断各命题的真假.<1>∀x∀y∃z<x- y=z>;<2>∀x∃y<x⋅y =1>.<1>可选的翻译:①"任意两个整数的差是整数."②"对于任意两个整数,都存在第三个整数,它等于这两个整数相减."③"对于任意整数x和y,都存在整数z,使得x- y=z."选③,直接翻译,无需数理逻辑以外的知识.以下翻译意思相同, 都是错的:"有个整数,它是任意两个整数的差.""存在一个整数,对于任意两个整数,第一个整数都等于这两个整数相减."❶ "存在整数z,使得对于任意整数x 和y,都有x- y= z."这3个句子都可以符号化为∃z∀x∀y<x- y=z>.0量词顺序不可随意调换.<2>可选的翻译:①"每个整数都有一个倒数."②"对于每个整数,都能找到另一个整数,它们相乘结果是零."③"对于任意整数x,都存在整数y, 使得x⋅y =z."选③,是直接翻译,无需数理逻辑以外的知识.4.8.指出下列公式中的指导变元, 量词的辖域,各个体变项的自由出现和约束出现:<3>∀x∃y<F<x,y>∧ G<y,z>> ∨ ∃xH<x,y, z>∀x∃y<F<x,y>∧ G<y,z>>∨ ∃x H<x,y,z>前件∀x∃y<F<x,y>∧G<y,z>>中,∀ 的指导变元是x, ∀ 的辖域是∃y<F<x,y>∧G<y,z>>;∃ 的指导变元是y, ∃ 的辖域是<F<x,y>∧G<y,z>>.后件∃xH<x,y,z>中, ∃ 的指导变元是x, ∃ 的辖域是H<x,y,z>.整个公式中, x约束出现两次, y约束出现两次,自由出现一次;z 自由出现两次.4.9.给定解释I如下:<a>个体域D I为实数集合\.<b>D I中特定元素↓a=0.<c>特定函数↓f<x,y>=x-y,x,y∈D I.<d>特定谓词↓F<x,y>:x=y,↓G<x,y>:x<y,x,y∈D I.说明下列公式在I下的含义,并指出各公式的真值:<1>∀x∀y<G<x,y>→⌝F<x,y>><2> ∀x∀y<F<f<x,y>,a>→G<x,y>><3>∀x∀y<G<x,y>→⌝F<f<x,y>,a>><4> ∀x∀y<G<f<x,y>,a> →F<x,y>><1>∀x∀y<x<y→x≠y>,真值为1.<2>∀x∀y<<x-y=0> →x<y>, 真值为0.<3>∀x∀y<<x<y>→ <x-y≠0>>,真值为1.<4>∀x∀y<<x-y<0> → <x=y>>,真值为0.4.10.给定解释I如下:<a>个体域D=Æ<Æ为自然数>.<b>D中特定元素↓a=2.<c>D上函数↓f<x,y>=x+y,↓g<x,y>=x·y.<d>D上谓词↓F<x,y>:x=y.说明下列公式在I下的含义,并指出各公式的真值:<1> ∀xF<g<x,a>,x><2> ∀x∀y<F<f<x,a>,y> →F<f<y,a>,x>><3> ∀x∀y∃z<F<f<x,y>,z><4> ∃xF<f<x,x>,g<x,x>><1>∀x<x·2=x>,真值为0.<2>∀x∀y<<x+2=y> → <y+2=x>>,真值为0.<3>∀x∀y∃z<x+y=z>,真值为1.<4>∃x<x+x=x·x>,真值为1.4.11.判断下列各式的类型:<1> F<x,y> → <G<x,y>→ F<x,y>>.<3> ∀x∃yF<x,y>→ ∃x∀yF<x,y>.<5> ∀x∀y<F<x,y>→ F<y,x>>.<1> 是命题重言式p → <q → p>的代换实例,所以是永真式.<3> 在某些解释下为假<举例>, 在某些解释下为真<举例>, 所以是非永真式的可满足式.<5> 同<3>.4.12.P69 12. 设I 为一个任意的解释,在解释I 下,下面哪些公式一定是命题?<1> ∀xF<x,y>→ ∃yG<x,y>.<2> ∀x<F<x> → G<x>>∧ ∃y<F< y>∧ H< y>>.<3> ∀x<∀yF<x,y>→ ∃yG<x,y>>.<4> ∀x<F<x> ∧ G<x>> ∧ H< y>.<2>, <3>一定是命题,因为它们是闭式.4.13.略4.14.证明下面公式既不是永真式也不是矛盾式:<1> ∀x<F<x> →∃y<G<y> ∧H<x,y>>><2> ∀x∀y<F<x> ∧G<y>→H<x,y>><1> 取个体域为全总个体域.解释I1: F<x>:x为有理数,G<y>: y为整数,H<x,y>: x<y在I1下: ∀x<F<x>→∃y<G<y> ∧H<x,y>>>为真命题,所以该公式不是矛盾式.解释I2:F<x>,G<y>同I1,H<x,y>: y整除x.在I2下: ∀x<F<x>→∃y<G<y> ∧H<x,y>>>为假命题,所以该公式不是永真式.<2> 请读者给出不同解释,使其分别为成真和成假的命题即可.4.15.<1>给出一个非闭式的永真式.<2> 给出一个非闭式的永假式.<3> 给出一个非闭式的可满足式,但不是永真式.<1>F<x>∨ ⌝F<x>.<2>F<x>∧ ⌝F<x>.<3> ∀x<F<x,y>→ F<y,x>>.习题五5.1.略5.2.设个体域D={a,b,c}, 消去下列各式的量词:<1> ∀x∃y<F<x> ∧G<y>><2> ∀x∀y<F<x> ∨G<y>><3> ∀xF<x> →∀yG<y><4> ∀x<F<x,y>→∃yG<y>><1> ∀x∃y<F<x> ∧G<y>>⇔∀xF<x> ∧∃yG<y>⇔ <F<a>∧F<b>> ∧F<c>> ∧ <G<a>∨G<b>∨G<c>><2> ∀x∀y<F<x> ∨G<y>>⇔∀xF<x> ∨∀yG<y>⇔ <F<a>∧F<b> ∧F<c>>∨ <G<a> ∧G<b>∧G<c>><3> ∀xF<x> →∀yG<y>⇔ <F<a>∧F<b> ∧F<c>>→ <G<a>∧G<b>∧G<c>><4> ∀x<F<x,y>→∃yG<y>>⇔∃xF<x,y> →∃yG<y>⇔ <F<a,y> ∨F<b,y> ∨F<c,y>>→ <G<a>∨G<b> ∨G<c>>5.3.设个体域D={1,2},请给出两种不同的解释I1和I2,使得下面公式在I1下都是真命题,而在I2下都是假命题.<1> ∀x<F<x> →G<x>><2> ∃x<F<x> ∧G<x>><1>I1:F<x>:x≤2,G<x>:x≤3F<1>,F<2>,G<1>,G<2>均为真,所以∀x<F<x>→G<x>>⇔ <F<1> →G<1>∧ <F<2>→G<2>>为真.I2: F<x>同I1,G<x>:x≤0则F<1>,F<2>均为真,而G<1>,G<2>均为假,∀x<F<x>→G<x>>为假.<2>留给读者自己做.5.4.略5.5.给定解释I如下:<a>个体域D={3,4}.<b>↓f<x>为↓f<3>=4,↓f<4>=3.<c>↓F<x,y>为↓F<3,3>=↓F<4,4>=0,↓F<3,4>=↓F<4,3>=1.试求下列公式在I下的真值:(1)∀x∃yF<x,y>(2)∃x∀yF<x,y><3> ∀x∀y<F<x,y>→F<f<x>,f<y>>>(1)∀x∃yF<x,y>⇔ <F<3,3> ∨F<3,4>> ∧ <F<4,3> ∨F<4,4>>⇔ <0∨1> ∧ <1∨0>⇔1(2)∃x∀yF<x,y>⇔ <F<3,3> ∧F<3,4>> ∨ <F<4,3> ∧F<4,4>>⇔ <0∧1> ∨ <1∧0>⇔0<3> ∀x∀y<F<x,y>→F<f<x>,f<y>>>⇔ <F<3,3>→F<f<3>,f<3>>>∧ <F<4,3> →F<f<4>,f<3>>>∧ <F<3,4> →F<f<3>,f<4>>>∧ <F<4,4> →F<f<4>,f<4>>>⇔ <0→0> ∧ <1→1>∧ <1→1> ∧ <0→0>⇔15.6.略5.7.略5.8.在一阶逻辑中将下列命题符号化,要求用两种不同的等值形式.<1> 没有小于负数的正数.<2> 相等的两个角未必都是对顶角.<1>令F<x>:x小于负数,G<x>:x是正数.符合化为:∃⌝x<<F<x>∧ G<x>>⇔ ∀x<G<x>→ ⌝G<x>>.<2>令F<x>:x是角,H<x,y>:x和y 是相等的, L<x,y>:x与y是对顶角.符合化为:⌝∀x∀y<F<x>∧ F<y>∧ H<x,y>→ L<x,y>>⇔ ∃x∃y<F<x>∧ F<y>∧ H<x,y>∧ ⌝L<x,y>>⇔ ∃x<F<x>∧ <∃y<F<y>∧ H<x,y>∧ ⌝L<x,y>>>.5.9.略5.10.略5.11.略5.12.求下列各式的前束范式.<1>∀xF<x> → ∀yG<x,y>;<3>∀xF<x,y>↔ ∃xG<x, y>;<5>∃x1F<x1,x2>→ <F<x1>→ ∃⌝x2G<x1,x2>>.前束范式不是唯一的.<1> ∀xF<x> → ∀yG<x,y>⇔ ∃x<F<x> → ∀yG<x,y>>⇔ ∃x∀y<F<x>→ G<x,y>>.<3> ∀xF<x,y>↔ ∃xG<x,y>⇔ <∀xF<x,y>→ ∃xG<x,y>>∧ <∃xG<x,y> → ∀xF<x,y>>⇔ <∀x1F<x1,y>→ ∃x2G<x2,y>>∧ <∃x3G<x3,y>→ ∀x4F<x4,y>>⇔ ∃x1∃x2<F<x1,y> → G<x2,y>>∧ ∀x3∀x4<G<x3,y>→ F<x4,y>>⇔ ∃x1∃x2∀x3∀x4<<F<x1,y>→ G<x2,y>>∧ <G<x3,y>→ F<x4,y>>>.5.13.将下列命题符号化,要求符号化的公式全为前束范式:<1> 有的汽车比有的火车跑得快.<2> 有的火车比所有的汽车跑得快.<3> 说所有的火车比所有的汽车跑得快是不对的.<4> 说有的飞机比有的汽车慢是不对的.<1>令F<x>:x是汽车,G< y>:y是火车,H<x,y>:x 比y跑得快.∃x<F<x> ∧ ∃y<G< y>∧ H<x,y>>⇔ ∃x∃y<F<x> ∧ G<y>∧ H<x,y>>.<2>令F<x>: x是火车,G<y>:y是汽车,H<x,y>:x 比y跑得快.∃x<F<x> ∧ ∀y<G< y> → H<x,y>>>⇔ ∃x∀y<F<x> ∧ <G<y> → H<x,y>>>.0错误的答案:∃x∀y<F<x>∧ G<y>→ H<x,y>>.<3>令F<x>: x是火车,G<y>:y是汽车,H<x,y>:x 比y跑得快.⌝∀x<F<x>→ ∀y<G<y>→ H<x,y>>>⇔ ⌝∀x∀y<F<x>→ <G<y>→ H<x,y>>>⇔ ⌝∀x∀y<F<x>∧ G<y>→ H<x,y>> <不是前束范式>⇔ ∃x∃y<F<x> ∧ G<y>∧ H<x,y>>.<4>令F<x>: x是飞机,G<y>:y是汽车,H<x,y>:x 比y跑得慢.⌝ ∃x<F<x>∧ ∃y<G<y>∧ H<x,y>>>⇔ ⌝ ∃x∃y<F<x>∧ G<y>∧ H<x,y>><不是前束范式>⇔ ∀x∀y⌝ <F<x>∧ G<y>∧ H<x,y>>⇔ ∀x∀y<F<x>∧ G<y>→ ⌝H<x,y>>.5.14.略5.15.在自然推理系统F中构造下面推理的证明:<1>前提: ∃xF<x> → ∀y<<F<y>∨ G<y>>→ R<y>>,∃xF<x>结论:∃xR<x>.<2>前提:∀x<F<x>→ <G<a> ∧R<x>>>,∃xF<x>结论:∃x<F<x> ∧R<x>><3>前提:∀x<F<x>∨G<x>>,⌝∃xG<x>结论:∃xF<x><4>前提:∀x<F<x>∨G<x>>,∀x<⌝G<x>∨⌝R<x>>,∀xR<x>结论:∀xF<x>①∃xF<x> → ∀y<<F<y> ∨ G<y>>→ R<y>> 前提引入②∃xF<x> 前提引入③∀y<<F<y> ∨ G<y>> → R<y>> ①②假言推理④<F<c>∨ G<c>>→ R<c> ③UI⑤F<c> ①EI⑥F<c>∨ G<c> ⑤附加⑦⑧R<c>∃xR<x>④⑥假言推理⑦EG<2>证明:①∃xF<x> 前提引入②F<c >①EI③∀x<F<x>→ <G<a>∧ <R<x>>> 前提引入④F<c> → <G<a>∧R<c>>④UI⑤G<a>∧R<c> ②④假言推理⑥R<c> ⑤化简⑦F<c>∧R<c> ②⑥合取⑧∃x<F<x>∧R<x>>⑥E G<3>证明:①⌝∃xG<x> 前提引入②∀x⌝G<x> ①置换③⌝G<c>②UI④∀x<F<x>∨G<x> 前提引入⑤F<c>∨G<c>④UI⑥F<c> ③⑤析取三段论⑦∃xF<x>⑥E G<4>证明:①∀x<F<x>∨G<x>> 前提引入②F<y>∨G<y>①UI③∀x<⌝G<x>∨⌝R<x>> 前提引入④⌝G<y>∨⌝R<y>③UI⑤∀xR<x> 前提引入⑥R<y >⑤UI⑦⌝G<y> ④⑥析取三段论⑧F<y> ②⑦析取三段论⑥∀xF<x> U G5.16.略。

第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(1)证明：① S结论否定引入② S→P前提引入③ P①②假言推理④ P→(q→r)前提引入⑤ q→r③④假言推论⑥ q前提引入⑦ r⑤⑥假言推理（2）证明：① p附加前提引入② p∨q①附加③ (p∨q)→(r∧s)前提引入④ r∧s②③假言推理⑤ s④化简⑥ s∨t⑤附加⑦ (s∨t)→u前提引入⑧ u⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

离散数学屈婉玲课后习题答案【篇一：离散数学第四版课后答案】xt>第1章习题解答1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。

分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。

本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。

其次，4）这个句子是陈述句，但它表示的判断结果是不确定。

又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。

（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。

这里的“且”为“合取”联结词。

在日常生活中，合取联结词有许多表述法，例如，“虽然??，但是??”、“不仅??，而且??”、“一面??，一面??”、“??和??”、“??与??”等。

但要注意，有时“和”或“与”联结的是主语，构成简单命题。

例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。

1．2 （1）p: 2是无理数，p为真命题。

（2）p:5能被2整除，p为假命题。

（6）p→q。

其中，p:2是素数，q：三角形有三条边。

由于p与q都是真命题，因而p→q为假命题。

（7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。

由于p为假命题，q为真命题，因而p→q为假命题。

（8）p:2000年10月1日天气晴好，今日（1999年2月 13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。

（9）p：太阳系外的星球上的生物。

它的真值情况而定，是确定的。

习题一1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明.答：此命题是简单命题，其真值为1.（2是无理数.答：此命题是简单命题，其真值为1.（3）3是素数或4是素数.答：是命题，但不是简单命题，其真值为1.x+<（4）235答：不是命题.（5）你去图书馆吗？答：不是命题.（6）2与3是偶数.答：是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！答：不是命题.（9）吸烟请到吸烟室去！答：不是命题.（10）圆的面积等于半径的平方乘以π.答：此命题是简单命题，其真值为1.（11）只有6是偶数，3才能是2的倍数.答：是命题，但不是简单命题，其真值为0.（12）8是偶数的充分必要条件是8能被3整除.答：是命题，但不是简单命题，其真值为0.（13）2008年元旦下大雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:（1）p：中国有四大发明.（2）p:错误!未找到引用源。

是无理数.（7）p:刘红与魏新是同学.（10）p:圆的面积等于半径的平方乘以π.（13）p:2008年元旦下大雪.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（1是有理数.是无理数.p.q.其否定式q的真值为1.（2不是无理数.答：是有理数. p 不是无理数. q 是有理数. 其否定式q 的真值为1.（3）2.5是自然数.答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1.（4）ln1是整数.答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1.4.将下列命题符号化，并指出真值. （1）2与5都是素数答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1.（2）不但π是无理数，而且自然对数的底e 也是无理数.答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数.答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧⌝，其真值为1. （4）3是偶素数.答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数.答：p ：4是素数，q ：4是偶数，符号化为p q ⌝∧⌝，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数.（4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数.答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ⌝∨⌝，其真值为1.(5) 符号化：r s ⌝∨⌝，其真值为0. 6.将下列命题符号化.（1）小丽只能从筐里拿一个苹果或一个梨.答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ⌝∧∨∧⌝. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化答:列出两种符号化的真值表：p q0 0 0 00 1 1 11 0 1 11 1 0 1根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值.（1）只要错误!未找到引用源。

离散数学(屈婉玲)答案-1-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所以公式类型为永真式//最后一列全为1（5）公式类型为可满足式（方法如上例）//最后一列至少有一个1（6）公式类型为永真式（方法如上例）//第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.主析取范式为∑(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 ⑤⑥拒取式证明（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)在两个个体域中都解释为)(x∀，在（a）中为假命题，在(b)中为真命xF题。

离散数学习题答案习题二及答案：（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。

7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())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 ⇔⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧⌝∨∧∧ 13567m m m m m ⇔∨∨∨∨，此即主析取范式。

主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ⇔∧∧。

9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨⌝∧ 解：公式的真值表如下：由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式1234567m m m m m m m ⇔∨∨∨∨∨∨习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。

前提：,,,p q q r r s p ⌝∨⌝∨→结论：s 证明：① p 前提引入 ② p q ⌝∨ 前提引入 ③ q ①②析取三段论 ④ q r ⌝∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入⑦ s ⑤⑥假言推理15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论：p u →证明：用附加前提证明法。