离散数学题库及答案

千里之行，始于足下。第2页/共2页精品文档推荐离散数学题库及答案数理逻辑部分

挑选、填空及推断

?下列语句别是命题的（A）。

(A)你计划考硕士研究生吗？(B)太阳系以外的星球上有生物。

(C)离散数学是计算机系的一门必修课。(D)雪是黑群的。

?命题公式P(PP)的类型是（A）

(A)永真式(B)矛盾式

(C)非永真式的可满脚式(D)析取范式

?A是重言式，这么A的否定式是(A)

A.矛盾式

B.重言式

C.可满脚式

D.别能确定

?以下命题公式中，为永假式的是(C)

A.p→(p∨q∨r)

B.(p→┐p)→┐p

C.┐(q→q)∧p

D.┐(q∨┐p)→(p∧┐p)

?命题公式P→Q的成假赋值是(D)

A.00,11

B.00,01,11

C.10,11

D.10

?谓词公式)

x

R

xP∧

?中，变元x是(B)

)

x

(

,

(y

A.自由变元

B.既是自由变元也是约束变元

C.约束变元

D.既别是自由变元也别是约束变元

?命题公式P(QQ)的类型是(A)。

(A)永真式(B)矛盾式

(C)非永真式的可满脚式(D)析取范式

?设B别含变元x，)

x→

?等值于(A)

A

(B

)

(

x

A.BxxA→?)(

B.))((BxAx∨?

C.BxxA→?)(

D.BxAx∧?)((

?下列语句中是真命题的是(D)。

A．你是杰克吗？

B．凡石头都可练成金。

C．假如2+2=4，这么雪是黑的。

D．假如1+2=4，这么雪是黑的。

?从集合分类的角度看，命题公式可分为(B)

A.永真式、矛盾式

B.永真式、可满脚式、矛盾式

C.可满脚式、矛盾式

D.永真式、可满脚式

?命题公式﹁p∨﹁q等价于(D)。

A.﹁p∨q

B.﹁(p∨q)

C.﹁p∧q

D.p→﹁q

?一具公式在等价意义下，下面写法唯一的是(D)。

(A)范式(B)析取范式(C)合取范式(D)主析取范式

?下列含有命题p，q，r的公式中，是主析取范式的是(D)。(A)(pqr)(pq)(B)(pqr)(pq)(C)(pqr)(pqr)(D)(pqr)(pqr)?设个体域是整数集合，P代表x

y((xy)(xyx))，下面描述正确的是

（C）。(A)P是真命题(B)P是假命题

(C)P是一阶逻辑公式，但别是命题(D)P别是一阶逻辑公式

?对一阶逻辑公式((,)(,))(,)xyPxyQyzxPxy??∧∧?的讲法正确的是(B).

(A)x是约束的，y是约束的，z是自由的；

(B)x是约束的，y既是约束的又是自由的，z是自由的；

(C)x是约束的，y既是约束的又是自由的，z是约束的；

(D)x是约束的，y是约束的，z是约束的；

?n个命题变元可产生(D)个互别等价的布尔小项。

(A)n(B)n2(C)2n(D)2n

?命题“没有别犯错误的人”符号化为（D）。

设xxM：)(是人，xxP：)(犯错误。

(A)))()((xPxMx∧?(B))))()(((xPxMx?→??

(C))))()(((xPxMx∧??(D))))()(((xPxMx?∧??

?下列命题公式等值的是（C）

B

BAAQPQQPQBAABAAQ

PQP),()D(),()C()(),()B(,)A(∧∨?∨∨?∨→→→?→→∨?∧??给定命题公式：)(RQP∧∨，则所有也许使它成真赋值为（B），成假赋

值为（C）。

(A)111，011；000(B)111，011，100，101，110；

(C)000，010，001；(D)000，110，011，001，100。

?给定前提：RPQSQP?∨→→,,)(，则它的有效结论为：（B）。

(A)S；(B)SR→；(C)P；(D)QR→。

?命题：“所有的马都比某些牛跑得快”的符号化公式为：（C）。

假设：)(xH：x是马；)(xC：x是牛；),(yxF：x比y跑得快。

(A)))),()(()((yxFyCyxHx∧?∧?；(B)))),()(()((yxFyCyxHx→?→?；

(C)))),()(()((yxFyCyxHx∧?→?；(D)))),()(()((yxFyCxHxy∧→??。?设P：a是偶数，Q：b是偶数.R：a+b是偶数，则命题“若a是偶数，b是

偶数，则

a+

b也是偶数”符号化为(C)．

(A)P∧Q∧R(B)P∧Q?R(C)P∨Q→R(D)P∧Q→R

?表达式))(),(())(),((zzQyxRyzQyxPx?→?∧∨?中x?的辖域是(B)．

(A)P(x,y)(B)P(x,y)

Q(z)(C)R(x,y)(D)P(x,y)R(x,y)

?推断一具语句是否为命题，首先要看它是否为陈述句，然后再看它是否有唯

一的真值。

?命题公式(P∨Q)→R的只含联结词?和∧的等值式为：

))((RQP?∧?∧???。?BABA?∧→)(为假言推理规则。

?在一阶逻辑中符号化命题“有会讲话的机器人。”设M(x):x是机器人；S(x):x

是会讲话的；上述句子可符号化为：(?x)(M(x)∧S(x))。

?设p:我们爬山,q:我们划船,在命题逻辑中，命题“我们别能既爬山又划船”的符号化形式为?（p∧q）.

?设p:小王走路,q:小王歌唱,在命题逻辑中，命题“小王边走路边歌唱”的符号

化形式为（p∧q）.?量词否定等值式???)(xxA)(xAx??。

?设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都别一样高”

的符号化形式为(()()(,))xyFxFyHxy??∧→.?若含有n个命题变项的公式A是矛盾式，则A的主合取范式含2n个

极小项。

?取个体域为全体整数的集合，给出下列各公式：

(1)()()()()xyzxyz???-=(2)()()xxyx?=(3)()()(2)

xyxyy??+=

其中公式(1)的真值为真，公式(3)的真值为假。

?若含有n个命题变项的公式A是重言式，则A的主合取范式为1或T。?命题公式)

∨的所有成假赋值为000,001,010。

P∧

(R

Q

?谓词公式()()

??∨。

xPxQx

xPxxQx

?→?的前束范式为(()())

?在一阶逻辑中，将命题“没有别能表示成分数的有理数”符号化为

?))

x

G

(x

(

F

?（设)

G：x能

)

F：x是有理数；)

