離散數(shù)學(xué)考試題詳細答案

1、離散數(shù)學(xué)離散數(shù)學(xué)考試題考試題(后附詳細答案后附詳細答案)一、命題符號化（共6小題，每小題3分，共計18分）1.用命題邏輯把下列命題符號化a)假如上午不下雨，我去看電影，否則就在家里讀書或看報。設(shè)P表示命題“上午下雨”，Q表示命題“我去看電影”，R表示命題“在家里讀書”，S表示命題“在家看報”，命題符號化為：（?P?Q）?(P?R?S)b)我今天進城，除非下雨。設(shè)P表示命題“我今天進城”，Q表示命題“天下雨”，命題符號化為：?Q→P或?P

2、→Qc)僅當(dāng)你走，我將留下。設(shè)P表示命題“你走”，Q表示命題“我留下”，命題符號化為：Q→P2.用謂詞邏輯把下列命題符號化a)有些實數(shù)不是有理數(shù)設(shè)R(x)表示“x是實數(shù)”，Q(x)表示“x是有理數(shù)”，命題符號化為：?x(R(x)??Q(x))或??x(R(x)→Q(x))b)對于所有非零實數(shù)x，總存在y使得xy=1。設(shè)R(x)表示“x是實數(shù)”，E(xy)表示“x=y”f(xy)=xy命題符號化為：?x(R(x)??E(x0)→?y(R(

3、y)?E(f(xy)1))))c)f是從A到B的函數(shù)當(dāng)且僅當(dāng)對于每個a∈A存在唯一的b∈B，使得f(a)=b.設(shè)F(f)表示“f是從A到B的函數(shù)”A(x)表示“x∈A”B(x)表示“x∈B”E(xy)表示“x=y”命題符號化為：F(f)??a(A(a)→?b(B(b)??E(f(a)b)???c(S(c)??E(f(a)c)→E(ab))))二、簡答題（共6道題，共32分）1.求命題公式(P→(Q→R))?(R→(Q→P))的主析取范式

4、、主合取范式，并寫出所有成真賦值。（5分）(P→(Q→R))?(R→(Q→P))?（?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)這是主合取范式公式的所有成真賦值為000001010100101111故主析取范式為（?P??Q??

5、R??（?P??Q?R??（?P?Q??R??（P??Q??R??（P??Q?R??（P?Q?R?2.設(shè)個體域為123，求下列命題的真值（4分）a)?x?y(xy=4)b)?y?x(xy=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))→?y

6、?z(F(y)→G(z))??x?y?z((F(x)→G(x))→(F(y)→G(z)))(8)(E→?F)→?CP(9)?(E→?F)T(7)(8)I(10)E∧FT(9)E(11)ET(10)I(12)B→ECPb)證(1)?x?R(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)

7、(8)?P(c)T(5)(7)I(9)?x?P(x)EG(8)2.設(shè)R1是A上的等價關(guān)系，R2是B上的等價關(guān)系，A≠?且B≠?，關(guān)系R滿足：∈R，當(dāng)且僅當(dāng)∈R1且∈R2。試證明：R是AB上的等價關(guān)系。（10分）證任取∈AB?x∈A?y∈B?∈R1?∈R2?∈R，故R是自反的任取∈R?∈R1?∈R2?∈R1?∈R2?∈R.故R是對稱的。任取∈R∈R?∈R1?∈R2?∈R1?∈R2?(∈R1?∈R1)?(∈R2?∈R2)?R1?∈R2?∈R

8、故R是傳遞的。綜上所述R是AB上的等價關(guān)系。3.用伯恩斯坦定理證明（01]和(ab)等勢。（10分）證構(gòu)造函數(shù)f：（01]→(ab)，f(x)=顯然f是入射函數(shù)22bxa?構(gòu)造函數(shù)g:(ab)→（01]，顯然g是入射函數(shù)，abaxxg???)(故（01]和(ab)等勢。由于，所以22122221?????????????rmmmrmmmrr??22rnrs?4.設(shè)R是集合A上的等價關(guān)系，A的元素個數(shù)為n，R作為集合有s個元素，若A關(guān)于R