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

离散数学考试试题(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再反用分配律

GAGGAGAGGAFFFFAFAF

( 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分）。

主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。

主析取范式可由析取范式经等值演算法算得。

GAGGAGAGGAFFFFAFAF

证明：

公式法：因为(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)

M∧5M∧6M使（非P析取Q析取R）为0

4

GAGGAGAGGAFFFFAFAF

所赋真值，即100，二进制为4

GAGGAGAGGAFFFFAFAF

m∨1m∨2m∨3m∨7m

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

真值表法：

P Q R Q

R

P(Q∨

R)

P∨

(Q R)

(P(Q∨R))∧(P

∨(Q R))

0 0 0

0 0 11

1

1

1

1

1

1

1

1

1

1

1

1

1

GAGGAGAGGAFFFFAFAF

GAGGAGAGGAFFFFAFAF

1

可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

三、推理证明题（10分）

1）P∨Q，Q∨R，R S P S。

证明：

(1)P附加前提

(2)P∨Q P

(3)Q T(1)(2)，I（析取三段论）

GAGGAGAGGAFFFFAFAF

(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))

GAGGAGAGGAFFFFAFAF

(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)

(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分）

证明：因为

GAGGAGAGGAFFFFAFAF

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)，

GAGGAGAGGAFFFFAFAF

即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）-1=f-1g-1（10分）。

GAGGAGAGGAFFFFAFAF

证明：

因为f、g是双射，所以gf：A→C是双射，所以gf 有逆函数（gf）-1：C→A 。同理可推f-1g -1：C→A 是双射。

因为∈f-1g-1存在z（∈g-1∈f-1）存在z（∈f ∈g）∈gf∈（gf）-1,所以（gf ）-1=f-1g -1。

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

一、证明题（10分）

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

证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧

GAGGAGAGGAFFFFAFAF