(3)?x?y(F(x,y)?F(f(x),f(y))) 解:(1) ?x?yF(x,y)??x(F(x,3)?F(x,4))
? (F(3,3)?F(3,4))?(F(4,3)?F(4,4)) ?(0?1)?(1?0)?1
(2) ?x?y(F(x,y)?F(f(x),f(y)))
??x((F(x,3)?F(f(x),f(3)))?(F(x,4)?F(f(x),f(4))))
??x((F(x,3)?F(f(x),4))?(F(x,4)?F(f(x),3))) ?((F(3,3)?F(f(3),4))?(F(3,4)?F(f(3),3)))
?((F(4,3)?F(f(4),4))?(F(4,4)?F(f(4),3)))
?((0?F(4,4))?(F(3,4)?F(4,3)))?((1?F(3,4))?(0?F(3,3)))
?(0?0)?(1?1)?(1?1)?(0?0)?1
12.求下列各式的前束范式。
(1)?xF(x)??yG(x,y)
(5)?x1F(x1,x2)?(H(x1)???x2G(x1,x2)) (本题课本上有错误) 解:(1) ?xF(x)??yG(x,y)??xF(x)??yG(t,y)??x?y(F(x)?G(t,y)) (5) ?x1F(x1,x2)?(H(x1)???x2G(x1,x2))
??x1F(x1,x2)?(H(x3)??x2?G(x3,x2)) ??x1F(x1,x4)??x2(H(x3)??G(x3,x2)) ??x1?x2(F(x1,x4)?(H(x3)??G(x3,x2)))
15.在自然数推理系统F中,构造下面推理的证明:
(1) 前提: ?xF(x)??y((F(y)?G(y))?R(y)),?xF(x)
结论: ?xR(x)
(2) 前提: ?x(F(x)→(G(a)∧R(x))), xF(x) 结论:x(F(x)∧R(x)) 证明(1)
①?xF(x) 前提引入 ②F(c) ①EI
③?xF(x)??y((F(y)?G(y))?R(y)) 前提引入
9
④?y((F(y)?G(y))?R(y)) ①③假言推理 ⑤(F(c)∨G(c))→R(c)) ④UI ⑥F(c)∨G(c) ②附加 ⑦R(c) ⑤⑥假言推理 ⑧?xR(x) ⑦EG (2)
①?xF(x) 前提引入 ②F(c) ①EI
③?x(F(x)→(G(a)∧R(x))) 前提引入 ④F(c)→(G(a)∧R(c)) ③UI
⑤G(a)∧R(c) ②④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ②⑥合取引入 ⑧?x(F(x)∧R(x)) ⑦EG
第六章部分课后习题参考答案
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｝ 真
10
（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?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 如图所示。
25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人
21.设集合A＝{{1，2}，{2，3}，{1，3},{?}},计算下列表达式： （1）?A （2）?A （3）??A
11
网球
（4）??A 解:
（1）?A={1，2}?{2，3}?{1，3}?{?}={1，2，3,?}
（2）?A={1，2}?{2，3}?{1，3}?{?}=?
（3）??A=1?2?3??=?
（4）??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?～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?～B) ?? = A?～(B?C) =A- B?C 由（1）得证。
第七章部分课后习题参考答案
7.列出集合A={2,3,4}上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA. 解：IA ={<2，2>,<3,3>,<4,4>}
EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}
LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>}
13.设A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>}
求A?B,A?B, domA, domB, dom(A?B), ranA, ranB, ran(A?B ), fld(A-B). 解：A?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}
12