当前位置：文档库 › 离散数学最全答案屈婉玲

离散数学最全答案屈婉玲

第一章命题逻辑基本概念

课后练习题答案

4.将下列命题符号化，并指出真值：

（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；

（2）p∧q,其中，p:是无理数，q:自然对数的底e 是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.

5.将下列命题符号化，并指出真值：

（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；

（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p ：刘晓月选学英语，q ：刘晓月选学日语；.

7.因为p 与q 不能同时为真.

13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：

（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）pq ，真值为1；

（4）p→r，若p 为真，则p→r 真值为0，否则，p→r 真值为1.

16 设p 、q 的真值为0；r 、s 的真值为1，求下列各命题公式的真值。（1）p ∨(q ∧r)? 0∨(0∧1) ?0 （2）（p?r ）∧(﹁q ∨s) ?

（0?1）∧(1∨1) ?0∧1?

0. （3）（?p ∧?

q ∧r ）?(p ∧q ∧﹁r) ?

（1∧1∧1） ? (0∧0∧0)?

0 (4)（?

r ∧s ）→(p ∧?q) ?

（0∧1）→(1∧0) ?0→0?

1 17．判断下面一段论述是否为真：“π

是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”

答：p: π

是无理数 1 q: 3是无理数 0 r: 2是无理数 1 s: 6能被2整除 1

t: 6能被4整除 0

命题符号化为： p ∧(q →r)∧(t →s)的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型：（4）(p →q) →(?q →?p) （5）(p ∧r) ?(?p ∧?

q) （6）((p →q) ∧(q →r)) →(p →r) 答：（4）

p q p →q ?q ?p ?q →?p (p →q)→(?q →?

p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式

等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?

(p ∧q →q)

(2)(p →(p ∨q))∨(p →r) (3)(p ∨q)→(p ∧r)

答：(2)（p →(p ∨q)）∨(p →r)?(?

p ∨(p ∨q))∨(?

p ∨r)??

p ∨p ∨q ∨r ?1

所以公式类型为永真式

(3) P q r p ∨q p ∧r （p ∨q ）→(p ∧r)

0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0

1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1

所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p →q)∧(p →r)?(p →(q ∧r)) (4)(p ∧?

q)∨(?p ∧q)?

(p ∨q) ∧?(p ∧q) 证明（2）(p →q)∧(p →r)

? (?

p ∨q)∧(?p ∨r)

??p ∨(q ∧r)) ?p →(q ∧r)

（4）(p ∧?q)∨(?p ∧q)?

(p ∨(?p ∧q)) ∧(?q ∨(?

p ∧q)

?(p ∨?

p)∧(p ∨q)∧(?q ∨?

p) ∧(?

q ∨q) ?

1∧(p ∨q)∧?(p ∧q)∧1 ?

(p ∨q)∧?(p ∧q)

5.求下列公式的主析取范式与主合取范式，并求成真赋值

(1)(?p →q)→(?q ∨p) (2)?

(p →q)∧q ∧r

(3)(p ∨(q ∧r))→(p ∨q ∨r) 解：

（1）主析取范式

p →q)→(?

q ∨p)

??(p ∨q)∨(?q ∨p) ?(?p ∧?q)∨(?q ∨p) ? (?p ∧?q)∨(?q ∧p)∨(?q ∧?p)∨(p ∧q)∨(p ∧?q)

? (?p ∧?q)∨(p ∧?

q)∨(p ∧q)

?320m m m ∨∨ ?

∑(0,2,3)

主合取范式：

p →q)→(?q ∨p)

(p ∨q)∨(?

q ∨p) ?(?p ∧?q)∨(?q ∨p)

?(?p ∨(?q ∨p))∧(?

q ∨(?

q ∨p)) ?1∧(p ∨?q) ?(p ∨?q) ? M 1 ?

∏(1) (2) 主合取范式为： ?(p →q)∧q ∧r ??(?

p ∨q)∧q ∧r ?(p ∧?

q)∧q ∧r ?

0 所以该式为矛盾式.

主合取范式为∏(0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为：

(p ∨(q ∧r))→(p ∨q ∨r) ??(p ∨(q ∧r))→(p ∨q ∨r)

?(?p ∧(?q ∨?

r))∨(p ∨q ∨r) ?(?p ∨(p ∨q ∨r))∧((?q ∨?

r))∨(p ∨q ∨r))

?1∧1 ?

所以该式为永真式.

永真式的主合取范式为 1

