搜索
第一章命题逻辑习题与解答⒈判断下列语句是否为命题，并讨论命题的真值。⑴。032=−x⑵前进！⑶如果，则三角形有四条边。2078+⑷请勿吸烟！⑸你喜欢鲁迅的作品吗？⑹如果太阳从西方升起，你就可以长生不老。⑺如果太阳从东方升起，你就可以长生不老。解⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。⒉将下列命题符号化：⑴逻辑不是枯燥无味的。⑵我看见的既不是小张也不是老李。⑶他生于1963年或1964年。⑷只有不怕困难，才能战胜困难。⑸只要上街，我就去书店。⑹如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。⑺如果林芳在家里，那么他不是在做作业就是在看电视。⑻三角形三条边相等是三个角相等的充分条件。⑼我进城的必要条件是我有时间。⑽他唱歌的充分必要条件是心情愉快。⑾小王总是在图书馆看书，除非他病了或者图书馆不开门。解⑴p：逻辑是枯燥无味的。“逻辑不是枯燥无味的”符号化为。p¬⑵p：我看见的是小张。q：我看见的是老李。“我看见的既不是小张也不是老李”符号化为。qp¬∧¬⑶p：他生于1963年。q：他生于1964年。“他生于1963年或1964年”符号化为。qp⊕⑷p：害怕困难。q：战胜困难。“只有不怕困难，才能战胜困难”符号化为。pq¬→⑸p：我上街。q：我去书店。“只要上街，我就去书店”符号化为。qp→⑹p：小杨晚上做完了作业。q：小杨晚上没有其它事情。r：小杨晚上看电视。s：小杨晚上听音乐。“如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为srqp∨→∧。⑺p：林芳在家里。q：林芳做作业。r：林芳看电视。“如果林芳在家里，那么他不是在做作业就是在看电视”符号化为rqp∨→。⑻p：三角形三条边相等。q：三角形三个角相等。“三角形三条边相等是三个角相等的充分条件”符号化为。qp→⑼p：我进城。q：我有时间。“我进城的必要条件是我有时间”符号化为。qp→⑽p：他唱歌。q：他心情愉快。“他唱歌的充分必要条件是心情愉快”符号化为。qp↔⑾p：小王在图书馆看书。q：小王病了。r：图书馆开门。“小王总是在图书馆看书，除非他病了或者图书馆不开门”符号化为prq→¬∨¬)(。⒊列出除，∨，⊕，→，↔之外的所有二元联结词的真值表。∧离散数学习题解答1解共有16个二元联结词，记除，∨，⊕，→，∧↔之外的二元联结词为1121,,,ΔΔΔΚ。pqqp1Δqp2Δqp3Δqp4Δqp5Δqp6Δ00000001010001101001100011001010pqqp7Δqp8Δqp9Δqp10Δqp11Δ0011111010011110110111101001⒋求下列公式在真值赋值下的值：)0/,0/,1/,1/(4321pppp⑴)(321ppp∧∨⑵))()(()(4321321ppppppp∨∧∨¬∨∧∧⑶)))((()(4321321ppppppp¬∧¬∨∧¬∨¬∨∧¬⑷4312)(pppp∨¬→¬↔⑸)()(4231pppp→¬∧↔⑹421321)(pppppp¬∨↔¬∧→∨⑺)()(4231pppp⊕¬∧↔解记真值赋值为v。)0/,0/,1/,1/(4321pppp⑴。1)01(1))((321=∧∨=∧∨pppv⑵1))00()11(()011()))()(()((4321321=∨∧∨¬∨∧∧=∨∧∨¬∨∧∧pppppppv⑶))))((()((4321321pppppppv¬∧¬∨∧¬∨¬∨∧¬1)0)0)11(((0)11(=¬∧¬∨∧¬∨¬∨∧¬=。⑷100)11())((4312=∨¬→¬↔=∨¬→¬↔ppppv。⑸0)01()01())()((4231=→¬∧↔=→¬∧↔ppppv。⑹101)101(1))((421321=¬∨↔¬∧→∨=¬∨↔¬∧→∨ppppppv。⑺0)01()01())()((4231=⊕¬∧↔=⊕¬∧↔ppppv。5.用真值表判断以下公式是不是永真式、永假式、可满足式。(1)))()(()(rqprqrp→∨→→→→离散数学习题解答2(2)ppp¬→¬→)((3)))(()(pqpqp→¬→→→(4)))()(())((rpqprqp→→→→→→(5)rrqrpqp→→∧→∧∧)()()((6))(qpp→¬∧¬(7)))(()(pqpqp¬→¬→→→解(1),(2),(4),(5),(7)是永真式，(6)是永假式，(3)是非永真的可满足式。6.指出满足下列公式的所有真值赋值。(1))()(rpqp∨¬∨∧(2)))((qprqp∨∧¬∧∨(3))()(rqrprp∨∧∨¬→∨(4))(rqp↔⊕解(1)，，，，)0/,0/,0/(rqp)1/,0/,0/(rqp)0/,1/,0/(rqp)1/,1/,0/(rqp，，。)1/,0/,1/(rqp)0/,1/,1/(rqp)1/,1/,1/(rqp(2)，，，，)0/,1/,0/(rqp)0/,0/,1/(rqp)1/,0/,1/(rqp)0/,1/,1/(rqp。)1/,1/,1/(rqp(3)，。)0/,0/,0/(rqp)0/,1/,0/(rqp(4)，，，。)0/,0/,0/(rqp)1/,1/,0/(rqp)1/,0/,1/(rqp)0/,1/,1/(rqp7.若公式A既不是永真式，也不是永假式，则A的每个替换实例一定既不是永真式，也不是永假式。对吗？解不对。若A是非永真的可满足式，则它的替换实例中既有永真式，也有永假式，也有非永真的可满足式。8.用真值表证明以下等值式。(1)(2)(3)(4)9.用等值演算证明以下等值式。(1))()(rpqrqp→→⇔→→(2)rqprpqp∧→⇔→∧→)()((3)qrpqrqp→∧⇔→∨→)()(离散数学习题解答3(4))()(qpppqp→→¬⇔→→(5)qrpqrqp→∨⇔→∧→)()((6)qpqp¬↔⇔↔¬)(解(1))()()()(rpqrpqrqprqp→→⇔∨¬∨¬⇔∨¬∨¬⇔→→(2)rqprqprpqprpqp∧→⇔∧∨¬⇔∨¬∧∨¬⇔→∧→)()()()()((3)qrpqrpqrqpqrqp→∧⇔→∧¬⇔∨¬∨∨¬⇔→∨→)()()((4))(1)(qppqpppqppqp→→¬⇔∨¬∨¬¬⇔⇔∨¬∨¬⇔→→(5)qrpqrqpqrqp∨¬∧¬⇔∨¬∧∨¬⇔→∧→)()()()()(qrpqrp→∨⇔∨∨¬⇔)((6)qpqpqpqpqp¬↔⇔¬⊕¬⇔⊕⊕⊕⇔⊕⇔↔¬)(1))1(()(10.用等值演算证明以下公式是永真式。(1)pqppq↔→¬∧→)()((2))()()(sqrpsrqp∧→∧→→∧→(3))()()()(srqpsprpqp∨∨→→→∨→∨→(4))()()(rqrprqp→∨→→→∨解(1)pqppq↔→¬∧→)()(1)()(⇔↔⇔↔¬∨∧∨¬⇔pppqppq(2))()()(sqrpsrqp∧→∧→→∧→sqrpsrqp∧→∧∧∨¬∧∨¬⇔)()(sqrsrpqp∧→∧∨¬∧∧∨¬⇔)()(1⇔∧→∧∧∧⇔sqrspq(3))()()()(srqpsprpqp∨∨→→→∨→∨→)(srqpsprpqp∨∨→→∨¬∨∨¬∨∨¬⇔1⇔∨∨∨¬→∨∨∨¬⇔srqpsrqp(4))()()(rqrprqp→∨→→→∨rqrprqp∨¬∨∨¬∨∨∨¬¬⇔))((离散数学习题解答4rqprqp∨¬∨¬∨¬∧∨⇔))((111)()(⇔∧⇔∨¬∨¬∨¬∧∨¬∨¬∨∨⇔rqprrqpqp11.用等值演算证明以下公式是永假式。(1)pqppq¬↔→¬∧→)()((2))()()(rprqqp→¬∧→∧→解(1)pqppq¬↔→¬∧→)()(0)()(⇔¬↔⇔¬↔¬∨∧∨¬⇔pppqppq(2))()()(rprqqp→¬∧→∧→)()()(rprqqp∨¬¬∧∨¬∧∨¬⇔rprqqp¬∧∧∨¬∧∨¬⇔)()())(())((rrqpqp¬∧∨¬∧∧∨¬⇔0⇔¬∧¬∧∧⇔rqqp12.找出与下列公式等值的尽可能简单的由生成的公式。},{∧¬13.找出与下列公式等值的尽可能简单的由生成的公式。},{∨¬(1))(prqp→¬∧¬∧¬(2)qprqp∧¬∧¬∨→)((3)pqp¬∧∧解(1))(prqp→¬∧¬∧¬)(prqp∨¬¬∧¬∧¬⇔)()(pqprqp∧¬∧¬∨¬¬∧¬∧¬⇔rqp¬¬∧¬∧¬⇔)(rqp¬∨∨¬⇔(2)))(()()(qprqpqprqpqprqp¬∨∨¬∨∨¬¬¬⇔∧¬∧¬∨∨¬⇔∧¬∧¬∨→(3))(pqppqp∨¬∨¬¬⇔¬∧∧14.设A是由生成的公式。证明：A是永真式当且仅当每个命题变元在A中出现偶数次。}{↔证明首先证明：若A是由生成的仅出现一个命题变元p的公式，则}{↔⎩⎨⎧⇔中出现奇数次在若中出现偶数次在若AppApA1对p在A中的出现次数进行归纳。①若p在A中出现1次，即A为p，显然。pA⇔②若p在A中出现2次，即A为pp↔，显然。1⇔A③设p在A中的出现n次，A为，p在B，C中的出现次数分别为k和l，则CB↔lkn+=，且。若n为偶数,则k和l的奇偶性相同，B和C等值于同一公式，。若n为奇数,则k和l的奇偶性不同，B和C中一个等值于p，另一个是永真式，因此nknl1⇔A离散数学习题解答5ppA⇔↔⇔1。设在A中的出现的所有命题变元为npp,,1Λ，它们的出现次数分别为nkk,,1Λ。因为ABA⊕¬⇔↔(ABABB↔⇔⊕¬⇔)()，并且11))(()(⊕⊕⊕⊕⇔⊕⊕¬¬⇔↔↔CBACBACBA)())((11CBACBACBA↔↔⇔⊕¬⊕¬⇔⊕⊕⊕⊕⇔所以满足交换律和结合律，存在由生成的公式↔}{↔nBB,,1Λ，使得nBBA↔↔⇔Λ1111，并且仅出现命题变元，出现次数为，。若全为偶数，则iBipiki,1Λ=n,nk,k,1Λ1⇔⊕⊕⇔↔↔⇔ΛΛnBBA。若中有nk,k,1Λmllkk,1,Λ是奇数，则mlplpnBBA↔↔⇔↔⇔↔ΛΛ1，显然A不是永真式。1}{⊕15.设A是由生成的公式。证明：A是永假式当且仅当每个命题变元在A中出现偶数次。证明首先证明：若A是由生成的仅出现一个命题变元p的公式，则}{⊕⎩⎨⎧⇔中出现奇数次在若中出现偶数次在若AppApA0对p在A中的出现次数进行归纳。①若p在A中出现1次，即A为p，显然。pA⇔②若p在A中出现2次，即A为pp⊕，显然。0⇔A③设p在A中的出现n次，A为，p在B，C中的出现次数分别为k和l，则CB⊕lkn+=，且。若n为偶数,则k和l的奇偶性相同，B和C等值于同一公式，。若n为奇数,则k和l的奇偶性不同，B和C中一个等值于p，另一个是永假式，因此。nknl0⇔AppA⇔⊕⇔0设在A中的出现的所有命题变元为npp,,1Λ，它们的出现次数分别为nkk,,1Λ。因为⊕满足交换律和结合律，所以存在由}{⊕生成的公式，使得nBB,,1ΛnA⇔BB⊕⊕Λ1，并且仅出现命题变元，出现次数为，。若iBipikni,,1Λ=nkk,,1Λ全为偶数，则0⊕00⊕⊕1⊕⇔ΛBA⇔⇔ΛnB。若nk,,k1Λ中有mlk,,l1kΛ是奇数，则mlplpnBBA⊕⊕⇔1⊕⊕⇔Λ1:2p:2qΛ，显然A不是永假式。16.北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。甲说：“天津第一，上海第二。”乙说：“天津第二，广州第三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解用字母表示命题如下：北京第二，上海第二，天津第一，:1r离散数学习题解答6:2r天津第二，广州第三，广州第四。:3s:4s由已知条件列出以下方程：甲猜对了一半：，乙猜对了一半：121=⊕qr132=⊕sr，丙猜对了一半：，142=⊕sp每个城市只能得一个名次：，；021=∧rr043=∧ss没有并列名次：，022=∧qp022=∧rp，022=∧qr。解以上8个方程组成的方程组。000)()()(1221221222=⊕=∧⊕∧=⊕∧=∧=qrrrqrrrr将代入得，将代入02=r132=⊕sr13=s13=s043=∧s