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

(完满版)失散数学答案(尹宝林版)第一章习题解答(完满版)失散数学答案(尹宝林版)第一章习题解答/(完满版)失散数学答案(尹宝林版)第一章习题解答第一章命题逻辑习题与解答⒈判断以下语句可否为命题，并谈论命题的真值。2x3=0。⑵前进！⑶若是8+7>20，则三角形有四条边。⑷请勿吸烟！⑸你喜欢鲁迅的作品吗？⑹若是太阳从西方升起，你就可以长生不老。⑺若是太阳从东方升起，你就可以长生不老。解⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。⒉将以下命题符号化：⑴逻辑不是无聊无味的。⑵我看见的既不是小张也不是老李。⑶他生于1963年或1964年。⑷只有不怕困难，才能战胜困难。⑸只要上街，我就去书店。⑹若是夜晚做完了作业并且没有其他事情，小杨就看电视或听音乐。⑺若是林芳在家里，那么他不是在做作业就是在看电视。⑻三角形三条边相等是三个角相等的充分条件。⑼我进城的必要条件是我有时间。⑽他唱歌的充分必要条件是心情快乐。⑾小王总是在图书馆看书，除非他病了也许图书馆不开门。解⑴p：逻辑是无聊无味的。“逻辑不是无聊无味的”符号化为p。p：我看见的是小张。q：我看见的是老李。“我看见的既不是小张也不是老李”符号化为pq。p：他生于1963年。q：他生于1964年。“他生于1963年或1964年”符号化为pq。p：害怕困难。q：战胜困难。“只有不怕困难，才能战胜困难”符号化为qp。p：我上街。q：我去书店。“只要上街，我就去书店”符号化为pq。p：小杨夜晚做完了作业。q：小杨夜晚没有其他事情。r：小杨夜晚看电视。“若是夜晚做完了作pqrs。

s：小杨夜晚听音乐。业并且没有其它事情，

小杨就看电视

或听音乐

