离散数学第三章习题详细答案 VIP免费

3.9解：符号化：p：a是奇数.q：a是偶数.r：a能被2整除前提：(p→¬r),(q→r)结论：(q→¬p)证明：方法1（真值法）pqrp→¬rq→r(p→¬r)∧(q→r)q→¬p00011110011111011100110011111010101011111111010001110100由上表可知，没有出现合取式(p→¬r)∧(q→r)为真，结论(q→¬p)为假的情况，因此推论正确。方法2（等值演算法）(p→¬r)∧(q→r)→(q→¬p)⇔(¬p∨¬r)∧(¬q∨r)→(¬q∨¬p)⇔(p∧r)∨(q∧¬r)∨¬q∨¬p⇔((p∧r)∨¬p)∨((q∧¬r)∨¬q)⇔(r∨¬p)∨(¬r∨¬q)⇔¬p∨(r∨¬r)∨¬q⇔1即证得该式为重言式，则原结论正确。方法3（主析取范式法）(p→¬r)∧(q→r)→(q→¬p)⇔(¬p∨¬r)∧(¬q∨r)→(¬q∨¬p)⇔(p∧r)∨(q∧¬r)∨¬q∨¬p⇔m0+m1+m2+m3+m4+m5+m6+m7可知该式为重言式，则结论推理正确。3.10.解：符号化：p：a是负数.q：b是负数.r：a、b之积为负前提：r→(p∧¬q)∨(¬p∧q)结论：¬r→(¬p∧¬q)方法1（真值法）证明：pqr(p∧¬q)∨(¬p∧q)(¬p∧¬q)r→(p∧¬q)∨(¬p∧q)¬r→(¬p∧¬q)00001110010101010101010010101100010101101101110111110001由上表可知，存在r→(p∧¬q)∨(¬p∧q)为真，结论¬r→(¬p∧¬q)为假的情况，因此推理不正确。方法2（主析取范式法）证明：(r→(p∧¬q)∨(¬p∧q))→(¬r→(¬p∧¬q))⇔¬(¬r∨(p∧¬q)∨(¬p∧q))∨(r∨(¬p∧¬q))⇔r∨(¬p∧¬q)⇔m0+m2+m4+m6+m7只含5个极小项，课件原始不是重言式，因此推理不正确3.11.填充下面推理证明中没有写出的推理规则。解：③：①②析取三段论⑤：③④析取三段论⑦：⑤⑥假言推理3.12.填充下面推理证明中没有写出的推理规则。解：②：①化简规则③：①化简规则⑤：②④假言推理⑥：③⑤假言推理⑧：③⑦假言推理⑨：⑥⑧假言推理3.13.证明： 前提¬(p→q)∧q⇔¬(¬p∨q)∧q⇔p∧¬q∧q⇔0为矛盾式∴以(¬(p→q)∧q)∧(p∨q)∧(r→s)→B.(B为任何结论)的推理的前件在任何赋值下均为假∴无论结论如何，推理总正确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→r①②假言推理④q前提引入⑤r③④假言推理⑥r∨s⑤附加律(2)证明:①¬(q∧r)前提引入②¬q∨¬r①置换③r前提引入④¬q②③析取三段论⑤p→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→s②化简④t∧r前提引入⑤t④化简⑥s③⑤假言推理⑦q↔s前提引入⑧(s→q)∧(q→s)⑦置换⑨s→q⑧化简⑩q⑥⑨假言推理11q→p前提引入12p⑩11假言推理13p∧q⑩○12合取(5)证明:①p→r前提引入②q→s前提引入③p∧q前提引入④p③化简⑤q③化简⑥r①④假言推理⑦s②⑤假言推理⑧r∧s⑥⑦合取(6)证明:①t附加前提引入②¬p∨r前提引入③p∧q前提引入④p③化简⑤r②④析取三段论⑥r∨s⑤附加3.15.在自然推理系统P中用附加前提法证明下面各推理:(1)前提:p→(q→r),s→p,q结论:s→r(2)前提:(p∨q)→(r∧s),(s∨t)→u结论:p→u(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⑥⑦假言推理3.16.在自然推理系统P中用归谬法证明下面推理:(1)前提:p→¬q,¬r∨q,r∧¬s结论:¬p(2)前提:p∨q,p→r,q→s结论:r∨s(1)证明:①P结论否定引入②p→¬q前提引入③¬q①②假言推理④¬r∨q前提引入⑤¬r③④析取三段论⑥r∧¬s前提引入⑦r⑥化简⑧¬r∧r⑤⑦合取⑧为矛盾式,由归谬法可知,推理正确.(2)证明:①¬(r∨s)结论否定引入②p∨q前提引入③p→r前提引入④q→s前提引入⑤r∨s②③④构造性二难⑥¬(r∨s)∧(r∨s)①⑤合取3.17.在自然推理系统P...