离散数学课后答案详细(3)

（b） D中特定元素=2. （c） D上函数

=x+y,(x,y)=xy.

（d） D上谓词(x,y):x=y.

说明下列各式在I下的含义，并讨论其真值. (1) xF(g(x,a),x)

(2) xy(F(f(x,a),y)→F(f(y,a),x) 答:(1) 对于任意自然数x, 都有2x=x, 真值0.

(2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0.

11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。 这里仅对(3)、(4)、(5)给出证明。

(3)取解释I 为：个体域为自然数集合N,F(x,y)：x ≤ y,在

下,xy F(x,y)为真,而xy F(x,y)也为真(只需取x =0即可),于是(3)中公

式为真,取解释 为：个体域仍为自然数集合N,而F(x,y)：x = y。此时,xyF(x,y)为真(取y为x即可),可是xyF(x,y)为假,于是(3)中公式在 下为假,这说明(3)中公式为可满足式。

(4)设I为任意一个解释,若在I下,蕴涵式前件xy F(x,y)为假,则

xyF(x,y)→yxF(x,y)为真,若前件xyF(x,y)为真,必存在I的个体域D1中的个体常项

x0,使

yF(0,y)为真,并且对于任意

x

y?,F(0,y)为真,由于有

xx0?

,F(0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以 yxF(x,y )为真,由于I的任意性,所

x

以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。 (5)取解释可满足式。

13．（1）取解释 取解释

为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在 下， x（F（x）∨G（x））为真命题。 为：个体域为自然数集合,F(x,y)：x = y在

下,(5)中公式为真,而将F(x,y)改为F(x,y)：x ＜ y,(5)中公式就为假了,所以它为

为：个体域为整数集合Z，F（x）：x为正整数，G（x）：x为为负整数，在 下， x（F（x）∨G（x））为假命题。

（2）与（3）可类似解答。

14．提示：对每个公式分别找个成真的解释，一个成假的解释。

返回

第五章 谓词逻辑等值演算与推理

本章自测答案

2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c)) (2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c)) (3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c)) (4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c))

5.提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1 . (1) 的演算如下：

xyF(x,y)

?x (F(x,3)∨F(x,4))

?(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4)) ?1∧1?1

6.乙说得对，甲错了。本题中，全称量词 的指导变元为x ，辖域为(F (x)→G(x,y)),其中F(x )与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。

7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“ ┐”。演算的第二步，在原错的基础上又用错了等值式，即 (F(x)∧(G(y)→ H(x,y))) ≠(F(x) ∧G(y)→H (x,y)) . 8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式。 (1) 没有小于负数的正数。(2) 相等的两个角未必都是对顶角。

