离散数学试卷及答案

离散数学试题(A卷答案)

一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程) 1)P?(P∨Q∨R) 2)?(P?Q)∧Q 3)(P?Q)∧?R

解：1)重言式；2)矛盾式；3)可满足式

二、（10分）求命题公式(?P?Q)?(?Q∨P)的主析取范式，并求成真赋值。

解：(?P?Q)?(?Q∨P)?(P∨Q)?(?Q∨P)??(P∨Q)∨(?Q∨P)

?(?P∧?Q)∨?Q∨P??Q∨P?((P∨?P)∧?Q)∨(P∧?Q)∨(P∧

Q)

?(?P∧?Q)∨(P∧?Q)∨(P∧?Q)∨(P∧Q)? m0∨m2∨m3

成真赋值为：00、10、11。

三、（10分）证明下列命题的等值关系：(P∨Q)∧?(P∧Q)??(P?Q）

证明：(P∨Q)∧?(P∧Q)?(P∨Q)∧(?P∨?Q)?(P∧?Q)∨(Q∧?P)

??((?P∨Q)∧(?Q∨P))??((P?Q)∧

(Q?P))??(P?Q）

四、（10分）叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。 命题符号化为?x（F（x）?G（x）），F（a）?G（a） 证明：

（1）?x(F(x)?G(x)) P （2）F(a)?G(a) T(1)，US （3）F(a) P

（4）G(a) T(2)(3)，I

五、（10分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)

证明：∵x? A∩（B∪C）? x? A∧x?（B∪C）

? x? A∧（x?B∨x?C）

?（ x? A∧x?B）∨（x? A∧x?C） ? x?（A∩B）∨x? A∩C ? x?（A∩B）∪（A∩C）

∴A∩（B∪C）=（A∩B）∪（A∩C）

六、（10分）R为集合X上的二元关系，X={1，2，3，4，5，6，7}，R={<1，1>，<1，2>，<2，4>，<6，3>，<6，6>，<7，1>}，求:R的等价闭包R*(即包含R的最小的等价关系)。

解：R*={<1，1>，<2，2>，<3，3>，<4，4>，<5，5>，<6，6>，<7，7>，<1，2>，<2，1>，<2，4>，<4，2>，<6，3>，<3，6>，<7，1>，<1，7>，<1，4>，<4，1>，<2，7>，<7，2>，<7，4>，<4，7>}

七、（10分）设函数f：R×R?R×R，R为实数集，f定义为：f()=。1)证明f是双射。

解：1）?，∈R×R，若f()=f()，即=，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。

2）?∈R×R，由f()=，通过计算可得x=(p+q)/2；y=(p-q)/2；从而的原象存在，f是满射。

八、（10分）设G是一群，H是G的子群，x∈G，证明x●H●x-1={x●h●x-1| h∈H }是G的子群。

解：由H非空，知x●H●X-1非空。

?a，b∈x●H●x-1，即存在h1，h2∈H，使得a=x●h1●x-1，b=x●h2●x-1，有a●b-1=(x●h1●x-1)●(x●h2●x-1)-1=x●h1●x-1●（X-1）-1●h2-1●x-1=x●(h1●h2-1) ●x-1因H为G的子群，有h1●h2-1=h3∈H从而a●b-1= x●h3●x-1∈x●H●x-1。所以x●H●x-1为子群。

九、（10分）若G是连通平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m?l(n?2)l?2

证明：设G有r个面，则2m=?d(fi)?lr，2m≥lr。

i?1r由欧拉公式得，n-m+r=2，r=2-n+m。于是

十、（10分）求叶的权分别为7、8、9、12、16的最优二叉树及其权。

解：最优二叉树如图所示：

树的权为(9+12+16)×2+(7+8)×3=119

离散数学试题(B卷答案）

一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程) 1)P?(P∨Q∨R) 2)?((Q?P)∨?P)∧(P∨R) 3)((?P∨Q)?R)?((P∧Q)∨R)

解：1)重言式；2)矛盾式；3)可满足式

m?l(n?2)l?2

二、（10分）求命题公式（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)∨(?P∧?R)∨(P∨Q)∨R ?(?(P∨Q)∨(P∨Q))∨(?P∧?R)∨R ?1∨((?P∧?R)∨R)?1 ?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7

该式为重言式，全部赋值都是成真赋值。

三、（10分）证明 ((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(A∧(P?Q))?C

证明：((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(?(P∧Q∧A)∨C)∧(?A∨(P∨Q∨C))

?((?P∨?Q∨?A)∨C)∧((?A∨P∨Q)∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((?P∨?Q∨?A)∧(?A∨P∨Q))?C ?(?(?P∨?Q∨?A)∨?(?A∨P∨Q))?C ?((P∧Q∧A)∨(A∧?P∧?Q))?C ?(A∧((P∧Q)∨(?P∧?Q)))?C ?(A∧((P∨?Q)∧(?P∨Q)))?C ?(A∧((Q?P)∧(P?Q)))?C ?(A∧(P?Q))?C

四、（10分）个体域为{1，2}，求?x?y（x+y=4）的真值。

解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））

?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））

?（0∨0）∧（0∨1）?0∧1?0

五、（10分）对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B)

解：?x?P(A)∩P(B)，x?P(A)且x?P(B)，有x?A且x?B，从而x?A∩B，x?P(A∩B)，由于上述过程可逆，故P(A)∩P(B)=P(A∩B)

六、（10分）已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>}

t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>}

七、（10分）设函数f：R×R?R×R，R为实数集，f定义为：f()=。1)证明f是双射。

解：1）?，∈R×R，若f()=f()，即=，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。

2）?∈R×R，由f()=，通过计算可得x=(p+q)/2；y=(p-q)/2；从而的原象存在，f是满射。

八、（10分）是个群，u∈G，定义G中的运算“?”为a?b=a*u-1*b，对任意a，b∈G，求证：也是个群。

证明：1）?a，b∈G，a?b=a*u-1*b∈G，运算是封闭的。

2）?a，b，c∈G，（a?b）?c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a?（b?c），运算是可结合的。

3）?a∈G，设E为?的单位元，则a?E=a*u-1*E=a，得E=u，存在单位元u。 4）?a∈G，a?x=a*u-1*x=E，x=u*a-1*u，则x?a=u*a-1*u*u-1*a=u=E，每个元素都有逆元。

所以也是个群。

九、（10分）已知：D=，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的邻接距阵A和可达距阵P。

解：1）D的邻接距阵A和可达距阵P如下：

0 1 0 1 0 1 1 1 1 1

0 0 1 0 0 1 1 1 1 1 A= 0 0 0 1 1 P= 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1

十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148

本文来源：https://www.bwwdw.com/article/5n9v.html