离散数学-第二章命题逻辑等值演算习题及答案

第二章作业评分要求：1.每小题6分:结果正确1分;方法格式正确3分;计算过程2分.合计48分2.给出每小题得分(注意:写出扣分理由)3.总得分在采分点1处正确设置.一.证明下面等值式(真值表法,解逻辑方程法,等值演算法,三种方法每种方法至少使用一次):说明证1.p⇔(p∧q)∨(p∧¬q)解逻辑方程法设p↔((p∧q)∨(p∧¬q))=0,分两种情况讨论:0)()(1)1(qpqpp或者1)()(0)2(qpqpp(1)(2)两种情况均无解,从而,p↔(p∧q)∨(p∧¬q)无成假赋值,为永真式.等值演算法(p∧q)∨(p∧¬q)⇔p∧(q∨¬q)∧对∨的分配率⇔p∧1排中律⇔p同一律真值表法pqp↔((p∧q)∨(p∧¬q))001011101111即p↔((p∧q)∨(p∧¬q))为永真式,得证2.(p→q)∧(p→r)⇔p→(q∧r)等值演算法(p→q)∧(p→r)⇔(¬p∨q)∧(¬p∨r)蕴含等值式⇔¬p∨(q∧r)析取对合取的分配律⇔p→(q∧r)蕴含等值式3.¬(p↔q)⇔(p∨q)∧¬(p∧q)等值演算法¬(p↔q)⇔¬((p→q)∧(q→p))等价等值式⇔¬((¬p∨q)∧(¬q∨p))蕴含等值式⇔¬((¬p∧¬q)∨(p∧q))合取对析取分配律,矛盾律,同一律⇔(p∨q)∧¬(p∧q)德摩根律4.(p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)等值演算法(p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)析取对合取分配律,排中律,同一律说明:用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象,熟练后可以不写.由于等值演算法证明具有较强的技巧性,平时应注意总结心得.二.求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1.2.3.4.1.(¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔(p∨q)→(¬q∨p)蕴含等值式⇔(¬p∧¬q)∨(¬q∨p)蕴含等值式,德摩根律⇔(¬p∧¬q)∨¬q∨p结合律⇔p∨¬q吸收律,交换律⇔M1因此,该式的主析取范式为m0∨m2∨m32.(¬p→q)∧(q∧r)解逻辑方程法设(¬p→q)∧(q∧r)=1,则¬p→q=1且q∧r=1,解得q=1,r=1,p=0或者q=1,r=1,p=1,从而所求主析取范式为m3∨m7,主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)(pq)(qr)蕴含等值式(pqr)(qr)对分配律,幂等律(pqr)(pqr)(pqr)同一律,矛盾律,对分配律m7m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63.(p↔q)→r解逻辑方程法设(p↔q)→r=0,解得p=q=1,r=0或者p=q=0,r=0,从而所求主合取范式为M0∧M6,主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r((pq)(qp))r等价等值式((pq)(qp))r蕴含等值式(pq)(qp)r德摩根律,蕴含等值式的否定(参见PPT)(pqr)(qpr)对分配律,矛盾律,同一律M0M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74.(p→q)∧(q→r)解等值演算法(p→q)∧(q→r)(pq)(qr)蕴含等值式(pq)(pr)(qr)对分配律,矛盾律,同一律(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m0m3m7主合取范式为M2M4M5M6.解逻辑方程法设(pq)(qr)=1,则pq=1且qr=1.前者解得:p=0,q=0;或者p=0,q=1;或者p=1,q=1.后者解得:q=0,r=0;或者q=0,r=1;或者q=1,r=1.综上可得成真赋值为000,001,011,111,从而主析取范式为m0m1m3m7,主合取范式为M2M4M5M6.真值表法公式(pq)(qr)真值表如下:pqr(pq)(qr)00010011010001111000101011001111从而主析取范式为m0m1m3m7,主合取范式为M2M4M5M6.