离散数学答案屈婉玲版第二版高等教育出版社课后答案离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1,求下列各命题公式的真值。(1)pV(qAr)二0V(0A1)=0(2)(p?r)A(「qVs)二(0?1)A(1V1)=0A1=0.(3)(—pA一qAr)?(pAqA「r)二(1A1A1)?(0A0A0)=0(4)(一「As)—(pA_q)=(0A1)—(1A0)=0—0=117.判断下面一段论述是否为真：“二是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。”答：p:二是无理数1q:3是无理数0r:'2是无理数1s:6能被2整除1t:6能被4整除0命题符号化为：pA(q—r)A(t—s)的真值为1,所以这一段的论述为真。19.用真值表判断下列公式的类型：(4)(p—q)—(一q—一p)(5)(pAr)'(一pA一q)(6)((p—q)A(q—r))—(p—r)答：(4)pqp—q_q_p—q—一p(p—q)—(一q—一p)0011111011011110010011110011所以公式类型为永真式(5)公式类型为可满足式(方法如上例)(6)公式类型为永真式(方法如上例)第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值?⑴飞Aq-q)(2)(p-(pVq))V(p-r)(3)(pVq)-(pAr)答：(2)(p—(pVq))V(p—r)=(—pV(pVq))V(_pVr)u-pVpVqVr=1所以公式类型为永真式⑶PqrpVqpAr(pVq)—(pAr)000001001001010100011100100100101111110100111111所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(p—q)A(p—r)二(p—(qAr))⑷(pA-q)V(-pAq)=(pVq)A一(pAq)证明(2)(p—q)A(p—r)(一pVq)A(一pVr):二_pV(qAr))二p—(qAr)(4)(pA-q)V(一pAq)u(pV(一pAq))A(_qV(一pAq)-(pV_p)A(pVq)A(一qV一p)A(一qVq)=1A(pVq)A一(pAq)A1二(pVq)A_(pAq)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(_p—q)—(一qVp)(2)_(P—q)AqAr(3)(pV(qAr))-(pVqVr)解：(1)主析取范式(-p-q)—(一qp)二_(pq)(一qp)=(-p-q)(一qp)=(一p_q)(一qp)(一q_p)(pq)(p_q)u(-p_q)(p_q)(pq)-刀(0,2,3)主合取范式：(_p—q)—(一qp)-_(pq)(一qp)=(-p-q)(一qp)=(一P(一qP))(一q(一qp))=1(p—q)二(p—q)二Mi=n(i)(2)主合取范式为：_(p—q)qr=—(一pq)qru(p_q)q产0所以该式为矛盾式?主合取范式为n(0,123,4,5,6,7)矛盾式的主析取范式为0(3)主合取范式为：(p(qr))—(pqr)=一(p(qr))—(pqr)=(一p(一q_r))(pqr)=(一p(pqr))((_q-r))(pqr))二1i二1所以该式为永真式永真式的主合取范式为1主析取范式为刀（0,123,4,5,6,7）第三章部分课后习题参考答案14.在自然推理系统P中构造下面推理的证明:(2)前提：p—.q,—(qr),r(4)前提：q—p,q『s,s『t,tr结论：pq证明：（2）①—(qr)前提引入②—q—r①置换③q，一「②蕴含等值式④r前提引入⑤一q③④拒取式⑥p-q前提引入⑦」p(3)⑤⑥拒取式证明（4）：①tr前提引入②t①化简律③qis前提引入④s—?t前提引入⑤qrt③④等价三段论(q>t)(trq)?⑤置换炉(q>t)⑥化简⑧q②⑥假言推理⑨q—；p前提引入⑩p⑧⑨假言推理(11)pq⑧⑩合取15在自然推理系统P中用附加前提法证1F面各推理:结论：_p(1)前提：pr(qrr),srp,q结论：s—?r①s附加前提引入②SrP前提引入③P①②假言推理④p—；(q—；r)前提引入⑤q—r③④假言推理⑥q前提引入⑦r⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p，—q,-rq,r_s结论：-p证明：①p结论的否定引入②p—「q前提引入q①②假言推理rq前提引入⑤「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)中为真命题。⑵在两个个体域中都解释为xG(x)，在(a)(b)中均为真命题。4.在一阶逻辑中将下列命题符号化：(1)没有不能表示成分数的有理数?(2)在北京卖菜的人不全是外地人.解：(1)F(x):x能表示成分数H(x):x是有理数命题符号化为：-x(—F(x)H(x))(2)F(x):x是北京卖菜的人H(x):x是外地人命题符号化为：—-x(F(x)—?H(x))5.在一阶逻辑将下列命题符号化：(1)火车都比轮船快?(3)不存在比所有火车都快的汽车?解：(1)F(x):x是火车；G(x):x是轮船；H(x,y):x比y快命题符号化为：-x-y((F(x)G(y))rH(x,y))(2)(1)F(x):x是火车；G(x):x是汽车；H(x,y):x比y快命题符号化为:-y(G(y)-x(F(x)>H(x,y)))9.给定解释I如下：(a)个体域D为实数集合R.(b)D中特定元素=0.(c)特定函数(x,y)=xy,x,yD.(d)特定谓词(x,y):x=y,(x,y):x<=""d=""p="">说明下列公式在I下的含义,并指出各公式的真值：
