离散数学作业布置第1次作业（P15）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=11.17判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则也是无理数。另外只有6能被2整除，6才能被4整除。”解：p:π是无理数1q:3是无理数0r:是无理数1s:6能被2整除1t:6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。1.19用真值表判断下列公式的类型：（4）(p→q)→(﹁q→﹁p)（5）(p∧r)↔(﹁p∧﹁q)（6）((p→q)∧(q→r))→(p→r)解：（4）pqp→qqpq→p(p→q)→(q→p)0011111011011110010011110011所以公式类型为永真式，最后一列全为1（5）公式类型为可满足式（方法如上例），最后一列至少有一个1（6）公式类型为永真式（方法如上例，最后一列全为1）。第2次作业（P38）2.3用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1)﹁(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)解：(1)﹁(p∧q→q)Û﹁(﹁(p∧q)∨q)Û(p∧q)∧﹁qÛp∧(q∧﹁q)Ûp∧0Û0所以公式类型为矛盾式(2)（p→(p∨q)）∨(p→r)Û(﹁p∨(p∨q))∨(﹁p∨r)Û﹁p∨p∨q∨rÛ1所以公式类型为永真式(3)(pq)→∨(pr)∧Û￢(pq)∨∨(pr)∧Û(￢p∧￢q)(pr)∨∧易见,是可满足式,但不是重言式.成真赋值为:000,001,101,111Pqr￢p∧￢qp∧r(￢p∧￢q)(pr)∨∧000101001101010000011000100000101011110000111011所以公式类型为可满足式2.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)第3次作业（P38）2.5求下列公式的主析取范式,并求成真赋值:(1)(￢p→q)→(￢qp)∨(2)(￢p→q)qr∧∧(3)(p∨(q∧r))∧→(pqr)∨∨(4)￢(p→q)qr∧∧解：(1)(￢p→q)→(￢qp)∨Û￢(pq)∨∨(￢qp)∨Û￢p∧￢q∨￢q∨pÛ￢q∨p(吸收律)Û(￢pp)∨∧￢qp(∨∧￢qq)∨Û￢p∧￢qp∨∧￢qp∨∧￢qpq∨∧Ûm0m∨2m∨2m∨3Ûm0m∨2m∨3成真赋值为00,10,11.(2)(￢p→q)qr∧∧Û(pq)qr∨∧∧Û(pqr)qr∧∧∨∧Û(pqr)(∧∧∨￢pp)qr∨∧∧Ûpqr∧∧∨￢pqrpqr∧∧∨∧∧Ûm3∨m7成真赋值为011，111.(3)(p(qr))∨∧→(pqr)∨∨Û￢(p(qr))(pqr)∨∧∨∨∨Û￢p∧￢(qr)(pqr)∧∨∨∨Û￢p(∧￢q∨￢r)(pqr)∨∨∨Û￢p∧￢q∨￢p∧￢rpqr∨∨∨Û￢p∧￢q(r∧∨￢r)∨￢p(q∧∨￢q)∧￢rp(q∨∧∨￢q)(r∧∨￢r)∨(p∨￢p)q(r∧∧∨￢r)(∨p∨￢p)(q∧∨￢q)r∧Ûm0m∨1m∨2m∨3m∨4m∨5m∨6m∨7,为重言式.(4)￢(p→q)qr∧∧Û￢(￢pq)qr∨∧∧Û(p∧￢q)qr∧∧Ûp(∧￢qq)r∧∧Û0主析取范式为0,无成真赋值,为矛盾式.第4次作业（P38）2.6求下列公式的主合取范式,并求成假赋值:(1)￢(q→￢p)∧￢p(2)(pq)(∧∨￢pr)∨(3)(p→(pq))r∨∨解：(1)￢(q→￢p)∧￢pÛ￢(￢q∨￢p)∧￢pÛqp∧∧￢pÛq0∧Û0ÛM0M∧1M∧2M∧3这是矛盾式.成假赋值为00,01,10,11.(2)(pq)(∧∨￢pr)∨Û(pq)∧∨￢pr∨Û(p∨￢p)∧(￢pq)r∨∨Û(￢pq)r∨∨Û￢pqr∨∨ÛM4,成假赋值为100.(3)(p→(pq))r∨∨Û(￢p(pq))r∨∨∨Û(￢pp)qr∨∨∨Û1主合取范式为1,为重言式.第5次作业（P41）2.32用消解原理证明下述公式是矛盾式:(1)(￢pq)(∨∧￢pr)∨∧(￢q∨￢r)(∧p∨￢r)r∧(2)￢((pq)∨∧￢p→q)解：(1)(￢pq)(∨∧￢pr)∨∧(￢q∨￢r)(∧p∨￢r)r∧第一次循环S0=Φ,S1=｛￢pq∨,￢pr∨,￢q∨￢r,p∨￢r,r｝,S2=Φ由￢pr∨,p∨￢r消解得到λ输出“no”，计算结束(2)￢((pq)∨∧￢p→q)Û￢(￢((pq)∨∧￢p)q)∨Û((pq)∨∧￢p)∧￢qÛ(pq)∨∧￢p∧￢q第一次循环S0=Φ,S1=｛pq∨,￢p,￢q｝,S2=Φ由pq∨,￢p消...
