离散数学课后答案(一)

自考 2324 离散数学课后答案1.21 答：a)的真值为 T;b)的真值为 T；c)不是命题；d)的真值为 F；e)F；f)不是命题；g)F；h)不是命题；i)T；j)不是命题；k)F。3A)设 P:小李聪明；Q:小李用功 则本例符号化为： PQb)设 P :小赵昨天晚自习时做了二三十道数学题 则本例符号化为: Pc)设 P:天下大雨；Q：他在体育馆内锻炼 则本例符号化为：PQd)设 P:天下大雨；Q：他在室内运动 则本例符号化为：|P|Qe)设 P:经一事；Q:长一智 则本例符号化为：|P|Q4 答：a)原子命题为：今天天气炎热；今天有雷阵雨 b)原子命题为：你去比赛；我去比赛；c)原子命题为：我看电视；我看电影；我做作业；d)原子命题为：四边形 ABCD 是平行四边形；四边形的对边平行；1.31. 答: a) 不是合式公式。b) 是合式公式。c) 是合式公式。d) 不是合式公式。e) 是合式公式2. 答：a) 由合式公式的定义中的规定(1)A、B 本身是一个合式公式；由规定(3)(AB)是一个合式公式；由规定(4)再次应用(3)可得式(A(AB)；b) 由合式公式定义规定(1)A、B 本身各是一合式公式；由规定(2)|A 是一合式公式；由规定(4)应用(3)得(|AB)是一合式公式；再应用(3)得原式 是一个合式公式。c) 由合式公式定义规定(1)A、B 本身各是一合式公式；由规定(2)|A 是一合式公式；由规定(3)(|AB)、(BA)各是合式公式；由规定(4)应用(3)得到的式子为合式公式。5.试以真值表证明下列命题。a)合取运算的结合律是 P(QR)=(PQ)R；真值表如下：最后两列的值完全相等，因此可证明合取运算结合律正确。(答案及点评)P Q RPQQRP(QR)(PQ)R0 0 000000 0 100000 1 000000 1 101001 0 000001 0 100001 1 010001 1 11111b)析取运算的结合律；(答案及点评)b)析取运算的结合律是 P(QR)=(PQ)R；真值表如下：最后两列的值完全相等，因此可证明析取运算结合律正确。P Q RPQQRP(QR)(PQ)R0 0 000000 0 101110 1 011110 1 111111 0 010111 0 111111 1 011111 1 11111c)合取()对析取()之分配律，(答案及点评)c)见下表:可证：P(QR)=(PQ)(PR)P Q R(QR)PQPRP(QR)(PQ)(PR)0 0 0000000 0 1100000 1 0100000 1 1100001 0 0000001 0 1101111 1 0110111 1 111111d)德摩根律。(答案及点评)d)此律公式为|(PQ)=|P|Q；|(PQ)=|P|Q,现取前者证明，真值表如下： P QPQ|P|Q |(PQ)|P|Q0 0011110 1110001 0101001 1100006 下表为含有两上变元的命题公式的各种情况真值表，对于每一列试写出一个至多包含此两个变元的命题公式 。1. (|PP)2.|(PQ)3.|(QP)4.|P 5.|(PQ)6.|Q7.|(PQ) 8.|(QP) 16.(|PP) 15.(PQ) 14.(QP) 13.P 12.PQ 11.Q 10.PQ 9.PQ请 注 意对 应 的行 正 好是 否 定的 关 1.41. (答案及点评) a)若 P 为 F,则该命题为 T。(双条件定义)若 P 为 T，则(PQR)必为 P。(析取)因此本式为永真式。b) 若 P 为 T，则(P|P)为 F,命题值为 T。若 P 为 F，则(P|P)为 T，|P 为 T，命题为 T。所以本式为永真式。c) 本式中，只有当 P 为 T，且(QP)为 F 时，命题为 T，而当 P 为 T 时，不论 Q 为何值，(QP)均为真，因此命题永假。本式也可用真值表来判断：P Q |(QP) |(QP)P0 0 0 00 1 0 01 0 0 01 1 0 0d) 本题可用真值表证明：P Q PQ Q|P (PQ)(Q|P)0 0 1 1 10 1 1 1 11 0 0 1 11 1 1 0 0 可见(PQ)(Q|P)式是一可满足式。e) (|PQ)(Q|P)(PQ)(|Q|P) (等值公式)|(PQ)|(QP) (德摩根律)|(PQ)(QP) (德摩根律)|(PQP)(QQP) (分配律)|(PQ) (幂等律)从这个化简式中可以明确地得出，只有当 P 与 Q 均为 F 时，命题为 T，其他情况均为 F。所以命题是可满足式。f)由 P|PT， (Q|Q)F (否定律), F|RF(同一律)可将原式化为：TFF，即原命题是一永假式。g) (P|P)QFQ，当 Q 为 T 时，命题为 F，当 Q 为 F 时，命题为 T，因此本命题是可满足式。h) 可列真值表如下:P Q PQ |(PQ) PQ)|(PQ)0 0 1 1 10 1 0 0 11 0 0 0 11 1 1 0 0 可见该命题是一可满足式。2.(答案及点评) a) 证明如下：P(QP)P(|QP) (等值公式)|P(|QP) (等值公式)P(|P|Q) (交换律)P(P|Q) (等值公式)b)证明如下：(PQ)|(PQ)(|P|Q) (等值公式)|(PQ)|(|P|Q) (德摩根律)|(PQ)(PQ) (德摩根律)(PQ)|(PQ) (交换律)c) 证明如下：|(PQ)|(|PQ) (等值公式)P|Q； (德摩根律)d) 证明如下：P(QR)|P(QR) (等值公式)(|PQ)R) (结合律)|(P|Q)R (德摩根律)(P|Q)R (德摩根式)e) 证明如下：(PR)(QR)(|PR)(|QR) (等值公式)(|P|Q)RR (交换、结合律)|(PQ)R (德摩根律)(PQ)R (等值公式)注意：证到这里，我们发现这个结果与题目所提供的右边公式不相同，那么就是说，原等价式是不成立的。也就是说，题目有错。于是我又加以验证:当 P 为 T，Q 为 F，R 为 F时，原命题等价式的左边命题为 T，右边命题为 F。可见题目所给等价式不成立。f) 证明如下：双条件式只有在前后件真值相同时为 T,所以证明时分为两种情况：若 P 与 Q 真值相同，则|PQ 为 F、|(PQ)也为 F，等价式成立。若 P 与 Q 真值不同，则|PQ 为 T、|(PQ)也为 T，等价式也成立。证毕。3. 答：a) AB 等价式不成立。假定有一组指派，A 为 T、B 为 F，这对于已知条件来说是成立的，而对于结论是不成立的。b) AB 也不成立。假定有一组指派，A 为 T、B 为 F，C 为 F，则对于已知条件来说是成立的，而对于结论是不成立的。c) AB 等价式成立若 A 为 T，由已知条件得 B 必为 T，反之若 A 为 F，则 B 必为 F，所以 AB 成立。4. (答案及点评)a)证明如下:假定 P(PQ)为 T，则 P 为 T，且 PQ 为 T，所以 Q 必为 T。因此蕴含式成立。b)证明如下：假定右边 P(PQ)为 F,则 P 必为 T，且 PQ 必为 F，可得 Q 必为 F。因此左边的值为 F。即可证蕴含式成立。c)证明如下：假定右边 PQ 为 F，则 P 为 F、Q 为 F,可得左边(PQ)Q 为 F，因此蕴含式成立。d)由于该题中有“CP”字样，不知是何含义，因此无法证明，请各位高手指点迷津。e) 题中的逗号“，”即表示合取“”的意思。这样可以使表达清晰，简洁易读。证明如下：假定左边的真值为 T，则(1) |A(BC)为 T；(2) (DE)为 T；(3) (DE)|A 为 T；由(2)和(3)可知|A 为 T，再由(1)得(BC)为 T，即右边为 T，因此该蕴含式成立。在学完第 6 节“推理理论”后，我们将可以用更科学更简洁的方法来表达这个推理过程。5. 答：设 P：我学习。Q：我数学会及格。R：我热衷于玩扑克。则本题的论证符号化为：P|Q，|RP,|Q=>R 要检验此论证的有效性就是要证明此蕴含式是否成立。设左边命题公式为 T，则P|QPQ 为 T;|RQ 为 T；|Q 为 T；可得 Q 为 F，P 为 F，R 为 T，所以蕴含式成立，因此上述论证是有效的。1.51.(答案及点评)a)解:|(P(Q(PR)|(P(|Q(PR) 等值公式(|P(|Q(PR) (|P(|Q(PR)(P|(|Q(PR) 等值公式2. (答案及点评)a) 解:此题不用化。b) 解：(PQ)R(PQ)(|P|Q)R 等值公式|(|(PQ)|(|P|Q)R 德摩根律|(|(PQ)|(|P|Q)|R) 德摩根律c) 解：P(QR)P|(|Q|R) 德摩根律3.解：析取范式就是在各个子公式中只含|，联结词，而各子公式之间只以“”联结的命题公式。|(PQ)(PQ)(|P|Q)(PQ)德摩根律(|P|Q)(PQ)(|(|P|Q)|(PQ)等值公式F(假)(|(|P|Q)|(PQ)交换律、结合律、否定律|(|P|Q)|(PQ)同一律(PQ)(|P|Q) (P(|P|Q)(Q(|P|Q) (P|Q)(|PQ) 4、a) 解：先求其主析取范式： (|PQ)(|QP) (PQ)(|QP) |(PQ)(|QP) (|P|Q)(|Q1)(P1) (|P|Q)(|Q(P|P)(P(Q|Q) (|P|Q)(|QP)(|Q|P)(PQ)(P|Q) (|P|Q)(P|Q)(PQ) m00m10m11 =0，2，3b) 解：我们仍先来求主析取范式：|(PQ)QR |(|PQ)QR (P|Q)QRP(|QQ)RF(永假)可见，此公式为永假式，它的主析取范式不存在。反之其主合取范式就包含全部大项：M000M001M010 M011M100M101M110M111 =0，1，2，3，4，5，6，7c) 解：等价式左边P(|P(PQ)T0，1，2，3等价式右边(|P|Q)(PQ) |(PQ)(PQ)T0，1，2，3两边都为永真式，因此都可化为包含全部 4 个小项的主析取范式。二者是等价的。5.a)证明如下：设 P：(AB)(AC)(|AB)(|AC)(|AB(|CC)(|AC)(|BB)(|ABC)(|AB|C)(|A|BC)(|ABC)M100M101M110=4,5,6 再设 Q：(A(BC)|A(BC)(|AB)(|AC)(|ABC)(|AB|C)(|ABC)(|A|BC)