① r?s前提引入
② ?s前提引入
③ ?r ①②拒取式 ④ (p?q)?r前提引入
⑤ ?(p?q) ③④拒取式 ⑥ ?p??q ⑤置换
（2）2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明
(1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式结构
前提：p?q, p?r, r??s 结论：s?q
(3) 证明
① s附加前提引入 ② p?r前提引入 ③ r??s前提引入
④ p??s ②③假言三段论 ⑤ ?p ①④拒取式 ⑥ p?q前提引入
⑦ q ⑤⑥析取三段论 （3）前提：?(p?q)?r, r?s, ?s, p 结论：?q 证明 用归缪法 ① q结论否定引入 ② r?s前提引入 ③ ?s前提引入
④ ?r ②③拒取式 ⑤ ?(p?q)?r前提引入
⑥ ?(p?q) ④⑤析取三段论 ⑦ ?p??q ⑥置换
⑧ ?p ①⑦析取三段论
⑨ p前提引入
??p?p ⑧⑨合取
（4） (P?（Q∨R))∧(┐S?┐Q)∧(P∧┐S)?R. 证：（1） P∧┐S P
（2） P T（1） I1 （3） ┐S T（1） I1 （4） P?（Q∨R) P
（5） Q∨R T (2)，(4) I11 （6） ┐S?┐Q P
（7） ┐Q T(3)，(6) I11 （8） R T(5)，(7) I11
四．求下列公式的前束范式。
解：
(1)(?x)F(x)??(?x)G(x)
?(?x)F(x)?(?x)?G(x)(量词转换律)
?(?x)(F(x)??G(x))(量词分配)
(?x)F(x)??(?x)G(x) (2) ?(?x)F(x)?(?x)?G(x)(量词转换律) ?(?x)F(x)?(?y)?G(y)(换名) ?(?x)(F(x)?(?y)?G(y))(辖域扩张) ?(?x)(?y)(F(x)??G(y))(辖域扩张)
五．将下列命题符号化。
(1) 所有的人都长着黑头发；(2)有的人登上过月球；
(3) 没有人登上过木星； (4)在美国留学的学生未必都是亚洲人。 解：令M(x)：x 为人。
(1) 令F(x)：x长着黑头发。则?x (M(x)→ F(x))。
(2) 令G(x)：x登上过月球。则?x (M(x)∧G(x))。 (3) 令H(x)：x登上过木星。则
┐?x (M(x)∧H(x))。
(4) 令F(x)：x是在美国留学的学生; G(x)：x是亚洲人。则
┐?x (F(x)→ G(x))。
六．给定解释I 如下：
（a） 个体域D= {2,3}; （b） D中特定元素，a=2; （c） D上特定函数f (x) 为：f (2)=3, f (3)=2。 （d） D上特定谓词：
G(x,y): G(2,2)=G(2,3)=G(3,2)=1, G(3,3)=0; L(x,y): L(2,2)= L(3,3)=1, L(2,3)= L(3,2) =0; F(x)：F(2)=0, F(3)=1 在I下求下列各式的真值。 (1) ?x(F(x)∧G(x,a));
(2) ?x(F(f(x)∧G(x,f(x))); (3) ?x?y L(x,y); (4) ?y?x L(x,y)
解：设公式（1）为A, 则
A ?(F(2)∧G(2,2))∧(F(3)∧G(3,2))
?(0∧1)∧(1∧1) ?0
(2) B ?(F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3))) ?(F(3)∧G(2,3))∨(F(2)∧G(3,2)) ? (1∧1)∨(0∧1) ? 1
(3) C ? (L(2, 2) ∨L(2,3))∧(L(3,2)∨L(3,3)) ? (1∨0)∧(0∨1) ? 1
(4) D ? (L(2,2) ∧ L(2,3))∨(L(3,2)∧L(3,3)) ? (1∧0)∨(0∧1) ? 0
七．求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？ 解：
S = { x | x?Z∧1?x?1000 }
A = { x | x?S∧x可被5整除}
B = { x | x?S∧x可被6整除}
C = { x | x?S∧x可被8整除}
|A| = int(1000/5) = 200
|B| = int(1000/6) = 166
|C| = int(1000/8) = 125
|A∩B| = int(1000/lcm(5,6)) = 33
|A∩C| = int(1000/lcm(5,8)) = 25 |B∩C| = int(1000/lcm(6,8)) = 41 |A∩B∩C| = int(1000/lcm(5,6,8)) = 8 1000-(200+100+33+67)=600
八．A={1,2,3,4}, R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},求关系的定义域、值域与域并求 R的关系矩阵MR和关系图GR
?1100?
?0011?解： ?MR?? ?0000???
?0100?
关系图为
domR={1, 2, 4} ranR={1，2, 3, 4} fldR={1, 2, 3, 4}
九．设A={a,b,c,d}, R={
R
r(R)
s(R)
t(R)
十．给出 A＝{1,2,3}上所有的等价关系 解：先求出A的所有划分：
?1={{1, 2, 3}}; ?2={{1}, {2, 3}}； ?3={{2}, {1, 3}}; ?4={{3}, {1, 2}}; ?5={ {1}, {2}, {3}}。
与这些划分一一对应的等价关系是： ?1: → 全域关系EA
?2: → R2={<2, 3>, <3, 2>}∪IA ?3: → R3={<1, 3>, <3, 1>}∪IA ?4: → R4={<1, 2>, <2, 1>}∪IA ?5: → 恒等关系IA
十一．设偏序集
解 A={ a, b, c, d, e, f, g, h }
R={
极小元：a, b, c, g； 极大元：a, f, h； 没有最小元与最大元.
B的下界和最大下界都不存在； 上界有 d 和 f, 最小上界为 d.