《离散数学》模拟试题
一、（每小题3分，共30分）填空题：
1．集合{1, {2}}的幂集为 。 2．某人有8件衬衫、4条裤子、5双鞋，全套衣服共有 种可能的搭配。
3．令P：明天下雨；Q：明天下雪。R：我将去学校。命题“除非明天不下雨并且不下雪，否则我将不去学校。”的符号化形式为 。 4．令F(x)：x会叫，G(x)：x会咬人，D(x)：x是狗。命题“会叫的狗未必会咬人。”符号化为 。 5．设A、B为任意命题公式，用A、B表示的命题公式基本等价关系中，等价转换式为 、蕴涵转换式为 、假言易位为 。 6．设|A|=3，则A上可定义 个不同的关系、 个不同的函数、 个不同的双射函数。
7．〈A，R〉为偏序集，其中A={1, 2, 3, 4, 6, 9, 24, 54}，R是A上的整除关系，对A的子集B={1, 2, 3}，B的极大元为 、 上界为 、上确界为 。 8．集合A={1，2，3}，IA={＜x，x＞| x∈A})为A上的恒等关系，则IA
具有 性质。 9．令S={a, b, c }，在S上定义的二元运算*如下运算表所示：
* a b c a a b c b b c a c c a b 则运算*（满足/不满足） 交换律、单位元 、零元 。
10． 设有代数系统B=＜S，*＞，其中载体S={a, b, c, d}，二元运算*定义为：
* a b c d a a b c d b b b d d c c d c d d d d d d 分别给出B的三个不同子代数的载体 、 和 。
二、（10分）设R为任意非空集合A上的关系，证明：R∪IA为R的自
反闭包，其中IA为A上的相等关系。
三、1．（6分）用公式等价转换法证明：P?(Q?R)?(P?Q)?R
2．（8分）用真值表法求公式A??(P?Q)?R的主析取范式和主合取范式。
四、A={a, b, c, d, e }，R是A上的关系，且R={〈a, b〉，〈a, c〉，〈e, d〉}，
设R*=tsr(R)，则R*为A上的等价关系。 1．（6分）给出R*的关系矩阵并画出R*的关系图； 2．（6分）写出商集A/ R*。 五、（14分）用演绎法证明下述论断的正确性。 1．(P?Q)?(R?S)，(S?T)?U ? P?U
2．(?x)(F(x)??G(x))，(?x)(G(x)?H(x)) ，(?x)?H(x)
?(?x)?F(x)
六、（10分）函数f：A→B，g：B→C，复合函数f?g：A→C。
证明：若f和g都是满射的，则f?g也是满射的。
七、（10分）设f和g都是从代数系统〈A，*〉到〈B，·〉的同态映射，“*”和“·”分别是A和B上的二元运算，且“·”是可交换和可结合的。定义函数 h：A→B h(x) =f(x)·g(x) 证明：h是〈A，*〉到〈B，·〉的同态映射。