离散数学课后习题答案第二章.pdf

习题习题2-12-22-12-2（1）用谓词表达式写出下列命题。a)小张不是工人。解：设W（x）：x是工人。c：小张。则有()Wcb)他是田径或球类运动员。解：设S（x）：x是田径运动员。B（x）：x是球类运动员。h：他则有S（h）B（h）c)小莉是非常聪明和美丽的。解：设C（x）：x是聪明的。B（x）：x是美丽的。l：小莉。则有C（l）B（l）d）若m是奇数，则2m不是奇数。解：设O（x）：x是奇数。则有O（m）O（2m）。e)每一个有理数是实数。解：设R（x）：x是实数。Q（x）：x是有理数。则有（x）（Q（x）R（x）f)某些实数是有理数。解：设R（x）：x是实数。Q（x）：x是有理数。则有（x）（R（x）Q（x）g)并非每个实数都是有理数。解：设R（x）：x是实数。Q（x）：x是有理数。则有（x）（R（x）Q（x）h)直线A平行于直线B，当且仅当直线A不相交于直线B。解：设P（x，y）：直线x平行于直线y，G（x，y）：直线x相交于直线y。则有P（A，B）G（A，B）（2）找出以下十二个句子所对应的谓词表达式。a)所有的教练员是运动员。（J(x)，L(x)）解：设J(x)：x是教练员。L(x)：x是运动员。则有（x）（J（x）L（x）b)某些运动员是大学生。（S(x)）解：设S(x)：x是大学生。L(x)：x是运动员。则有（x）（L（x）S（x）c)某些教练是年老的，但是健壮的。（O(x)，V（x）解：设J(x)：x是教练员。O(x)：x是年老的。V（x）：x是健壮的。则有（x）（J（x）O（x）V（x）d)金教练既不老但也不健壮的。（j）解：设O(x)：x是年老的。V（x）：x是健壮的。j：金教练则有O（j）V（j）e)不是所有的运动员都是教练。解：设L(x)：x是运动员。J(x)：x是教练员。则（x）（L（x）J（x）f)某些大学生运动员是国家选手。（C（x）解：设S（x）：x是大学生。L（x）：x是运动员。C（x）：x是国家选手。则有（x）（S（x）L（x）C（x）g)没有一个国家选手不是健壮的。解：设C（x）：x是国家选手。V（x）：x是健壮的。则有（x）（C（x）V（x）或（x）（C（x）V（x）h)所有老的国家选手都是运动员。解：设C（x）：x是国家选手。O（x）：x是老的。L（x）：x是运动员。则有（x）（O（x）C（x）L（x）i)没有一位女同志既是国家选手又是家庭妇女。（W（x），H（x）解：设W（x）：x是女同志。H（x）：x是家庭妇女。C（x）：x是国家选手。则有（x）（W（x）C（x）H（x）j）有些女同志既是教练员又是国家选手。解：W（x）：x是女同志。J（x）：x是教练。C（x）：x是国家选手。则有（x）（W（x）J（x）C（x）k）所有运动员都钦佩某些教练。（A（x，y）解：L（x）：x是运动员。J（y）：y是教练。A(xy)：x钦佩y。则有（x）（L（x）（y）（J（y）A（x，y）l）有些大学生不钦佩运动员。解：设S（x）：x是大学生。L（x）：x是运动员。A(xy)：x钦佩y。则（x）（S（x）（y）（L（y）A(xy)）习题习题2-32-3（1）令()Px为“x是质数”；()Ex为“x是偶数”；()Ox为“x是奇数”；()Dxy为“x除尽y”，把以下各式翻译成汉语：解：a）(5)P。解：5是质数。b）(2)(2)EP。解：2是偶数且2是质数。c）()(2)()xDxEx。解：对所有的x，若x能被2除尽，则x是偶数。d）()()(6)xExDx。解：存在x，x是偶数，且x能除尽6。（即某些偶数能除尽6）e）()()(2)xExDx。解：对所有的x，若x不是偶数，则x不能被2除尽。f）()()()()()xExyDxyEy。解：对所有的x，若x是偶数，则对所有的y，若x能除尽y，则y也是偶数。g）()()()()()xPxyEyDxy。解：对所有的x，若x是质数，则存在y，y是偶数且x能除尽y（即所有质数能除尽某些偶数）。h）()()()()()xOxyPyDxy。解：对所有的x，若x是奇数，则对所有y，y是质数，则x不能除尽y（即任何奇数不能除尽任何质数）。（2）令()()()()PxLxRxyzExy分别表示“x是一个点”，“x是一条直线”，“z通过x和y”和“x=y”。符号化下面的句子。对每两个点有且仅有一条直线通过该两点。解：（x）(y)(P(x)P(y)E(xy)(!z)(L(z)R(xyz)或（x）(y)(P(x)P(y)E(xy)(z)(L(z)R(xyz)(u)(E(zu)L(u)R(xyu)（3）利用谓词公式翻译下列命题。A）如果有限个数的乘积为零，那么至少有一个因子等于零。B）对于每一个实数x，存在一个更大的实数y。C）存在实数x，y和z，使得x与y之和大于x与z之积。解：a)设N(x):x是有限个数的乘积。z(y):y为0。P(x):x的乘积为零。F(y):y是乘积中的一个因子。则有(x)(N(x)P(x)(y)(F(y)z(y)b)设R(x):x是实数。Q(xy):y大于x。故(x)(R(x)(y)(Q(xy)R(y)c)R(x):x是实数。G(xy):x大于y。则(x)(y)(z)(R(x)R(y)R(z)G(x+yxz)（4）用谓词公式写出下式：若xy，存在一个0，使得对所有x，若xa而:5a，论域是236解：a)(x)(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)，但P(1)为T，Q(1)为F，P(2)为F，Q(2)为T所以(x)(P(x)Q(x)(TF)(FT)T。b)(x)(PQ(x)R(a)(PQ(2)(PQ(3)(PQ(6)R(a)因为P为T，Q(2)为T，Q(3)为T，Q(6)为F，R(5)为F，所以(x)(PQ(x)R(a)(TT)(TT)(TF)FF(4)对下列谓词公式中的约束变元进行换名。A）()()()xyPxzQySxyB）()()()()()xPxRxQxxRxzSxz解：a)(u)(v)(P(u，z)Q(v)S(x，y)b)(u)(P(u)(R(u)Q(u)(v)R(v)(z)S(xz)(5)对下列谓词公式中的自由变元进行代入。A）()()()yAxyxBxzxzCxyzB）()()()yPxyzQxzxRxy解：a)(y)A(u，y)(x)B(x，v)(x)(z)C(x，t，z)b)(y)P(u，y)(z)Q(u，z)(x)R(x，t)习题习题2-52-5（1）考虑以下赋值，论域：12D=指定常数a和b：ab12指定函数f：指定谓词P：求以下各公式的真值。(1)f(2)f21(11)P(12)P(21)P(22)PTTFFA）()()PafaPbfbB）()()()xyPyxC）()()()()()xyPxyPfxfy解：a)P(af(a)P(bf(b)P(1f(1)P(2f(2)P(12)P(21)TFFb)(x)(y)P(yx)(x)(P(1x)P(2x)(P(11)P(21)(P(12)P(22)(TF)(TF)Tc)(x)(y)(P(xy)P(f(x)f(y)(x)(P(x1)P(f(x)f(1)(P(x2)P(f(x)f(2)(P(11)P(f(1)f(1)(P(12)P(f(1)f(2)(P(21)P(f(2)f(1)(P(22)P(f(2)f(2)(P(11)P(22)(P(12)P(21)(P(21)P(12)(P(22)P(11)(TF(TF)(FT)(FT)FFTTF（2）对以下各公式赋值后求真值。A）()()()xPxQfxaB）()()()xPfxQxfaC）()()()xPxQxaD）()()()()xyPxQxy其中，论域121Da=:fP：:Q(1)f(2)f21(1)P(2)PFT(11)Q(12)Q(21)Q(22)QTTFF解：a)(x)(P(x)Q(f(x)a)(P(1)Q(f(1)1)(P(2)Q(f(2)1)(FQ(21)(TQ(11)(FF)(TT)Tb)(x)(P(f(x)Q(xf(a)(P(f(1)Q(1f(1)(P(f(2)Q(2f(1)(TT)(FF)Tc)(x)(P(x)Q(xa)(P(1)Q(1a)(P(2)Q(2a)(P(1)Q(11)(P(2)Q(21)(FT)(TF)Fd)(x)(y)(P(x)Q(xy)(x)(P(x)(y)Q(xy)(x)(P(x)(Q(x1)Q(x2)(P(1)(Q(11)Q(12)(P(2)(Q(21)Q(22)(F(TT)(T(FF)F(3)举例说明下列各蕴含式。a)(x)(P(x)Q(a)(x)P(x)Q(a)b)(x)(P(x)Q(x)(x)Q(x)P(a)c)(x)(P(x)Q(x)(x)(Q(x)R(x)(x)(P(x)R(x)d)(x)(P(x)Q(x)(x)P(x)(x)Q(x)e)(x)(P(x)Q(x)(x)P(x)(x)Q(x)解：a）因为(x)(P(x)Q(a)(x)P(x)Q(a)故原式为(x)P(x)Q(a)(x)P(x)Q(a)设P（x）：x是大学生。Q（x）：x是运动员前提：或者不存在x，x是大学生，或者a是运动员结论：如果存在x是大学生，则必有a是运动员。b)设P（x）：x是研究生。Q（x）：x是大学生。a：论域中的某人。前提：对论域中所有x，如果x不是研究生则x是大学生。对论域中所有x，x不是大学生。结论：对论域中所有x都是研究生。故，对论域中某个a，必有结论a是研究生，即P（a）成立。c）设P（x）：x是研究生。Q（x）：x曾读过大学。R（x）：x曾读过中学。前提：对所有x，如果x是研究生，则x曾读过大学。对所有x，如果x曾读过大学，则x曾读过中学。结论：对所有x，如果x是研究生，则x曾读过中学。d）设P（x）：x是研究生。Q（x）：x是运动员。前提：对所有x，或者x是研究生，或者x是运动员。对所有x，x不是研究生结论：必存在x，x是运动员。e）设P（x）：x是研究生。Q（x）：x是运动员。前提：对所有x，或者x是研究生，或者x是运动员。对所有x，x不是研究生结论：对所有x，x是运动员。（4）求证：()()()()()()()xAxBxxAxxBx证明：(x)(A(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)（5）设论域D=a，b，c，求证(x)A(x)(x)B(x)(x)(A(x)B(x)证明：因为论域D=a，b，c，所以(x)A(x)(x)B(x)(A(a)A(b)A(c)(B(a)B(b)B(c)(A(a)B(a)(A(a)B(b)(A(a)B(c)(A(b)B(a)(A(b)B(b)(A(b)B(c)(A(c)B(a)(A(c)B(b)(A(c)B(c)(A(a)B(a)(A(b)B(b)(A(c)B(c)(x)(A(x)B(x)所以(x)A(x)(x)B(x)(x)(A(x)B(x)（7）求证(x)(y)(P(x)Q(y)(x)P(x)(y)Q(y)证明：(x)(y)(P(x)Q(y)(x)(y)(P(x)Q(y)(x)P(x)(y)Q(y)(x)P(x)(y)Q(y)(x)P(x)(y)Q(y)习题习题2-62-6（1）把以下各式化为前束范式。解：a)(x)(P(x)(y)Q(xy)(x)(P(x)(y)Q(xy)(x)(y)(P(x)Q(xy)b)(x)(y)P(xy)(z)Q(z)R(x)(x)(y)P(xy)(z)Q(z)R(x)(x)(y)P(xy)(z)Q(z)R(x)(x)(y)P(xy)(z)Q(z)R(x)(x)(y)(z)(P(xy)Q(z)R(x)c)(x)(y)(zP(xyz)(u)Q(xu)(v)Q(yv)(x)(y)(z)P(xyz)(u)Q(xu)(v)Q(yv)(x)(y)(z)P(xyz)(u)Q(xu)(v)Q(yv)(x)(y)(z)P(xyz)(u)Q(xu)(v)Q(yv)(x)(y)(z)(u)(v)(P(xyz)Q(xu)Q(yv)（2）求等价于下面wff的前束合取范式与前束析取范式。解：a)(x)P(x)(x)Q(x)(x)(P(x)Q(x)(x)P(x)(x)Q(x)(x)(P(x)Q(x)(x)(P(x)Q(x)(x)(P(x)Q(x)Tb)(x)(P(x)(y)(z)Q(xy)(z)R(yx)(x)(P(x)(y)(Q(xy)R(yx)(x)(y)(P(x)Q(xy)R(yx)前束合取范式(x)(y)(P(x)Q(xy)R(yx)(P(x)Q(xy)R(yx)(P(x)Q(xy)R(yx)(P(x)Q(xy)R(yx)(P(x)Q(xy)R(yx)(P(x)Q(xy)R(yx)(P(x)Q(xy)R(yx)前束析取范式c)(x)P(x)(x)(z)Q(xz)(z)R(xyz)(x)P(x)(x)(z)Q(xz)(z)R(xyz)(x)P(x)(x)(z)Q(xz)(u)R(xyu)(x)(P(x)(z)Q(xz)(u)R(xyu)(x)(z)(u)(P(x)Q(xz)R(xyu)前束合取范式(x)(z)(u)(P(x)Q(xz)R(xyu)(P(x)Q(xz)R(xyu)(P(x)Q(xz)R(xyu)(P(x)Q(xz)R(xyu)(P(x)Q(xz)R(xyu)(P(x)Q(xz)R(xyu)(P(x)Q(xz)R(xyu)前束析取范式d)(x)(P(x)Q(xy)(y)P(y)(z)Q(yz)(x)(P(x)Q(xy)(y)P(y)(z)Q(yz)(x)(P(x)Q(xy)(u)P(u)(z)Q(yz)(x)(u)(z)(P(x)Q(xy)(P(u)Q(yz)前束析取范式(x)(u)(z)(P(x)P(u)(P(x)Q(yz)(Q(xy)P(u)(Q(xy)Q(yz)前束合取范式习题习题2-72-7(1)证明下列各式证明：a)(x)(A(x)B(x)PA(u)B(u)US(x)B(x)PB(u)USA(u)B(u)TEA(u)TI(x)A(x)EGb)(x)(A(x)B(x)P（附加前提）(x)(A(x)B(x)TE(A(c)B(c)ESA(c)TIB(c)TI(x)A(x)EG(x)A(x)(x)B(x)P(x)B(x)TIB(c)USB(c)B(c)T矛盾c）(x)(A(x)B(x)PA(u)B(u)US(x)(C(x)B(x)PC(u)B(u)USB(u)A(u)TEC(u)A(u)TI(x)(C(x)A(x)UGd)(x)(A(x)B(x)(x)(B(x)C(x)(x)C(x)(x)A(x)(x)(B(x)C(x)PB(u)C(u)US(x)C(x)PC(u)USB(u)TI(x)(A(x)B(x)PA(u)B(u)USA(u)TI(x)A(x)UG(2)用CP规则证明。证明：a)(x)P(x)P（附加前提）P(u)US(x)(P(x)Q(x)PP(u)Q(u)USQ(u)TI(x)Q(x)UG(x)P(x)(x)Q(x)CPb)因为(x)P(x)(x)Q(x)(x)P(x)(x)Q(x)故本题就是推证(x)(P(x)Q(x)(x)P(x)(x)Q(x)(x)P(x)P（附加前提）(x)P(x)TEP(c)ES(x)(P(x)Q(x)PP(c)Q(c)ESQ(c)TI(x)Q(x)EG(x)P(x)(x)Q(x)CP(3)符号化下列命题并推证其结论。A）所有的有理数是实数，某些有理数是整数，因此某些实数是整数。B）任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。C）每个大学生不是文科