离散数学(屈婉玲版)第一章部分习题

离散数学(屈婉玲版)第一章部分习题离散数学(屈婉玲版)第一章部分习题离散数学(屈婉玲版)第一章部分习题资料仅供参考文件编号：2022年4月离散数学(屈婉玲版)第一章部分习题版本号：A修改号：1页次：1.0审核：批准:发布日期：第一章习题&判断下列语句是否为命题,若是命题请指出是简单命题还是复合命题.并将命题符号化,并讨论它们的真值.(1)√2是无理数.是命题,简单命题.p:√2是无理数.真值:1(2)5能被2整除.是命题,简单命题.p:5能被2整除.真值:0现在在开会吗不是命题.x+5>0.不是命题.(5)这朵花真好看呀! 不是命题.(6)2是素数当且仅当三角形有3条边.是命题,复合命题.p:2是素数.q:三角形有3条边.pq真值:1(7)雪是黑色的当且仅当太阳从东方升起.是命题,复合命题.p:雪是黑色的.q:太阳从东方升起.pq真值:0(8)2008年10月1日天气晴好.是命题,简单命题.p:2008年10月1日天气晴好.真值唯一.(9)太阳系以外的星球上有生物.是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一.(10)小李在宿舍里.是命题,简单命题.P:小李在宿舍里.真值唯一.(11)全体起立!不是命题.(12)4是2的倍数或是3的倍数.是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q真值:1(13)4是偶数且是奇数.是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0(14)李明与王华是同学.是命题,简单命题.p:李明与王华是同学.真值唯一.(15)蓝色和黄色可以调配成绿色.是命题,简单命题.p:蓝色和黄色可以调配成绿色.真值:1判断下列各命题的真值.(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.(5)2+2=4当且仅当3+3=6.(6)2+2=4当且仅当3+3≠6.(7)2+2≠4当且仅当3+3=6.(8)2+2≠4当且仅当3+3≠6.答案:设p:2+2=4,q:3+3=6,则p,q都是真命题.(1)p→q,真值为1.(2)p→┐q,真值为0.(3)┐p→q,真值为1.(4)┐p→┐q,真值为1.(5)pq,真值为1.(6)p┐q,真值为0.(7)┐pq,真值为0.(8)┐p┐q,真值为1.1．4将下列命题符号化，并讨论其真值。（1）如果今天是1号，则明天是2号。p:今天是1号。q:明天是2号。符号化为：pq真值为：1（2）如果今天是1号，则明天是3号。p:今天是1号。q:明天是3号。符号化为：pq真值为：0将下列命题符号化。（1）2是偶数又是素数。（2）小王不但聪明而且用功。（3）虽然天气很冷，老王还是来了。（4）他一边吃饭，一边看电视。（5）如果天下雨，他就乘公共汽车上班。（6）只有天下雨，他才乘公共汽车上班。（7）除非天下雨，否则他不乘公共汽车上班。(意思为：如果他乘公共汽车上班，则天下雨或如果不是天下雨，那么他就不乘公共汽车上班)（8）不经一事，不长一智。答案：（1）设p：2是偶数，q：2是素数。符号化为：p∧q（2）设p：小王聪明，q：小王用功。符号化为：p∧q（3）设p：天气很冷，q：老王来了。符号化为：p∧q（4）设p：他吃饭,q：他看电视。符号化为：p∧q（5）设p：天下雨，q：他乘公共汽车。符号化为：p→q（6）设p：天下雨，q：他乘公共汽上班。符号化为：q→p（7）设p：天下雨，q：他乘公共汽车上班。符号化为：q→p或q→p（8）设p：经一事，q：长一智。符号化为：p→q设p,q的真值为0；r,s的真值为1，求下列各命题公式的真值。（1） p∨(q∧r)（2） (p↔r)∧(¬p∨s)（3） (p∧(q∨r))→(p∨q)∧(r∧s)（4） ¬(p∨(q→(r∧¬p))→(r∨¬s)解：（1）p∨(q∧r)pqrq∧rp∨(q∧r)00100(2)(p↔r)∧(¬p∨s)pqrspr¬p¬p∨s(pr)∧(¬p∨s)00110110(3)(p∧(q∨r))→(p∨q)∧(r∧s)pqrsq∨rp∧(q∨r)p∨qr∧s(p∨q)∧(r∧s)(p∧(q∨r))→(p∨q)∧(r∧s)0011100101(4)¬(p∨(q→(r∧¬p))→(r∨¬s)pqrs¬pr∧¬pq→(r∧¬p)(p∨(q→(r∧¬p))(r∨¬s)¬(p∨(q→(r∧¬p))→(r∨¬s)00111111111．7判断下列命题公式的类型。（1）p(pqr)解：pqrpqpqrp(pqr)000001001011010111011111100111101111110111111111由真值表可知，该命题公式为重言式。（2）（p→┑p）→┑pp┑pp→┑p（p→┑p）→┑p01111001由真值知命题公式的类型是：重言式（3）┐(q→p)∧ppqq→p┐（q→p）┐(q→p)∧p00100010101010011100此命题公式是矛盾式。(4)(p→q)→(﹁q→﹁p)解:其真值表为:pq﹁p﹁qp→q﹁q→﹁p(p→q)→(﹁q→﹁p)0011111011011110010011100111由真值表观察,此命题为重言式.(5)(﹁p→q)→(q→﹁p)解:其真值表为:pq﹁p﹁p→qq→﹁p(﹁p→q)→(q→﹁p)001011011111100111110100由真值表观察,此命题为非重言式的可满足式.（7）（p∨p）→((q∧q)∧r)解：pqrp∨pq∧qr(q∧q)∧r（p∨p）→((q∧q)∧r)00010100001100000101010001110000100101001011000011010101111000结论：此命题为矛盾式(8)(pq)→﹁(p∨q).pq(pq)(p∨q)﹁(p∨q)(pq)→﹁(p∨q)001011010101100101111100由此可以知道，上式为非重言式的可满足式.(9)((ｐ→ｑ)∧(ｑ→ｒ))→(ｐ→ｒ)解:pｑｒｐ→ｑｑ→ｒ（ｐ→ｑ）∧（ｑ→ｒ）ｐ→ｒA0001111100111111010100110111111110001001101010111101000111111111该命题为永真式（10）（（p∨q）→r）s解：pqrsp∨q（p∨q）→r（p∨q）→r）s0000010000101100100100011011010010101011000110110011111111111111110110110110011001011001100101011010111111000101结论：此命题为非重言式可满足式用等值演算法证明下列等值式（1）（p∧q）∨(p∧﹁q)p证明：（p∧q）∨(p∧﹁q)（分配律）p∧(q∨﹁q)（排中律）p∧1(同一律)p（3）（pq）((pq)(pq))证明：（pq）((pq)(qp))((pq)(qp))(pq)(qp)(pq)(qp)((pq)q)((pq)p)((pq)(qq))((pp)(qp))((pq)1)(1(qp))(pq)(qp)(pq)(pq)用等值演算法判断下列公式的类型。（1）（（pq）p）.解：（1）（（pq）p）（（pq）p）蕴含等值式（（pq））p德·摩根律pqp双重否定律ppq交换律0q矛盾律0零律即原式为矛盾式.((pq)(qp))(pq)解：((pq)(qp))(pq)(pq)(pq)((pq)(pq))((pq)(pq))(Pq)(pq)(pq)(pq))1即((pq)(qp))(pq)是重言式。(3)(p→q)→(q→p).解：(p→q)→(q→p)((p∨q))∨(q∨p) (p∧q)∨(q∨p) (p∨(p∧q))∧(q∨(q∨p)) ((p∨p)∨q)∧((q∨q)∨p] (p∨q)∧(p∨q) (p∨q)或(p→q)→(q→p)((p∨q))∨(q∨p) (p∧q)∨(q∨p)（(p∧q)∨q）∨p结合律p∨q吸收律结论：该公式为可满足式。(1)求下面命题公式的主析取范式、主合取范式、成真赋值、成假赋值。(p∨(q∧r))→（p∧q∧r）¬(p∨(q∧r))∨(p∧q∧r)(¬p∧(¬q∨¬r))∨(p∧q∧r)(¬p∧¬q)∨(¬p∧¬r)∨(p∧q∧r)((¬p∧¬q)∧(r∨¬r))∨((¬p∧¬r)∧(q∨¬q))∨(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)∨(¬p∧q∧¬r)∨(p∧q∧r)m0∨m1∨m2∨m7∑(0,1,2,7)故其主析取范式为(p∨(q∧r))→（p∧q∧r）∑(0,1,2,7)由最小项定义可知道原命题的成真赋值为(0,0,0)(0,1,0)(0,0,1)(1,1,1)成假赋值为(0,1,1)(1,0,0)(1,0,1)(1,1,0)由主析取范式和主合取范式的关系即可知道主合取范式为(p∨(q∧r))→（p∧q∧r）∏(3,4,5,6)（3）（pq）qr解：（pq）qr（pq）qrpqqr0既（pq）qr是矛盾式。（pq）qr的主合取范式为M0M1M2M3M4M5M6M7，成假赋值为：000，001，010，011，100，101，111．13.通过求主析取范式判断下列各组命题公式是否等值。（1）①p→(q→r);②q→(p→r).解：p→(q→r)﹁p(q→r)﹁p(﹁qr)﹁p﹁qr(﹁p(q﹁q)(r﹁r))((p﹁p)﹁q(r﹁r))((p﹁p)(q﹁q)r)(﹁pqr)(﹁pq﹁r)(﹁p﹁qr)(﹁p﹁q﹁r)(p﹁qr)(p﹁q﹁r)(﹁pqr)∑(0,1,2,3,4,5,7)q→(p→r)﹁q(﹁pr)﹁p﹁qr∑(0,1,2,3,4,5,7)所以两式等值。（2）①pq¬(p∧q)(p∧(q∨¬q))∨(q∧(p∨¬p))(p∧q)∨(¬p∧¬q)∨(¬q∧p)∨(¬p∧¬q)(¬p∧q)∨(¬p∧¬q)∨(p∧¬q)m1∨m0∨m2∑(0,1,2)(p∧¬q)处原为(¬q∧p)，不是极小项②令A=pqB=¬(p∧q)C=(¬p∧q)∨(¬p∧¬q)∨(p∧¬q)D=p↓q则B*=¬(p∨q)p↓q=D且ABC所以DA*C*C*=(¬p∨q)∧(¬p∨¬q)∧(p∨¬q)∏（0，1，2）∑(3)所以①!②某勘探队有3名队员，有一天取得一块矿样，3人判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁；经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个人全错了。根据以上情况判断矿样的种类。解：p：是铁q：是铜r：是锡由题意可得共有6种情况：1)甲全对，乙对一半，丙全错：(﹁p∧﹁q)∧((﹁p∧﹁r)∨(p∧r))∧(r∧﹁p)①2)甲全对，丙对一半，乙全错：(﹁p∧﹁q)∧（（﹁r∧﹁p）∨(r∧p)）∧(p∧﹁r)②3)乙全对，甲对一半，丙全错：（﹁p∧r）∧((﹁p∧q)∨(﹁q∧p))∧(r∧﹁p)③4)乙全对，丙对一半，甲全错：（﹁p∧r）∧((﹁r∧﹁p)∨(r∧p))∧(p∧q)④5)丙全对，甲对一半，乙全错：(﹁r∧p)∧((﹁p∧q)∨(p∧﹁q))∧(p∧﹁r)⑤6)丙全对，乙对一半，甲全错：(﹁r∧p)∧((﹁p∧﹁r)∨(p∧r))∧(p∧q)⑥则①∨②∨③∨④∨⑤∨⑥1①(﹁p∧﹁q∧﹁p∧﹁r∧r∧﹁p)∨(﹁p∧﹁q∧p∧r∧r∧﹁p)0∨00②(﹁p∧﹁q∧﹁r∧﹁p∧p∧﹁r)∨(﹁p∧﹁q∧r∧p∧p∧﹁r)0∨00③(﹁p∧r∧﹁p∧q∧r∧﹁p)∨（﹁p∧r∧﹁q∧p∧r∧﹁p）(﹁p∧q∧r)∨0﹁p∧q∧r④（﹁p∧r∧﹁r∧﹁p∧p∧q）∨（﹁p∧r∧r∧p∧p∧q）0∨00⑤(﹁r∧p∧﹁p∧q∧p∧﹁r)∨(﹁r∧p∧p∧﹁q∧p∧﹁r)0∨(p∧﹁q∧﹁r)p∧﹁q∧﹁r⑥(﹁r∧p∧﹁p∧﹁r∧p∧q)∨(﹁r∧p∧p∧r∧p∧q)0∨00所以①∨②∨③∨④∨⑤∨⑥（﹁p∧q∧r）∨（p∧﹁q∧﹁r）而这块矿石不可能既是铜又是锡，所以只能是判断下列推理是否正确，先将命题符号化，再写出前提和结论，让后进行判断。如果今天是1号，则明天是5号。今天是1号，所以明天是5号。p：今天是1号q：明天是5号解：前提：p→q,p结论：q推理的形式结构为：((p→q)∧p)→q证明：①p→q前提引入②p前提引入③q假言推理此命题是正确命题（2）判断下列推理是否正确，先将命题符号化再写出前提和结论，然后进行判断如果今天是1号，则明天是5号。明天是5号，所以今天是1号。解设p:今天是1号,q:明天是5号,则该推理可以写为((p→q)∧q)→p前提p→q，q结论p判断证明((p→q)∧q)→p¬((p→q)∧q)∨p¬(p→q)∨¬q∨p¬(¬p∨q)∨¬q∨p(p∧¬q)∨¬q∨p¬q∨p此式子为非重言式的可满足式，故不可以判断其正确性所以此推理不正确（3）如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。解：p:今天1号.q:明天是5号.((p→q)∧¬q)→¬p前提:p→q,¬q.结论:¬p.证明:①p→q前提引入②¬q前提引入③¬p①②拒取式推理正确(1)前提：﹁（p∧﹁q）,﹁q∨r,﹁r结论：﹁p.证明：①﹁q∨r前提引入②﹁r前提引入③﹁q①②析取三段论④﹁(p∧﹁q)前提引入⑤﹁p∨q④置换⑥﹁p③⑤析取三段论即推理正确。（2）前提：p→(q→s),q,p∨﹁r结论：r→s.证明：①p∨﹁r前提引入②r附加前提引入③p析取三段论④p→(q→s)前提引入⑤q→s假言推理⑥q前提引入⑦s假言推理由附加前提证明法可知，结论正确。(3):前提:p→q.结论:p→(p∧q).证明:①p→q.前提引入②p附加前提引入③q①②假言推理④p∧q②③合取引入规则（4）前提：qp,qs,st,tr.结论：pqsr.证明：1)tr；前提引入2)t；1)的化简3)st；前提引入4)（st）(ts);3)的置换5)ts4)的化简6)s；2),5)的假言推理7)qs；前提引入8)(qs)(sq)；7)置换9)sq8)的化简10)q；6),9)的假言推理11)qp；前提引入12)p；10),11)的假言推理13）r1)的化简14)pqsr6),10),12),13)的合取所以推理正确。1．18如果他是理科学生，他必学好数学。如果他不是文科学生，他必是理科学生。他没学好数学。所以它是文科学生。判断上面推理是否正确，并证明你的结论。解：p:他是理科学生q:他学好数学r:他是文科学生前提：p→q，┐r→p，┐q结论：r①┐p前提引入②p→q前提引入③┐p①②拒取式④┐r→p前提引入⑤r③④拒取式给定命题公式如下：p(qr)。求命题公式的主析取范式、主合取范式、成真赋值、成假赋值。解：p(qr)((pqq))(rr))((qr)(pp))pqr)pqr)(pqr)(pqr)(pqr)(pqr)m7m6m5vm4m6m2m7m6m5vm4m22、4、5、6、7∴p(qr)0、1、3既010、100、101、110、111是成真赋值，000、001、011是成假赋值给定命题公式如下：（pq）r。求命题公式的主析取范式、主合取范式、成真赋值、成假赋值。解：（pq）r(pq)r((pq)(rr))((pp)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m7m6m7m5m3m1m7m6m5m3m11、3、5、6、7∴（pq）r0、2、4既001、011、101、110、111是成真赋值，000、010、100是成假赋值。例题例给定命题公式如下，用等值演算判断公式类型(1)(p∧q)→(p∨q)解：﹁(p∧q)∨(p∨q)﹁p∨﹁q∨p∨q(﹁p∨p)∨(﹁q∨q)1∨11所以为重言式（2）(p↔q)↔((p→q)∧(q→p))解：(p↔q)↔((p→q)∧(q→p))(p↔q)↔(↔q)