资源描述：
《离散数学练习题2答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1-1．都是命题：1-2设P：明天天气晴朗Q：我们就去郊游则P®Q：如果明天天气晴朗，我们就去郊游1-3根据真值表求公式P®(P∧(Q®R))的主析取范式。解 表1.15例1.42真值表PQRP®(P∧(Q®R))TTTTTTFFTFTTTFFTFTTTFTFTFFTTFFFT则P®(P∧(Q®R))Û(﹁P∧Q∧R)∨(﹁P∧Q∧﹁R)∨(﹁P∧﹁Q∧R)∨(﹁P∧Q∧﹁R)∨(P∧﹁Q∧R)∨(P∧﹁Q∧﹁R)∨(P∧Q∧R)■由于任意一组命题变元P1,P2,…,Pn的真值指派和它的极小项之间是一一对应的，故可以对极小项进行编码。首先需要规定
2、变元在极小项中的排列次序，假设为P1,P2,…,Pn，用m表示极小项，若Pi出现在极小项中，则编码的第i个位置上的值为1，否则为0。比如变元P,Q,R（规定次序为P,Q,R）的极小项P∧﹁Q∧﹁R的编码为100，将此极小项记为m100。若将编码看作是一个二进制数，又可将例中的极小项记为m4。用此方法，可以简写所求得的给定公式的主析取范式。P®(P∧(Q®R))Ûm0∨m1∨m2∨m3∨m4∨m5∨m7（规定P,Q,R的次序为P,Q,R）公式P®(P∧(Q®R))的主析取范式。解 P®(P∧(Q®R))Û﹁P∨(P∧(﹁Q∨R))Û(﹁P∨P)∧(
3、﹁P∨﹁Q∨R)Û(﹁P∨﹁Q∨R)Û(﹁P∨﹁Q∨R)1-4试证明(﹁P®Q)∧(P®R)∧(﹁Q∨S)ÞS∨R。证明（1）﹁P®QP（2）﹁Q∨SP（3）Q®ST,(2),E16（4）﹁P®ST,(1),(3),I13（5）﹁S®PT,(4),E18（6）P®RP（7）﹁S®RT,(5),(6),I13（8）﹁﹁S∨RT,(7),E16图1.1例1.51证明过程的树表示（9）S∨RT,(8),E11-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。迈克没有向别人借钱，所以如果迈克没有卖掉洗衣机，则他没有电冰箱。解 设P：迈克有电冰
4、箱Q：迈克卖了洗衣机R：迈克向别人借了钱。则上述语句可翻译为命题关系式P®Q∨R,﹁RÞ﹁Q®﹁P（1）P®Q∨RP（2）﹁P∨Q∨RT,(1),E16（3）﹁(﹁P∨Q)®RT,(2),E16（4）﹁﹁P∧﹁Q®RT,(3),E9（5）P∧﹁Q®RT,(4),E1（6）﹁R®﹁(P∧﹁Q)T,(5),E18（7）﹁R®﹁P∨QT,(6),E8（8）﹁RP（9）﹁P∨QT,(7),(8),I11（10）P®QT,(9),E16（11）﹁Q®﹁PT,(10),E181-6如果今天我没课，则我去机房上机或去图书馆查资料；若机房没有空机器，则我没法去上
5、机；今天我没课，机房也没有空机器，所以我去图书馆查资料。解 设P：今天我没课Q：我去机房上机R：我去图书馆查资料S：机房没有空机器则上述语句可翻译为命题关系式P®Q∨R,S®﹁Q,P,SÞR（1）﹁RP（2）P®Q∨RP（3）﹁P∨Q∨RT,(2),E16（4）R∨﹁P∨QT,(3),E3（5）﹁R®﹁P∨QT,(4),E16（6）﹁P∨QT,(1),(5),I11（7）P®QT,(6),E16（8）S®﹁QP（9）﹁﹁Q®﹁ST,(8),E18（10）Q®﹁ST,(9),E1（11）P®﹁ST,(7),(11),I13（12）PP（13）﹁ST
6、,(11),(12),I11（14）SP（15）F(13),(14)1-7北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。甲说：“天津第一，上海第二。”乙说：“天津第二，广州第三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解 设P2：北京第二Q2：上海第二R1：天津第一R2：天津第二S3：广州第三S4：广州第四由已知条件：甲猜对了一半，(﹁R1∧Q2)∨(R1∧﹁Q2)在真值指派f下为T；乙猜对了一半，(﹁R2∧S3)∨(R2∧﹁S3)在真值指派f下为T；丙猜对了一半，(﹁
7、P2∧S4)∨(P2∧﹁S4)在真值指派f下为T。由事实知，每个城市只能得一个名次即R1∧R2,S3∧S4为永假式。再由题意，没有并列名次可得：P2∧Q2,P2∧R2,R2∧Q2在真值指派f下为F。以上8个方程组成的方程组可解得f为P2=T,Q2=F,R1=T,R2=F,S3=T,S4=F因此，实际名次为：天津第一、北京第二、广州第三、上海第四。2-1说明下列各式中量词的辖域与变元约束的情况：（1）("x)A(y)（2）("x)(A(x)®B(x))（3）("x)(A(x)®($y)B(x,y))（4）("x)(y)(A(x,y)∧B(y,z))
8、∧($x)A(x,y)（5）("x)(A(x)∧($x)B(x,z)®($y)C(x,y))∨B(x,y)（6）("x)(A(x)«B(
