离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案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）（⌝(4)（176能被2q:3r:2s:619（4）(p（5）(p（6）((p答：（pqp→q⌝0011111011011110010011110011所以公式类型为永真式（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 qrp∨qp∧r（p∨q）→(p∧r)0000010010014.(2)(p→(4)(p∧证明（2（45.(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⇔1∧(p⇔(p∨⇔∏(2)⌝(p→q)⇔(p∧(3)⇔⌝⇔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②t③q④s⑤q⑥（⑦（⑧q⑨q⑩p15在自然推理系统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③﹁④￢⑤￢⑥r⑦r⑧r3.:(1)均有2=(x+)(x).(2)其中(a)(b)解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为)(x∀，在（a）中为假命题，在(b)中为真命题。

xF(2)在两个个体域中都解释为)∃，在（a）(b)中均为真命题。

(xxG4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解:(1)F(x):x能表示成分数H(x):x是有理数命题符号化为:))x∧⌝⌝∃Fx)((xH((2)F(x):x是北京卖菜的人H(x):x是外地人命题符号化为:))xF⌝∀x→(x()(H5.(1)(3)解:9.(a)(b)D=0.(c)y,x,y(d)特定谓词(x,y):x=y,(x,y):x<y,x,y答10.给定解释I如下：（a）个体域D=N(N为自然数集合).（b）D中特定元素=2.（c）D上函数=x+y,(x,y)=xy.（d）D上谓词(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1)xF(g(x,a),x)(2) x y(F(f(x,a),y)→F(f(y,a),x)答:(1)对于任意自然数x,都有2x=x,真值0.(2)对于任意两个自然数x,y,使得如果x+2=y,那么y+2=x.真值0.11.判断下列各式的类型: (1)(3)yF(x,y).解:(1)因为1)()(⇔∨⌝∨⌝⇔→→p q p p q p 为永真式； 所以为永真式；所以,13.(1)(F(x) (2)G(x)H(x))解(2)F(x)：x 出生在山东,G(x):x 出生在北京,H(x):x 出生在江苏,成假解释.F(x)：x 会吃饭,G(x)：x 会睡觉,H(x)：x 会呼吸.成真解释.第五章部分课后习题参考答案5.给定解释Ｉ如下:(a)个体域D={3,4}; (b))(x f 为3)4(,4)3(==f f(c)1F=F=FFxy=F为.,0)3,4((=)4,4()4,3(),)3,3(试求下列公式在Ｉ下的真值.(1))yF∀x∃x(y,(3))))xFFy∀f∀x→y),(((),f(y(x解:(1)))xyxFyFx∨∃⇔∀∀x)3,(4,(((x,)F(2))))yFfxFxx→y∀∀(),f(((y)(,12.求下列各式的前束范式。

(1)(5)∃解(5)∃15.(1)(2)R(x))),xF(x)证明①∃②F(c)③(∃xF④((∀y⑤(F(c)⑥F(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))⑦EG第六章部分课后习题参考答案5.确定下列命题是否为真：（1）∅⊆∅真（2）∅（3）∅（4）∅（5）｛（6）｛（7）｛（8）｛6．设（1）｛｛（2）｛（3）｛｛a （4）｛∅8（1）｛（2）｛1（3）｛∅（4）｛∅，｛∅｝｝P(A)={∅,{1},{{2,3}},{1，{2，3}}}14．化简下列集合表达式：（1）（A B ） B ）-（A B ）（2）（（A B C ）-（B C ）） A解:(1)（A B ） B ）-（A B ）=（A B ） B ） ～（A B ）=（A B） ～（A B）) B=∅ B=∅（2）（（A B C）-（B C）） A=（（A B C） ～（B C）） A=（A ～（B C）） （（B C） ～（B C）） A=（A ～（B C）） ∅ A=（A ～（B C）） A=A18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。

已知6个会打网球的人都会打篮球或排球。

求不会打球的人数。

解:阿A={会打篮球的人}，B={会打排球的人}，C={会打网球的人}21.（1）（2）（3）（4）解:（1（2（3（4）27、设A,B,C是任意集合，证明(1)(A-B)-C=A-B⋃C(2)(A-B)-C=(A-C)-(B-C)证明(1)(A-B)-C=(A ～B) ～C=A (～B ～C)=A ～(B⋃C)=A-B⋃C(2)(A-C)-(B-C)=(A ～C) ～(B ～C)=(A ～C) (～B C)=(A ～C ～B) (A ～C C)=(A ～C ～B) ∅=A ～(B ⋃C )=A-B ⋃C 由（1）得证。

第七章部分课后习题参考答案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 ⋃解：A ⋃A ⋂dom(A ∨14.设求R 解：R R -1,R ↑R[{1,2}]=ran(R|{1,2})={2,3}16．设A={a,b,c,d}，1R ，2R 为A 上的关系，其中1R ={},,,,,a a a b d求23122112,,,R R R R R R 。

解:R 1 R 2={<a,d>,<a,c>,<a,d>}R2 R1={<c,d>}R12=R1 R1={<a,a>,<a,b>,<a,d>}R22=R2 R2={<b,b>,<c,c>,<c,d>}R23=R2 R22={<b,c>,<c,b>,<b,d>}36．设A={1，2，3，4}，在A⨯A上定义二元关系R，∀<u,v>,<x,y>∈A⨯A，〈u,v>R<x,y>⇔u+y=x+v.(1)证明R是A⨯A上的等价关系.(2)（1∴∵∴∴∴∴R若则∴∴∴R是A×A上的等价关系(2)∏={{<1,1>,<2,2>,<3,3>,<4,4>},{<2,1>,<3,2>,<4,3>},{<3,1>,<4,2>}, {<4,1>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>}}41.设A={1，2，3，4}，R为A⨯A上的二元关系,∀〈a，b〉，〈c，d〉∈A⨯A, 〈a，b〉R〈c，d〉⇔a+b=c+d(1)证明R为等价关系.(2)求R导出的划分.(1)证明：∀<a ，b 〉∈A ⨯Aa+b=a+b ∴<a,b>R<a,b> ∴R 是自反的任意的<a,b>,<c,d>∈A ×A 设<a,b>R<c,d>，则a+b=c+d ∴c+d=a+b ∴<c,d>R<a,b> ∴R 是对称的若则∴∴∴(2)∏43.解: (1)(2)45.解:(a)A={a,b,c,d,e,f,g}R ={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>}A I ⋃ (b)A={a,b,c,d,e,f,g}R ={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}A I ⋃46.分别画出下列各偏序集<A,R >的哈斯图,并找出A 的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e}R ={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}⋃I A .(2)A={a,b,c,d,e},R ={<c,d>}⋃IA.解:(1)(2)项目(1)(2) 极大元:ea,b,d,e 极小元:aa,b,c,e 最大元:e 无 最小元:a 无1．设f(x)=12x ⎧⎪⎨⎪⎩求解：4.(1)f:N →(2)f:N →(3)f:N →(4)f:N →(6)f:R →R,f(x)=x 2-2x-15不是满射，不是单射5.设X={a,b,c,d},Y={1,2,3},f={<a,1>,<b,2>,<c,3>,}判断以下命题的真假: (1)f 是从X 到Y 的二元关系,但不是从X 到Y 的函数;对 (2)f 是从X 到Y 的函数,但不是满射,也不是单射的;错 (3)f 是从X 到Y 的满射,但不是单射;错 (4)f 是从X 到Y 的双射.错第十章部分课后习题参考答案4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。