”符号化为p：林芳在家里。q：林芳做作业。r：林芳看电视。“若是林芳在家里，那么他不是在做作业就是在看电视”符号化为pqr。⑻p：三角形三条边相等。q：三角形三个角相等。“三角形三条边相等是三个角相等的充分条件”符号化为pq。p：我进城。q：我有时间。“我进城的必要条件是我有时间”符号化为pq。p：他唱歌。q：他心情快乐。“他唱歌的充分必要条件是心情快乐”符号化为pq。p：小王在图书馆看书。q：小王病了。r：图书馆开门。“小王总是在图书馆看书，除非他病了也许图书馆不开门”符号化为(qr)p，也许(qr)p。也可符号化为(qr)p，也许(qr)p。⒊列出除，，，，之外的所有二元联系词的真值表。解共有16个二元联系词，记除，，，，之外的二元联系词为1,2,,11。pqp1qp2qp3qp4qp5qp6q00000001010001101001100011001010pqp7qp8qp9qp10qp11q0011111010011110110111101001⒋求以下公式在真值赋值(p1/1,p/1,p/0,p/0)234下的值：p1(p2p3)⑵(pp2p3)((pp)(pp4))1123⑶(pp2)p3(((pp2)p3)p4)11(4)(pp)(pp)2134⑸(pp3)(p2p4)1⑹p(p2pp)pp41312(7)(p1p3)(p2p4)解记真值赋值(p1/1,p2/1,p3/0,p4/0)为v。⑴v(p(p2p3))1(10)1。1⑵v((ppp3)((pp2)(pp4)))(110)((11)(00))11213⑶v((p1p2)p3(((p1p2)p3)p4))(11)0(((11)0)0)1。(4)v((p2p)(pp))=(11)(00)=01=1。134⑸v((pp3)(p2p4))(10)(10)0。1⑹v(p(pp3p)p2p4)1(101)101。121(7)v((p1p3)(p2p4))=(10)(10)=00=0。用真值表判断以下公式可否是永真式、永假式、可满足式。(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)pqppq(pq)p(pq)001100011100100010110100(pq)是永假式。解(1),(2),(4),(5),(7)是永真式，(6)是永假式，(3)是非永真的可满足式。指出满足以下公式的所有真值赋值。(1)(pq)(pr)p(qr(pq))(3)pr(pr)(qr)(4)p(qr)解(1)(p/0,q/0,r/0)，(p/0,q/0,r/1)，(p/0,q/1,r/0)，(p/0,q/1,r/1)，(p/1,q/0,r/1)，(p/1,q/1,r/0)，(p/1,q/1,r/1)。(2)(p/0,q/1,r/0)，(p/1,q/0,r/0)，(p/1,q/0,r/1)，(p/1,q/1,r/0)，(p/1,q/1,r/1)。(p/0,q/0,r/0)，(p/0,q/1,r/0)。(4)任取满足p(qr)的真值赋值v。若v(p)=0，则v(qr)=1v(q)=v(r)。v(p)=1v(q，v(q)v(r)若，则r)=0。，所以，满足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)。7.若公式A既不是永真式，也不是永假式，则A的每个代替实例必然既不是永真式，也不是永假式。对吗？解不对。若A是非永真的可满足式，则它的代替实例中既有永真式，也有永假式，也有非永真的可满足式。设A中出现的命题变元是p1,,pv1和v2分别是使得A为真的真值赋值和使得A为假n的真值赋值。取公式,,B,C,,CB1n1n以下：Bippv1(pi)1Cippv2(pi)1ppv1(pi)0ppv2(pi)0任取真值赋值v，v(ABp1,,,B,pn)v[p1/v(B1),,pn/v(Bn)](A)v1(A)1，1nv(ACp1,,,,Cpn)v[p1/v(C1),,pn/v(Cn)](A)v2(A)0，1n所以，A的代替实例Ap1,,pn是永真式，A的代替实例Ap1,,pn是永假式。B,,BC,,Cn1n1A自己也是A的代替实例，它是非永真的可满足式。用真值表证明以低等值式。(1)p(qr)(pq)(pr)pqrqrp(qr)pqpr(pq)(pr)0000000000110000010100000110000010000000101110111101110111100110(2)(3)(4)用等值演算证明以低等值式。(1)p(qr)q(pr)(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)(pq)p(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)(pq)p(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)pqqr012.找出与以下公式等值的尽可能简单的由{,}生成的公式。13.找出与以下公式等值的尽可能简单的由{,}生成的公式。(1)pq(rp)(2)(pqr)pqpqp解(1)pq(rp)pq(rp)(pqr)(pqp)pqr(pqr)(2)(pqr)pq(pqr)pq((pqr)pq)(3)pqp(pqp)14.设A是由{}生成的公式。证明：A是永真式当且仅当每个命题变元在A中出现偶数次。证明第一证明：若A是由{}生成的仅出现一个命题变元p的公式，则pAApA对p在A中的出现次数进行归纳。①若p在A中出现1次，即A为pp。，显然A②若p在A中出现2次，即A为pp，显然A1。③设p在A中的出现nABCpBCk和l，则nkl，次，为，在，中的出现次数分别为kn且ln。若n为偶数,则k和l的奇偶性相同，B和C等值于同一公式，A1。若n为奇数,则k和l的奇偶性不相同，B和C中一个等值于p，另一个是永真式，所以Ap1p。设在A中的出现的所有命题变元为p1,,pn，它们的出现次数分别为k1,,kn。因为AB(AB)(BA)BA，并且(AB)C((AB)C)AB1C1ABC11(A(BC))A(BC)所以满足交换律和结合律，存在由{}生成的公式B1,,Bn，使得AB1Bn，并且Bi仅出现命题变元pi，出现次数为ki，i1,,n。若k1,,kn全为偶数，则AB1Bn111。若k1,,kn中有kl1,,klm是奇数，则AB1Bnpl1plm，显然A不是永真式。15.设A是由{}A是永假式当且仅当每个命题变元在A中出现偶数次。生成的公式。证明：证明第一证明：若A是由{}生成的仅出现一个命题变元p的公式，则pAApA对p在A中的出现次数进行归纳。①若p在A中出现1次，即A为p，显然AppAAp。②若在中出现2次，即为pA0，显然。③设p在A中出现n次，A为BC，p在B，C中的出现次数分别为k和l，则n=k+l，k<n且l<n。若n为偶数,则k和l的奇偶性相同，B和C等值于同一公式，0。若n为奇数,则k和l的奇偶性不相同，B和C中一个等值于p，另一个是永假式，所以Ap0p。设在A中的出现的所有命题变元为p1n，它们的出现次数分别为1n满,,pk,,k。因为足交换律和结合律，所以存在由{}生成的公式B1,,BABBBn，使得1n，i中仅出现命题变元pi，并且出现次数为ki，i=1,。若1n全为偶数，则,nk,,kABB000k,,kn中有kl1,klm1n。若1,是奇数，则AB1Bnpl1plm，显然A不是永假式。北京、上海、天津、广州四市乒乓球队比赛，三个观众猜想比赛结果。甲说：“天津第一，上海第二。”乙说：“天津第二，广州第三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实质名次怎样排列？解用字母表示命题以下：p2：北京第二，q2：上海第二，r1：天津第一，r2：天津第二，s3：广州第三，s4：广州第四。由已知条件列出以下方程：甲猜对了一半：r12r2324，乙猜对了一半：，丙猜对了一半：；每个城市只能得一个名次：r1r2=0ss=0；34没有并列名次：p2q=0，pr2=0r2q=022，2。解以上8个方程组成的方程组。r)(rq)=00=0，r=r21=r2(r1q)=(r222212ss=0s=0s=0p将r2=0代入r2s=1得s=1，将s=1代入得代入333344r，将42s=1得p=1p=1代入pq=0得q=0q=0代入q=1得r=1。42，将2222，将2121将p2=r1=s3=1，q2=r2=s4=0代入8个方程考据它们满足方程组。所以，天津第一，北京第二，广州第三，上海第四。某勘探队取回一块矿样，三人判断以下。甲说：“矿样不含铁，也不含铜。”乙说：“矿样不含铁，含锡。”丙说：“矿样不含锡，含铁。”已经知道，这三人中有一个是专家，一个是老队员，一个是实习队员。化验结果表示：这块矿样只含一种金属，专家的两个判断皆对，老队员的判断一对一错，实习队员的两个判断皆错。问：这三人的身分各是什么？解p:矿样含铁，q:矿样含铜，r:矿样含锡。甲说的两句话为：p，q乙说的两句话为：p，r丙说的两句话为：r，p若是用一个公式表达出这三人中有一个是专家，一个是老队员，一个是实习队员，公式会特别复杂。其实我们不用完满写出这样的公式。因为矿样只含一种金属，所以pq0，qr0，rp0。甲是实习队员，即甲说的两句话都是错的，可表示为：pq。乙是实习队员，即乙说的两句话都是错的，可表示为：pr。丙是实习队员，即丙说的两句话都是错的，可表示为：rp。甲、乙、丙三人中最少有一个是实习队员，可表示为：(pq)(pr)(rp)1因为pq0(pr)(rp)1，即pr1，p和r中恰好有一个为，，所以所以q0。甲是老队员，即甲说的话一半对一半错，可表示为：pq。乙是老队员，即乙说的话一半对一半错，可表示为：pr。丙是老队员，即丙说的话一半对一半错，可表示为：rp。甲、乙、丙三人中有奇数个老队员，可表示为：(

p

q)(

p

r)

(

r

p)1由教材上的等值式可获取(p(p01

q)p)(q

((1

prp)

r)r)

(r(qqp

p)p)又知道

q

0，所以

p

1。因为

r

p0

，所以

r

0。所以，甲说的话一半对一半错，甲是老队员。乙说的话全错，乙是实习队员。丙说的话全对，丙是专家。先用等值演算证明以低等值式，再用对偶定理得出新等值式。(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)19.设A是由{0,1,,,}生成的公式，A*与A互为对偶式。若A是永真式，则A*是永假式。若A是永假式，则A*是永真式。证明(1)设A是永真式，则A1，由对偶定理得A*0，所以A*是永假式。(2)设A是永假式，则A0，由对偶定理得A*1，所以A*是永真式。证明以下联系词会集是极小完满集。(1){0,}(2){,}(3){,,}(4){,,}{0,}证明(1)pp0p0，因为{,}是完满集，所以是完满集。任p取由{0}生成的不出现除命题变元之外的命题变元的公式A，令真值赋值v=(p/0)，则v(A)=0，而v(p)=1，所以{0}不能够定义。所以{0}不是完满集。任取由{}生成的仅出现命题变元p的公式Av=(p/1)，则v(A)=1，而v(p)=0，所以{}，令真值赋值不能够定义。所以{}不是完满集。所以{0,}是极小完满集。(2)pp1p(pp)，因为{,}是完满集，所以{,}是完满集。任取由{}生成的仅出现命题变元p的公式A，令真值赋值v=(p/0)，则v(A)=0，而v(p)=1，所以{}不能够定义。所以{}不是完满集。{}不是完满集。所以{,}是极小完满集。(3)p}p1p(pp)，因为{,}是完满集，所以{,,}是完满集。任取由{,生成的仅出现命题变元p的公式Av=(p/0)v(A)=0，而，令真值赋值，则v(p)=1，所以{,}不能够定义。所以{,}不是完满集。任取由{,}生成的仅出}现命题变元p的公式A，令真值赋值v=(p/1)，则v(A)=1v(p)=0{,，而，所以不能够定义。所以{,}不是完满集。{,}不是完满集。所以{,,}是极小完满集。(4)pp1p(pp)，因为{,}是完满集，所以{,,}是完满集。任取由{,}生成的仅出现命题变元p的公式A，令真值赋值v=(p/0)，则v(A)=0，而v(p)=1，所以{,}不能够定义。所以{,}不是完满集。任取由{,}生成的仅出}现命题变元p的公式A，令真值赋值v=(p/1)，则v(A)=1v(p)=0{,，而，所以不能够定义。所以{,}不是完满集。{,}不是完满集。所以{,,}是极小完满集。证明以下联系词会集不是完满集。(1){,,,}(2){,,}证明(1)任取由{,,,}生成的仅出现命题变元p的公式Av(p/1)，，令真值赋值则v(A)1，而v(p)0，所以{,,,}不能够定义。所以{,,,}不是完全集。(2)任取由{,,}生成的仅出现命题变元p的公式A，令真值赋值v(p/0)，则v(A)0，而v(p)1，所以{,,}不能够定义。所以{,,}不是完满集。22.二元联系词（称为“与非”）和（称为“或非”）的真值表以下。pqpqpq0011011010101100证明：{}是完满集。{}是完满集。(3)若是二元联系词且{}是完满集，则是或。证明(1)ppp,pq(pq)(pq)(pq)(pq)，因为{,}是完满集，所以{}是完满集。(2)ppp,pq(pq)(pq)(pq)(pq)，因为{,}是完满集，所以{}是完满集。(3)若00=0或11=1，则不能够由{}定义。所以，00=1且11=0。若0110，则的真值表的最后一列有偶数个1，真值表最后一列有奇数个1的不能够由{}定义。所以，01=1001=10=1是。若。若，则01=10=0，则是。23.三元联系词的真值表以下。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的主析取范式，pqr是关于p,q,r的主合取范式。可否有这样的公式，它既是主合取范式，又是主析取范式？若是有，举出一例。解有。p既是关于p的主析取范式，又是关于p的主合取范式。求以下公式的主范式，进而判断其可否永真式、永假式、可满足式。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)(pq)r的主合取范式是(pqr)(pqr)(pqr)，包含了三个极大项，所以它是非永真的可满足式。(3)pq(pq)(pq)((pq)(pq))(pq)(pq)(pq)pqpqq(pq)的主合取范式为pq，包含了一个极大项，所以它是非永真的可满足式。(4)p(pq(qr))p(pq(qr))1p(pq(qr))的主合取范式为1，不包含任何极大项，所以它是永真式。(5)(pqr)(pqr)(p(qr))(p(qr))(pp)(pqr)(qrp)(qrqr)(

p

q

r)