(x

x→

(x(x

(

)

(

G

(

??或))

∧

x?

F

x

表示成分数。）

?设个体域D＝{1,2},这么谓词公式)

xA?

∨

?消去量词后的等值式为

x

(

)

(y

yB

A(1)A(2)(B(1)B(2)).

?设P，Q是两个命题，当且仅当P，Q的真值均为1时，Q

P?的值为1。(×)?谓词公式A是q

(的代换实例，则A是重言式。(×)

→

?)

p∧

q

?重言式的主析取范式包含了该公式的所有的极小项。(√)

?命题公式A→(B→C)与(A∧B)→C等价。(√)

?。(√)

?设A，B，C为命题公式，若,

ABBC

??，则AC

?在一阶谓词公式中，同一变元符号别可以既约束浮现又自由浮现。(×)?在一阶逻辑中，公式的前束范式是唯一的。(×)

计算

?求命题公式(((p∨q)∧?p)→q)∧r的主析取范式。

答案：m1∨m3∨m5∨m7

?用等值演算法求公式(())

∨→∧?的主析取范式，并由主析取范式求主

PQRP

合取范式。

解：主析取范式：

013

(())()()()()()()()()

PQRP

PQRP

PPQPRPPQRPQRPQRPQRmmm∨→∧??∨?∨∧??∧?∨?∧?∨∧???∧?∧?∨?∧?∧∨?∧?∧∨?∧∧?∨∨

主合取范式为：24567MMMMM∧∧∧∧

?求公式（P∧Q）∨（﹁P∧R）的主析取范式，并由主析取范式求主合取范

式。

解：（P∧Q）∨（﹁P∧R）的真值表如下：

故主析取范式为：

（﹁P∧﹁Q∧R）∨（﹁P∧Q∧R）∨（P∧Q∧﹁R）∨（P∧Q∧R）

主合取范式为：

（P∨R∨Q）∧（﹁Q∨P∨R）∧（﹁P∨Q∨R）∧（﹁P∨Q∨﹁R）

?化公式))]}

