文档库

最新最全的文档下载
当前位置:文档库 > 华东交大 离散数学试卷四试题与答案

华东交大 离散数学试卷四试题与答案

华东交大试卷四试题与答案

一、

填空 10% (每小题 2分)

1、 若P ,Q ,为两命题,Q P →真值为0 当且仅当 。

2、 命题“对于任意给定的正实数,都存在比它大的实数”令F(x):x 为实数,

y x y x L >:),(则命题的逻辑谓词公式为 。

3、 谓词合式公式)()(x xQ x xP ?→?的前束范式为 。

4、 将量词辖域中出现的 和指导变元交换为另一变元符号,公式其余

的部分不变,这种方法称为换名规则。

5、 某人有三个儿子,组成集合A={S 1,S 2,S 3},在A 上的兄弟关系具有 性质。

二、 选择 25% (每小题 2.5分)

1、 下列语句是命题的有( )。

A 、 明年中秋节的晚上是晴天;

B 、0>+

y x ;

C 、0>xy 当且仅当x 和y 都大于0;

D 、我正在说谎。

2、 下列各命题中真值为真的命题有( )。

A 、 2+2=4当且仅当3是奇数;

B 、2+2=4当且仅当3不是奇数;

C 、2+2≠4当且仅当3是奇数;

D 、2+2≠4当且仅当3不是奇数;

3、 下列符号串是合式公式的有( )

A 、Q P ?;

B 、Q P P ∨?;

C 、)()(Q P Q P ?∨∧∨?;

D 、)(Q P ??。 4、 下列等价式成立的有( )。

A 、P Q Q P ?→??→;

B 、R R P P ?∧∨)(;

C 、 Q Q P P ?→∧)(;

D 、R Q P R Q P →∧?→→)()(。 5、 若n A A A 21,和B 为wff ,且B A A A n ?∧∧∧ 21则( )。 A 、称n A A A ∧∧∧ 21为B 的前件; B 、称B 为n A A A 21,的有效结论

C 、当且仅当F B A A A n ?∧∧∧∧ 21;

D 、当且仅当F B A A A n ??∧∧∧∧ 21。

6、 A ,B 为二合式公式,且B A ?,则( )。

A 、

B A →为重言式; B 、*

*B A ?; C 、B A ?; D 、*

*B A ?;

E 、B A ?为重言式。

7、 “人总是要死的”谓词公式表示为( )。 (论域为全总个体域)M(x):x 是人;Mortal(x):x 是要死的。 A 、)()(x Mortal x M →; B 、)()(x Mortal x M ∧ C 、))()((x Mortal x M x →?;D 、))()((x Mortal x M x ∧?

8、 公式))()((x Q x P x A →?=的解释I 为:个体域D={2},P(x):x>3, Q(x):x=4则A

的真值为( )。

A 、1;

B 、0;

C 、可满足式;

D 、无法判定。 9、 下列等价关系正确的是( )。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?; B 、)()())()((x xQ x xP x Q x P x ?∨??∨?; C 、Q x xP Q x P x →??→?)())((; D 、Q x xP Q x P x →??→?)())((。 10、 下列推理步骤错在( )。 ①))()((x G x F x →? P ②)()(y G y F → US ① ③)(x xF ? P ④)(y F ES ③ ⑤)(y G T ②④I ⑥)(x xG ?

EG ⑤

A 、②;

B 、④;

C 、⑤;

D 、⑥

三、 逻辑判断30%

1、 用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类

型。(10分)

2、 下列问题,若成立请证明,若不成立请举出反例:(10分)

(1) 已知C B C A ∨?∨,问B A ?成立吗? (2) 已知B A ???,问B A ?成立吗?

.3、一棵树T 中,有3个2度结点,一个3度结点,其余结点都是树叶。

(1)T 中有几个结点;

(2)画出具有上述度数的所有非同构的无向图。

4、如果厂方拒绝增加工资,那么罢工就不会停止,除非罢工超过一年并且工厂撤换了厂长。问:若厂方拒绝增加工资,面罢工刚开始,罢工是否能够停止。(10分)

四、计算10%

1、 设命题A 1,A 2的真值为1,A 3,A 4真值为0,求命题

)()))(((421321A A A A A A ?∨??∧→∨的真值。(5分)

2、 利用主析取范式,求公式R Q Q P ∧∧→?)(的类型。(5分)

五、谓词逻辑推理 15%

符号化语句:“有些人喜欢所有的花,但是人们不喜欢杂草,那么花不是杂草”。并推证其结论。

六、证明:(10%)

设论域D={a , b , c},求证:))()(()()(x B x A x x xB x xA ∨???∨?。

答 案

一、 填空 10%(每小题2分)

1、P 真值为1,Q 的真值为0;

2、)),()(()0,()((x y L y F y x L x F x ∧?→∧?;

3、

))()((x Q x P x ∨??;4、约束变元;5、)()(y A x xA ??,y 为D 的某些元素。

二、 选择 25%(每小题2.5分)

华东交大 离散数学试卷四试题与答案

三、 逻辑判断 30% 1、(1)等值演算法

T Q P Q P Q P P Q Q P A ???????→∧→=)()()())()((

(2)真值表法

华东交大 离散数学试卷四试题与答案

所以A 2、(1)不成立。

若取T C B C A T T B T

T A T

C ?∨?∨?∨?∨=有则

但A 与B 不一定等价,可为任意不等价的公式。 (2)成立。

证明:T B A B A ???????充要条件

即:B A A B B A B A A B A B B A A B B A T ??→∧→?∨?∧∨???∨∧?∨??→?∧?→??)()()()()

()()()(

所以T B A ??故 B A ?。

3、解:(1)设该树树叶数为t ,则树T 的结点数为t ++13,又边数 = 结点数 - 1,

∑=倍边数2)deg(i

v ,∴ )113(213123-++=?+?+?t t

即t t 269+=+,∵ 3=t ,∴ T 中7个结点。

(2)具有3个两度结点,一个3度结点,3片树叶的树(非同构的)共有以下三种:

华东交大 离散数学试卷四试题与答案

4、解:设P :厂方拒绝增加工资;Q :罢工停止;R 罢工超壶过一年;R :撤换厂长 前提:R P Q S R P ??→∧?→,,))(( 结论:Q ?

①))((Q S R P ?→∧?→ P ②P

P ③Q S R ?→∧?)( T ①②I ④R ?

P

⑤S R ?∨? T ④I ⑥)(S R ∧? T ⑤E ⑦Q ?

T ③⑥I

罢工不会停止是有效结论。 四、计算 10%

1、 解:1111)01(1

)01(1()11()))001(1(=?=?∨=?→∨=∨?∧→∨ 2、 F R Q Q P R Q Q P R Q Q P R Q Q P ?∧∧?∧?∧∧?∧?∧∧∨???∧∧→?)()()

()()(

它无成真赋值,所以为矛盾式。

五、谓词逻辑推理 15%

解:y x y x H x x G x x F x x M 喜欢是杂草是花是人:),(;:)(;:)(;

:)(

))),()(()((y x H y F y x M x →?∧? ))),()(()((y x H y G y x M x ?→?→? ))()((x G x F x ?→??

证明:

⑴))),()(()((y x H y F y x M x →?∧? P ⑵)),()(()(y a H y F y a M →?∧ ES ⑴ ⑶)(a M

T ⑵I ⑷)),()((y a H y F y →?

T ⑵I ⑸))),()(()((y x H y G y x M x ?→?→? P ⑹)),()(()(y a H y G y a M ?→?→ US ⑸ ⑺)),()((y a H y G y ?→? T ⑶⑹I ⑻))(),((y G y a H y ?→? T ⑺E ⑼),()(z a H z F → US ⑷ ⑽)(),(z G z a H ?→ US ⑻ ⑾)()(z G z F ?→ T ⑼⑽I ⑿))()((x G x F x ?→? UG ⑾

四、 证明10%

))

()(()()(())()(())()(())()(())()(())()(())()(())()(())()(())()(())()(())()(()()()(()()()(()()(x B x A x c B c A b B b A a B a A c B c A b B c A a B c A c B b A b B b A a B b A c B a A b B a A a B a A c B b B a B c A b A a A x xB x xA ∨??∨∧∨∧∨?∨∧∨∧∨∧∨∧∨∧∨∧∨∧∨∧∨?∧∧∨∧∧??∨?