离散数学例题
一、证明对任意集合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∪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)∪(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，即∪f g。所以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))。
