离散数学考试题(后附详细答案)一、命题符号化(共6小题,每小题3分,共计18分)1.用命题逻辑把下列命题符号化a)假如上午不下雨,我去看电影,否则就在家里读书或看报。设P表示命题“上午下雨”,Q表示命题“我去看电影”,R表示命题“在家里读书”,S表示命题“在家看报”,命题符号化为:(P⇄Q)(P⇄RS)b)我今天进城,除非下雨。设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:Q→P或P→Qc)仅当你走,我将留下。设P表示命题“你走”,Q表示命题“我留下”,命题符号化为:Q→P2.用谓词逻辑把下列命题符号化a)有些实数不是有理数设R(x)表示“x是实数”,Q(x)表示“x是有理数”,命题符号化为:x(R(x)Q(x))或x(R(x)→Q(x))b)对于所有非零实数x,总存在y使得xy=1。设R(x)表示“x是实数”,E(x,y)表示“x=y”,f(x,y)=xy,命题符号化为:x(R(x)E(x,0)→y(R(y)E(f(x,y),1))))c)f是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b.设F(f)表示“f是从A到B的函数”,A(x)表示“x∈A”,B(x)表示“x∈B”,E(x,y)表示“x=y”,命题符号化为:F(f)⇄a(A(a)→b(B(b)E(f(a),b)c(S(c)E(f(a),c)→E(a,b))))二、简答题(共6道题,共32分)1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋值。(5分)(P→(Q→R))(R→(Q→P))(PQR)(PQR)((PQR)→(PQR))((PQR)→(PQR)).((PQR)(PQR))((PQR)(PQR))(PQR)(PQR)这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为(PQR(PQR(PQR(PQR(PQR(PQR2.设个体域为{1,2,3},求下列命题的真值(4分)a)xy(x+y=4)b)yx(x+y=4)a)Tb)F3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。(4分)x(F(x)→G(x))→(xF(x)→xG(x))x(F(x)→G(x))→(yF(y)→zG(z))x(F(x)→G(x))→yz(F(y)→G(z))xyz((F(x)→G(x))→(F(y)→G(z)))4.判断下面命题的真假,并说明原因。(每小题2分,共4分)aa)(AB)-C=(A-B)(A-C)b)若f是从集合A到集合B的入射函数,则|A|≤|B|a)真命题。因为(AB)-C=(AB)~C=(A~C)(B~C)=(A-C)(B-C)b)真命题。因为如果f是从集合A到集合B的入射函数,则|ranf|=|A|,且ranfB,故命题成立。5.设A是有穷集,|A|=5,问(每小题2分,共4分)a)A上有多少种不同的等价关系?b)从A到A的不同双射函数有多少个?a)52b)5!=1206.设有偏序集
,其哈斯图如图1,求子集B={b,d,e}的最小元,最大元、极大元、极小元、上界集合、下界集合、上确界、下确界,(5分)fgdebc图1B的最小元是b,无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b}、上确界是g、下确界是b.7.已知有限集S={a1,a2,…,an},N为自然数集合,R为实数集合,求下列集合的基数S;P(S);N,Nn;P(N);R,R×R,{o,1}N(写出即可)(6分)K[S]=n;K[P(S)]=;K[N]=0,K[Nn]=0,K[P(N)]=;K[R]=,K=[R×R]=,K[{0,1}N]=三、证明题(共3小题,共计40分)1.使用构造性证明,证明下面推理的有效性。(每小题5分,共10分)a)A→(B∧C),(E→F)→C,B→(A∧S)B→Eb)x(P(x)→Q(x)),x(Q(x)∨R(x)),xR(x)xP(x)a)证(1)BP(附加条件)(2)B→(A∧S)P(3)A∧ST(1)(2)I(4)AT(3)I(5)A→(B∧C)P(6)B∧CT(4)(5)I(7)CT(6)I(8)(E→F)→CP(9)(E→F)T(7)(8)I(10)E∧FT(9)E(11)ET(10)I(12)B→ECPb)证(1)xR(x)P(2)R(c)ES(1)(3)x(Q(x)∨R(x))P(4)Q(c)∨R(c)US(3)(5)Q(c)T(2)(4)I(6)x(P(x)→Q(x))P(7)P(c)→Q(c)US(6)(8)P(c)T(5)(7)I(9)xP(x)EG(8)2.设R1是A上的等价关系,R2是B上的等价关系,A≠且B≠,关系R满足:<,>∈R,当且仅当∈R1且∈R2。试证明:R是A×B上的等价关系。(10分)证任取,∈A×...