资源描述：
《离散数学考试试题(A、B卷及答案)test7.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途离散数学考试试题（Ａ卷及答案)一、（1０分）证明Ø(A∨B）®Ø(P∨Q）,P，(B®A)∨ØＰA。 证明:(1)Ø（A∨B)®Ø(P∨Ｑ） Ｐ(2）(P∨Q)®(A∨Ｂ) T(1)，E(3）P Ｐ（4)Ａ∨Ｂ T(2)(3)，I（5)(B®A）∨ØＰ P(6)B®A T(3)(５),Ｉ(7)A∨ØB Ｔ(6)，E(8)（Ａ∨B)∧(A∨ØB) T(4)(7)，I（9)Ａ∧（B∨ØB) T(8),E（10)A T(9),E二、（10分)甲、乙、丙、丁4个人有且
2、仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的：（1)甲和乙只有一人参加；（2)丙参加，丁必参加；(3)乙或丁至多参加一人;(4)丁不参加,甲也不会参加。请推出哪两个人参加了围棋比赛。解 符号化命题,设A:甲参加了比赛；B：乙参加了比赛；C:丙参加了比赛；D：丁参加了比赛。依题意有,(1)甲和乙只有一人参加,符号化为AÅBÛ（ØA∧B）∨(Ａ∧ØB）;(２)丙参加，丁必参加,符号化为C®Ｄ；(3)乙或丁至多参加一人，符号化为Ø(B∧D);(4)丁不参加，甲也不会参加,符号化为ØD®ØA。所以原命题为:(AÅB)∧(C®D)∧（Ø(B∧Ｄ))∧（Ø
3、D®ØA)Û（(ØA∧B)∨(A∧ØB))∧(ØＣ∨D）∧(ØB∨ØD）∧(D∨ØA)Û(（ØA∧Ｂ∧ØC)∨(A∧ØB∧ØC）∨（ØＡ∧B∧Ｄ)∨(Ａ∧ØB∧Ｄ))∧((ØＢ∧D)∨(ØB∧ØＡ)∨(ØD∧ØA)）Û(Ａ∧ØＢ∧ØC∧D)∨(Ａ∧ØB∧D）∨（ØA∧B∧ØC∧ØＤ)ÛT但依据题意条件，有且仅有两人参加竞赛，故ØＡ∧B∧ØC∧ØD为F。所以只有:(Ａ∧ØＢ∧ØC∧D）∨（A∧ØB∧D)ÛT,即甲、丁参加了围棋比赛。三、(１０分）指出下列推理中,在哪些步骤上有错误？为什么?给出正确的推理形式。(1)"x（P(x)®Ｑ(x）) Ｐ个人收
4、集整理勿做商业用途(2）P(y)®Q(y) T(1），US（3）$xP（x) P(4）Ｐ(y） T（3)，EＳ(5)Q(y) T(2)(４)，I(6)$ｘQ(x） T(5)，EＧ解 (４)中ES错，因为对存在量词限制的变元x引用ES规则，只能将ｘ换成某个个体常元c,而不能将其改为自由变元。所以应将(4）中P(y)改为Ｐ(ｃ），c为个体常元。正确的推理过程为:(1)$ｘＰ(ｘ) P(2）Ｐ(ｃ) T(1)，ES(３）"x(P(x)®Ｑ(x))
5、 P(4)P（c)®Q(c） T(3），US(5)Ｑ(c） T(2)(4），I(6)$xQ(x) T（５),ＥG四、（10分）设Ａ＝{a，b，c},试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。解 设R＝｛，＜a，b>,，｝,则因为<ｂ,ｂ＞ÏR，R不自反；因为∈R，R不反自反;因为<ｂ，c>∈R,ÏR，R不对称；因为∈R,＜ｂ，a＞∈R，R不反对称；因为<ｂ,ａ>∈Ｒ，∈R，但<ｂ,ｂ>ÏR,R不传递。五、（１５分
6、)设函数ｇ:A→B，ｆ:Ｂ→C,(1）若fog是满射，则f是满射。(2)若ｆｏg是单射，则g是单射。证明 因为g：Ａ→Ｂ，f:B→Ｃ,由定理5.5知，ｆog为Ａ到C的函数。(1)对任意的z∈C,因fog是满射,则存在ｘ∈A使fｏｇ(x)＝z,即f(g(ｘ）)=z。由ｇ：A→B可知g(x）∈B,于是有y＝g（x)∈Ｂ，使得f（ｙ)=ｚ。因此，f是满射。（２）对任意的ｘ1、x2∈Ａ，若x1≠x２,则由foｇ是单射得fog(x1）≠fog(x2)，于是f(g(ｘ1））≠f(ｇ（x2）),必有g（x1）≠g(ｘ2）。所以,g是单射。六、（１5分）设R是集合A上的一个具有传递
7、和自反性质的关系，T是A上的关系，使得ÎＴÛ<ａ，b>ÎR且＜b，a>ÎR，证明Ｔ是一个等价关系。证明 因R自反，任意a∈A，有＜a，a＞∈R，由T的定义，有＜a,a＞∈T,故Ｔ自反。若＜a，b>∈T，即<ａ,ｂ>∈Ｒ且∈R，也就是＜ｂ,a>∈R且∈T，故T个人收集整理勿做商业用途对称。若＜a,b>∈T，＜ｂ,ｃ>∈T，即＜ａ,b>∈R且∈R，∈R可得∈R和<ｃ，ｂ>∈R可得＜c,a>∈Ｒ,由＜a,ｃ>∈R
