离散数学(屈婉玲)答案-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⇔1 17．判断下面一段论述是否为真：“π是无理数。

并且，如果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)⇔∑(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,均有2=(x+)(x).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x):2=(x+)(x).G(x): x+5=9.(1)在两个个体域中都解释为)(x∀，在（a）中为假命xF题，在(b)中为真命题。

离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案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)在两个个体域中都解释为)∀，在（a）中为假命题，在(b)中为真命题。

离散数学答案屈婉玲版第二版高等教育出版社课后答案离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1,求下列各命题公式的真值。

(1) p V (q A r)二0 V (0 A 1) =0(2) ( p?r)A (「q V s)二(0?1)A (1 V 1) = 0A 1= 0.(3) ( — p A 一q A r) ?(p A q A「r)二(1 A 1 A 1) ? (0 A 0A 0)=0(4) (一「A s)—(p A _q) = (0A 1)—(1 A 0) =0—0=117.判断下面一段论述是否为真：“二是无理数。

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

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

”答：p:二是无理数1q: 3 是无理数0r: ' 2是无理数1s: 6能被2整除1t: 6 能被4整除0命题符号化为：p A (q —r) A (t —s)的真值为1,所以这一段的论述为真。

19.用真值表判断下列公式的类型：(4) (p —q) —( 一q—一p)(5) (p A r) ' ( 一p A 一q)(6) ((p —q) A (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. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值?⑴飞A q-q)(2) (p -(p V q)) V (p -r)(3) (p V q) -(p A r)答：(2) (p—(p V q) )V (p —r)=(—p V (p V q)) V (_p V r) u - p V p V q V r= 1 所以公式类型为永真式⑶P q r p V q p A r (p V q)—(p A 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) A (p —r)二(p —(q A r))⑷(p A - q) V (-p A q)=(p V q) A 一(p A q)证明(2) (p —q) A (p —r)(一p V q) A ( 一p V r):二_ p V (q A r))二p—(q A r)(4) (p A - q) V ( 一p A q)u (p V (一p A q)) A(_ q V (一p A q)-(p V _ p) A (p V q) A ( 一q V 一p) A ( 一q V q)=1 A (p V q) A 一(p A q) A 1二(p V q) A _ (p A q)5. 求下列公式的主析取范式与主合取范式，并求成真赋值(1) ( _p—q) —(一q V p)(2) _(P —q) A q A r(3) (p V (q A r)) -(p V q V r)解：(1) 主析取范式(- p-q) —( 一q p)二_(p q) ( 一q p)=(- p -q) ( 一q p)=(一p _q) (一q p) (一q _p) (p q) (p _q)u ( - p _q) (p _q) (p q)-刀(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 i=n (i)(2) 主合取范式为：_(p —q) q r=—(一p q) q ru (p _q) q 产0所以该式为矛盾式?主合取范式为n (0,123,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 i二 1所以该式为永真式永真式的主合取范式为1主析取范式为刀（0,123,4,5,6,7）第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明:(2) 前提：p—. q, —(q r),r(4)前提：q— p,q『s,s『t,t r结论：p q证明：（2）①—(q r) 前提引入②—q —r ①置换③q，一「②蕴含等值式④r 前提引入⑤一q ③④拒取式⑥p- q 前提引入⑦」p (3)⑤⑥拒取式证明（4）：①t r 前提引入②t ①化简律③qi s 前提引入④s—?t 前提引入⑤q r t ③④等价三段论( q > t)(t r q)?⑤置换炉(q >t)⑥化简⑧q ②⑥假言推理⑨ q—；p 前提引入⑩p ⑧⑨假言推理(11)p q ⑧⑩合取15在自然推理系统P中用附加前提法证1 F面各推理:结论：_ p(1)前提：pr (qr r),s r p,q结论：s —? r ①s 附加前提引入②Sr 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.在一阶逻辑中将下面将下面命题符号化，并分别讨论个体域限制为的真值：(1)对于任意 x,均有 2=(x+ )(x ).证明(a),(b) 条件时命题(2)存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合.解:F(x): 2=(x+ 一)(x 一).G(x): x+5=9.(1) 在两个个体域中都解释为-xF(x)，在(a)中为假命题，在(b)中为真命题。

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

