离散数学期末复习例题讲解 李伟生 下面先对课程考核做一些说明，然后结合考试题型讲解一些例题，供大家复习参考. 一、考核说明 考核对象：本课程考核说明适用于中央广播电视大学开放教育本科电气信息类计算机科 学与技术专业的学生。 考核依据：本考核说明是以本课程的教学大纲(2007年6月审定)和指定的参考教材 为依据制定的.本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的《离 散数学》· 考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式.其中终结性考核 采用半开卷、笔试方式，试卷满分100分. 半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课 程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考. 考试时间：90分钟， 试题类型及结构：单项选择题的分数占15%，填空题的分数占15%，公式翻译题的分 数占12%，判断说明题的分数占14%，计算题的分数占36%：证明题的分数占8%. 二、例题讲解 (一)集合论 1.单项选择题 (1)若集合A={2,a,{a,4},则下列表述正确的是0. A.{a,{a}∈B.{alsA C.(2)EAD.EA 答：B (2)若集合作{a,b,{1,2}},{1,2},则()， A.RA,且BEB.BtA,且BEA C.RA,但BED.BEA,但BtA 答：D (3)设集合年{1，a,则P()=0. A.{1,{a}B.{☑，{1}，{a} C.{☑，{1}，{ad,{1,a}D.{1},{al,1,a} 答：C (4)设集合：{1,2,3,4,5,6}上的二元关系={|a,b∈A,且a肿=8}，则R 具有的性质为()·
1 离散数学期末复习例题讲解 李伟生 下面先对课程考核做一些说明，然后结合考试题型讲解一些例题，供大家复习参考． 一、考核说明 考核对象：本课程考核说明适用于中央广播电视大学开放教育本科电气信息类计算机科 学与技术专业的学生． 考核依据：本考核说明是以本课程的教学大纲（2007 年 6 月审定）和指定的参考教材 为依据制定的．本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的《离 散数学》． 考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式．其中终结性考核 采用半开卷、笔试方式，试卷满分 100 分． 半开卷考试允许考生携带指定的一张专用 A4 纸（统一印制），考生可以将自己对全课 程学习内容的总结归纳写在这张 A4 纸上带入考场，作为答卷时参考． 考试时间：90 分钟． 试题类型及结构：单项选择题的分数占 15％，填空题的分数占 15％，公式翻译题的分 数占 12％，判断说明题的分数占 14％，计算题的分数占 36％；证明题的分数占 8％． 二、例题讲解 （一）集合论 1．单项选择题 （1）若集合 A＝{2，a，{a}，4}，则下列表述正确的是()． A．{a，{a}}AB．{a}A C．{2}AD． A 答：B （2）若集合 A={a，b，{1，2}}，B={1，2}，则（）． A．BA，且 BAB．BA，且 BA C．BA，但 BAD．BA，但 BA 答：D （3）设集合 A={1,a}，则 P(A)=()． A．{{1},{a}}B．{ ,{1},{a}} C．{ ,{1},{a},{1,a}}D．{{1},{a},{1,a}} 答：C （4）设集合 A={1，2，3，4，5，6}上的二元关系 R={ a,b a,b A,且 a+b=8}，则 R 具有的性质为（）．
A.对称的B.自反的 C.对称和传递的D.反自反和传递的 答：A (5)设集合：{1,2,3,4}上的二元关系 {,,,}, {,,,,}, 则S是R的()闭包， A.自反B.传递C.对称D.以上都不对 答：C (6)设集合：1,2,3,4,5}上的偏序关 系的哈斯图如图1所示，若A的子集正{3,4,5}， 则元素3为B的()· A.最小上界B.最大下界 C.下界D.以上答案都不对图1 答：A 2.填空题 (1)设集合A有n个元素，那么A的幂集合P(A)的元素个数为. 答：2 (2)设集合年{0,1,2}，{0,2,4}，R是A到B的二元关系， R={kx,y>x∈A且y∈B且x,y∈A∩B) 则R的集合表示式为. 答：{，，，} (3)设集合非{a,b,C,d},A上的二元关系{《a,b>,,,〈c,D},则R的 自反闭包是. 答：r(0={Ka,b>,,,,},{K1,b>,,},{K1,b,} 3.如果R和尼是A上的自反关系，判断结论：“R、RUB、⌒R是自反的”是否成 立？并说明理由
2 A．对称的 B．自反的 C．对称和传递的 D．反自反和传递的 答：A （5）设集合 A={1,2,3,4}上的二元关系 R={ 1,1 ， 2,2 ， 2,3 ， 4,4 }， S={ 1,1 ， 2,2 ， 2,3 ， 3,2 ， 4,4 }， 则 S 是 R 的（）闭包． A．自反 B．传递 C．对称 D．以上都不对 答：C （6）设集合 A={1,2,3,4,5}上的偏序关 系的哈斯图如图 1 所示,若 A 的子集 B={3,4,5}， 则元素 3 为 B 的（）． A．最小上界 B．最大下界 C．下界 D．以上答案都不对图 1 答：A 2．填空题 （1）设集合 A 有 n 个元素，那么 A 的幂集合 P(A)的元素个数为． 答：2 n （2）设集合 A={0,1,2},B={0,2,4},R 是 A 到 B 的二元关系， R ={ x, y x A且yB且x, y A B} 则 R 的集合表示式为． 答：{,,,} （3）设集合 A=｛a,b,c,d｝，A 上的二元关系 R={,,,}，则 R 的 自反闭包是． 答：r(R)={,,,}∪IA （4）设 A={1,2,3,4,5,6,7,8}，R 是 A 上的整除关系，B={2,4,6}，则集合 B 的最大元、 最小元、上界、下界依次为． 答：无、2、无、2 （5）设集合 A={1,2},B={a,b}，那么集合 A 到 B 的不同函数的个数有． 答：4 因为：f：{,},{,} {,},{,} 3．如果 R1和 R2是 A 上的自反关系，判断结论：“R1 -1、R1∪R2、R1R2 是自反的”是否成 立？并说明理由． 2 4 1 3 5
答：结论成立 因为R和R是A上的自反关系，即IcR,IcR. 由逆关系定义和IcR,得IcR; 由IcR,Ic,得LCRUR,IEROR. 所以，R、RU&、RO尼是自反的. 注：R-R是自反的吗？ 4.若偏序集,,, ,,,,,} 6.设作{0,1,2,3,4}，{Kx,>|xeA,yeA且xHK0},{Kx,y>|x∈A,yeA且 xHy≤3}，试求R,S,PS,R,S,r(0,s(0,t(ǜ，r(S,s(S,t(S. 解：⑦， {,,,,,,,,,} P0,F=0,5=S: r(0=I,s(0=0,t(0=0: r(S=SU{K2,2>,,,,,,,} 7.试证明集合等式：AU(O=(AUO(UO. 证：若x∈承U(nO,则x∈A或x∈BC, 即x∈A或x∈B且x∈A或x∈C. 即x∈AUB且x∈AUC, 即x∈=(UO(AUO, 所以AU(nOs(Un(AUO. 反之，若x∈(U励O(AUO,则x∈AUB且x∈承UC, 即x∈A或x∈B且x∈A或x∈CG 即x∈A或x∈RC, 即x∈AU(BO
3 答：结论成立． 因为 R1 和 R2 是 A 上的自反关系，即 IAR1，IAR2． 由逆关系定义和 IAR1，得 IAR1 -1； 由 IAR1，IAR2，得 IAR1∪R2，IAR1R2． 所以，R1 -1、R1∪R2、R1R2 是自反的． 注：R1-R2 是自反的吗？ 4．若偏序集，R的哈斯图如图 2 所示，则集合 A 的最大元为 a；最小元不存在． 答：错 a 是集合 A 的极大元，最大元不存在．图 2 5．设集合 A＝{a,b,{a,b}}，B={{a},{b},b}，求 （1）BA；（2）A－B；（3）AB． 解：（1）BA={a,b,{a,b}}{{a},{b},b}={b} （2）A－B={a,b,{a,b}}－{{a},{b},b}={a,{a,b}} （ 3 ） AB ＝ {a,b,{a,b}}{{a},{b},b} ＝ {,, ， ,,,,,} 6．设 A={0，1，2，3，4}，R={|xA，yA 且 x+y|xA，yA 且 x+y≤3}，试求 R，S，RS，R -1，S -1，r(R)，s(R)，t(R)，r(S)，s(S)，t(S)． 解：R=， S={,,,,,,,,,} RS=，R -1 =，S -1 =S； r(R)=IA，s(R)=，t(R)=； r(S)=S∪{，,}，s(S)=S； t(S)=S∪{，,,，,} 7．试证明集合等式：A(BC)=(AB)(AC)． 证：若 x∈A(BC)，则 x∈A 或 x∈BC， 即 x∈A 或 x∈B 且 x∈A 或 x∈C． 即 x∈AB 且 x∈AC， 即 x∈T=(AB)(AC)， 所以 A(BC)(AB)(AC)． 反之，若 x∈(AB)(AC)，则 x∈AB 且 x∈AC， 即 x∈A 或 x∈B 且 x∈A 或 x∈C， 即 x∈A 或 x∈BC， 即 x∈A(BC)， a b c f d e
所以(AUO(OCA(RnO. 因此.承U(nO=(AUn(AUO 8.设R是集合A上的对称关系和传递关系，试证明：若对HaEA,3beA,使得eR, 则R是等价关系。 证明：已知R是对称关系和传递关系，只需证明R是自反关系， ta∈A,3beA,使得eR,因为R是对称的，故∈R 又R是传递的，即当eR〈b,a>eP=eR 由元素a的任意性，知R是自反的. 所以，R是等价关系， (二)图论 1.单项选择题 (1)设图G的邻接矩阵为 00100 00011 10000 0 1001 10 1010 则G的边数为0. A.5B.6C.3D.4 答：D (2)设图=<？，D,则下列结论成立的是(O. A.deg()=21ElB.deg(v)=E c. ∑deg(v)=2ElD.∑deg()=lE 答：C (3)设有向图(a)、(b)、(c)与(dD如图3所示，则下列结论成立的是0. 图3 A.(a)是强连通的B.(b)是强连通的 C.(c)是强连通的D.(dD是强连通的
4 所以(AB)(AC)A(BC)． 因此．A(BC)=(AB)(AC)． 8．设 R 是集合 A 上的对称关系和传递关系，试证明：若对aA，bA，使得R， 则 R 是等价关系． 证明：已知 R 是对称关系和传递关系，只需证明 R 是自反关系． aA，bA，使得R，因为 R 是对称的，故R； 又 R 是传递的，即当R，RR； 由元素 a 的任意性，知 R 是自反的． 所以，R 是等价关系． （二）图论 1．单项选择题 （1）设图 G 的邻接矩阵为 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 则 G 的边数为()． A．5B．6C．3D．4 答：D （2）设图 G＝，则下列结论成立的是()． A．deg(V)=2EB．deg(V)=E C． v E v V deg( ) = 2 D． v E v V = deg( ) 答：C （3）设有向图（a）、（b）、（c）与（d）如图 3 所示，则下列结论成立的是()． 图 3 A．（a）是强连通的 B．（b）是强连通的 C．（c）是强连通的 D．（d）是强连通的 (a) (b) (c) (d) a g b d f c e
答：A (4)给定无向图G如图4所示，下面给出的结点集 子集中，不是点割集的为()， A.(b,dB.d C.(a,cD.g,e) 答：A图4 (5)图G如图5所示，以下说法正确的是0. A.{(a,d}是割边 B.{(a,d}是边割集 c.{(d,e)}是边割集 D.{(a,d,(a,c}是边割集 答：C图5 (6)设G是连通平面图，有v个结点，e条边，r个面，则=O. A.e-v+2B.v+e-2C.e-v-2D.e+v+2 答：A 2.填空题 (1)已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 答：15(1×1+2x2+3×3+4×4)/2 (2)设无向图G=<?D是汉密尔顿图，则V的任意非空子集K,都有 ≤g. 答：W(G) (3)设无向图G为欧拉图，则图G连通且· 答：每个结点的度数为偶数 (4)设图G=<VB,其中=n,=m.则图G是树当且仅当G是连通的，且脏。 答：r1 (5)连通无向图G有6个顶点9条边，从G中删去条边才有可能得到G的一棵生成树 2 答：4 (6)给定一个序列集合{1,01,10,11,001,000}，若去掉其中的元素，则该序列集 合构成前缀码. e 答：1 es 3.给定图G(如图6所示)： e es (1)试判断它们是否为欧拉图？并说明理由. e3 图6
5 答：A （4）给定无向图 G 如图 4 所示，下面给出的结点集 子集中，不是点割集的为（）． A．{b,d}B．{d} C．{a,c}D．{g,e} 答：A 图 4 （5）图 G 如图 5 所示，以下说法正确的是()． A．{(a,d)}是割边 B．{(a,d)}是边割集 C．{(d,e)}是边割集 D．{(a,d),(a,c)}是边割集 答：C 图 5 （6）设 G 是连通平面图，有 v 个结点，e 条边，r 个面，则 r=()． A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋2 答：A 2．填空题 （1）已知图 G 中有 1 个 1 度结点，2 个 2 度结点，3 个 3 度结点，4 个 4 度结点，则 G 的边数是． 答：15（11+22+33+44）/2 （2）设无向图 G＝是汉密尔顿图，则 V 的任意非空子集 V1，都有 V1． 答：W（G-V1） （3）设无向图 G 为欧拉图，则图 G 连通且． 答：每个结点的度数为偶数 （4）设图 G=V,E，其中V=n,E=m．则图 G 是树当且仅当 G 是连通的，且 m=． 答：n-1 （5）连通无向图 G 有 6 个顶点 9 条边，从 G 中删去条边才有可能得到 G 的一棵生成树 T． 答：4 （6）给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素，则该序列集 合构成前缀码． 答：1 3．给定图 G（如图 6 所示）: （1）试判断它们是否为欧拉图？并说明理由． v1 v2 v4 v3 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 图 6 a b c d f e
(2)若是欧拉图，请写出一条欧拉回路 答：(1)图G是欧拉图，因为图G是连通图且每个结 点的度数是偶数， (2)欧拉回路为：evzevsenesvse%aWa 注意：回路是不惟一 4.试判断“设G是一个有5个结点、10条边的连通图，则G为平面图”是否正确，为 什么？ 答：错误。 因为它不满足定理4.3.3，即“设G是一个有v个结点e条边的连通简单平面图，若v≥3， 则e≤3-6.” 5.设图G=<,B,其中{a,,a,a,}, {(a,a),(,a),（,a),(a,),(,)} (1)试给出G的图形表示；(2)求G的邻接矩阵： (3)求出每个结点的度数：(4)画出其补图的图形 解：(1)图G是无向图，图形如图7所示： as 0 图7 (2)图G的邻接矩阵如下： 「01100 10011 A(G)=10000 01001 01010 (3)结点a,a,a,a,的度数分别为：2,3,1,2,2. (4)图G的补图的如图8所示： a
6 （2）若是欧拉图，请写出一条欧拉回路． 答：（1）图 G 是欧拉图，因为图 G 是连通图且每个结 点的度数是偶数． （2）欧拉回路为：v1e1v2e2v3e3v4e5v5e7v2e8v6e6v4e4v1 注意：回路是不惟一 4．试判断“设 G 是一个有 5 个结点、10 条边的连通图，则 G 为平面图”是否正确，为 什么？ 答：错误． 因为它不满足定理4.3.3，即“设G是一个有v个结点e条边的连通简单平面图，若v≥3， 则 e≤3v-6．” 5．设图 G=V，E，其中 V=a1,a2,a3,a4,a5, E=(a1,a2)，(a2,a4)，(a3,a1)，(a4,a5)，(a5,a2) （1）试给出 G 的图形表示；（2）求 G 的邻接矩阵； （3）求出每个结点的度数；（4）画出其补图的图形． 解：（1）图 G 是无向图，图形如图 7 所示： 图 7 （2）图 G 的邻接矩阵如下： = 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 A(G) （3）结点 a1,a2,a3,a4,a5 的度数分别为：2，3，1，2，2． （4）图 G 的补图的如图 8 所示： a1 a2 a3 a4 a5 a1 a2 a3 a4 a5 a1 a2 a3 a4 a5
图8 6 图 GV,E ,其中 Va,b,c,d,e,f, {(a,b),(a,c,(a,e,(b,d山，(b,e,(c,e,(de,(d,f,(e,)},对应边的权值依次为5， 2,1,2,6,1,9,3及8. (1)画出G的图形： (2)写出G的邻接矩阵： a 5 b (3)求出G权最小的生成树及其权值. 解：(1)G的图形如图9所示： 2 6 (2)邻接矩阵： 011010 100110 100010 图9 010011 111101 000 110 (3)粗线表示最小的生成树（见图10）： 最小的生成树的权为：1+1+5+2+3=12.图10 7.设有一组权为2,3,6,9,13,15，试 (1)画出相应的最优二叉树： (2)计算它们的权值， 解：最优二叉树如图11所示： 48 20 28 11 8 0 95 5 13 0 6 0 3 >
7 图 8 6 ． 图 G= ， 其 中 V={a,b,c,d,e,f} ， E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)}，对应边的权值依次为 5， 2，1，2，6，1，9，3 及 8． （1）画出 G 的图形； （2）写出 G 的邻接矩阵； （3）求出 G 权最小的生成树及其权值． 解：（1）G 的图形如图 9 所示： （2）邻接矩阵： 0 0 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 图 9 （3）粗线表示最小的生成树（见图 10）： 最小的生成树的权为：1+1+5+2+3=12．图 10 7．设有一组权为 2,3,6,9,13,15,试 （1）画出相应的最优二叉树； （2）计算它们的权值． 解：最优二叉树如图 11 所示： c a b e d f 1 5 2 2 6 1 9 3 8 c a b e d f 1 5 2 2 6 1 9 3 8 2 3 9 13 5 6 11 15 20 48 28
图11 权值：2×4+3×4+6×3+9×2+13×2+15×2 =8+12+18+18+26+30=112 8.设G是一个n阶无向简单图，n是大于等于2的奇数.证明图G与它的补图G中的 奇数度顶点个数相等， 证明：设G=,G=.则E'是由n阶无向完全图K的边删去E所得 到的.所以对于任意结点u∈V,u在G和G中的度数之和等于u在K,中的度数.由于n 是大于等于2的奇数，从而K,的每个结点都是偶数度的(n-1(≥2)度)，于是若u∈V在 G中是奇数度结点，则它在G中也是奇数度结点.故图G与它的补图G中的奇数度结点个 数相等 9.设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧 拉图. 证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数 又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点.因此 只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图. 散最少要加条边到图G才能使其成为欧拉图 (三)数理逻辑 1.单项选择题 (1)下列命题公式是等价公式的为0. A.P队=VB.A→(B→0台7A→(A→ C.Q→（台(Rv)D.(AA台B 答：B因为A→(B→A)台A→(vA)台N(BA0 台AN()台v(A→台A→(A→ (2)下列公式0为重言式. A.(Rv(PA0)→B.(B→()→(A()】 C.ABAD.(P→(Q→P))(P→(P0) 答：D因为(P→(Q→P乃)-v(w乃)=1 (P→(P→0)台v(Rv0)台1
8 图 11 权值：24+34+63+92+132+152 =8+12+18+18+26+30=112 8．设 G 是一个 n 阶无向简单图，n 是大于等于 2 的奇数．证明图 G 与它的补图 G 中的 奇数度顶点个数相等． 证明：设 G V E = , ，G V E = , ．则 E 是由 n 阶无向完全图 K n 的边删去 E 所得 到的．所以对于任意结点 u V ，u 在 G 和 G 中的度数之和等于 u 在 K n 中的度数．由于 n 是大于等于 2 的奇数，从而 K n 的每个结点都是偶数度的（ n − 1 ( 2) 度），于是若 u V 在 G 中是奇数度结点，则它在 G 中也是奇数度结点．故图 G 与它的补图 G 中的奇数度结点个 数相等． 9．设连通图 G 有 k 个奇数度的结点，证明在图 G 中至少要添加 2 k 条边才能使其成为欧 拉图． 证明：由定理 3.1.2，任何图中度数为奇数的结点必是偶数，可知 k 是偶数． 又根据定理 4.1.1 的推论，图 G 是欧拉图的充分必要条件是图 G 不含奇数度结点．因此 只要在每对奇数度结点之间各加一条边，使图 G 的所有结点的度数变为偶数，成为欧拉图． 故最少要加 2 k 条边到图 G 才能使其成为欧拉图． （三）数理逻辑 1．单项选择题 （1）下列命题公式是等价公式的为()． A．PQPQB．A→(B→A)A→(A→B) C．Q→(PQQ(PQ)D．A(AB)B 答：B 因为 A→(B→A)A→(BA)A(BA) A(AB)A(A→B)A→(A→B) （2）下列公式()为重言式． A．(P(PQ))QB．(B→(AB))(A(AB)) C．ABABD．(P→(Q→P))(P→(P→Q)) 答：D 因为(P→(Q→P))P(QP))1 (P→(P→Q))P(PQ))1
(3)命题公式(P→0的主析取范式是0. A.PA-OB-PAOC.-PVOD.PV-O 答：A因为-(P→)白(v0白P%Q (4)设C(x):x是国家级运动员，G(x):x是健壮的，则命题“没有一个国家级运动员 不是健壮的”可符号化为) A.-Vx(C(x)A-G(x))B.Vx(C(x)>G(x)) C.x(C(x)>G(x))D.x(C(x)AG(x)) 答：D (5)表达式x(P(x,y)VQ(z)A3y(R(x,y)→zQ(z)中Vx的辖域是0. A.P(x,月B.Px,)VQ(z C.R(x,y)D.P(x,y)AR(x,y) 答：B 2.填空题 (1)命题公式P→(QVP)的真值是. 答：1因为P→(QVP)台v(wPD=1 (2)含有三个命题变项P,Q,R的命题公式P%Q的主析取范式是. 答：(P一V(PAA) 因为PA=PA(vd=(PAA)(PA) (3)设个体域D={1,2},那么谓词公式3xA(x)VyB(y)消去量词后的等值式为. 答：(A(1)VA(2))v(B(1)AB(2) (5)谓词命题公式（付x)(P(x)→Q(x)V(x,))中的约束变元为. 答：x 3.请将语句翻译成命题公式： (1)今天不是天晴 (2)你去听课，他也去听课。 (3)如果天下雪，则我明天就不去市里 (4)尽管他参加了考试，但他没有通过考试。 解：(1)设P今天是天晴： 命题公式为：一P (2)设P你去听课，他去听课： 命题公式为：PAQ. (3)设P天下雪，我明天去市里： 命题公式为：P→Q. 9
9 （3）命题公式(P→Q)的主析取范式是()． A． P Q B P Q C．P Q D． P Q 答：A 因为(P→Q)(PQ)PQ （4）设 C(x):x 是国家级运动员，G(x):x 是健壮的，则命题“没有一个国家级运动员 不是健壮的”可符号化为() A． x(C(x) G(x)) B． x(C(x) → G(x)) C． x(C(x) → G(x)) D． x(C(x) G(x)) 答：D （5）表达式 x(P(x, y) Q(z)) y(R(x, y) → zQ(z)) 中 x 的辖域是()． A．P(x,y)B．P(x,y)Q(z) C．R(x,y)D．P(x,y)R(x,y) 答：B 2．填空题 （1）命题公式 P Q P → ( ) 的真值是． 答：1 因为 P Q P → ( ) P(QP)1 （2）含有三个命题变项 P，Q，R 的命题公式 PQ 的主析取范式是． 答：(PQR)(PQR) 因为 PQPQ(RR)(PQR)(PQR) （3）设个体域 D＝{1,2},那么谓词公式 xA(x) yB(y) 消去量词后的等值式为． 答：(A(1)A(2))(B(1)B(2)) （5）谓词命题公式(x)(P(x)→Q(x)∨R(x，y))中的约束变元为． 答：x 3．请将语句翻译成命题公式： （1）今天不是天晴． （2）你去听课，他也去听课． （3）如果天下雪，则我明天就不去市里． （4）尽管他参加了考试，但他没有通过考试． 解：（1）设 P：今天是天晴； 命题公式为：P． （2）设 P：你去听课，Q：他去听课： 命题公式为：PQ． （3）设 P：天下雪，Q：我明天去市里； 命题公式为：P→Q．
(4)设P他参加了考试，：他没有通过考试： 命题公式为：PQ. 4.请将语句翻译成谓词公式： (1)所有人都不去上课。 (2)有人不去工作. 解：(1)设P(x):x是人，Q(x):x去上课. 谓词公式为：（付x)(P(x)→Q(x)). (2)设P(x):x是人，Q():x去工作， 谓词公式为：（臼x)(P(xA7Q(x). 5.判断下列各题正误，并说明理由 (1)公式(0→P乃A(P→w0→VR为永真式. (2)求命题公式(P%A(一Pv0的真值表，并判断它的类型. 解：(1)该公式是永真式 因为(QAR)→P)A(P→QVR)←→PVR (OVRVP)A(PVOVR)PVR 台PVRv(-QAQ))PVR 91 (2)作真值表 P- (PA)Λ(V) ΛQ Q 0 1 0 0 1 0 0 1 0 1 0 0 所以，该公式为永假式。 6.判断下列各题正误，并说明理由. (1)公式xP(x)→（白G(x,y)→xP(x)》是逻辑有效式（永真式）. (2)下面的推理是否正确，请给予说明， ①P(a)p ②(Hx)P(x)S① 解：(1)该公式是永真式 因为xP(x)→(yG(x,y)→xP(x)=xP(x)V(vG(x,y)VxP(x) 台xPx)V-3yG(x,y)VxP(x)台1 10
10 （4）设 P：他参加了考试，Q：他没有通过考试； 命题公式为：PQ． 4．请将语句翻译成谓词公式： （1）所有人都不去上课． （2）有人不去工作． 解：（1）设 P(x)：x 是人，Q(x)：x 去上课． 谓词公式为：(x)(P(x)→┐Q(x))． （2）设 P(x)：x 是人，Q(x)：x 去工作， 谓词公式为：(x)(P(x)┐Q(x))． 5．判断下列各题正误，并说明理由． （1）公式((QR)→P)(P→QR)PR 为永真式． （2）求命题公式(PQ)(PR)的真值表，并判断它的类型. 解：（1）该公式是永真式． 因为 ((Q R) → P) (P → Q R) P R (Q R P) (P Q R) P R P R (Q Q) P R 1 （2）作真值表 P Q P Q P Q P Q (PQ)(PQ) 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 所以，该公式为永假式． 6．判断下列各题正误，并说明理由． （1）公式 xP(x) → (yG(x, y) → xP(x)) 是逻辑有效式(永真式)． （2）下面的推理是否正确，请给予说明． ①P（a）P ②（x）P（x）US① 解：（1）该公式是永真式． 因为 xP(x) → (yG(x, y) → xP(x)) xP(x) (yG(x, y) xP(x)) x P(x) yG(x, y) x P(x) 1