離散數(shù)學(xué)題庫及答案

千里之行，始于足下。第2頁/共2頁精品文檔推薦離散數(shù)學(xué)題庫及答案數(shù)理邏輯部分

挑選、填空及推斷

?下列語句別是命題的（A）。

(A)你計劃考碩士研究生嗎？(B)太陽系以外的星球上有生物。

(C)離散數(shù)學(xué)是計算機系的一門必修課。(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)析取范式

?設(shè)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)?設(shè)個體域是整數(shù)集合，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個命題變元可產(chǎn)生(D)個互別等價的布爾小項。

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

?命題“沒有別犯錯誤的人”符號化為（D）。

設(shè)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?∨→→,,)(，則它的有效結(jié)論為：（B）。

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

?命題：“所有的馬都比某些牛跑得快”的符號化公式為：（C）。

假設(shè)：)(xH：x是馬；)(xC：x是牛；),(yxF：x比y跑得快。

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

(C)))),()(()((yxFyCyxHx∧?→?；(D)))),()(()((yxFyCxHxy∧→??。?設(shè)P：a是偶數(shù)，Q：b是偶數(shù).R：a+b是偶數(shù)，則命題“若a是偶數(shù)，b是

偶數(shù)，則

a+

b也是偶數(shù)”符號化為(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的只含聯(lián)結(jié)詞?和∧的等值式為：

))((RQP?∧?∧???。?BABA?∧→)(為假言推理規(guī)則。

?在一階邏輯中符號化命題“有會講話的機器人?！痹O(shè)M(x):x是機器人；S(x):x

是會講話的；上述句子可符號化為：(?x)(M(x)∧S(x))。

?設(shè)p:我們爬山,q:我們劃船,在命題邏輯中，命題“我們別能既爬山又劃船”的符號化形式為?（p∧q）.

?設(shè)p:小王走路,q:小王歌唱,在命題邏輯中，命題“小王邊走路邊歌唱”的符號

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

?設(shè)F(x):x是人，H(x,y):x與y一樣高，在一階邏輯中，命題“人都別一樣高”

的符號化形式為(()()(,))xyFxFyHxy??∧→.?若含有n個命題變項的公式A是矛盾式，則A的主合取范式含2n個

極小項。

?取個體域為全體整數(shù)的集合，給出下列各公式：

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

xyxyy??+=

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

?若含有n個命題變項的公式A是重言式，則A的主合取范式為1或T。?命題公式)

∨的所有成假賦值為000,001,010。

P∧

(R

Q

?謂詞公式()()

??∨。

xPxQx

xPxxQx

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

?在一階邏輯中，將命題“沒有別能表示成分數(shù)的有理數(shù)”符號化為

?))

x

G

(x

(

F

?（設(shè))

G：x能

)

F：x是有理數(shù)；)

(x

x→

(x(x

(

)

(

G

(

??或))

∧

x?

F

x

表示成分數(shù)。）

?設(shè)個體域D＝{1,2},這么謂詞公式)

xA?

∨

?消去量詞后的等值式為

x

(

)

(y

yB

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

?設(shè)P，Q是兩個命題，當(dāng)且僅當(dāng)P，Q的真值均為1時，Q

P?的值為1。(×)?謂詞公式A是q

(的代換實例，則A是重言式。(×)

→

?)

p∧

q

?重言式的主析取范式包含了該公式的所有的極小項。(√)

?命題公式A→(B→C)與(A∧B)→C等價。(√)

?。(√)

?設(shè)A，B，C為命題公式，若,

ABBC

??，則AC

?在一階謂詞公式中，同一變元符號別可以既約束浮現(xiàn)又自由浮現(xiàn)。(×)?在一階邏輯中，公式的前束范式是唯一的。(×)

計算

?求命題公式(((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

證明

?構(gòu)造下面推理的證明：

任何自然數(shù)基本上整數(shù)；存在著自然數(shù)。因此存在著整數(shù)。個體域為實數(shù)集合R。證明：先將原子命題符號化：設(shè)()

Gx：x為整數(shù)。則

Fx：x為自然數(shù)，()

前提：(()())

xFx

?

xFxGx

?→，()

結(jié)論：()

xGx

?

①()

?前提引入

xFx

②()

Fc①ES規(guī)則

③(()())

?→前提引入

xFxGx

④()()

→③US規(guī)則

Fc

Gc

⑤()

Gc②④假言推理

⑥()

?⑤EG規(guī)則

xGx

?用自然推理系統(tǒng)中，證明下列推理：

(?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規(guī)則

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

?推斷下面推理是否正確，并證明你的結(jié)論。

假如他是計算機系本科生或者是計算機系研究生，這么他一定學(xué)過DELPHI語言而且學(xué)過C++語言。只要他學(xué)過DELPHI語言或者C++語言，這么他就會編程序。所以假如他是計算機系本科生，這么他就會編程序。請用命題邏輯推理辦法，證明該推理的有效結(jié)論。

證明：令p：他是計算機系本科生

q：他是計算機系研究生

r：他學(xué)過DELPHI語言

s:他學(xué)過C++語言

t:他會編程序

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

結(jié)論：p→t

證①p附加前提

②p∨q①附加律

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

④r∧s②③假言推理

⑤r④化簡律

⑥r(nóng)∨s⑤附加律

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

⑧t⑤⑥假言推理

?在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：

前提：qprqp,),(→→

結(jié)論：sr∨

證明：○

1)(rqp→→前提引入○

2p前提引入○

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

4q前提引入○

5r○3○4假言推理○

6sr∨○5附加律?推斷下面推理是否正確，并證明你的結(jié)論。

假如小王今天家里有事，則他不可能來開會。假如小張今天看到小王，則小王今天來開會了。小張今天看到小王。因此小王今天家里沒事。

解：

設(shè)p:小王今天家里有事，q:小王來開會，r:小張今天看到小王

本題推理的形式結(jié)構(gòu)是：

前提：pq→?,rq→,r

結(jié)論：p?

證明：1.rq→前提引入

2.r前