1/5北京化工大学试卷2004.6离散数学（参考答案）一、填空题（共10分，每小题2分）1.xF(x)→yG(y,z)的前束范式是xy(F(x)→yG(y,z))。2.(p→q)∨p是（永真/永假/可满足）永真式。3.设全集E={1,2,3,4,5,6}，其子集A={1,4},B={1,2,5}，则A∩~B={4}。4.设集合M={a,b,c,d,e}，则M上一共有52个不同的等价关系。5.设f：N×N→N，f(
)=x+y+1，令A={|x,y∈N且f()=3}，则A的列举法表示为A={<1,1>,<2,0>,<0,2>}。二、判断题（共10分，每小题2分，正确的在题号前打，错误的在题号前打×）(√)1.设X={a,b,c,d}，Y={1,2,3}，f={,,}，则f是从X到Y的二元关系，但不是从X到Y的函数。(×)2.已知A和B为两个集合，且AB，则AB一定为假。(√)3.设p,q,r,s为命题公式，如果pq且rs，则p∧rq∧s。(×)4.一个谓词公式，如果量词均出现在全式的开头，则称该谓词公式为前束范式。(√)5.设R是A上的自反关系，且当∈R和∈R时，必有∈R，则R是A上的等价关系。三、选择题（共10分，每小题2分）1.设个体域为整数集，P(x,y)：x+y=1，Q(x,y)：x×y>0，下列命题为真的是（A）。A、xyP(x,y)B、xyP(x,y)C、xyQ(x,y)D、xyQ(x,y)2.设R是集合A上的自反关系，则下列叙述中不成立的是（C）。A、RR-1一定是A上的自反关系B、RR-1一定是A上的对称关系C、RR-1一定是A上的传递关系2/5D、仅有A和B是正确的3.下列命题真值为真的是（A）。A、2>3当且仅当5>7B、2>3当且仅当5<7C、2+2≠4与4+4=8互为充分必要条件D、如果π无理数，则3也是无理数，反之亦然4.下列每组两个集合中相等的一组集合是（A）。A、A={3,1,1,5,5}，B={1,3,5}B、A=，B={}C、A=，B={x|x∈N且x是偶素数}D、A={1,2,}，B={1,2,{}}5.在谓词演算中，若谓词公式中含有自由变元，则不能被使用的规则是（C）。A、US规则B、UG规则C、ES规则D、EG规则四、简答及计算题（共30分，每题10分）1．采用真值表求命题公式(p∧q)∨(~p∧r)的主析取范式和主合取范式。解：求解过程（4分）pqrp∧q~p∧r(p∧q)∨(~p∧r)000000001011010000011011100000101000110101111101主析取范式（3分）：(p∧q)∨(~p∧r)m1∨m3∨m6∨m7(~p∧~q∧r)∨(~p∧q∧r)∨(p∧q∧~r)∨(p∧q∧r)主合取范式（3分）：(p∧q)∨(~p∧r)M0∨M2∨M4∨M5=(p∨q∨r)∧(p∨~q∨r)∧(~p∨q∨r)∧(~p∨q∨~r)3/52．设A={a,b,c,d,e,f}，R是A上的二元关系，其关系定义如下：R={,,,,}求最小自然数s和t，使得s,,,,}R2={,,,,}R3={,,,,}R4={,,,,}R5={,,,,}R6={,,,,}（4分）因此有：R6=IA=R0即：s=0，t=63．如图为偏序集的哈斯图。（1）给出X和≤的集合表示（6分）；（2）求该偏序集的极大元、极小元、最大元和最小元（4分）。解：X={a,b,c,d,e,f}X={,,,,,,,,}∪IX极大元e,f，极小元a，最大元不存在，最小元a五、证明题（共40分，每题10分）1．采用形式证明推理证明下式：已知：x(~P(x)Q(x))，x(Q(x)~R(x))，xR(x)结论：xP(x)解：（1）xR(x)P（2）R(c)ES（1）（3）x(Q(x)~R(x))P（4）Q(c)~R(c)US（3）（5）~Q(c)T（2）（4）fdcaeb4/5（6）x(~P(x)Q(x))P（7）~P(c)Q(c)US（6）（8）P(c)T（5）（7）（9）xP(x)EG（8）2．设A,B,C为集合，已知(A∩C)(B∩C),(A∩~C)(B∩~C),证明：AB。解：A=A∩(C∪~C)=(A∩C)∪(A∩~C)(B∩C)∪(B∩~C)=B∩(C∪~C)=B故：AB3．采用形式证明法证明下面的推理：如果周强是上海人，则他是复旦大学或中山大学的学生；如果他不想离开上海，他就不是中山大学的学生；周强是上海人并且不想离开上海，所以他是复旦大学的学生。解：令：p：周强是上海人，q：周强是复旦大学的学生，r：周强是中山大学的学生，s：周强想离开上海。（3分）前提：p(q∨r)，~s~r，p∧~s结论：q（3分）（4分）（1）p∧~sP（2）~sT（1）（3）~s~rP（4）~rT（2）（3）（5）p(q∨r)P（6）pT（1）5/5（7）q∨rT（5）（6...