主析取范式为∑(0,1,2,3,4,5,6,7)

7.(1)：∨∨∨∨?∧∧； (2)：∨∨∨?∧∧∧；

8.(1)：1?∨∨∨,重言式； (2)：∨?∨∨∨∨∨∨；

(3)：∧∧∧∧∧∧∧?0，矛盾式.

11.(1)：∨∨?∧∧∧∧； (2)：∨∨∨∨∨∨∨?1； (3)：0?∧∧∧.

?∧∧∧∧?∨∨.

第三章命题逻辑的推理理论

本章自测答案

6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系

(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确

(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为

(p→q)∧p→q(记作*1)

在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.

可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ? q

(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为

(p→q)∧p→q(记作*2)

可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等

(p→q)∧q→p

?(┐p∨q) ∧q →p

?q →p

?┐p∨┐q

??∨∨

从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.

9.设p:a是奇数，q:a能被2整除，r:a：是偶数

推理的形式结构为

(p→q┐)∧(r→q)→(r→┐p) (记为*)

可以用多种方法证明*为重言式，下面用等值演算法证明：

(p→┐q)∧(r→q)→(r→┐p)

?(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)

?(p∨q)∨(┐p∧r)∨┐q∨┐r

?(┐p∨q)∨(┐q∧┐r)

?┐p∨(q∨┐q)∧┐r

10.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.

推理的形式结构为

(p→q)∧┐p→(┐q∧┐r)

?(┐p∨q) ∧┐p→(┐q∧┐r)

?┐p→(┐q∧┐r) (使用了吸收律)

?p∨(┐q∧┐r)

?∨∨∨

由于主析取范式中只含有5个W极小项，故推理不正确.

11.略

14.证明的命题序列可不惟一，下面对每一小题各给出一个证明

① p→(q→r)前提引入

② P前提引入

③ q→r①②假言推理

④ q前提引入

⑤ r③④假言推理

⑥ r∨s前提引入

（2）证明：

① ┐(p∧r)前提引入

② ┐q∨┐r①置换

③ r前提引入

④ ┐q ②③析取三段论

⑤ p→q前提引入

⑥ ┐p④⑤拒取式

（3）证明：

① p→q前提引入

② ┐q∨q①置换

③ (┐p∨q)∧(┐p∨p) ②置换

④ ┐p∨(q∧p③置换

⑤ p→(p∨q) ④置换

15.(1)证明：

① S结论否定引入

② S→P前提引入

③ P①②假言推理

④ P→(q→r)前提引入

⑥ q前提引入

⑦ r⑤⑥假言推理

（2）证明：

① p附加前提引入

② p∨q①附加

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

④ r∧s②③假言推理

⑤ s④化简

⑥ s∨t ⑤附加

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

⑧ u⑥⑦拒取式

16.(1)证明：

① p结论否定引入

② p→ ┐q前提引入

③ ┐q ①②假言推理

④ ┐r∨q前提引入

⑤ ┐r③④析取三段论

⑥ r∧┐s前提引入

⑦ r⑥化简

⑧ ┐r∧r⑤⑦合取

（2）证明：

① ┐(r∨s)结论否定引入

② ┐r∨┐s①置换

③ ┐r②化简

④ ┐s②化简

⑤ p→r前提引入

⑥ ┐p③⑤拒取式

⑦ q→s前提引入

⑧ ┐q④⑦拒取式

⑨ ┐p∧┐q⑥⑧合取

⑩ ┐(p∨q)⑨置换

口p∨q前提引入

⑾①口┐(p∨q) ∧(p∨q) ⑩口合取

16在自然推理系统P中用归谬法证明下面各推理：

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

结论：?p

证明：

①p 结论的否定引入

②p→﹁q 前提引入

③﹁q ①②假言推理

④￢r∨q 前提引入

⑤￢r ④化简律

⑥r∧￢s 前提引入

⑦r ⑥化简律

⑧r∧﹁r ⑤⑦合取

由于最后一步r∧﹁r 是矛盾式,所以推理正确.

17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

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

结论：r

证明：

① q→s 前提引入

② ┐s 前提引入

③ ┐q ①②拒取式

④ p 前提引入

⑤ p∧┐q ③④合取

⑥（p∧┐q）→r 前提引入

⑦ r ⑤⑥假言推理

18．（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。

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

结论：r

证明：

① s→┐q前提引入

② s前提引入

③ ┐q①②假言推理

④ p 前提引入

⑤ p→(q∨r)前提引入

⑥ q∨r④⑤假言推理

（2）设p:小王是理科学生，q ：小王数学成绩好，r ：小王是文科学生。前提：p→q ,┐r→p ,┐q 结论：r 证明：

① p→q 前提引入 ② ┐q 前提引入 ③ ┐p ①②拒取式 ④ ┐r→p 前提引入 ⑤ r ③④拒取式

第四章 (一阶)谓词逻辑基本概念

本章自测答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:

(1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解：

F(x): 2=(x+)(x). G(x): x+5=9.

(1)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。

4.(1)┐x(F(x)∧ ┐G(x))?x( F (x) →G (x) ),其中,F(x)：x 是有理数,G(x) ：x 能表示成分数； (2)┐x( F (x) →G (x) ) ?x(F(x)∧ ┐G(x)),其中,F (x)：x 在北京卖菜,G (x) ：x 是外地人； (3)x( F (x) →G (x) ),其中,F (x)：x 是乌鸦,G (x) ：x 是黑色的； (4)xF(x)∧ G(x)),其中,F (x)：x 是人,G (x) ：x 天天锻炼身体。因为本题中没有指明个体域,因而使用全总个体域。

5.(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)┐x(F(x)∧y(G (y) → H (x,y)))?x(F(x) → y(G(y) ∧ ┐H(x,y))),其中,F(x)：x 是汽车,G (y) ：y 是火车,H(x,y)：x 比y 快； (4)┐x(F(x)→y(G(y) → H(x,y)))?xy(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x 是汽车,G(y) ：y 是火车,H(x,y)：x 比y 慢。 6.各命题符号化形式如下： (1)xy (x ．y = 0)； (2)xy (x ．y = 0)； (3)xy (y =x+1)

(4)xy(x ．y = y ．x) (5)xy(x ．y =x+ y) (6)xy (x + y ＜0 )

9.(1)对任意数的实数x 和y,若x ＜y,则x ≠ y； (2)对任意数的实数x 和y,若x –y = 0,则x ＜y ； (3)对任意数的实数x 和y,若x ＜y,则x –y≠0； (4)对任意数的实数x 和y,若x –y ＜0,则x=y. 其中,(1)(3)真值为1(2)与(4)真值为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 的个体域D 1中的个体常项x 0,使yF(x 0,y)为真,并且对于任意y∈,F(x

0,y)为真,由于有x 0∈,F(x

0,y)为真,所以xF(x,y)为真,又其中y 是任意个体变项,所以 yxF(x,y )为真,由于I 的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。

(5)取解释为：个体域为自然数集合,F(x,y)：x = y 在下,(5)中公式为真,而将F(x,y)改为F(x,y)：x ＜ y,(5)中公式就为假了,所以它为可满足式。

10. 给定解释I 如下：

（a ）个体域D=N(N 为自然数集合). （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)

(3) yF(x,y).

解:(1)因为 1)()(?∨?∨??→→p q p p q p 为永真式；所以为永真式；

(3)取解释I 个体域为全体实数 F(x,y)：x+y=5

所以,前件为任意实数x 存在实数y 使x+y=5，前件真；后件为存在实数x 对任意实数y 都有x+y=5，后件假，] 此时为假命题

再取解释I 个体域为自然数N ， F(x,y)：:x+y=5

所以,前件为任意自然数x 存在自然数y 使x+y=5，前件假。此时为假命题。

此公式为非永真式的可满足式。

13．（1）取解释为：个体域为自然数集合N ，F （x ）：x 为奇数，G （x ）：x 为偶数，在下， x （F （x ）∨G（x ））为真命题。取解释为：个体域为整数集合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))

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

(3) x 4 ((F(,y) →G(,y))∧(G(,y) →F(x

4,y))); (4) ((F()→G(,)) → (H () → L(,))); (5) (F(,)→(F() → ┐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) ⑧ 6.只有(2)为真，其余为假。

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}} } 14．化简下列集合表达式：（1）（A Y B ）I B ）-（A Y B ）（2）（（A Y B Y C ）-（B Y C ））Y A 解:

