离散数学第1章习题解答

习题1.1以下句子中，哪些是命题？哪些不是命题？假如是命题，指出它的真值。⑴中国有四大发明。⑵计算机有空吗?⑶不存在最大素数。21+3＜5。⑸老王是山东人或河北人。2与3都是偶数。⑺小李在宿舍里。⑻这朵玫瑰花多漂亮呀!⑼请勿随处吐痰!⑽圆的面积等于半径的平方乘以p。⑾只有6是偶数，3才能是2的倍数。⑿雪是黑色的当且仅当太阳从东方升起。⒀假如天下大雨，他就乘班车上班。解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，此中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值当前没法确立；⑵⑻⑼不是命题。将以下复合命题分红若干原子命题。⑴李辛与李末是兄弟。⑵由于天气冷，因此我穿了羽绒服。⑶天正在下雨或湿度很高。⑷刘英与李进上山。⑸王强与刘威都学过法语。⑹假如你不看电影，那么我也不看电影。⑺我既不看电视也不出门，我在睡觉。⑻除非天下大雨，不然他不乘班车上班。解：⑴本命题为原子命题；p：天气冷；q：我穿羽绒服；⑶p：天在下雨；q：湿度很高；⑷p：刘英上山；q：李进上山；p：王强学过法语；q：刘威学过法语；⑹p：你看电影；q：我看电影；⑺p：我看电视；q：我出门；r：我睡觉；⑻p：天下大雨；q：他乘班车上班。将以下命题符号化。⑴他一面吃饭，一面听音乐。⑵3是素数或2是素数。可编写范本⑶若地球上没有树木，则人类不可以生计。⑷8是偶数的充分必需条件是8能被3整除。⑸停机的原由在于语法错误或程序错误。⑹四边形ABCD是平行四边形当且仅当它的对边平行。⑺假如a和b是偶数，则a+b是偶数。解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q⑵p：3是素数；q：2是素数；原命题符号化为：p∨q⑶p：地球上有树木；q：人类能生计；原命题符号化为：p→q⑷p：8是偶数；q：8能被3整除；原命题符号化为：p?q⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→pp：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p?q。⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r将以下命题符号化，并指出各复合命题的真值。⑴假如3+3=6，则雪是白的。⑵假如3+3≠6，则雪是白的。⑶假如3+3=6，则雪不是白的。⑷假如3+3≠6，则雪不是白的。3是无理数当且仅当加拿大位于亚洲。⑹2+3=5的充要条件是3是无理数。(假定是10进制)⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。⑻当王小红心情快乐时，她就唱歌，反之，当她唱歌时，一安心情快乐。解：设p：3＋3＝6。q：雪是白的。⑴原命题符号化为：p→q；该命题是真命题。⑵原命题符号化为：p→q；该命题是真命题。⑶原命题符号化为：p→q；该命题是假命题。⑷原命题符号化为：p→q；该命题是真命题。⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：p?q；该命题是假命题。p：2+3＝5；q：3是无理数；原命题符号化为：p?q；该命题是真命题。⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：p?q；该命题是真命题。⑻p：王小红心情快乐；q：王小红唱歌；原命题符号化为：p?q；该命题是真命题。可编写范本习题1.21.判断以下公式哪些是合式公式，哪些不是合式公式。(p∧q→r)(p∧(q→r)((?p→q)?(r∨s))(p∧q→rs)((p→(q→r))→((q→p)?q∨r))。解：⑴⑶⑸是合式公式；⑵⑷不是合式公式。2.设p：天下雪。q：我将进城。：我有时间。将以下命题符号化。天没有下雪，我也没有进城。⑵假如我有时间，我将进城。⑶假如天不下雪而我又有时间的话，我将进城。解：⑴p∧qr→qp∧r→q3.设p、q、r所 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示的命题与上题同样，试把以下公式译成自然语言。r∧q?(r∨q)q?(r∧?p)(q→r)∧(r→q)解：⑴我有时间而且我将进城。⑵我没有时间而且我也没有进城。⑶我进城，当且仅当我有时间而且天不下雪。⑷假如我有时间，那么我将进城，反之亦然。试把原子命题表示为p、q、r等，将以下命题符号化。⑴或许你没有给我写信，或许它在途中丢掉了。⑵假如张三和李四都不去，他就去。⑶我们不可以既划船又跑步。⑷假如你来了，那末他唱不唱歌将看你能否伴奏而定。解：⑴p：你给我写信；q：信在途中丢掉；原命题符号化为：(p∧q)∨(p∧q)。⑵p：张三去；q：李四去；r：他去；原命题符号化为：p∧q→r。⑶p：我们划船；q：我们跑步；原命题符号化为：（p∧q）。⑷p：你来了；：他唱歌；：你伴奏；原命题符号化为：p→（?）。qrqr用符号形式写出以下命题。可编写范本⑴若是上午不下雨，我去看电影，不然就在家里念书或看报。⑵我今日进城，除非下雨。⑶仅当你走，我将留下。解：⑴p：上午下雨；q：我去看电影；r：我在家念书；s：我在家看报；原命题符号化为：（p→q）∧（p→r∨s）。p：我今日进城；q：天下雨；原命题符号化为：q→p。⑶p：你走；q：我留下；原命题符号化为：q→p。可编写范本习题1.31.设A、B、C是随意命题公式，证明：AA⑵若AB，则BA⑶若AB，BC，则AC证明：⑴由双条件的定义可知A?A是一个永真式，由等价式的定义可知AA建立。⑵由于AB，由等价的定义可知A?B是一个永真式，再由双条件的定义可知B?A也是一个永真式，因此，BA建立。⑶对A、、C的任一赋值，由于AB，则A?B是永真式，即A与B拥有同样的B真值，又由于BC，则B?C是永真式，即B与C也拥有同样的真值，因此A与C也具有同样的真值；即AC建立。2.设A、B、C是随意命题公式，⑴若A∨C?B∨C,A?B必定建立吗？⑵若A∧C?B∧C,A?B必定建立吗？⑶若?A??B，A?B必定建立吗？解：⑴不必定有AB。若A为真，B为假，C为真，则A∨CB∨C建立，但AB不建立。⑵不必定有AB。若A为真，B为假，C为假，则A∧CB∧C建立，但AB不可立。⑶必定有AB。3.结构以下命题公式的真值表，并求成真赋值和成假赋值。q∧(p→q)→pp→(q∨r)(p∨q)?(q∨p)(p∧?q)∨(r∧q)→r((?p→(p∧?q))→r)∨(q∧?r)解：⑴q∧(p→q)→p的真值表如表1.24所示。表1.24pqp→qq∧(p→q)q∧(p→q)→p00101011101000111111使得公式q∧(p→q)→p成真的赋值是：00，10，11，使得公式q∧(p→q)→p成假的赋值是：01。可编写范本p→(q∨r)的真值表如表1.25所示。表1.25pqrq∨rp→(q∨r)0000100111010110111110000101111101111111使得公式p→(q∨r)成真的赋值是：000，001，010，011，101，110，111，使得公式p(q∨r)成假的赋值是：100。(p∨q)?(q∨p)的真值表如表1.26所示。表1.26pqp∨qq∨p(p∨q)?(q∨p)00001011111011111111全部的赋值均使得公式(p∨q)?(q∨p)成真，即(p∨q)?(q∨p)是一个永真式。⑷(p∧q)∨(r∧q)→r的真值表如表1.27所示。表1.27pqrqp∧qr∧q(p∧q)∨(r∧q)(p∧q)∨(r∧q)→r0001000100110001010000010110011110011010101110111100000111100111使得公式(∧)∨(∧)→r成真的赋值是：000，001，010，011，101，110，111，pqrq可编写范本使得公式(p∧q)∨(r∧q)→r成假的赋值是：100。⑸((p→(p∧q))→r)∨(q∧r)的真值表如表1.28所示。表1.28pqrp∧qp→(p∧q)(p→(p∧q))→rq∧r((p→(p∧q))→r)∨(q∧r)0000010100100101010001110110010110011000101111011100101111101101使得公式((p→(p∧q))→r)∨(q∧r)成真的赋值是：000，001，010，011，101，110，111，使得公式((p→(p∧q))→r)∨(q∧r)成假的赋值是：100。4.用真值表证明以下等价式：(p→q)p∧q证明：证明(p→q)p∧q的真值表如表1.29所示。表1.29pqp→q(p→q)qp∧q001010011000100111111000由上表可见：(p→q)和p∧q的真值表完整同样，因此(p→q)p∧q。⑵p→qq→p证明：证明p→qq→p的真值表如表1.30所示。表1.30pqp→qpqq→p001111011101100010111001由上表可见：p→q和q→p的真值表完整同样，因此p→qq→p。可编写范本(p?q)p?q证明：证明(p?q)和p?q的真值表如表1.31所示。表1.31pqp?q(p?q)qp?q001010010101100111111000由上表可见：(p?q)和p?q的真值表完整同样，因此(p?q)p?q。p→(q→r)(p∧q)→r证明：证明p→(q→r)和(p∧q)→r的真值表如表1.32所示。表1.32pqrq→rp→(q→r)p∧q(p∧q)→r00011010011101010010101111011001101101110111000101111111由上表可见：p→(q→r)和(p∧q)→r的真值表完整同样，因此p→(q→r)(p∧q)→r。⑸p→(q→p)p→(p→q)证明：证明p→(q→p)和p→(p→q)的真值表如表1.33所示。表1.33pqq→pp→(q→p)pqp→qp→(p→q)00111111010110111011011111110001由上表可见：p→(q→p)和p→(p→q)的真值表完整同样，且都是永真式，因此p→(q→p)p→(p→q)。⑹(p?q)(p∨q)∧(p∧q)可编写范本证明：证明(?)和(∨)∧(∧)的真值表如表1.34所示。pqpqpq表1.34pqp?q(p?q)p∨qp∧q(p∧q)(p∨q)∧(p∧q)00100010010110111001101111101100由上表可见：(p?q)和(p∨q)∧(p∧q)的真值表完整同样，因此(p?q)(p∨q)∧(p∧q)(p?q)(p∧q)∨(p∧q)证明：证明(p?q)和(p∧q)∨(p∧q)的真值表如表1.35所示。表1.35pqp?q(p?q)p∧qp∧q(p∧q)∨(p∧q)0010000010101110011011110000由上表可见：(p?q)和(p∧q)∨(p∧q)的真值表完整同样，因此(p?q)(p∧)∨(p∧)。qqp→(q∨r)(p∧q)→r证明：证明p→(q∨r)和(p∧q)→r的真值表如表1.36所示。表1.36pqrq∨rp→(q∨r)qp∧q(p∧q)→r0000110100111101010110010111100110000110101111111101100111111001由上表可见：p→(q∨r)和(p∧q)→r的真值表完整同样，因此p→(q∨r)(p∧q)→r。可编写范本用等价演算证明习题4中的等价式。(p→q)(p∨q)p∧qq→pq∨pq∨pp∨qp→q(p?q)((p→q)∧(q→p))((p∨q)∧(q∨p))(p∧q)∨(q∧p)((p∧q)∨q)∧((p∧q)∨p)(p∨q)∧(q∨p)(p∨q)∧(q∨p)(p→q)∧(q→p)p?qp→(q→r)p∨(q∨r)(p∨q)∨r(p∧q)∨r(p∧q)→rp→(q→p)p∨(q∨p)Tp→(p→q)p∨(p∨q)T因此p→(q→p)p→(p→q)(p?q)((p∧q)∨(p∧q))(p∨q)∧(p∨q)(p∨q)∧(p∧q)因此(p?q)(p∨q)∧(p∧q)(p?q)((p→q)∧(q→p))((p∨q)∧(q∨p))(p∧q)∨(p∧q)(条件等价式)(德·摩根律)(条件等价式)(两重否认律)(互换律)(条件等价式)(双条件等价式)(条件等价式)(德·摩根律)(分派律)(分派律)(互换律)(条件等价式)(双条件等价式)(条件等价式)(联合律)(德·摩根律)(条件等价式)(条件等价式)(条件等价式)(例1.17)(德·摩根律)(德·摩根律)(双条件等价式)(条件等价式)(德·摩根律)可编写范本p→(q∨r)p∨(q∨r)(条件等价式)(p∨q)∨r(联合律)(p∧q)∨r(德·摩根律)(p∧q)→r(条件等价式)6.试用真值表证明以下命题定律。⑴联合律：(p∨q)∨rp∨(q∨r)，(p∧q)∧rp∧(q∧r)证明：证明联合律的真值表如表1.37和表1.38所示。表1.37pqrp∨q(p∨q)∨rq∨rp∨(q∨r)00000000010111010111101111111001101101111111011111111111表1.38pqrp∧q(p∧q)∧rq∧rp∧(q∧r)00000000010000010000001100101000000101000011010001111111由真值表可知联合律建立。⑵分派律：p∧(q∨r)(p∧q)∨(p∧r)，p∨(q∧r)(p∨q)∧(p∨r)证明：证明合取对析取的分派律的真值表如表1.39所示，析取对合取的的分派律的真值表如表1.40所示。可编写范本表1.39pqrq∨rp∧(q∨r)p∧qp∧r(p∧q)∨(p∧r)0000000000110000010100000111000010000000101110111101110111111111表1.40pqrq∧rp∨(q∧r)p∨qp∨r(p∨q)∧(p∨r)0000000000100010010001000111111110001111101011111100111111111111由真值表可知分派律建立。⑶假言易位式：p→qq→p证明：证明假言易位式的真值表如表1.41所示。表1.41pqp→qqpq→p001111011011100100111001由真值表可知假言易位律建立。⑷双条件否认等价式：p?qp?q证明：证明双条件否认的真值表如表1.42所示。可编写范本表1.42pqp?qpqp?q001111010100100010111001由真值表可知双条件否认等价式建立。可编写范本习题1.41.用真值表或等价演算判断以下命题公式的种类。(p∨q)→q(∨q)∨qp(p∧q)∨q（可知足式）(p→q)∧q(p∨q)∧q(p∧q)∧qF（永假式）(p→q)∧p→q(p∨q)∧p→q(p∧p)∨(q∧p)→q(q∧p)→q(q∧p)∨q(q∨p)∨qT(永真式)(p→q)∧q(p∨q)∧qq（可知足式）(p→q)→(q→p)(p→q)→(p→q)T(永真式)((p→q)∧(q→r))→(p→r)((p∨q)∧(q∨r))∨(p∨r)(p∧q)∨(q∧r)∨(p∨r)(p∧q)∨((p∨q∨r)∧(p∨r∨r))(p∧q)∨(p∨q∨r)(p∨q∨r∨p)∧(p∨q∨r∨q)T(永真式)p→(p→q)p∨(p∨q)T(永真式)p→(p∨q∨r)p∨(p∨q∨r)T(永真式)2.用真值表证明以下命题公式是重言式。（条件等价式）（德·摩根律）（汲取律）（条件等价式）（德·摩根律）（联合律、矛盾律）（条件等价式）（分派律）（同一律、矛盾律）（条件等价式）（德·摩根律）（零律、排中律）（条件等价式）（汲取律）（假言易位式）（条件等价式）（德·摩根律）（分派律）（同一律、排中律、零律）（分派律）（条件等价式）（条件等价式）可编写范本(p∧(p→q))→q(p∧(p→q))→q的真值表如表1.43所示。由表1.43能够看出(p∧(p→q))→q是重言式。表1.43pqp→qp∧(p→q)(p∧(p→q))→q00101011011000111111⑵(q∧(p→q))→p(q∧(p→q))→p的真值表如表1.44所示。由表1.44能够看出(q∧(p→q))→p是重言式。表1.44pqp→qqq∧(p→q)p(q∧(p→q))→p0011111011001110010011110001(p∧(p∨q))→q(∧(∨))→q的真值表如表1.45所示。由表1.45能够看出(∧(∨))→q是重言ppqppq式。表1.45pqp∨qpp∧(p∨q)(p∧(p∨q))→q000101011111101001111001((p→q)∧(q→r))→(p→r)((p→q)∧(q→r))→(p→r)的真值表如表1.46所示。由表1.46能够看出((p→q)∧(q→r))→(p→r)是重言式。可编写范本表1.46pqrp→qq→r(p→q)∧(q→r)p→r((p→q)∧(q→r))→(p→r)0001111100111111010100110111111110001001101010111101000111111111((p∨q)∧(p→r)∧(q→r))→r((p∨q)∧(p→r)∧(q→r))→r的真值表如表1.47所示。由表1.47能够看出((p∨q)∧(p→r)∧(q→r))→r是重言式。表1.47pqrp∨qp→rq→r(p∨q)∧(p→r)∧(q→r)((p∨q)∧(p→r)∧(q→r))→r0000110100101101010110010111111110010101101111111101000111111111可编写范本((p→q)∧(r→s))→((p∧r)→(q∧s))((p→q)∧(r→s))→((p∧r)→(q∧s))的真值表如表1.48所示。由表1.48能够看出((p→q)∧(r→s))→((p∧r)→(q∧s))是重言式。表1.48pqrsp→qr→s(p→q)∧(r→s)p∧rq∧s(p∧r)→(q∧s)原公式00001110011000111100110010100001100111110011010011100110101111011101101000011011111101111000010001110010100011101000010011011010100111001110011110111101111110100100111111111111((p?q)∧(q?r))→(p?r)((p?q)∧(q?r))→(p?r)的真值表如表1.49所示。由表1.49能够看出((p?q)∧(q?r))→(p?r)是重言式。表1.49pqrp?qq?r(p?q)∧(q?r)p?r((p?q)∧(q?r))→(p?r)0001111100110001010000110110100110001001101000111101000111111111可编写范本用等价演算证明题2中的命题公式是重言式。⑴(p∧(p→q))→q(p∧(p∨q))∨q(p∨(p∧q))∨q((p∨p)∧(p∨q))∨q(∨q)∨qpT⑵(q∧(p→q))→p(q∧(p∨q))→p(q∧(p∨q))∨p(q∨(p∧q))∨p(p∨q)∨(p∧q)(p∧q)∨(p∧q)T(p∧(p∨q))→q(p∧q)→q(p∧q)∨qp∨q∨qT((p→q)∧(q→r))→(p→r)((p∨q)∧(q∨r))∨(p∨r)(p∧q)∨(q∧r)∨(p∨r)(p∧q)∨((p∨q∨r)∧(p∨r∨r))(p∧q)∨(p∨q∨r)(p∨q∨r∨p)∧(p∨q∨r∨q)T((p∨q)∧(p→r)∧(q→r))→r((p∨q)∧(p∨r)∧(q∨r))→r((p∨q)∧((p∨q)∨r))→r((p∨q)∧r)→r((p∨q)∧r)∨r(p∨q)∨r∨rT((p→q)∧(r→s))→((p∧r)→(q∧s))((p∨q)∧(r∨s))∨((p∧r)∨(q∧s))((p∧q)∨(r∧s))∨((p∨r)∨(q∧s))((p∧q)∨(r∧s))∨((p∨r∨q)∧(p∨r∨s))((∧)∨(∧)∨(p∨∨))∧((∧)∨(∧)∨(∨∨))pqrsrqpqrsprs((r∧s)∨((p∨r∨q∨p)∧(p∨r∨q∨q)))∧((r∧s)∨可编写范本((p∨r∨∨)∧(p∨r∨∨)))spsq((r∧s)∨T)∧((r∧s)∨(p∨q∨r∨s))(r∧s)∨(p∨q∨r∨s)(p∨q∨r∨s∨r)∧(p∨q∨r∨s∨s)T((p?q)∧(q?r))→(p?r)((p∨q)∧(q∨p)∧(q∨r)∧(r∨q))→(p?r)((p∨q)∧(q∨p)∧(q∨r)∧(r∨q))∨(p∧r)∨(p∧r)(p∧q)∨(p∧r)∨(r∧q)∨(q∧r)∨(q∧p)∨(p∧r)((p∧(q∨r))∨(q∨r))∨(r∧q)∨(q∧p)∨(p∧r)(((q∨)∨(∨))∧(∨(q∨)))∨(∧)∨(∧)∨(p∧)rqrprrqqpr(T∧(p∨(q∨r)))∨(r∧q)∨(q∧p)∨(p∧r)p∨(q∧r)∨(r∧q)∨(q∧p)∨(p∧r)p∨(q∧r)∨((q∧p)∨(p∧r))∨(r∧q)p∨(q∧r)∨((p∧(q∨r))∨(q∨r))p∨(∧)∨p∨(q∧r)qrT4.证明以下等价式：((p→r)∧(q→r))(p∨r)∧(q∨r)(∧q)∨rp(p∨q)∨r(p∨q)→r(p→q)∧(p→q)(p∨q)∧(p∨q)p∨(q∧q)p∨Fpp∧(p→q)p∧(p∨q)(p∧p)∨(p∧q)F∨(p∧q)p∧q可编写范本习题1.51.求以下命题公式的析取范式。(p∧q)→r(∧q)∨rpp∨q∨r(p→q)→r(p∨q)∨r(p∨q)∨rp∨q∨rp∧(p→q)p∧(p∨q)(p∧p)∨(p∧q)p∧q(p→q)∧(q∨r)(p∨q)∧(q∨r)q∨(p∧r)⑸(p∨q)∧(r→t)(p∧q)∧(r∨t)(∧∧r)∨(∧∧)pqpqt求以下命题公式的合取范式。⑴(p→q)(p∨q)p∧qq∨(p∧q∧r)(q∨p)∧(q∨q)∧(q∨r)(q∨p)∧(q∨r)(p∧q)∨(p∧q)((p∧q)∨p)∧((p∧q)∨q))(p∨p)∧(q∨p)∧(p∨q)∧(q∨q)(p∨q)∧(p∨q)(p?q)((p∧q)∨(p∧q))(p∨q)∧(p∨q)(p→q)→r(p∨q)∨r(p∨q)∨rp∨q∨r可编写范本3.求以下命题公式的主析取范式，并求命题公式的成真赋值。(p∧q)∨(p∧r)作(p∧q)∨(p∧r)的真值表，如表1.50所示。表1.50pqrp∧qp∧r(p∧q)∨(p∧r)000000001000010000011000100000101011110101111111由真值表可知，原式(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)(主析取范式)∑5,6,7使得命题公式(p∧q)∨(p∧r)成真的赋值是：101，110，111。⑵(p∨q)→(p∧r)(p∨q)∨(p∧r)(p∨q)∨(p∧r)(p∨q∨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)∨(p∧q∧r)(主析取范式)1,2,3,4,5,6,7使得命题公式(p∨q)→(p∧r)成真的赋值是：001，010、011，100，101，110，111。(p∨q)→(p?q)作(p∨q)→(p?q)的真值表，如表1.51所示。表1.51pqpqp∨qp?q(p∨q)→(p?q)0011100011011110011111100001由真值表可知:原式(p∧q)∨(p∧q)∨(p∧q)(主析取范式)∑1,2,3使得命题公式(p∨q)→(p?q)成真的赋值是：01，10，11。可编写范本⑷(p→q)→(p∨q)(p∨q)∨(p∨q)(p∨q)∨(p∨q)(p∧q)∨(p∨q)(p∨q∨p)∧(p∨q∨q)p∨q(p∧q)∨(p∧q)∨(p∧q)(主析取范式)0,2,3使得命题公式(p→q)→(p∨q)成真的赋值是：00,10,11。⑸(p→(q∧r))∧(p→(q∧r))(∨(∧))∧(p∨(pqr(p∨q)∧(p∨r)∧(p∨(p∨q∨r)∧(p∨q∨(p∨q∨r)∧(p∨q∨(p∨q∨r)∧(p∨q∨)q∧r))q)∧(p∨r)r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧r)∧(p∨q∨r)r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨(p∧q∧r)∨(p∧q∧r)(主析取范式)使得命题公式(p→(q∧r))∧(p→(q∧r))成真的赋值是：000,111。求以下命题公式的主合取范式，并求命题公式的成假赋值。⑴(p→q)∧r(∨)∧rpq(p∨q∨r)∧(p∨q∨r)∧(p∨r)∧(p∨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)0,2,4,5,6使得命题公式(p→q)∧r成假的赋值是：000,010,100,101,110。(p→q)?(p→q)作(p→q)?(p→q)的真值表，如表1.52所示。表1.52pqp→q(p→q)qp→q(p→q)?(p→q)0010110011001010011111110001由真值表可知:原式(p∨q)∧(p∨q)∏0,1使得命题公式(p→q)?(p→q)成假的赋值是：00,01。可编写范本⑶(p∨q)→(p∧r)(p∨q)∨(p∧r)(p∨q)∨(p∧r)(p∨q∨p)∧(p∨q∨r)p∨q∨r0使得命题公式(p∨q)→(p∧r)成假的赋值是：000。⑷(p→q)∧p(p∨q)∧pp∧q∧pF0,1,2,3使得命题公式(p→q)∧p成假的赋值是：00,01,10,11。(p→(q∨r))∨rp∨q∨r∨rp∨q∨r4使得命题公式(p→(q∨r))∨r成假的赋值是：100。求以下命题公式的主析取范式，再用主析取范式求出主合取范式。⑴(p→q)∧(q→r)(∨)∧(∨)pqqr((p∨q)∧q)∨((p∨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)(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)(主析取范式)0,1,3,72,4,5,6(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∧r)∨(p∧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)(主析取范式)∑1,3,5,6,7∏0,2,4(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)(主合取范式)求以下命题公式的主合取范式，再用主合取范式求出主析取范式。⑴(p?q)∧r可编写范本(→)∧(→)∧rpqqp(p∨q)∧(q∨p)∧r(p∨q∨r)∧(p∨q∨r)∧(q∨p∨r)∧(q∨p∨r)∧(p∨r)∧(p∨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∨∨r)∧(p∨q∨)∧(p∨∨)∧pqrqrqr(p∨q∨r)∧(p∨q∨r)(主合取范式)∏0,2,3,4,5,6∑1,7(p∧q∧r)∨(p∧q∧r)(主析取范式)(p∧q)→q(p∧q)∨qp∨q∨qT(无主合取范式)0,1,2,3(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)7.用主析取范式判断以下命题公式能否等价。p→(q→r)和q→(p→r)p→(→)∨(∨)∨∨qrpqrpqr(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)(主析取范式)0,1,2,3,4,5,7q→(p→r)q∨(p∨r)p∨q∨r(p∧q∧)∨(p∧∧)∨(p∧∧)∨(p∧∧)∨rqrqrqr(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)(主析取范式)0,1,2,3,4,5,7由于p→(q→r)与q→(p→r)的主析取范式同样，因此p→(q→r)q→(p→r)。(p→q)∧(p→r)和p→(q∧p)(p→q)∧(p→r)(p∨q)∧((p∧q)∨(p∧q)∨((p∧q∧r)∨(p∧q∧p∨r)p∨(q∧r)p∧q∧r)∨(p∧q∧r)r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧qr)(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)(主析取范式)0,1,2,3,7p→(q∧p)p∨(q∧p)(p∨q)∧(p∨p)p∨q(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)(p∧q)∨(p∧q)∨(p∧q)(主析取范式)0,1,3由于(p→q)∧(p→r)与p→(q∧p)的主析取范式不同样，因此(p→q)∧(p→r)与p→(q∧p)不等价。用主合取范式判断以下命题公式能否等价。可编写范本(p→q)→r和p→(q→r)(p→q)→r(p∨q)∨r(p∧q)∨r(p∨r)∧(q∨r)(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)0,2,6p→(q→r)p∨(q∨r)p∨q∨r6由于(p→q)→r与p→(q→r)的主合取范式不同样，因此(p→q)→r与p→(q→r)不等价。(p∧q)∨(p∧q)和(p∨q)∧(p∧q)(p∧q)∨(p∧q)∑1,2∏0,3(p∨q)∧(p∨q)(p∨q)∧(p∧q)(p∨q)∧(p∨q)∏0,3由于(∧)∨(p∧)和(∨)∧(∧)的主合取范式同样，因此(∧)∨(p∧pqqpqpqpqq)(p∨q)∧(p∧q)。可编写范本习题1.61.将以下命题公式用只含，∧，∨的等价式表示。⑴(p?q)→r((p∨q)∧(q∨p))∨r(p∧q)∨(p∧q)∨r⑵(p→(q?(q∧r)))(p∨((q∧q∧r)∨(q∧(q∧r))))p∧(q∧r)∧(q∨(q∧r))p∧(q∨r)∧qp∧q∧rp(p→q)p(p∨q)(p∧(p∨q))∨(p∧(p∨q))(p∧q)∨pp∨q(p?q)?r((p∧q)∨(p∧q))?r(((p∧q)∨(p∧q))∧r)∨(((p∧q)∨(p∧q))∧r)((p∧q∧r)∨(p∧q∧r))∨(((p∨q)∧(p∨q))∧r)(p∧q∧r)∨(p∧q∧r)∨((p∨q)∧(p∨q)∧r)⑸(?q)(→)((∨)∧(q∨))(r∨)prtpqpt((p∨q)∧(q∨p)∧(r∨t))∨(((p∨q)∧(q∨p))∧(r∨t))((p∨q)∧(q∨p)∧(r∧t))∨(((p∧q)∨(q∧p))∧(r∨t))2.将以下命题公式用只含，∨的等价式表示。⑴(p∧q)∧p((p∨q)∨p)⑵p?q(p∨q)∧(q∨p)((p∨q)∨(q∨p))⑶(p↑q)∧r(p∧q)∧r((p∨q)∨r)⑷pq(p?q)(p∧q)∧(q∧p)((p∨q)∨(p∨q))⑸(p?q)∧r(p∨q)∧(q∨p)∧r((p∨q)∨(q∨p)∨r)3.将以下命题公式用只含，∧的等价式表示。p∨q∨(r→p)p∨q∨(r∨p)(p∧q∧r∧p)(p∨q)→(p?r)(p∨q)∨(p∧r)∨(p∧r)((p∧q)∧(p∧r)∧(p∧r))⑶(p∨q)∨(p→q)(p∨q)∨(p∨q)可编写范本p∨q(p∧q)(p→q)→(pq)(p∨q)∨(p?q)(p∧q)∨((p∧q)∨(p∧q))((∧)∧((∧)∧(p∧)))pqpqq⑸(p→(q∨r))∨(p→r)(p∨q∨r)∨(p∨r)T4.以下结论能否建立？若建立，请证明。若不建立，举反例说明。p↑qq↑p建立。p↑q(p∧q)(q∧p)q↑pp↓qq↓p建立。p↓q(p∨q)(q∨p)q↓pp↑(q↑r)(p↑q)↑r不建立↑(↑)p↑(∧)(∧(∧))∨(∧)。pqrqrpqrpqr(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∏4,5,6而(p↑q)↑r(p∧q)↑r((p∧q)∧r)(p∧q)∨r(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∏1,3,5明显上式不建立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)∑1,2,3而(p↓q)↓r(p∨q)↓r((p∨q)∨r)(p∨q)∧r(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∑2,4,6明显上式不建立。5.证明以下等价式。⑴(p↑q)p↓q证明：(p↑q)(p↑q)(p∧q)p∧qp↓q(p∨q)p∧q因此：(p↑q)p↓q⑵(p↓q)p↑q证明：(p↓q)(p∨q)p∨qp↑q(p∧q)p∨q因此：(p↓q)p↑q6.将以下命题公式仅用“↓”表示。pp↓p⑵p∨q(p↓q)(p↓q)↓(p↓q)⑶p∧q(p∨q)p↓q(p↓p)↓(q↓q)可编写范本7.将以下命题公式仅用“↑”表示。p(p∧p)p↑p⑵p∨q(p∧q)p↑q(p↑p)↑(q↑q)⑶p∧q(p∧q)(p↑q)(p↑q)↑(p↑q)习题1.7写出以下命题公式的对偶式。⑴(p∧q)∧r的对偶式是：(p∨q)∨r⑵(p∨q)∧(r∨p)对偶式是(p∧q)∨(r∧p)⑶pq(?q)p(p→q)∨(q→p)(p∨q)∨(q∨p)(p∧q)∨(q∧p)因此pq的对偶式是(p∨q)∧(q∨p)而(∨q)∧(∨)pqp(p→q)∧(q→p)p?qp?q(p?q)(pq)因此pq的对偶式是(pq)(p∧q)→r(p∧q)∨rp∨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)∧rp→((q→r)∧(p∧q))p∨((q∨r)∧(p∧q))(p∨q)∧(p∨q∨r)因此p→((q→r)∧(p∧q))的对偶式是(p∧q)∨(p∧q∧r)(p?q)→r(p?q)∨r(p→q)∨(q→p)∨r(p∨q)∨(q∨p)∨r(∧)∨(p∧)∨rpqq因此(p?q)→r的对偶式是(p∨q)∧(p∨q)∧r可编写范本设p→q为公式，则q→p称为该公式的逆换式，?p→?q称为反换式，?q→?p称为逆反式。证明：⑴公式与它的逆反式等价，即p→q??q→?p证明：p→qp∨q而q→pq∨pp∨q因此→q→pqp⑵公式的逆换式与公式的反换式等价，即q→pp→q证明：q→pq∨p而p→qp∨qp∨qq∨p因此q→pp→q3.用真值表或等价演算证明以下包含式。p∧qp→q证明：(p∧q)→(p→q)(p∧q)∨(p∨q)p∨q∨p∨qT因此，p∧qp→qp→qp→(p∧q)证明：作(p→q)→(p→(p∧q))的真值表，如表1.53所示。表1.53pqp→qp∧qp→(p∧q)(p→q)→(p→(p∧q))001011011011100001111111由以上真值表可知：(p→q)→(p→(p∧q))是一个永真式，因此p→qp→(p∧q)pp→q证明：p→(p→q)p∨p∨qp∨p∨qT因此，pp→qp→(q→r)(p→q)→(p→r)证明：(p→(q→r))→((p→q)→(p→r))(p∨q∨r)∨((p∨q)∨(p∨r))(p∧q∧r)∨(p∧q)∨p∨r((p∧q∧r))∨r)∨((p∧q)∨p)((p∨r)∧(q∨r)∧(r∨r))∨((p∨p)∧(p∨q))可编写范本((p∨r)∧(q∨r))∨p∨q((p∨r∨p)∧(q∨r∨p))∨qq∨r∨p∨q1因此，p→(q→r)(p→q)→(p→r)p∧(p→q)q证明：作(p∧(p→q))→q的真值表，如表1.54所示。表1.54pqp→qp∧(p→q)(p∧(p→q))→q00101011011000111111由以上真值表可知：(p∧(p→q))→q是一个永真式，因此p∧(p→q)qq∧(p→q)p证明：作(p∧(p→q))→q的真值表，如表1.55所示。表1.55pqqp→qq∧(p→q)(q∧(p→q))→p001111010101101001110101由以上真值表可知：(q∧(p→q))→p是一个永真式，因此q∧(p→q)p4.用“假定前件为真，推证后件也为真或假定后件为假，推证前件也为假“的方法证明以下包含式。p∧qp→q证明：假定前件p∧q为真，证明后件p→q也为真。由于p∧q为真，因此p为真而且q也为真，依据条件的定义可知p→q也为真。因此，p∧→qpqp→qp→(p∧q)证明:假定后件p→(p∧q)为假,证明前件p→q必为假；由于p→(p∧q)为假，则p为真,q为假；依据条件的定义可知p→q也为假。即：p→qp→(p∧q)⑶pp→q证明:假定前件p为真,则p为假,依据条件的定义可知p→q必为真。可编写范本因此，原包含式建立。p→(q→r)(p→q)→(p→r)证明:假定后件(p→q)→(p→r)为假,证明前件p→(q→r)必为假。由于(p→q)→(p→r)为假，因此，p→q为真，p→r为假；由于p→r为假，因此p为真，r为假；因此，q必为真；由于q为真，r为假，因此q→r必为假；由于p为真，因此，p→(q→r)必为假。因此，原包含式建立。p∧(p→q)q证明：假定前件p∧(p→q)为真，证明后件q也为真。由于p∧(p→q)为真，因此p为真，p→q也为真，依据条件的定义q必为真。因此，原包含式建立。⑹q∧(p→q)p证明：假定前件q∧(p→q)为真，证明后件p也为真。由于q∧(p→q)为真，因此，q为真，q为假，又由于p→q为真，依据条件的定义p为假，因此p必为真。因此，原包含式建立。5.设A是随意的命题公式，证明AA证明：由条件的定义可知：A→A是一个永真式；依据包含式的定义可知AA。可编写范本习题1.81.用全真值表或部分真值表证明以下各题的有效结论。(p→(q→r))，p∧qr((p→(q→r))∧(p∧q))→r的全真值表如表1.56所示。表1.56pqrq→rp→(q→r)p∧q(p→(q→r))∧(p∧q)((p→(q→r))∧(p∧q))→r0001100100111001010010010111100110011001101110011100010111111111由真值表可知，((p→(q→r))∧(p∧q))→r是永真式，因此(p→(q→r))，p∧qr。⑵p∨q,(q∧r),rp((p∨q)∧((q∧r))∧r)→p的全真值表如表1.57所示。表1.57pqRp∨qr(q∧r)(p∨q)∧((q∧r))∧r((p∨q)∧((q∧r))∧r)→p0001111100110101010110010111010110001101101001011101100111110101由真值表可知：((