离散数学例题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学典型例题”。
离散数学例题
一、证明对任意集合A，B，C，有 a）A-B）-C=A-（B∪C）； b）（A-B）-C=（A-C）-B；
c）（A-B）-C=（A-C）-（B-C）。
证明
a）（A-B）-C=（A∩～B）∩～C =A∩（～B∩～C）=A∩～（B∩C）=A-B∪C）
b）（A-B）-C= A∩～B∩～C = A∩～C∩～B =（A-C）-B
c）（A-C）-（B-C）
=（A∩～C）∩～（B∩～C）=（A∩～C）∩（～B∪C）
=（A∩～C∩～B）∪（A∩～C∩C）= A∩～B∩～C =（A-B）-C
二、设命题公式G =(P→Q)∨(Q∧(P→R)), 求G的主析取范式 G =(P→Q)∨(Q∧(P→R))=(P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧ R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 =(3, 4, 5, 6, 7).三、假设f和g是函数，证明f∩g也是函数。
证明
f∩g＝{| x∈dom f∧x∈dom g∧y=f（x）∧y=g（x）} ＝{| x∈dom f∩dom g∧y=f（x）=g（x）} 令h=f∩g，则
dom h={ x | x∈dom f∩dom g，f（x）=g（x）}
若y1 =y2，因为f是函数，故必有y1 ＝／f（x1），y2 ＝／f（x2），且x1 ≠x2，所以h=f∩g
是一个函数。
因为dom h存在且y1 ≠y2 时x1 ≠x2，即 h＝{| x∈ Dom h，y=h（x）=f（x）=g（x）}
四、设函数f：R→R，若x≤y＝＞f（x）≤f（y），则称函数f是单调递增的。设f和g是在R上单调递增，证明
1)若(f十g)(x)=f(x)+g(x)，则f+g是单调递增； 2)复合函数f○g是单调递增：
3)f和g的乘积不一定是单调递增。
证明
1)因为f和g是单调递增，若x≤y，则有f（x）≤f(y)，g(x)≤g(y)，(f+g)(x)=f(x)十g(x)≤f(y)+g（y）=(f十g)(y)所以f+g是单调递增。
2)若x≤y，则f(x)≤f(y)且g(x)≤ g（y），f○g（x）＝f(g(x))≤f(g(y))＝f○g(y)所以f○g是单凋递增。
3）令f(x)=g（x）=x，则f和g是单调递增，但其积函数
g*g(x)=f（x）*g（x）=x2 在R上不是单凋递增。
五、设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)},S＝{(a, b),(b, c),(b, d),(d, d)}.计算R•S, R∪S, R－ 1, S－ 1•R－ 1.R•S＝{(a, b),(c, d)}，R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－ 1＝{(a, a),(c, a),(c, b),(d, c)}, S－ 1•R－ 1＝{(b, a),(d, c)}.六、若f：A→B是双射，则f－1 ：B→A是双射。
证明
因为f：A→B是双射，则f－1 是B到A的函数。下证f－1是双射。
对任意x∈A，必存在y∈B使f(x)＝y，从而f－1(y)＝x，所以f－1 是满射。对任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B 是函数，则y1＝y2。所以f－1 是单射。综上可得，f－1 ：B→A是双射。
七、设函数g：A→B，f：B→C，则：(1)f。g是A到C的函数；
(2)对任意的x∈A，有fg(x)＝f(g(x))。
证明
(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈。所以Df。g＝A。
对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。
综上可知，f。g是A到C的函数。
(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝f。g。又因f。g是A到C的函数，则可写为 f。g(x)＝f(g(x))。