(1)（A Y B ）I B ）-（A Y B ）=（A Y B ）I B ）I ～（A Y B ）

=（A Y B ）I ～（A Y B ）)I B=?I B=? （2）（（A Y B Y C ）-（B Y C ））Y A=（（A Y B Y C ）I ～（B Y C ））Y A =（A I ～（B Y C ））Y （（B Y C ）I ～（B Y C ））Y A =（A I ～（B Y C ））Y ?Y A=（A I ～（B Y C ））Y A=A

18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。

解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打网球的人} |A|=14, |B|=12, |A I B|=6,|A I C|=5,| A I B I C|=2, |C|=6,C ?

A Y

B 如图所示。

25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人

21.设集合A ＝{{1，2}，{2，3}，{1，3},{?}},计算下列表达式：（1）Y A （2）I A （3）I Y A （4）YI A

解: （1）Y A={1，2}Y {2，3}Y {1，3}Y {?}={1，2，3,?}

（2）I A={1，2}I {2，3}I {1，3}I {?}=?

（3）I Y A=1I 2I 3I ?=?

（4）YI A=?

27、设A,B,C 是任意集合，证明 (1)(A-B)-C=A- B ?C (2)(A-B)-C=(A-C)-(B-C)

证明

(1) (A-B)-C=(A I ～B) I ～C= A I ( ～B I ～C)= A I ～(B ?C) =A- B ?C (2) (A-C)-(B-C)=(A I ～C) I ～(B I ～C)= (A I ～C) I (～B Y C)

