离散数学考试试题(A、B卷及参考答案) 下载本文

内容发布更新时间 : 2024/12/23 13:16:03星期一 下面是文章的全部内容请认真阅读。

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

一、证明题(10分)

1) (P∧Q∧A?C)∧(A?P∨Q∨C)? (A∧(P?Q))?C。P<->Q=(p->Q)合取(Q->p)

证明: (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

??( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律 ??( A∧(P?Q))∨C ?(A∧(P?Q))?C

2) ?(P?Q)? ?P??Q。

证明:?(P?Q)??(?(P∧Q))??(?P∨?Q))??P??Q。

二、分别用真值表法和公式法求(P?(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式,并写出其相应的成真赋值和成假赋值(15分)。

主析取范式与析取范式的区别:主析取范式里每个括号里都必须有全部的变元。 主析取范式可由 析取范式经等值演算法算得。 证明:

公式法:因为(P?(Q∨R))∧(?P∨(Q?R))

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

?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律

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

∨R∨?R)

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

?M4∧M5∧M6使(非P析取Q析取R)为0所赋真值,即100,二进制

为4

?m0∨m1∨m2∨m3∨m7

所以,公式(P?(Q∨R))∧(?P∨(Q?R))为可满足式,其相应的成真赋值为000、001、010、011、111:成假赋值为:100、101、110。

1 / 6

真值表法:

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Q?R 1 0 0 1 1 0 0 1 P?(Q∨R) 1 1 1 1 0 1 1 1 ?P∨(Q?R) 1 1 1 1 1 0 0 1 (P?(Q∨R))∧(?P∨(Q?R)) 1 1 1 1 0 0 0 1 由真值表可知,公式(P?(Q∨R))∧(?P∨(Q?R))为可满足式,其相应的成真赋值为000、001、010、011、111:成假赋值为:100、101、110。 三、推理证明题(10分)

1)?P∨Q,?Q∨R,R?SP?S。

证明:

(1)P 附加前提 (2)?P∨Q P

(3)Q T(1)(2),I(析取三段论) (4)?Q∨R P

(5)R T(3)(4),I(析取三段论) (6)R?S P

(7)S T(5)(6),I(假言推理) (8)P?S CP

2) ?x(P(x)?Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x))

证明(1)?xP(x) (2)P(a)

(3)?x(P(x)?Q(y)∧R(x)) (4)P(a)?Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a)

2 / 6

(10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x))

五、已知A、B、C是三个集合,证明(A∪B)-C=(A-C)∪(B-C) (10分)

证明:因为

x∈(A∪B)-C?x∈(A∪B)-C

?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C

?(x∈A∧x?C)∨(x∈B∧x?C) ?x∈(A-C)∨x∈(B-C) ?x∈(A-C)∪(B-C)

所以,(A∪B)-C=(A-C)∪(B-C)。

八、证明整数集I上的模m同余关系R={|x?y(mod m)}是等价关系。其中,x?y(mod m)的含义是x-y可以被m整除(15分)。X(modm)=y(modm) 证明:1)?x∈I,因为(x-x)/m=0,所以x?x(mod m),即xRx。

2)?x,y∈I,若xRy,则x?y(mod m),即(x-y)/m=k∈I,所以(y - x)/m=-k∈I,所以y?x(mod m),即yRx。

3)?x,y,z∈I,若xRy,yRz,则(x-y)/m=u∈I,(y-z)/m=v∈I,于是(x-z)/m=(x-y+y-z)/m=u+v ∈I,因此xRz。

九、若f:A→B和g:B→C是双射,则(gf)=fg(10分)。

-1

-1-1

证明:

因为f、g是双射,所以gf:A→C是双射,所以gf有逆函数(gf):C→A。同理可推fg:C→A是双射。

因为∈fg?存在z(∈g?∈f)?存在z(∈f?∈g)?∈gf?∈(gf),所以(gf)=fg。

-1

-1

-1-1

-1-1

-1

-1

-1-1

-1

离散数学考试试题(B卷及答案)

一、证明题(10分)

1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T

3 / 6