(p

q

r)(p

qr)

(p

q

r)

的主析取范式为

(

p

q

r)

(p

q

r)，包含了两个极小项，所以它是非永真的可满足式。(6)p

q

(

p

q)(p(pp

(qq)q(

q))(pp

((pp)q)(pq)(pq)(pq)q)的主合取范式为(pq)

q)(p

q)(p

q)

(

p

q)，包含了所有的四个极大项，所以它是永假式。用主范式证明以低等值式。(1)(pq)pq(pp)(rp)(2)(pq)(pr)pqr解(1)(pq)pq(pq)(pq)(pq)(pq)(pq(rr))(pq(rr))(p

q

r)

(p

(

qp

r))p)

(p(r

q

r)p)(

(p

qr)pp)

(r

p)p(p

r)

p

p(q

q)

(r

r)(p

q

r)

(p

qr))

(p

q

r)

(p

qr)(p

q)

pq和(p

p)

(r

p)等值于同一个关于

p,q,

r

的主析取范式(p(2)(p

qq)

r)(p

(pr)

qr))(pq)(p(p

(pqpqq)(pq(r

r)(r)r))

(pp(p

qp)(q

r)，所以，(rp)。q)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的主合取范式相同，所以，(pq)(pr)pqr。判断以下关系可否成立，并说明原由。(1)pq,p|qpq,,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,p|q。(2)真值赋值v(p/0,q/1)使得v(pq)v(pq)v(q)1，但v(p)0，所以q,pq,q|/p。(3)若真值赋值v使得v(pq)v(p2q2)v(pp)1，则v(p)v(p2)1，11121所以v(q)v(q)1，v(qq2)