（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（pr）∧(﹁q∨s) ⇔（01）∧(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) ⌝(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 ⑤⑥拒取式证明（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 是矛盾式,所以推理正确.。

第一章 命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（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.5.将下列命题符号化，并指出真值：（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；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p ：刘晓月选学英语，q ：刘晓月选学日语；.7.因为p 与q 不能同时为真.13.设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.16 设p 、q 的真值为0；r 、s 的真值为1，求下列各命题公式的真值。

（1）p ∨(q ∧r)⇔ 0∨(0∧1) ⇔（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．判断下面一段论述是否为真：“π是无理数。

第一章部分课后习题参考答案16设p 、q 的真值为0; r. s 的真值为1,求下列各命题公式的真值。

(1) pV (qAr) <=> 0V (0A1) o0(2) (p<-r) A (—'qVs) O (OTL) A (IV1) o0/\lo0.(3) ( A -•qAr) ^(p Aq A —^r) <=> ( 1 Al Al) — (0A0A0) <=>0 (4) ( ->r As) — (P /X F ) O (0A1) -* (1 AO) oO —Ool17. 判断下面一段论述是否为真：“兀是无理数。

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

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

”答：P ：兀是无理数1 q ： 3是无理数0 r:、迈是无理数1 s ： 6能被2整除1 t: 6能被4整除0命题符号化为：pA(q-r)A(t-*s)的真值为1,所以这一段的论述为真。

19. 用真值表判断下列公式的类型: (4) (p — q) f (「qf 「p) (5) (pAr)㈠"(「p/\「q)(6) 公式类型为永真式(方法如上例)第二章部分课后习题参考答案(6) ((pf q)A (qf r)) f (pf r)答:(4)Pqpf q ~>q「p 「qf 「p 「P )0 0 1 1 1 10 1 1 0 1 11 0 0 1 0 01 1 1 0 01(pf q) — (「qf1 1 1 1所以公式类型为永真式(5) 公式类型为可满足式(方法如上例)3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1)「(pAq~*q)(2)(pf (pVq)) V (p-*r)(3)(pVq) f (pAr)答：(2) (p~* (p Vq) ) V (p-*r)<=>(~i pV (pVq))V (-1pVr)0_,pVpVqV r<=>l 所以公式类型为永真式(3) P Q r pVq p Ar (pVq) f (p Ar)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)(pf q) A (p-*r) <=> (p~* (qAr))(4)(pA-'q) V (-^pAq) <=> (pVq) A(pAq)证明(2) (p-*q) A (p~*r)<=> (-'pVq) A (-'pVr)<=> -'pV (qAr))Opf (qAr)(4) (pA_,q)V ("'pAq) O(pV (_,pAq)) /\ (「qV (~>p/\q)<=> (pV -^p) A (pVq) A (-'qV -^P) /XGqVq)Ol/\ (pVq) A -1 (pAq) Al<=> (pVq) A (pAq)5.求下列公式的主析取范式及主合取范式，并求成真赋值(1)(「pf q) —(「qVp)(2)「(pf q) AqAr(3)(pV (qAr)) -* (pVqVr)解：(1)主析取范式(「pf q) C-1 v)O-!(v)v(-w)'V)O (—>A_1)V (-1A)V (~'A_1)V(A)V(A-1)O (-1A-1) V(A->)V(A)O w；() v rn2 v0刀(0, 2, 3)主合取范式：(_,p-*Q)-*(_, v)°-(v) v (-v)<^=*> ( ~i A -1 ) V ( -' V )O(-ipv (-> v ) ) A (~'q v (~1 v ))01 A (v ~n)O (\/ -i) O Mion⑴(2)主合取范式为：-1(P-* q) AA<=>_'(_1V)AAO (人一i) /\ 人<=>0所以该式为矛盾式.主合取范式为口(0,1, 2, 3, 4, 5, 6, 7)矛盾式的主析取范式为0(3)主合取范式为:(pv ( A )) -* (v v) O-i (pv ( A )) -* (v v)<=>(_'PA (_1V _1))V ( V V )O(-ipv ( V V ) ) A ( (~' V -') ) 7 ( V V ))<=>1A 101所以该式为永真式. 永真式的主合取范式为1 主析取范式为E (0,1, 2, 3, 4, 5, 6, 7)第三章部分课后习题参考答案14. 在自然推理系统P 中构造下面推理的证明： (2)前提：,—I (A ) 结论：->p (4) 前提：TROA 结论：A前提引入 ① 置换② 蕴含等值式 前提引入 ③④拒取式 前提引入 ⑤⑥拒取式证明：(2) ①7八) (2) —1 7 -1 ③-> -1 ④r ⑤ -iq ⑥ T ⑦ —'p (3) 证明(4)：®A前提引入①化简律③O 前提引入 ④O 前提引入⑤O③④等价三段论⑥（T ） 人（T ） ⑤置换 ⑦（T ） ⑥化简⑧q ②⑥假言推理 ⑨T 前提引入 ⑩P⑧⑨假言推理(ID A⑧⑩合取15在自然推理系统P 中用附加前提法证明下面各推理: （1）前提：PT （T ）T 结论：T证明®s附加前提引入 ②T 前提引入 ®P①②假言推理④PT 1 （T ）前提引入 ⑤T ③④假言推理 ⑥q前提引入 ⑦r⑤⑥假言推理16在自然推理系统P 中用归谬法证明下面各推理:（1）前提： T —）—1 V —I 结论：-<P 证明：结论的否定引入前提引入 ©P②p-> —q ③ 一iq①②假言推理④「V 前提引入⑤「r ④化简律@r A ~'s 前提引入⑦r ⑥化简律®TA -ir ⑤⑦合取由于最后一步rA -r是矛盾式，所以推理正确.第四章部分课后习题参考答案3.在一阶逻辑中将下面将下面命题符号化，并分别讨论个体域限制为(a), (b)条件时命题的真值：(1)对于任意x,均有以-2二(0(x-2).(2)存在x,使得5二9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x):以-2二(护)6-卩).G(x): 5=9.(1)在两个个体域中都解释为V A F(A),在(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,均有错误！未找到引用源。

第一章 命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（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.5.将下列命题符号化，并指出真值：（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；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p ：刘晓月选学英语，q ：刘晓月选学日语；.7.因为p 与q 不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）pq ，真值为1；（4）p→r，若p 为真，则p→r 真值为0，否则，p→r 真值为1.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．判断下面一段论述是否为真：“π是无理数。