x

y

yA

y

x

y

y

x→

B

∧

?

?

?为前束范

→

?

A

?

?

x

)

,

(

(

(

(

)

,

[

)

x

B

x

(y

){

,

,

(

y

式。

解：原式))]}

y

yA

x→

x

y

y

x

B

?

∧

?

?

y

?

??

?

∨

?

x

,(

[

)

(

(

A

)

,

,(

)

B

x

{

x

y

(y

,(

)

x

x→

yA

y

B

?

x

y

x

?

?

?

y

∧

?

∨

?

?

?

y

(

)

,(

(

,

A

,(

)

[

))]}

)

x

y

x

B

(y

,(

){

y

x

x→

yA

u

?

B

v

u

?

?

?

?

∧

?

v

?

?

∨

(

)

,(

(

,

w

,(

)

[

))]}

)

w

A

B

u

,(

u

){

(w

x

A

x→

y

w

?

v

u

y

∧

?

?

B

?

?

?

?

?

∨

u

)

,(

[

(

(

))]}

)

,

)

,(

,(

A

v

u

w

B

u

{w

u

x→

y

y

?

x

w

v

?

?

?

B

?

?

?

∧

?

∨

A

(

)

,(

(

,

u

,(

)

[

))]}

A

v

)

u

w

{w

u

,(

B

（或))]}

v

u

x?

y

y

∧

x

w

?

?

?）

B

?

?

?

∧

?

∨

A

(

)

[

(

,

u

,(

)

)

,(

,(

A

v

u

w

{w

u

B

证明

?构造下面推理的证明：

任何自然数基本上整数；存在着自然数。因此存在着整数。个体域为实数集合R。证明：先将原子命题符号化：设()

Gx：x为整数。则

Fx：x为自然数，()

前提：(()())

xFx

?

xFxGx

?→，()

结论：()

xGx

?

①()

?前提引入

xFx

②()

Fc①ES规则

③(()())

?→前提引入

xFxGx

④()()

→③US规则

Fc

Gc

⑤()

Gc②④假言推理

⑥()

?⑤EG规则

xGx

?用自然推理系统中，证明下列推理：

(?x)(A(x)→B(x))?((?x)A(x)→(?x)B(x))

证明：

①(?x)A(x)附加前提引入

②A(c)①-

?

③(?x)(A(x)→B(x))前提引入

④A(c)→B(c)③-

?

⑤B(c)②④假言推理

?

⑥(?x)B(x)⑤+

⑦(?x)A(x)→(?x)B(x)①⑥CP规则

因此(?x)(A(x)→B(x))?((?x)A(x)→(?x)B(x))

?推断下面推理是否正确，并证明你的结论。

假如他是计算机系本科生或者是计算机系研究生，这么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，这么他就会编程序。所以假如他是计算机系本科生，这么他就会编程序。请用命题逻辑推理办法，证明该推理的有效结论。

证明：令p：他是计算机系本科生

q：他是计算机系研究生

r：他学过DELPHI语言

s:他学过C++语言

t:他会编程序

前提：(p∨q)→(r∧s),(r∨s)→t

结论：p→t

证①p附加前提

②p∨q①附加律

③(p∨q)→(r∧s)前提引入

④r∧s②③假言推理

⑤r④化简律

⑥r∨s⑤附加律

⑦(r∨s)→t前提引入

⑧t⑤⑥假言推理

?在自然推理系统P中构造下面推理的证明：

前提：qprqp,),(→→

结论：sr∨

证明：○

1)(rqp→→前提引入○

2p前提引入○

3rq→○1○2假言推理○

4q前提引入○

5r○3○4假言推理○

6sr∨○5附加律?推断下面推理是否正确，并证明你的结论。

假如小王今天家里有事，则他不可能来开会。假如小张今天看到小王，则小王今天来开会了。小张今天看到小王。因此小王今天家里没事。

解：

设p:小王今天家里有事，q:小王来开会，r:小张今天看到小王

本题推理的形式结构是：

前提：pq→?,rq→,r

结论：p?

证明：1.rq→前提引入

2.r前