(1) 破产令 f (x): x 小于负数，g (x): x 是正数。符合化为: ??x((F(x) ∧G(x)) ??x(G(x) →?G(x))。(2) 破产令 f (x): x 是

H (x，y) →L (x，y)) ??x?y(F(x)

角，H (x，y)： x，y 是相等的，L (x，y)： x，y 是对顶角。符合化为: ??x?y(F(x) ∧∧

12.公式的前束范式不唯一，下面每题各给出一个答案。 (1) xy (F(x)→ G(z,y)); (2) xt (x,y) → G(x,t,z)); (3) (4) (5)

(F(

F(y) ∧H (x，y) ∧?L (x，y)) ??x(F(x) ∧(?y(F(y) ∧F(y) ∧H (x，y) ∧?L (x，y)))。

x4 ((F(

((F(,

)→G()→(F(

,y) →G(,

,y))∧(G(,y) →F(4,y)));

,

)));

x

)) → (H (

,

) → L())).

) → ┐G (

13.(1)xy(F(x) ∧G(y) ∧H(x ,y)),其中，F(x):x是汽车，G(y)：y是火车，H(x，y)：x比y跑的快； (2)xy(F(x) ∧G(y)→H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (3)xy(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (4)xy(F(x) ∧G(y) → ┐H(x ,y)),其中，F(x):x是飞机，G(y)：y是汽车，H(x，y)：x比y慢； 14.(1)对F(x) → xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式。 F(x) → xG(x) <=> x(F(y)→G(x))

因为量词辖域(F(y)→G(x))中，除x外还有自由出现的y，所以不能使用EI规则。

(2)对 x F(x) → y G(y)也应先化成前束范式才能消去量词，其前束范式为 x y(F(x) →G(y)),要消去量词，既要使用UI规则，又要使用EI规则。

(3)在自然推理系统F中EG规则为 A(c)/∴x(x)

其中c为特定的个体常项，这里A(y) = F(y) →G(y)不满足要求。

(4)这里，使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如，F(x):x为奇数，G(x):x为偶数，显然F(3)∧G(4)为真，但不存在使F(x)∧G(x)为真的个体。

(5)这里c为个体常项，不能对F(c)→G(c)引入全称量词。 15.(1)证明：①xF(x) 前提引入 ②xF(x)→ y((F(y)∨G(y)) →R(y)) 前提引入 ③y((F(y)∨G(y)) →R(y) ①②假言推理 ④F(c) ①EI ⑤(F(c)∨G(c))→R(c) ③UI ⑥F(c)∨G(c) ④附加

⑦R(c) ⑤⑥假言推理 ⑧xR(x) ⑦EG (2)证明①xF(x) 前提引入 ②x((F(x)→G(a)∧R(x))) 前提引入 ③F(c) ①EI ④F(c)→G(a)∧R(a) ②UI ⑤G(a)∧R(c) ③④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ③⑥合取 ⑧x(F(x)∧R(x)) ⑦EG (3)证明：①┐xF(x) 前提引入 ②x┐F(x) ①置换 ③┐F(c) ②UI ④x(F(x)∨G(x)) 前提引入 ⑤F(c)∨G(c) ④UI

⑥F(c) ③⑤析取三段论 ⑦xF(x) ⑥EG (4)证明①x(F(x)∨G(x)) 前提引入 ②F(y)∨G(y) ①UI ③x(┐G(x)∨┐R(x)) 前提引入 ④┐G(y)┐R(y) ③UI ⑤x R(x) 前提引入 ⑥R(y) ⑤UI

⑦┐G(y) ④⑥析取三段论 ⑧F（y） ②⑦析取三段论 ⑨xF(x) ⑧UG

17．本题不能用附加前提证明法.

20.(1)与(2)均可用附加前提证明法。

22.(1)设F(x)：x为偶数，G(x):x能被2整除。 前提:x(F(x)→G(x))，F(6) 结论：G(6)

(2)设F(x)：x是大学生，G(x):x是勤奋的，a：王晓山。 前提:x(F(x)→G(x))，┐G(a) 结论：┐F(a)

23.(1)设F(x)：x是有理数，G(x):x是实数，H(x)：x是整数。 前提:x( F(x)→G(x))， x(F(x)∧H(x)) 结论:x(G(x)∧H(x)) 证明提示：先消存在量词。

(2)设F(x)：x是有理数，G(x):x是无理数，H(x)：x是实数，I(x)：x是虚数。 前提:x((F(x)∨G(x)) →H(x))， x( I(x)→┐H(x)) 结论:x(I(x)→(┐F(x)∧┐G(x)))

证明①x(I(x)→(┐H(x)) 前提引入

②I(y)→H(y) ①UI ③x((F(x)∨G(x))→H(x)) 前提引入 ④(F(y)∨G(y))→H(y) ③UI ⑤┐H(y)→(┐F(y)∧┐G(y)) ④置换 ⑥I(y)→(┐F(y)∧┐G(y)) ②⑤假言三段论 ⑦x(I(x)→(┐F(x)∧┐G(x)) ⑧UG

24.设F(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。 前提:x(┐F(x)→┐G(x))， x(G(x)∨H(x))， x┐H(x) 结论:x┐F(x)

证明①x┐H(x) 前提引入 ②┐H(c) ①UI ③x(G(x)∨H(x)) 前提引入 ④G(c)∨H(c) ③UI

⑤G(c) ②④析取三段论 ⑥x(F(x) →G(x)) 前提引入 ⑦F(c)→┐G(c) ⑥UI ⑧┐F(c) ⑤⑦拒取式 ⑨x┐F(x) ⑧UG

25.设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在事业中获得成功。 前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(a)，H(a) 结论：I(a)

证明①F(a) 前提引入 ②x(F(x)→G(x)) 前提引入 ③F(a)→G(a) ②UI ④G(a) ①③假言推理 ⑤H(a) 前提引入 ⑥x(G(x)∧H(x)→I(x)) 前提引入 ⑦G(a)∧H(a)→I(a) ⑥UI ⑧G(a)∧H(a) ④⑤合取 ⑨I(a) ⑦⑧假言推理

第六章 集合代数

本章自测答案

4.(1) ③ (2) ④ (3) ⑤ (4) ⑦ (5) ⑧

5.确定下列命题是否为真：

（1）??? 真 （2）??? 假 （3）??{?} 真 （4）??{?} 真

返回

（5）｛a,b｝?｛a,b,c,｛a,b,c｝｝ 真 （6）｛a,b｝?｛a,b,c,｛a,b｝｝ 真 （7）｛a,b｝?｛a,b,｛｛a,b｝｝｝ 真 （8）｛a,b｝?｛a,b,｛｛a,b｝｝｝ 假

6．设a,b,c各不相同，判断下述等式中哪个等式为真: （1）｛｛a,b｝，c,?｝ =｛｛a,b｝,c｝ 假 （2）｛a ,b,a｝=｛a,b｝ 真 （3）｛｛a｝，{b}｝=｛｛a,b｝｝ 假 （4）｛?，｛?｝，a,b｝=｛｛?,｛?｝｝,a,b｝ 假 8．求下列集合的幂集：

（1）｛a,b,c｝ P(A)={ ?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} （2）｛1，｛2，3｝｝ P(A)={ ?, {1}, {{2,3}}, {1，{2，3}} } （3）｛?｝ P(A)={ ?, ｛?｝ }

（4）｛?，｛?｝｝ P(A)={ ?, {1}, {{2,3}}, {1，{2，3}} }

9.(1) {4}；(2) {1,3,5,6}；(3) {2,3,4,5,6}；(4) {, { 1 }}；(5) {{ 4 },{1,4}}. 11.(1)； (2) {1,4,5}.

14．化简下列集合表达式： （1）（A?B）?B ）-（A?B） （2）（（A?B?C）-（B?C））?A 解:

(1)（A?B）?B ）-（A?B）=（A?B）?B ）?～（A?B）

=（A?B）?～（A?B）)?B=??B=?

（2）（（A?B?C）-（B?C））?A=（（A?B?C）?～（B?C））?A =（A?～（B?C））?（（B?C ）?～（B?C））?A =（A?～（B?C））???A=（A?～（B?C））?A=A

18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。 解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打网球的人} |A|=14, |B|=12, |A?B|=6,|A?C|=5,| A?B?C|=2, |C|=6,C?A?B

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库离散数学课后答案详细(3)在线全文阅读。