=(A I ～C I ～B) Y (A I ～C I C)= (A I ～C I ～B) Y ? = A I ～(B ?C ) =A- B ?C 由（1）得证。

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}.

22.(2)、(3)、(4)、(8)、(10)为真，其余为假。

24.(1)为真，其余为假，因为

(P-Q) = P ? (P-Q)∩Q = P ∩Q ? = P∩Q

(2)(3)(4)的反例：P ={1} ，Q ={2}

26.(A–B)∪(B–A) = (A∩B)∪(B∩A)

=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)

=(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B)

27.(1)(A-B)-C = A∩B∩C =A∩(B∪C) = A-(B∪C)

(2)(A-C)-(B-C)A∩C∩(B∩C)

=A∩C∩(B∪C) = (A∩C∩B)∪(A∩C∩C)

=A∩∩C=(A–B)- C

(3)(A–B-C=A∩B∩C =A∩C∩B=(A–C)–B

28.(1)A∩(B∪A) = (A∩B)∪(A∩A) =(A∩B)∪

=A∩B=B∩A

(2)((A∪B)∩A) = (A∪B)∪A

=(A∩B)∪A = A

29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾.

?x(x∈A→x∈B)?x(xB→xA)

?x(x∈B→x∈A)?BA

AB ? A∪AA∪B ? E A∪B

而A∪BE，因此AB ? A∪B=E反之，

A∪B = E ? A∩(A∪B)= A ? A∩B = A ? AB

综合上述，AB?A∪B = E

AB ? A-B = ? A-BB

反之A-BB ? (A-B)∪BB ? A∪BB ? A∪B = B ? AB

综合上述AB?A-BB

31.任取x ,x∈A ? {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B ? x∈B

32.先证CA∧CB ? C A∩B,任取x,x∈C ? x∈C∧x∈C ? x∈A∧x∈B ? x∈A∪B,从而得到CA∪B.再证CA∩B ? C A∧CB，这可以由CA∩BA,CA∩BB 得到。

? P-Q= ? P-QP，反之，P-QP ? P∩(P-Q)P∩P ? P-Q= ? PQ

34.令X=，则有∪Y =，即Y = .

? A∪AB∪A ? E B∪A因为E为全集,B∪AE综合上述B∪A=E.

36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有：

(A∩C)∪(A-C) (B∩C)∪(B-C)

? (A∩C)∪(A∩C)(B∩C)∪(B∩C)

? (A∩(C∪C)(B∩(C∪C) ? A∩E B∩E ? AB

37.恒等变形法

B=B∩(B∪A)=B∩(AB)=B∩(AC)

=(B∩A)∪(B∩C)=(A∩C)∪(B∩C)

=(A∪B)∩C=(A∪C)∩C=C

39.任取x，有x∈P(A) ? x A ? x B ? x∈P(B)，因此P(A)P(B).

40.(1)任取x有

x∈P(A)∩P(B)?x∈P(A)∧x∈P(B)?x A∧xB

?x A∩B?x∈P(A∩B)

(2)任取x有

x∈P(A)∪P(B)?x∈P(A)∨x∈P(B)?x A∧xB

? x A∪B?x∈P(A∪B)

注意与(1)的推理不同，上面的推理中有一步是“ ? ”符号，而不是“?”符号。

(3)反例如下：A = {1}，B = {2}，则

P(A)∪P(B)= {,{1},{2}}

P(A∪B)={,{1},{2},{1,2}}

第七章二元关系

本章自测答案

3.(1) 任取< x,y >,有

∈(A ∩ B)×(C ∩ D) <=>x∈A ∩ B ∧ y ∈C ∩ D

?x ∈A∧x ∈ B∧y ∈C∧y ∈ D

?(x ∈A∧y ∈C )∧(x∈B∧y∈D)

?∈A×C∧< x,y >∈B×D

?∈(A×C)∩(B×D)

(2)都为假,反例如下:

A ={1},

B ={1,2},

C ={2},

D ={3} 4.(1)为假,反例如下:A ={1}, B =,C = {2}; (2)为真,证明如下:任取有

∈A×(B∩C)×(C∩D)?x ∈A ∩B ∧y ∈B ∧y ∈C ?(x ∈A ∧y ∈B)∧(x ∈A ∧y ∈C)

?∈A ×B ∧∈A ×C?∈(A ×B)∩(A ×C) (3)为真,令A = 即可; (4)为假,反例如下: A = 7.={<2,2>,<3,3 >,<4,4>}

={<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>} ∪ L A ={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} D A ={<2,2>,<2,4>,<3,3>,<4,4>}

9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>} (2){<1,2>,<2,1>};

(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>} (4){<1,2>,<2,2>,<4,2>,<6,2>} 12.（略）

∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>} domA = {1,2,3},domB = {1,2,4},dom(A ∪ B) = {1,2,3,4}

ranA = {2,3,4},ranB = {2,3,4},ran(A ∪ B) = {4},fld(A - B) = {1,2,3}

= {<0,2>,<0,3>,<1,3>}

R= {<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R{0,1} = {<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}] = {2,3}

16．设A={a,b,c,d}，1R ，

2R 为A 上的关系，其中

1R ={

}

,,,,,a a a b b d

{

}

,,,,,,,R a d b c b d c b = 求23

122112,,,R R R R R R o o 。解: R 1οR 2={,,} R 2οR 1={}

R 12

=R 1οR 1={,,} R 22

=R 2οR 2={,,} R 23=R 2οR 22

={,,}

18.(1)F(G∪H) = FG∪FH 任取 ,有

∈F (G∪H)?t(∈F ∧∈G∪H) ?t(∈F∧(∈G∨∈H))

?t((∈F∧∈G)∨(∈F∧∈H)) ?t(∈F∧∈G)∨t(∈F∧∈H)) ?∈F G∨∈FH ?∈F G∪FH (2)和(4)类似可证 19.(2)任取y,有

y∈R[T∪W]?x(x∈T∪W∧∈R) ?x((x∈T∨x∈W)∧∈R

?x((x∈A∧∈R)∨(x∈W∧∈R)) ?x(x∈T∧∈R)∨x(x∈W∧∈R) ?y ∈R[T]∨y ∈R[W]?y ∈R[T]∩R[W] (3)任取,有

∈F(A∩B)?x ∈A ∩B ∈F ?x ∈A ∧x ∈B ∧∈F

?(x ∈A ∧∈F)(x ∈B ∧∈F) ?∈F A∧∈FB ?∈F A∩F B 20.(1)任取,有

∈(∪) <=>∈∪ ?∈∨∈ ?∈∨∈ ?∈∪ (2)和(1)类似可证.

21.只有对称性,因为1+1≠10,<1,1>R,R 不是自反的,又由于<5,5>∈R,因此R 不是反自反的,根据xRy?x+y = 10=>yRx ,可知R 是对称的,又由于<1,9>,<9,1>都是属于R,因此R 不是反对称的, <1,9>,<9,1>都属于R,如果R 是传递的,必有<1,1>属于R.但这是不成立的,因此R 也不是传递的. 22.(1)关系图如图所示; (P148)

(2)具有反自反性、反对称性、传递性.

26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>}

(2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>} s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>}

T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>}

31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪；(2)R ； (3)R. 32.(1)不是等价关系，因为<1,1> R ，R 不是自反的；

(2)不是等价关系，因为R 不是传递的，1R3，3R2但是没有1R2； (3)不是等价关系，因为<2,2> R ，R 不是自反的； (4)不是等价关系，因为R 不是传递的。 (5)是等价关系。

33．关系图如图说示 (P151)

[a] = [b] ={a,b},[c] = [d] = {c,d}

36．设A={1，2，3，4}，在A ?A 上定义二元关系R ， ?

,∈

A ?A ，〈u,v> R ?

u + y = x + v.