a 离散数学考试题 (后附详细答案 ) 一、命题符号化（共6 小题，每小题3 分，共计 18 分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。b)我今天进城，除非下雨。c)仅当你走，我将留下。2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y 使得 xy=1。c)f 是从 A 到 B 的函数当且仅当对于每个a∈A 存在唯一的b∈B，使得 f(a)=b. 二、简答题（共6 道题，共 32 分）1.求命题公式 (P→(Q→R))(R→(Q→P)) 的主析取范式、主合取范式，并写出所有成真赋值。（5 分）2.设个体域为 {1,2,3}，求下列命题的真值（4 分）a)x y(x+y=4) b)yx (x+y=4)3.求x(F(x) →G(x)) →(xF(x) → xG(x)) 的前束范式。 （ 4 分）4.判断下面命题的真假，并说明原因。（每小题 2 分，共 4 分）a)（AB）－ C=(A-B)(A-C) b)若 f 是从集合 A 到集合 B 的入射函数，则|A| ≤|B|5.设 A 是有穷集， |A|=5 ，问（每小题2 分，共 4 分）a)A上有多少种不同的等价关系？b)从 A 到 A 的不同双射函数有多少个？6.设有偏序集
，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5 分)f g d e b c 图 1 7.已知有限集S={a 1,a 2, ⋯,a n},N为自然数集合，R 为实数集合，求下列集合的基数S;P(S);N,Nn;P(N);R,R × R,{o,1}N（写出即可） (6 分)三、证明题（共3 小题，共计 40 分）1.使用构造性证明，证明下面推理的有效性。（每小题 5 分，共 10 分）a)A→(B∧C),(E →F) →C, B → (A∧S)B→E b)x(P(x) →Q(x)), x(Q(x) ∨R(x)) ， xR(x) xP(x) 2.设 R1 是 A 上的等价关系，R2 是 B 上的等价关系，A ≠且 B≠，关系R 满足：<,>∈R，当且仅当 < x 1, x 2>∈R1且∈R2。试证明： R 是 A×B 上的等价关系。（ 10 分）3.用伯恩斯坦定理证明（0,1] 和(a,b)等势。（10 分）4.设 R 是集合 A 上的等价关系， A 的元素个数为n，R 作为集合有s 个元素，若 A 关于 R的商集 A/R 有 r 个元素，证明：rs≥n2。（10 分）四、应用题（ 10 分）在一个道路上连接有8 个城市，分别标记为a,b,c,d,e,f,g,h。城市之间的直接连接的道路是单向的，有 a→b, a→c,b →g,g →b,c →f,f → e,b →d...
