离散数学答案(尹宝林版)第一章习题解答

第一章 命题逻辑习题与解答⒈判断下列语句是否为命题，并讨论命题的真值。⑴2x3=0。⑵前进！⑶如果8+7>20，则三角形有四条边。⑷请勿吸烟！⑸你喜欢鲁迅的作品吗？⑹如果太阳从西方升起，你就可以长生不老。⑺如果太阳从东方升起，你就可以长生不老。解 ⑶,⑹,⑺表达命题，其中表达真命题，⑺表达假命题。⒉将下列命题符号化：⑴逻辑不是枯燥无味的。⑵我看见的既不是小张也不是老李。⑶他生于1963年或1964年。⑷只有不怕困难，才能战胜困难。⑸只要上街，我就去书店。⑹如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。⑺如果林芳在家里，那么他不是在做作业就是在看电视。⑻三角形三条边相等是三个角相等的充分条件。⑼我进城的必要条件是我有时间。⑽他唱歌的充分必要条件是心情愉快。⑾小王总是在图书馆看书，除非他病了或者图书馆不开门解 ⑴p：逻辑是枯燥无味的。“逻辑不是枯燥无味的”符号化为p。⑵ pq：我看见的是老李。“我看见的既不是小张也不是老李”符号化为pq⑶ p：他生于1963年。q：他生于1964年。“19631964pq⑷ pq：战胜困难。“只有不怕困难，才能战胜困难”符号化为q⑸ pq：我去书店。pq⑹ pqrs：小杨晚上听音乐。“如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为pqrs。⑺ pqr：林芳看电视。pqr⑻ pq：三角形三个角相等。“三角形三条边相等是三个角相等的充分条件”符号化为pq。⑼ pq：我有时间。“我进城的必要条件是我有时间”符号化为pq⑽ pq：他心情愉快。pq⑾ pqr：图书馆开门。“小王总是在图书馆看书，除非他病了或者图书馆不开门”符号化为(qr)p，或者(qr)p。也可符号化为(qr)p，或者(qr)p。⒊列出除，，，，之外的所有二元联结词的真值表。解 共有16个二元联结词记除之外的二元联结词为1,2, ,11。pqp1qp2qp3qp4qp5qp6q00000001010001101001100011001010pqp7qp8qp9qp10qp11q0011111010011110110111101001⒋求下列公式在真值赋值(p1/1,p2/1,p3/0,p4/0)下的值：⑴p1(p2p3)⑵(p1p2p3)((p1p2)(p3p4))⑶(p1p2)p3(((p1p2)p3)p4)(4) (p2p1)(p3p4)⑸(p3)(p2p4)⑹p1(p2p3p1)p2p4(7) (p1p3)(p2p4)解 记真值赋(p1/1,p2/1,p3/0,p4/0)为v。⑴v(p1(p2p3))1(10)1。⑵v((p2p3)((p2)(p3p4)))10)(00))1⑶v((p1p2)p3(((p1p2)p3)p4))(11)0(((11)0)0)1。(4) v((p2p1(p3p4(11)00)011。⑸v((p1p3)(p2p4))(10)(10)0。⑹v(p1(p2p3p1)p2p4)1(101)101。(7) v((p1p3(p2p4(10)(10)000。用真值表判断以下公式是不是永真式、永假式、可满足式。(1) (pr)((qr)(pqr))(2)(pp)p(3) (pq)((pq)p)(4)(p(qr))((pq)(pr))(5)(pq)(pr)(qr)r(6) p(pq)(7)(pq)((pq)p)解 (1)将(pr)((qr)(pqr))记为A。pqrprqrpqpqr(qr)(pqr)A000110111001110111010101011011111111100011001101111111110001011111111111(pr)((qr)(pqr))是永真式。(3)将(pq)((pq)p)记为A。pqpqqpq(pq)pA0011100011010010011111110011(pq)((pq)p)是非永真的可满足式。(6)ppq0p pq0 1 1(p0p(p0011100100010110100p(pq)是永假式。解 (1),(2),(4),(5),是永真式，(6)是永假式是非永真的可满足式。指出满足下列公式的所有真值赋值。(1)(pq)(pr)(2)p(qr(pq))(3)prpr)(qr)(4) p(qr)解 (1)(p/0,q/0,r/0)，(p/0,q/0,r，(p/0,q/1,r/0)，(p/0,q/1,r，(p/1,q/0,r，(p/1,q/1,r/0)，(p/1,q/1,r/1)。(2)p/0q/1r/0p/1q/0r/0p/1q/0rp/1q/1r/0，p/1q/1r/1)。(3)p/0q/0r/0p/0q/1r/0。(4)p(qr)的真值赋值。v(p0v(qr1，v(qv(r)。若v(p1v(qr0，v(qv(r)。所以p(qr)p/0,q/0,r/0)，p/0,q/1,r/1)，p/1,q/0,r/1)，p/0,q/1,r/0)。A既不是永真式，也不是永假式，则A是永假式。对吗？解 不对。若A是非永真的可满足式，则它的替换实例中既有永真式，也有永假式，也有非永真的可满足式。Ap1,…,pn，v1v2AA为假B1,…BnC1,…Cn如下：pp vp

pp

(p)1B

1 i C 2 ii

pp vp01 i

i pp vp02 i1v(Ap1

)

/v(B),,

/v(B)](A)v(A)1，B,,B 1 1 n n 11 1v(Appn1C,,C

)p1

/v(C),,p1

/v(Cn

)](A)v2

(A)0，1 n1所以，AAp1B,,B

是永真式，AAp1C1

是永假式。1 n 1 nA本身也是A的替换实例，它是非永真的可满足式。用真值表证明以下等值式。(1)p(qr)(pq)(pr)pqrqrp(qr) pqpr (pq)(pr)00000 00 000110 00 001010 00 001100 00 010000 00 010111 01 111011 10 111100 11 0(2)(3)(4)用等值演算证明以下等值式。(1)p(qrqpr)(2)(pq)(pr)pqr(3)(pq)(rq)prq(4)p(qp)p(pq)(5)(pq)(rq)prq(6)(pq)pq解 (1)p(qr)p(qr)q(pr)q(pr)(2)(pq)(pr)(pq)(pr)p(qr)pqr(3) (pq)(rq)(pq)(rq)(pr)(qq)(pr)q(pr)qprq(4)p(qp)pqp1ppqp(pq)(5) (pq)(rq)(pq)(rq)(pr)q(pr)qprq(6) (pq)pqpq(pq)(p(q1))1(pq)(11)(pq)0pq(1)(qp(pqp(2)(pq)(rs)(prqs)(3)(pq)(pr)(ps)(pqrs)(4)(pqr)(pr)(qr)解 (1)(qp)(pq)p(qp)(pq)ppp1(2) (pq)(rs)(prqs)(pq)(rs)prqs(pq)p(rs)rqsqpsrqs1(3) (pq)(pr)(ps)(pqrs)pqprps(pqrs)pqrspqrs1(4) (pqr)(pr)(qr)((pq)r)prqr((pq)r)pqr(pqpqr)(rpqr)111(1)(qp)(pqp(2)(pq)(qr)(pr)解 (1)(qp)(pq)p(qp)(pq)ppp0(2) (pq)(qr)pr)(pq)(qr)(pr)(pq)(qr)pr((pq)p)((qr)r)pqqr0{,}生成的公式。{,}生成的公式。(1)pq(rp)(2)(pqr)pq(3)pqp解(1)pq(rp)pq(rp)(pqr)(pqp)pqrpqr)(2)(pqr)pq(pqr)pq((pqr)pq)(3)pqp(pqp)A是由{}A中出现偶数次。证明 首先证明：若A是由{}生成的仅出现一个命题变元p的公式，则1pAppA中的出现次数进行归纳。

若p在A中出现偶数次若p在A中出现奇数次① pA1ApAp。② pA2AppA1。③ 设p在A中的出现nA为BCp在C中的出现次数分别为k和lnkl，kn且lnnklCA1。nklCp，另一个是永真式，因此Ap1p。设在A中的出现的所有命题变元为p1,,pn，它们的出现次数分别为k1,,kn。因为AB(AB)(BA)BA，并且(AB)C((AB)C)AB1C1ABC11(A(BC))A(BC)nn i i }B1,BBB仅出现命题变元pki1,n。若k1,kn全为偶数，则ABn111k1,knnn i i llk,,kll1

A

p p

，显然A不是永真式。n设A是由{生成的公式证明A是永假式当且仅当每个命题变元在A中出现偶数次证明 首先证明：若A是{}生成的仅出现一个命题变元p的公式，则nApA中的出现次数进行归纳。

pApA① pA1ApA。② pA2AppA0。③ pAn次，ABC，pB，Ckl，则nkl，knlnnklC等值于同一公式，A0nklCp，另一个是永假式，Ap0p。Ap1,…pnk1,…kn满{}B1,…BnAB1piki，i1,…nk1,…kn全为偶数，则lAB1Bn000k1,…,kn中有kl1

,,klml

是奇数，则nAn

pp

，显然A不是永假式。问：实际名次怎样排列？解 用字母表示命题如下：p2：北京第二，q2：上海第二，r1：天津第一，r2：天津第二，s3：广州第三，s4：广州第四。由已知条件列出以下方程：q21s31s41；r20，s3s40；没有并列名次：p2q2=0，p2r2=0，r2q2=0。解以上8个方程组成的方程组。r2=r21=r2(r1q2)=(r2r1)(r2q2)=00=0，将r2=0代入r23=1得s3=3=1代入3s4=0得4=4=0代入2s41p2p21p2q20q2q20r1q21r11。p2r1s31，q2r2s408因此，天津第一，北京第二，广州第三，上海第四。17.某勘探队取回一块矿样，三人判断如下。已经知道，这三人中有一个是专家，一个是老队员，一个是实习队员。化验结果表明：这块矿样只含一种金属，专家的两个判断皆对，老队员的判断一对一错，实习队员的两个判断皆错。问：这三人的身分各是什么？解 p:矿样含铁， q:矿样含铜，rrp

r:矿样含锡。这三人中有一个是专家，一个是老队员，一个是实习队员，公式会非常pq0r0，rp0pq。乙是实习队员，即prrp。甲、乙、丙三人中至少有一个是实习队员，可表示为：(pq)(pr)(rp)1pq0，所以pr(rp1pr1p和r1，因此q0q即乙说的话一半对一半错，可表示为：pr。丙是老队员，即丙说的话一半对一半错，rp。甲、乙、丙三人中有奇数个老队员，可表示为：(pq)(pr)(rp)1由教材上的等值式可得到(pq)(pr)(rp)(pp)(rr)(qp)01(q1p)qp又知道q0p1。因为rp0，所以r0。因此，甲说的话一半对一半错，甲是老队员。乙说的话全错，乙是实习队员。丙说的话全对，丙是专家。18.先用等值演算证明下列等值式，再用对偶定理得出新等值式。(1)(pq)(pq)p(2)(pq)(pq)(pq)(pq)(3)q((pq)p)1解 (1)(pq)(pq)(pq)(pq)p(qq)p由对偶定理得(pq)(pq)p。(2) (pq)(pq)(pq)(p(qq))(pq)p(pq)(pp)(pq)pq(pq)由对偶定理得(pq)(pq)(pq)(pq)。(3)A是由{0,1,}A互为对偶式。AA*是永假式。AA*是永真式。证明 (1)设A是永真式，则A1，由对偶定理得A*0，因此A*是永假式。(2)AA0A*1A*是永真式。证明以下联结词集合是极小完全集。(1){0,} (2){,} (3){,,} (4){,,}证明(1)pp0p0，因为{,}{0,}是完全集。任取由{0}生成的不出现除命题变元p之外的命题变元的公式A，令真值赋值v=(p/0)，则v(A0，而v(p1{0}{0}{}出现命题变元p的公式A，令真值赋值vp/1)，则v(A1v(p0，因此{}{}{0,}是极小完全集。(2)pp1p(pp)，因为{,}是完全集，所以{,}是完全集。任取由{}生成的仅出现命题变元p的公式A，令真值赋值v=(p/0)，则v(A)=0，而v(p)=1，因此{}不能定义。所以{}不是完全集。{}不是完全集。所以{,}是极小完全集。(3)pp1p(pp){}{}是完全集。任取由{}生成的仅出现命题变元p的公式A，令真值赋值vp/0)v(A0，而v(p)=1，因此{,}{,}{,}生成的仅出现命题变元p的公式A，令真值赋值vp/1)，则v(A1v(p0，因此{}{,}{,}{,,}是极小完全集。(4)pp1p(pp){}{}是完全集。任取由{}生成的仅出现命题变元p的公式A，令真值赋值vp/0)v(A0，而v(p)=1，因此{,}{,}{,}生成的仅出现命题变元p的公式A，令真值赋值vp/1)，则v(A1v(p0，因此{}{,}{,}{,,}是极小完全集。(1){,,(2),,证明(1)任取由,,,}生成的仅出现命题变元p的公式v(p/)，则v(A)1，而v(p)0，因此{,,,}不能定义。所以{,,,}不是完全集。(2)任取由}生成的仅出现命题变元p的公式Avp/0，则v(A)0，而v(p)1，因此{,,}不能定义。所以{,,}不是完全集。二元联结词（）和（）的真值表如下。pqpqpq0011011010101100证明：若是二元联结词{}是完全集，则是或证明 (1)ppp,pq(pq)(pq(pq(pq)，因为{}{}是完全集。(2)ppp, pq(pq)(pq)(pq)(pq)，因为{,}是完全集，所以{}是完全集。(3) 000111{}01110。01101，真值表最后一列有奇数个1的不能由{}定义。所以，01=10。若01=10=1，则是。若01=100，则。三元联结词的真值表如下。pqr(p,q,r)00010011010001101000101011011110证明{}是极小完全集。证明 pqpqq，因为{}是完全集，所以{}是极小完全集。24.在下列公式中，哪些是析取范式，哪些是合取范?p，pq，(pq)r，pr，pp，((pq)q)r解 p，pq，pr，pp是析取范式，p，pq，pr，(pq)r，pp是合取范式。25.在下列公式中，哪些是关于p,q,r的主析取范式，哪些是关于p,q,r的主合取范式？pqr, pqr, (pqr)(pqr),p(qr), (ppq)(pqr)解 pqr是关于p,q,r的主析取范式qr是关于p,q,r的主合取范式。26.是否有这样的公式，它既是主合取范式，又是主析取范式？如果有，举出一例。解 有p既是关于p的主析取范式，又是关于p的主合取范式。求下列公式的主范式，进而判断其是否永真式、永假式、可满足式。(1)pqr(2)(pq)r(3)pq(pq)(4)p(pq(qr))(5)(pqr)(pqr)(6)pq(pq)解 (1)pqr(pq)rpqrpqr的主合取范式是pqr，包含一个极大项，因此它是非永真的可满足式。(2)(pq)r(pq)r(pq)r(pr)(qr)(p(qq)r)((pp)qr)(pqr)(pqr)(pqr)pqr的主合取范式是pqrpqr(pqr(3)pq(pq)(pq)((pq)(pq))(pq)(pq)(pq)pqpqpqpqpq(4)p(pq(qr))p(pq(qr))1ppq(qr的主合取范式为1(5)(pqr)(pqr)(p(qr))(p(qr))(pp)(pqr)(qrp)(qrqr)(pqr)(pqr)pqr(pqr的主析取范式为(pqrpqr，包含了两个极小项，因此它是非永真的可满足式。(6)pq(pq)(p(qq))((pp)q)(pq)(pq)(pq)(pq)(pq)pq(pq的主合取范式为pqpq(pq(pq，包含了所有的四个极大项，因此它是永假式。用主范式证明下列等值式。(1)(pq)pq(pp)(rp)(2)(pq)(pr)pqr解(1)(pq)pq(pq)(pq)(pq)(pq)(pq(rr))(pq(rr))(pqr)(pqr))(pqr)(pqr)(pp)(rp)(pp)(rp)p(pr)pp(qq)(rr)(pqr)(pqr))(pqr)(pqr)(pq)pq和(pp)(rp)等值于同一个关于p,q,r的主析取范式(pqr)(pqr))(pqr)(pqr)，因此，(pq)pq(pp)(rp)。(2)(pq)(pr)(pq)(pr)(pq(rr))(p(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)pqrp(qr)(pq)(pr)(pq(rr))(p(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pq)(pr)和pqr的主合取范式相同，所以，pqpr)pqr。29.判断以下关系是否成立，并说明理由。(1)pq,pq(2)pq,,q|p(3)p1q1,p2q2,p1p2|q1q2(4)pq,qp|pq(5)pqr,pqr|pqr解 (1)若真值赋值v使得v(pq)v(p)1，则v(q)1。所以pq,pq。(2)真值赋值v(p/0,q使得v(pq)v(pq)v(q)1，但v(p