离散数学答案新版_甜梦文库
离散数学答案新版
第1章 命题逻辑P7 习题 1. 给出下列命题的否定命题： （1）大连的每条街道都临海。 否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。 否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1） (?P ∧ R ) → Q 如果非 P 与 R，那么 Q。 （2） Q ∧ R Q 并且 R。 3. 给出命题 P → Q ，我们把 Q → P 、 ?P → ?Q 、 ?Q → ?P 分别称为命题 P → Q 的 逆命题、反命题、逆反命题。 （1）如果天不下雨，我将去公园。 解：逆命题：如果我去公园，则天不下雨； 反命题：如果天下雨，则我不去公园； 逆反命题：如果我不去公园，则天下雨了。 （2）仅当你去我才逗留。 解： （此题注意：p 仅当 q 翻译成 p → q ） 逆命题：如果你去，那么我逗留。 反命题：如果我不逗留，那么你没去。 逆反命题：如果你没去，那么我不逗留。 （3）如果 n 是大于 2 的正整数，那么方程 x 解：逆命题：如果方程 xn n+ yn = z n 无整数解。+ yn = z n 无整数解，那么 n 是大于 2 的正整数。n反命题：如果 n 不是大于 2 的正整数，那么方程 x 逆反命题：如果方程 xn+ yn = z n 有整数解。+ yn = z n 有整数解，那么 n 不是大于 2 的正整数。（4）如果我不获得更多的帮助，那么我不能完成这项任务。 解：逆命题：如果我不完成任务，那么我不获得更多的帮助。 反命题：如果我获得了更多的帮助，那么我能完成任务。 逆反命题：如果我能完成任务，那么我获得了更多的帮助。 4. 给 P 和 Q 指派真值 T，给 R 和 S 指派真值 F，求出下列命题的真值。 （1） (?( P ∧ Q ∨ ?R ) ∨ ((Q ? ?P ) → ( R ∨ ?S )))= (?(T ∧ T ∨ ?F ) ∨ ((T ? ?T ) → ( F ∨ ?F ))) = ?T ∨ ( F → T ) =T ∨ F =T （2） Q ∧ ( P → Q ) → P = T ∧ (T → T ) → T =T ∧T → T =T → T =T （3） ( P ∨ (Q → ( R ∧ ?P ))) ? (Q ∨ ?S ) = (T ∨ (T → ( F ∧ ?T ))) ? (T ∨ ?F ) = (T ∨ (T → F )) ? T =T ? T =T （4） ( P → R ) ∧ (?Q → S ) = (T → F ) ∧ (?T → F ) = F ∧ (F → F ) =F 5. 构成下来公式的真值表： （1） Q ∧ ( P → Q ) → P P F F T T Q F T F TQ ∧ ( P → Q)F T F TQ ∧ ( P → Q) → PT F T T（2） ?( P ∨ Q ∧ R ) ? ( P ∨ Q ) ∧ ( P ∨ R ) P F F Q F F R F T?( P ∨ Q ∧ R)T T( P ∨ Q) ∧ ( P ∨ R)F F?( P ∨ Q ∧ R) ? ( P ∨ Q) ∧ ( P ∨ R )F FF F T T T TT T F F T TF T F T F TT F F F F FF T T T T TF F F F F F（3） ( P ∨ Q → Q ∧ P ) → P ∧ ?R P F F F F T T T T Q F F T T F F T T R F T F T F T F T( P ∨ Q → Q ∧ P)T T F F F F T TP ∧ ?RF F F F T F T F( P ∨ Q → Q ∧ P ) → P ∧ ?RF F T T T T T F（4） ?( P → P ∧ ?Q → R ) ∧ Q ∨ ?R P F F F F T T T T Q F F T T F F T T R F T F T F T F T?( P → P ∧ ?Q → R )T F T F T F F F?( P → P ∧ ?Q → R ) ∧ Q ∨ ?RT F T F T F T F6. 使用真值表证明：如果 P ? Q 为 T ，那么 P → Q 和 Q → P 都是 T ，反之亦然。 证明： P F F T T Q F T F TP?QT F F TP→QT T F TQ→PT F T T由上表可知：当 P ? Q 为 T 时， P → Q 和 Q → P 都是 T ； P → Q 和 Q → P 为 T 时，P ? Q 为 T 。故命题得证。7. 使用真值表证明：对于 P 和 Q 的所有值， P → Q 与 ?P ∨ Q 有同样的真值。 P F F T T Q F T F TP→QT T F T?P ∨ QT T F T8. 一个有两个运算对象的逻辑运算符，如果颠倒其运算对象的次序，产生一逻辑等价命题， 则称此逻辑运算符是可交换的。 （1）确定所给出的逻辑运算符哪些是可交换的： ∧ ， ∨ ， → ， ? 。 （2）用真值表证明你的判断。 解： （1） ∧ ， ∨ ， ? 是可交换的。 （2）真值表如下： P F F T T Q F T F TP∧QF F F TQ∧PF F F TP∨QF T T TQ∨ PF T T TP→QT T F TQ→PT F T TP?QT F F TQ?PT F F T9.设 ? 是具有两个运算对象的逻辑运算符， 如果 ( x ? y ) ? z 和 x ? ( y ? z ) 逻辑等价， 那么运算 符 ? 是可结合的。 （1）确定逻辑运算符 ∧ ， ∨ ， → ， ? 哪些是可结合的？ （2）用真值表证明你的判断。 解： （1） ∧, ∨, ? 是可结合的。 （2）真值表如下： P F F F F T T T T Q F F T T F F T T R F T F T F T F T( P ∧ Q) ∧ RF F F F F F F T( P ∨ Q) ∨ RF T T T T T T T( P → Q) → RF T F T T T F T( P ? Q) ? RT T T F T F F TPQRP ∧ (Q ∧ R)P ∨ (Q ∨ R)P → (Q → R )P ? (Q ? R )F F F F T T T TF F T T F F T TF T F T F T F TF F F F F F F TF T T T T T T TT T T T T T F TT T T F T F F T10. 令 P 表示命题“苹果是添的” ， Q 表示命题“苹果是红的” ， R 表示命题“我买苹果” 。 试将下列命题符号化： （1）如果苹果甜而红，那么我买苹果。 （2）苹果不是甜的。 （3）我没买苹果，因为苹果不红也不甜。 解： （1 ） P ∧ Q → R （2） ?P （3） ?R → ?P ∧ ?QP15 习题 1. 指出下面命题公式哪些是重言式、永假式或可满足式。 解： （1）重言式P ∨ ?P =T（2）永假式P ∧ ?P = F（3）重言式P → ?(?P) =T（4）重言式?( P ∧ Q) ? (?P ∨ ?Q) = (?P ∨ ?Q) ? (?P ∨ ?Q) = T（5）重言式?( P ∨ Q) ? (?P ∧ ?Q) = (?P ∧ ?Q) ? (?P ∧ ?Q) = T（6）重言式( P → Q ) ? ( ?Q → ?P )= (?P ∨ Q ) ? (Q ∨ ?P ) =T （7）重言式(( P → Q) ∧ (Q → P)) ? ( P ? Q)= ( P ? Q) ? ( P ? Q) = T （8）重言式P ∧ (Q ∨ R) → ( P ∧ Q ∨ P ∧ R)= (( P ∧ Q ) ∨ ( P ∧ R )) → ( P ∧ Q ∨ P ∧ R ) = ( P ∧ Q ∨ P ∧ R) → ( P ∧ Q ∨ P ∧ R) =T （9）重言式P ∧ ?P → Q=F →Q = T （10）可满足式P ∨ ?Q → Q= ?( P ∨ ?Q ) ∨ Q = ?P ∧ Q ∨ Q ，当 Q 为真时公式为真， Q 为假时公式为假。故为可 满足式。 （11）重言式P → P∨Q = ?P ∨ P ∨ Q = T（12）重言式P∧Q → P = ?( P ∧ Q) ∨ P = ?P ∨ ?Q ∨ P = T（13）可满足式( P ∧ Q ? P) ? ( P ? Q) 的真值表如下：P F F T T （14）可满足式 Q F T F TP∧Q ? PT T F TP?QT F F T( P ∧ Q ? P) ? ( P ? Q)T F T T(( P → Q) ∨ ( R → S )) → (( P ∨ R ) → (Q ∨ S ))= ( ?P ∨ Q ∨ ?R ∨ S ) → ( ? P ∧ ?R ∨ Q ∨ S )= ((?P ∨ ?R ) ∨ (Q ∨ S )) → ((?P ∧ ?R ) ∨ (Q ∨ S )) 当 Q 或 S 有一个为真时公式为真；当 Q 和 S 均为假时，若 P 和 R 真值相同时，公式 为真；真值不同时，公式为假。故公式是可满足式。 2. 写出与下面给出的公式等价并且仅含有联接词 ∧ 与 ? 的最简公式。 （1） ?( P ? (Q → ( R ∨ P )))? ?(( P → (Q → ( R ∨ P ))) ∧ ((Q → ( R ∨ P )) → P )) ? ?((?P ∨ ?Q ∨ R ∨ P ) ∧ ((?Q ∨ R ∨ P ) → P )) ? ?(T ∧ (Q ∧ ?R ∧ ?P ∨ P )) ? ?(Q ∧ ?R ∧ ?P ∨ P) ? ?P ∧ ?(?P ∧ Q ∧ ?R)（2） (( P ∨ Q ) → R ) → ( P ∨ R )? (?( P ∨ Q) ∨ R) → ( P ∨ R) ? ?(?( P ∨ Q) ∨ R) ∨ ( P ∨ R) ? (( P ∨ Q) ∧ ?R) ∨ P ∨ R ? ( P ∨ Q ∨ P ) ∧ ( ?R ∨ P ) ∨ R ? (( P ∨ Q) ∧ (?R ∨ P)) ∨ R ? ( P ∨ Q ∨ R ) ∧ ( ?R ∨ P ∨ R ) ? ( P ∨ Q ∨ R) ? ?(?P ∧ ?Q ∧ ?R)（3） P ∨ Q ∨ ?R? ?(?P ∧ ?Q ∧ R)（4） P ∨ (?Q ∧ R → P )? P ∨ (?(?Q ∧ R) ∨ P) ? P ∨ (Q ∨ ?R ∨ P) ? P ∨ Q ∨ ?R ? ?(?P ∧ ?Q ∧ R)（5） P → (Q → P )? P → ( ?Q ∨ P ) ? ?P ∨ ( ?Q ∨ P ) ?T3. 写出与下面的公式等价并且仅含联结词 ∨ 和 ? 的最简公式。（1） ( P ∧ Q ) ∧ ?P? P ∧ Q ∧ ?P ?F（2） ( P → (Q ∨ ?Q )) ∧ ?P ∧ Q? ( P → T ) ∧ ?P ∧ Q ? T ∧ ?P ∧ Q ? ?P ∧ Q ? ?( P ∨ ?Q)（3） ?P ∧ ?Q ∧ (?R → P )? ?P ∧ ?Q ∧ ( R ∨ P ) ? ( ?P ∧ ?Q ∧ R ) ∨ ( ?P ∧ ?Q ∧ P ) ? ( ?P ∧ ?Q ∧ R ) ∨ F ? ?P ∧ ?Q ∧ R ? ?( P ∨ Q ∨ ?R)4. 使用常用恒等式证明下列各式，并给出下列各式的对偶式。 （1） ?(?P ∨ ?Q ) ∨ ?(?P ∨ Q ) ? P 证明：?(?P ∨ ?Q) ∨ ?(?P ∨ Q) ? ( P ∧ Q ) ∨ ( P ∧ ?Q ) ? P ∧ (Q ∨ ?Q) ? P ∧T ?P对偶式： ?(?P ∧ ?Q ) ∧ ?(?P ∧ Q ) ? P （2） ( P ∨ ?Q ) ∧ ( P ∨ Q ) ∧ (?P ∨ ?Q ) ? ?(?P ∨ Q ) 证明：( P ∨ ?Q ) ∧ ( P ∨ Q ) ∧ ( ?P ∨ ?Q ) ? ( P ∨ (?Q ∧ Q)) ∧ (?P ∨ ?Q) ? P ∧ ( ?P ∨ ?Q ) ? ( P ∧ ?P ) ∨ ( P ∧ ?Q ) ? ( P ∧ ?Q ) ? ?(?P ∨ Q)对偶式： ( P ∧ ?Q ) ∨ ( P ∧ Q ) ∨ (?P ∧ ?Q ) ? ?(?P ∧ Q )（3） Q ∨ ?((?P ∨ Q ) ∧ P ) ? T 证明：Q ∨ ?((?P ∨ Q) ∧ P) ? Q ∨ (?(?P ∨ Q) ∨ ?P) ? Q ∨ ( P ∧ ?Q ) ∨ ?P ? ( P ∧ ?Q) ∨ ?( P ∧ ?Q) ?T对偶式： Q ∧ ?((?P ∧ Q ) ∨ P ) ? F 5. 试证明下列合式公式是永真式。 （1） (( P ∧ Q ) → P ) ? T 证明：(( P ∧ Q) → P) ? ?( P ∧ Q) ∨ P ? ?P ∨ ?Q ∨ P ?T（2） ?(?( P ∨ Q ) → ?P ) ? F 证明：?(?( P ∨ Q) → ?P) ? ?(( P ∨ Q) ∨ ?P) ? ?( P ∨ Q) ∧ P ? ?P ∧ ?Q ∧ P ?F（3） (Q → P ) ∧ (?P → Q ) ? P 证明：(Q → P) ∧ (?P → Q) ? ( ?Q ∨ P ) ∧ ( P ∨ Q ) ? P ∨ ( ?Q ∧ Q ) ? P∨ F ?P（4） ( P → ?P ) ∧ (?P → P ) ? F 证明：( P → ?P ) ∧ ( ?P → P ) ? ( ?P ∨ ?P ) ∧ ( P ∨ P ) ? ?P ∧ P ?F6. 证明下列蕴含式。 （1） P ∧ Q ? P → Q 证明：( P ∧ Q) → ( P → Q) ? ?( P ∧ Q) ∨ (?P ∨ Q) ? ?P ∨ ?Q ∨ ?P ∨ Q ? ?P ∨ ?Q ∨ Q ?T（2） P → (Q → R ) ? ( P → Q ) → ( P → R ) 证明：( P → (Q → R )) → (( P → Q) → ( P → R)) ? (?P ∨ (?Q ∨ R)) → (?(?P ∨ Q) ∨ (?P ∨ R)) ? (?P ∨ ?Q ∨ R) → (( P ∧ ?Q) ∨ ?P ∨ R) ? ( ?P ∨ ?Q ∨ R ) → ( ?P ∨ ?Q ∨ R ) ?T（3） P → Q ? P → P ∧ Q 证明：( P → Q) → ( P → P ∧ Q) ? ( P → Q) → (?P ∨ ( P ∧ Q)) ? ( P → Q) → ((?P ∨ P) ∧ (?P ∨ Q)) ? ( P → Q ) → ( ?P ∨ Q ) ? ( P → Q) → ( P → Q) ?T（4） ( P → Q ) → Q ? P ∨ Q 证明：(( P → Q) → Q) → ( P ∨ Q) ? (?(?P ∨ Q) ∨ Q) → ( P ∨ Q) ? (( P ∧ ?Q) ∨ Q) → ( P ∨ Q) ? (( P ∨ Q) ∧ (?Q ∨ Q)) → ( P ∨ Q) ? ( P ∨ Q) → ( P ∨ Q) ?T（5） ( P ∨ ?P → Q ) → ( P ∨ ?P → R ) ? Q → R 证明：(( P ∨ ?P → Q) → ( P ∨ ?P → R )) → (Q → R ) ? ((T → Q) → (T → R)) → (Q → R) ? (( F ∨ Q) → ( F ∨ R )) → (Q → R ) ? (Q → R) → (Q → R) ?T（6） (Q → P ∧ ?P ) → ( R → P ∧ ?P ) ? R → Q 证明：((Q → P ∧ ?P ) → ( R → P ∧ ?P )) → ( R → Q) ? ((Q → F ) → ( R → F )) → ( R → Q) ? ((?Q ∨ F ) → (?R ∨ F )) → ( R → Q) ? ( ?Q → ?R ) → ( R → Q ) ? ( R → Q) → ( R → Q) ?T7. 对一个重言式使用代入规则后仍为一个重言式，对一个可满足式和一个矛盾式，使用代 入规则后，结果如何？对重言式、可满足式和矛盾式，使用替换规则后，结果如何？ 解：对于代入规则： （1）如果是可满足式，使用代入规则后可能是重言式、可满足式或矛盾式。如：可满 足式 P ∨ Q ，将 Q 分别替换为 ?P ， R 分别得到重言式 P ∨ ?P 和可满足式 P ∨ R ，对于可 满足式 P ∧ Q ，将 Q 替换为 ?P 得到矛盾式 P ∧ ?P 。 （2）如果是矛盾式，使用代入规则后仍然是矛盾式。设 P 是矛盾式，则 ?P 是重言式。 而对于重言式使用代入规则后仍为重言式，即 ?P′ 是重言式，故 P′ 是矛盾式。 对于替换规则：由于替换规则是一种对子公式逻辑上等价的替换，故对于重言式、可满 足式和矛盾式使用替换规则后其真值不变。 8. 求出下列各式的代入实例。 （1） ((( P → Q ) → P ) → P ) ；用 P → Q 代 P ，用 (( P → Q ) → P ) 代 Q 。 解： (((( P → Q ) → (( P → Q) → P )) → ( P → Q)) → ( P → Q)) （2） (( P → Q ) → (Q → P )) ；用 Q 代 P ，用 ?P 代 Q 解： ((Q → ?P ) → (?P → Q ))P21 习题 1.求下列各式的主合取范式。 （1） ( P ∧ Q ∧ R ) ∨ (?P ∧ Q ∧ R ) ∨ (?P ∧ ?Q ∧ ?R )解：? (( P ∧ (Q ∧ R)) ∨ (?P ∧ (Q ∧ R))) ∨ (?P ∧ ?Q ∧ ?R) ? (( P ∨ ?P) ∧ (Q ∧ R)) ∨ (?P ∧ ?Q ∧ ?R ) ? (Q ∧ R) ∨ (?P ∧ ?Q ∧ ?R) ? (?P ∨ Q) ∧ (Q ∨ ?R) ∧ (?P ∨ R) ∧ (?Q ∨ R) ? ( ?P ∨ Q ∨ ?R ) ∧ ( ? P ∨ Q ∨ R ) ∧ ( P ∨ Q ∨ ? R ) ∧ (? P ∨ ? Q ∨ R ) ∧ ( P ∨ ? Q ∨ R ) ? ∏(1, 2, 4,5, 6)（2） ( P ∧ Q ) ∨ (?P ∧ Q ) ∨ ( P ∧ ?Q )? (( P ∨ ?P) ∧ Q) ∨ ( P ∧ ?Q) ? Q ∨ ( P ∧ ?Q ) ? ( P ∨ Q) ∧ (Q ∨ ?Q) ? P∨Q ? ∏(0)（3） ( P ∧ Q ) ∨ (?P ∧ Q ∧ R )? ( P ∨ ?P) ∧ ( P ∨ Q) ∧ ( P ∨ R) ∧ (?P ∨ Q) ∧ (Q ∨ Q) ∧ (Q ∨ R) ? ( P ∨ Q) ∧ ( P ∨ R) ∧ (?P ∨ Q) ∧ Q ∧ (Q ∨ R) ? ( P ∨ Q ∨ R ) ∧ ( P ∨ Q ∨ ?R ) ∧ ( P ∨ ?Q ∨ R ) ∧ (?P ∨ Q ∨ R ) ∧ (? P ∨ Q ∨ ? R ) ? ∏(0,1, 2, 4,5)2.求下列公式的主析取范式和主合取范式： （1） (?P ∨ ?Q ) → ( P ? ?Q ) 合取范式：? ( P → ?Q) → (( P → ?Q) ∧ (?Q → P )) ? ?( P → ?Q) ∨ (( P → ?Q) ∧ (?Q → P )) ? ?( P → ?Q) ∨ (?Q → P ) ? ?(?P ∨ ?Q) ∨ ( P ∨ Q) ? ( P ∧ Q) ∨ P ∨ Q ? P∨Q ? ∏(0)析取范式： ∏(1, 2,3) （2） P ∨ (?P → (Q ∨ (?Q → R ))) 合取范式：? P ∨ ( P ∨ (Q ∨ (Q ∨ R))) ? P∨Q∨ R ? ∏(0)析取范式： ∑(1, 2,3) （3） ( P → (Q ∧ R )) ∧ (?P → (?Q ∧ ?R )) 合取范式：? (?P ∨ (Q ∧ R)) ∧ ( P ∨ (?Q ∧ ?R)) ? ( ?P ∨ Q ) ∧ ( ?P ∨ R ) ∧ ( P ∨ ?Q ) ∧ ( P ∨ ?R ) ? ( ?P ∨ Q ∨ R ) ∧ ( ?P ∨ Q ∨ ? R ) ∧ ( ? P ∨ ? Q ∨ R ) ∧ ( P ∨ ? Q ∨ R ) ∧ ( P ∨ ? Q ∨ ? R ) ∧ ( P ∨ Q ∨ ? R ) ? ∏(1, 2,3, 4,5, 6)析取范式： ∑(0, 7) （4） ( P ∧ ?Q ∧ S ) ∨ (?P ∧ Q ∧ R ) 析取范式：? ( P ∧ ?Q ∧ R ∧ S ) ∨ ( P ∧ ?Q ∧ ?R ∧ S ) ∨ ( ?P ∧ Q ∧ R ∧ S ) ∨ ( ?P ∧ Q ∧ R ∧ ?S ) ? ∑(6, 7,9,11)合取范式： ∏(0,1, 2,3, 4,5,8,10,12,13,14,15)P25 习题 1.试用真值表法证明： A ∧ E 不是 A ? B , B ? (C ∧ D ) , C ? ( A ∨ E ) 和 A ∨ E 的有效 结论。 解：构造真值表如下： ABCDE
A? B1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0B ? (C ∧ D)1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1C ? ( A ∨ E)1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1A∨ E0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1A∧ E0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 11 1 1 1 1 1 0 0 0 0 0 0 0 0 1 10 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1第 6，31 行前提取值均为 1 时，结论为 0。故命题得证。 在下列情况下， 试确定结论 C 是否有效 （可以使用真值表法证明。 ） 2. H1 ，H 2 和 H 3 是前提。 （1） H1 : P → QC : P → ( P ∧ Q)证明：真值表如下： PQ 00 01 10 11 （2） H1 : ?P ∨ QP→Q1 1 0 1P → ( P ∧ Q)1 1 0 1第 1，2，4 行当前提取值为 1 时，结论都为 1。故结论 C 是有效的。H 2 : ?(Q ∧ ?R) H 3 : ?R C : ?P证明： {1} {1} {3} （1） （2） （3）?(Q ∧ ?R) ?Q ∨ R ?RP 规则 T 规则， （1） ， E11 P 规则{1，3} {5}（4） （5）?Q ?P ∨ QT 规则， （2） ， （3） ， I9 P 规则 T 规则， （4） ， （5） ， E11{1，3，5}（6） 结论 C 是有效结论。?P（3） H1 : P → (Q → P )H2 : P → QC:R（4） H1 : P → QH2 : Q → RC:P→R证明： {1} {2} {1，2} {4} {1，2，4} {1，2，4} （1） （2） （3） （4） （5） （6）PP→Q Q Q→RP 规则（附加前提） P 规则 T 规则， （1） ， （2） ， I10 P 规则 T 规则， （3） ， （4） ， I10 （1） ， （5） CP 规则，RP→R3.不构成真值表证明：A ∨ C 不是 A ? ( B → C ) 、B ? (?A ∨ ?C ) 、C ? ( A ∨ ?B ) 和 B 的有效结论。 证明： （1） （2） （3） （4） （5） （6） （7） （8）BB ? ( ?A ∨ ?C )?A ∨ ?CP 规则 P 规则 T 规则，(1)(2) P 规则 T 规则,(1)(4) T 规则(5) T 规则(3) T 规则(6)(7)A ? (B → C)A?C( A ∧ C ) ∨ ( ?A ∧ ?C )?( A ∧ C )?A ∧ ?C（9）?( A ∨ C )T 规则(8)因此， ?( A ∨ C ) 是题目的有效结论， A ∨ C 不是。 4.使用推理的方法证明： L ∨ M 是 P ∧ Q ∧ R 和 (Q ? R ) → ( L ∨ M ) 的有效结论。 证明： {1} {1} {1} {1} {1} {1} {1} {1} {9} {1，9} （1） （2） （3） （4） （5） （6） （7） （8） （9） （10）P∧Q∧ RP 规则 T 规则， （1） ， I2 T 规则， （2） ， I4 T 规则， （3） ， E27 T 规则， （1） ， I2 T 规则， （5） ， I4 T 规则， （6） ， E27 T 规则， （4） ， （7） ， E26R?Q ∨ R Q→R Q ?R ∨ Q R→Q Q?R(Q ? R) → ( L ∨ M ) P 规则L∨MT 规则， （8） ， （9） ， I105.不构成真值表证明下列命题公式不能同时全为真。 （1） P ? Q ， Q → R ， ?R ∨ S ， ?P → S ， ?S 证明： {1} {2} {1，2} {4} {1，2，4} {6} {1，2，4，6} {8} （1） （2） （3） （4） （5） （6） （7） （8）?S ?P → SP 规则 P 规则 T 规则， （1） ， （2） ， I11 P 规则 T 规则， （3） ， （4） ， I10 P 规则 T 规则， （5） ， （6） ， I10 P 规则PP?Q Q Q→RR?R ∨ S(1，2，4，6，8) （9）ST 规则， （7） ， （8） ， I9推出结论与前提矛盾，因此命题公式不能同时为真。 （2） R ∨ M ， ?R ∨ S ， ?M ， ?S 证明： {1} {2} {1，2} {4} {1，2，4} （1） （2） （3） （4） （5）?M R∨M R?R ∨ SP 规则 P 规则 T 规则， （1） ， （2） ， I9 P 规则 T 规则， （3） ， （4） ， I9S推出的结论与命题公式 ?S 矛盾，因此命题公式不能同时为真。 6. H1 ， H 2 和 H 3 是前提，根据推理规则断定，在下列情况下 C 是否是有效结论。 （1） H1 : P ∨ QH2 : P → R H3 : Q → RC:R证明： {1} {2} {1，2} {4} {1，2，4} {6} {1，2，4，6} {1，2，4，6} （1） （2） （3） （4） （5） （6） （7） （8）?R P→R ?PP∨Q Q Q→RP 规则（假设前提） P 规则 T 规则， （1） ， （2） ， I11 P 规则 T 规则， （3） ， （4） ， I9 P 规则 T 规则， （5） ， （6） ， I10 T 规则， （1） ， （7） ， I16 F 规则， （1） ， （8）R ?R ∧ R R{1，2，4，6} （9） 因此 C 是有效结论。 （2） H1 : P → (Q → R )H2 : RC:P证明：因为 P → (Q → R ) ? ?P ∨ ?Q ∨ R ，再由前提 H 2 : R ，得到 ?P 、?Q 的值任意， 即 P 、 Q 的值任意。因此 C 不是有效结论。 7.证明下列结论的有效性。 （1） ?( P ∧ ?Q ) ， ?Q ∨ R ， ?R ? ?P 证明： （1） （2） （3） （4） （5） （6）?R?Q ∨ R ?Q ?( P ∧ ?Q) ?P ∨ QP 规则 P 规则 T 规则， （1） ， （2） ， I9 P 规则 T 规则， （4） ， E11 T 规则， （3） ， （5） ， I9?P（2） ( P ∧ Q ) → R ， ?R ∨ ?S ， ?S ? ?P ∨ ?Q 证明： （1） （2） （3） （4） （5） （6）S ?R ∨ ?S ?RP 规则 P 规则 T 规则（1） （2） P 规则 T 规则（3） （4） T 规则（5）( P ∧ Q) → R ?( P ∧ Q) ?P ∨ ?Q（3） ( P → Q ) → R ， R ∧ S ， Q ∧ T ? P 由 R ∧ S 得 R 为真， 再由 ( P → Q ) → R 得 ( P → Q ) 真假任意， 故无法推出 P 一定为真的结 论。 （题目有问题） 8.导出下列结论（如果需要，就是用规则 CP ） （1） ?P ∨ Q, ?Q ∨ R, R → S ? P → S 证明： （1） （2） （3） （4） P P 规则（假设前提） P 规则 T 规则（1） （2） P 规则?P ∨ QQ?Q ∨ R（5） （6） （7） （8）RT 规则（3） （4） P 规则 T 规则（5） （6） CP 规则（1） （7）R→SSP→S（2） P → Q ? P → ( P ∧ Q ) 证明： （1） （2） （3） （4） （5） P P 规则（假设前提） P 规则 T 规则（1） （2） T 规则（1） （3） CP 规则（1） （4）P→QQP∧Q P → ( P ∧ Q)（3） ( P ∨ Q ) → R ? ( P ∧ Q ) → R 证明： （1） （2） （3） （4） （5） （6） （7）P∧QP QP 规则（假设前提） T 规则（1） T 规则（1） T 规则（2） （3） P 规则 T 规则（4） （5） CP 规则（1） （6）P∨Q ( P ∨ Q) → RR( P ∧ Q) → R9.证明下列各式的有效性（如果需要，就使用间接证明法） 。 （1） ( R → ?Q ), R ∨ S , S → ?Q, P → Q ? ?P 证明： （1） （2） （3） （4） （5） （6） （7） （8） （9）??PPP 规则（假设前提） T 规则（1） P 规则 T 规则（2） （3） P 规则 T 规则（4） （5） P 规则 T 规则（6） （7 ） P 规则 T 规则（8） （9）P→QQS → ?Q?SR∨SRR → ?Q（10） ?Q（11） Q ∧ ?Q （12） ?P （2） S → ?Q, R ∨ S , ?R, P ? Q ? ?P 证明： （1） （2） （3） （4） （5） （6） （7） （8）T 规则（4） （10） F 规则（1） （11）??PPP 规则（假设前提） T 规则（1） P 规则 T 规则（2） （3） P 规则 T 规则（4） （5） P 规则 T 规则（6） （7 ） P 规则 T 规则（8） （9） F 规则（1） （10）P?QQS → ?Q?SR∨SR（9） ?R （10） R ∧ ?R （11） ?P（3） ?( P → Q ) → ?( R ∨ S ), ((Q → P ) ∨ ?R ), R ? P ? Q 证明： （1） （2） （3） （4） （5） （6） （7） （8） （9） R P 规则 P 规则 T 规则（1） （2） T 规则（1） P 规则 T 规则（4） （5） T 规则（6） T 规则（3） （7） T 规则（8）(Q → P) ∨ ?R Q→PR∨S?( P → Q) → ?( R ∨ S ) ??( P → Q) P→Q ( P → Q) ∧ (Q → P) P?Q第2章习题 P39 1.证明下列各式。谓词逻辑（1） (?x)(?A( x) → B ( x)) ， (?x)?B ( x) ? (?x) A( x) 证明： （1） （2） （3） （4） （5） （6）(?x)(?A( x) → B( x)) ?A(a ) → B (a ) (?x)?B( x) ?B ( a ) A(a ) (?x) A( x)P US， （1） P US， （3） T， （2） ， （4） ， EG， （5 ）（2） (?x) A( x) → (?x) B ( x) ? (?x)( A( x) → B ( x)) 证明： （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12）?(?x)( A( x) → B( x)) (?x)(?( A( x) → B( x))) (?x)( A( x) ∧ ?B( x)) (?x) A( x) ∧ (?x)?B( x) (?x) A( x) (?x)?B( x) (?x) A( x) → (?x) B( x) (?x) B( x) ?B ( a ) B(a) ?B ( a ) ∧ B ( a ) (?x)( A( x) → B( x))P（假设前提） T T T T T P T（5） （7） ES（6） US（8） T（9） （10） F（1） （11）（3） (?x)( A( x) → B ( x)) ， (?x)(C ( x) → ?B ( x)) ? (?x)(C ( x) → ?A( x)) 证明： （1）?(?x)(C ( x) → ?A( x))P（假设前提）（2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12）(?x)?(?C ( x) ∨ ?A( x)) C (a ) ∧ A(a ) C (a) A(a ) (?x)( A( x) → B( x)) A(a ) → B (a ) B(a) (?x)(C ( x) → ?B( x)) C ( a ) → ?B ( a ) ?B ( a ) B ( a ) ∧ ?B ( a )T， （1） US， （2） T， （3） T， （3） P US， （6） T， （5） ， （7） P US， （8） T， （4） ， （10） T， （8） ， （11）（4） (?x)( A( x) ∨ B ( x)), (?x)( B ( x) → ?C ( x)), (?x)C ( x) ? (?x) A( x) 证明： （1） （2） （3） （4） （5） （6） （7） （8） （9）(?x)C ( x) C ( x) (?x)( B( x) → ?C ( x)) B ( x ) → ?C ( x ) ?B ( x ) (?x)( A( x) ∨ B( x)) A( x) ∨ B( x) A( x) (?x) A( x)P US（1） P US（3） T（2） （4） P US（6） T（5） （7） UG（8）2.用 CP 规则证明下列各式。 （1） (?x)( P ( x) → Q ( x)) ? (?x) P ( x) → (?x)Q ( x)证明： （1） （2） （3） （4） （5） （6） （7）(?x) P( x) P( x) (?x)( P( x) → Q( x)) P( x) → Q( x) Q( x) (?x)Q( x) (?x) P( x) → (?x)Q( x)P（假设前提） US（1） P US（3） T（2） （4） UG（5） CP（1） （6）（2） (?x)( P ( x) ∨ Q ( x)) ? (?x) P ( x) ∨ (?x)Q ( x) 证明：由于 (?x) P ( x) ∨ (?x)Q ( x) ? ?(?x)(?Q ( x)) ∨ (?x) P ( x)? (?x)(?Q( x)) → (?x) P( x)因此，原题等价于证明 (?x)( P ( x) ∨ Q ( x)) ? (?x)(?Q ( x)) → (?x) P ( x) （1） （2） （3） （4） （5） （6） （7）(?x)(?Q( x)) ?Q ( x ) (?x)( P( x) ∨ Q( x)) P( x) ∨ Q( x) P( x) (?x) P( x) (?x)(?Q( x)) → (?x) P( x)P（假设前提） US（1） P US（3） T（2） （4 ） UG（5） CP（1） （6 ）3.将下列命题符号化并推证其结论。 （1）所有的有理数是实数，某些有理数是整数，因此某些实数是整数。 解：首先定义如下谓词：P ( x) : x 是有理数 R ( x) : x 是实数 I ( x) : x 是整数于是问题符号化为：(?x)( P( x) → R( x)),(?x)( P( x) ∧ I ( x)) ? (?x)( R( x) ∧ I ( x))推理如下： （1） （2） （3） （4） （5） （6） （7） （8） （9）(?x)( P( x) ∧ I ( x)) P(a) ∧ I (a) (?x)( P ( x) → R ( x)) P(a) → R(a) P(a) I (a) R(a) R(a) ∧ I (a) (?x)( R( x) ∧ I ( x))P ES（1） P US（3） T（2） T（2） T（4） （5） T（6） （7） EG（8）（2）任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自 行车，有的人不爱骑自行车，因而有的人不爱步行。 解：首先定义如下谓词：P ( x) : x 是人 F ( x) : x 喜欢步行 C ( x) : x 喜欢乘汽车 B( x) : x 喜欢骑自行车于是问题符号化为：(?x)( P ( x) ∧ F ( x) → ?C ( x)),(?x)( P ( x) → C ( x) ∨ B( x)), (?x)( P ( x) ∧ ?B ( x)) ? (?x)( P ( x) ∧ ?F ( x))推理如下： （1） （2） （3）(?x)( P( x) ∧ ?B( x)) P ( a ) ∧ ?B ( a ) P(a)P ES（1） T（2）（4） （5） （6） （7） （8） （9） （10） （11） （12） （13） （14） （15）?B ( a ) (?x)( P ( x) → C ( x) ∨ B( x)) P(a) → C (a) ∨ B(a ) C (a) ∨ B(a) C (a) (?x)( P ( x) ∧ F ( x) → ?C ( x)) P ( a ) ∧ F ( a ) → ?C ( a ) ?( P(a ) ∧ F (a )) ?P ( a ) ∨ ?F ( a ) ?F ( a ) P ( a ) ∧ ?F ( a ) (?x)( P( x) ∧ ?F ( x))T（2） P US（5） T（3） （6） T（4） （7 ） P US（9） T（8） （10） T（11） T（3） （12） T（3） （13） EG（14）（3）每个科学工作者都是刻苦钻研的，每个刻苦钻研而且聪明的科学工作者在他的事业中 都将获得成功。华为是科学工作者并且他是聪明的，所以，华为在他的事业中将获得成功。 解：首先定义如下谓词：P ( x) : x 是科学工作者 Q( x) : x 是刻苦钻研的 R ( x) : x 是聪明的 S ( x) : x 在他的事业中将获得成功定义个体 a：华为 于是命题符号化为：(?x)( P( x) → Q( x)),(?x)( P( x) ∧ Q( x) ∧ R ( x) → S ( x)), P(a) ∧ R(a ) ? S (a )推理如下： （1） （2）(?x)( P( x) → Q( x)) P(a) → Q(a)P US（1）（3） （4） （5） （6） （7） （8） （9） （10）P(a) ∧ R(a) P(a) R(a) Q(a) (?x)( P( x) ∧ Q( x) ∧ R ( x) → S ( x)) P (a ) ∧ Q(a ) ∧ R (a ) → S (a ) P(a ) ∧ Q(a ) ∧ R (a ) S (a)P T（3） T（3） T（2） （4） P US（7） T（3） （6） T（8） （9）（4）每位资深名士或是中科院院士或是国务院参事，所有的资深名士都是政协委员。张伟 是资深名士，但他不是中科院院士。因此，有的政协委员是国务院参事。 解：首先定义如下谓词：P ( x) : x 是资深名士 Q( x) : x 是中科院院士 R ( x) : x 是国务院参事 S ( x) : x 是政协委员定义个体 a：张伟 于是命题符号化为：(?x)( P( x) → Q( x) ∨ R( x)),(?x)( P( x) → S ( x)), P(a ) ∧ ?Q(a ) ? (?x)( S ( x) ∧ R ( x))推理如下： （1） （2） （3） （4） （5） （6）P ( a ) ∧ ?Q ( a ) P(a) ?Q ( a ) (?x)( P( x) → S ( x)) P(a) → S (a) S (a)P T（1） T（1） P US（4） T（2） （5 ）（7） （8） （9） （10） （11） （12）(?x)( P ( x) → Q( x) ∨ R ( x)) P(a) → Q(a ) ∨ R(a ) Q(a) ∨ R(a ) R(a) S (a) ∧ R(a) (?x)( S ( x) ∧ R( x))P US（7） T（2） （8） T（3） （9） T（6） （10） EG（11）（5）每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被 2 整除。并不是所有 的自然数都能被 2 所整除。因此，有的自然数是奇数。 解：首先定义如下谓词：N ( x) : x 是自然数 Q( x) : x 是奇数 O( x) : x 是偶数 P ( x) : x 能被 2 整除于是命题符号化为：(?x)( N ( x) → (Q( x)?O( x))),(?x)( N ( x) → (O( x) ? P ( x))), ?(?x)( N ( x) → P( x)) ? (?x)( N ( x) ∧ Q( x))推理如下： （1） （2） （3） （4） （5） （6） （7） （8）?(?x)( N ( x) → P( x)) (?x)( N ( x) ∧ ?P( x)) N ( a ) ∧ ?P ( a ) N (a) ?P ( a ) (?x)( N ( x) → (O( x) ? P ( x))) N (a ) → (O(a ) ? P (a )) O(a) ? P(a )P T（1） ES（2） T（3） T（3） P US（6） T（4） （7）（9） （10） （11） （12） （13） （14） （15）?O ( a ) (?x)( N ( x) → (Q( x)?O( x))) N (a ) → (Q(a )?O(a )) Q(a )?O(a ) Q(a) N (a) ∧ Q(a) (?x)( N ( x) ∧ Q( x))T（5） （8） P US（10） T（4） （11） T（9） （12） T（4） （13） EG（14）（6）如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过。有些 人未曾失败过，所以，有些人不怕困难。 解：首先定义如下谓词：P ( x) : x 是人 Q( x) : x 怕困难 R ( x) : x 曾获得成功 S ( x) : x 曾获得失败于是命题符号化为：(?x)( P( x) ∧ Q( x) → ?R ( x)),(?x)( P ( x) → ( R ( x) ∨ S ( x))), (?x)( P( x) ∧ ?S ( x)) ? (?x)( P( x) ∧ ?Q( x))推理如下： （1） （2） （3） （4） （5） （6） （7）(?x)( P( x) ∧ ?S ( x)) P ( a ) ∧ ?S ( a ) P(a) ?S ( a ) (?x)( P( x) → ( R( x) ∨ S ( x))) P(a ) → ( R (a ) ∨ S (a )) R(a) ∨ S (a)P ES（1） T（2） T（2） P US（5） T（3） （6）（8） （9） （10） （11） （12） （13） （14） （15）R(a) (?x)( P( x) ∧ Q( x) → ?R ( x)) P ( a ) ∧ Q ( a ) → ?R ( a ) ?( P(a ) ∧ Q(a )) ?P ( a ) ∨ ?Q ( a ) ?Q ( a ) P ( a ) ∧ ?Q ( a ) (?x)( P( x) ∧ ?Q( x))(?x) P( x) → Q( x) P( x) → Q( x)P US，1）T（4） （7） P US（9） T（8） （10） T（11） T（3） （12） T（3） （13） EG（14）4.下列推导步骤中哪个是错误的？ （1） 1） 2）解：错误。1）中改为 (?x)( P ( x) → Q ( x)) 。 （2） 1） 2）(?x)( P( x) ∨ Q( x)) P(a ) ∨ Q(b)P EG，1）解：错误。 (?x)( P ( x) ∨ Q ( x)) ? (?x) P ( x) ∨ (?x)Q ( x) ? P ( a ) ∨ Q (b) （3） 1） 2）P( x) → Q( x) (?x) P( x) → Q( x)P EG，1）解：错误。变量 x 不自由。 （4） 1） 2）P(a ) → Q(b) (?x)( P( x) → Q( x))P EG，1）解：错误。 5.试找出下列推导过程中的错误，并问结论是否有效？如果有效，写出正确的推导过程。 解：错误，第 2 行的 y 是泛指，第 4 行的 y 是特制 更改如下： （1）(?x) P( x)P（2） （3） （4） （5） （6）P( y ) (?x)( P( x) → Q( x)) P( y ) → Q( y ) Q( y ) (?x)Q( x)ES（1） P US（3） T（2） （4） EG（5）6.用构成推导过程的方法证明下列蕴含式。 （1） (?x) P ( x) → (?x)(( P ( x) ∨ Q( x)) → R ( x)),(?x) P( x), (?x)Q( x) ? (?x)(?y )( R( x) ∧ R( y ))证明：(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15)(?x) P( x) P P(a) ES , (1) (?x)Q( x) P Q(b) ES , (3) (?x) P( x) → (?x)(( P( x) ∨ Q( x)) → R( x)) P (?x)(( P( x) ∨ Q( x)) → R( x)) T , (1), (5) ( P(a ) ∨ Q(a )) → R(a ) US , (6) P(a) ∨ Q(a) T , (2) R(a) T , (7), (8) ( P(b) ∨ Q(b)) → R(b) US , (6) P(b) ∨ Q(b) R(b) R(a ) ∧ R(b) (?y )( R(a ) ∧ R( y )) (?x)(?y )( R( x) ∧ R( y )) T , (4) T , (10), (11) T , (9), (12) EG, (13) EG, (14)（2） (?x) P ( x) → (?x)Q ( x) ? (?x)( P ( x) → Q ( x)) 证明： （1） （2） （3） （4）(?x) P( x) → (?x)Q( x) ?(?x) P( x) ∨ (?x)Q( x) (?x)?P( x) ∨ (?x)Q( x) (?x)(?P( x) ∨ Q( x))P T（1） T（2） T（3）（5）(?x)( P( x) → Q( x))T（4）习题 P42 1.将下列公式化为前束范式。 （1） (?x)( P ( x) → (?y )Q ( y )) 解： (?x)( P ( x) → (?y )Q ( y ))? (?x)(?P( x) ∨ (?y )Q( y )) ? (?x)(?y )(?P( x) ∨ Q( y ))（2） (?x)(?y )((?z )( P ( x, y ) ∧ P ( y, z )) → (?u )Q( x, y, u )) 解：(?x)(?y )((?z )( P( x, y ) ∧ P( y, z )) → (?u )Q( x, y, u )) ? (?x)(?y )(?(?z )( P( x, y ) ∧ P( y, z )) ∨ (?u )Q( x, y, u )) ? (?x)(?y )((?z )(?P( x, y ) ∨ ?P( y, z )) ∨ (?u )Q( x, y, u )) ? (?x)(?y )(?z )(?u )(?P( x, y ) ∨ ?P( y, z ) ∨ Q( x, y, u ))（3） ?(?x)(?y ) A( x, y ) → (?x)(?y )( B ( x, y ) ∧ (?y )( A( y, x) → B ( x, y ))) 解：?(?x)(?y ) A( x, y ) → (?x)(?y )( B( x, y ) ∧ (?y )( A( y, x) → B( x, y ))) ? (?x)(?y ) A( x, y ) ∨ (?x)(?y )( B( x, y ) ∧ (?y )( A( y, x) → B( x, y ))) ? (?x)(?y ) A( x, y ) ∨ (?x)(?y )( B( x, y ) ∧ (?y )(?A( y, x) ∨ B( x, y ))) ? (?x)(?y ) A( x, y ) ∨ (?u )(?v)( B(u, v) ∧ (?z )(?A( z , u ) ∨ B(u , z ))) ? (?x)(?y )(?u )(?v)(?z )( A( x, y ) ∨ ( B(u, v) ∧ (?A( z , u ) ∨ B(u, z ))))2.求等价于下面公式的前束主析取范式与前束主合取范式。 （1） (?x) P ( x) ∨ (?x)Q( x) → (?x)( P ( x) ∨ Q( x)) 解：前束主析取范式：(?x) P( x) ∨ (?x)Q( x) → (?x)( P( x) ∨ Q( x))? ?((?x) P( x) ∨ (?x)Q( x)) ∨ (?x)( P( x) ∨ Q( x)) ? (?x)?P( x) ∧ (?x)?Q( x) ∨ (?x)( P( x) ∨ Q( x)) ? (?x)?P( x) ∧ (?x)?Q( x) ∨ (?y )( P( y ) ∨ Q( y )) ? (?x)(?y )(?P( x) ∧ ?Q( x) ∨ Q( y )) ? (?x)(?y )((?P( x) ∧ ?Q( x)) ∨ Q( y ))前束主合取范式：(?x) P( x) ∨ (?x)Q( x) → (?x)( P( x) ∨ Q( x))? ?((?x) P( x) ∨ (?x)Q( x)) ∨ (?x)( P( x) ∨ Q( x)) ? (?x)?P( x) ∧ (?x)?Q( x) ∨ (?x)( P( x) ∨ Q( x)) ? (?x)?P( x) ∧ (?x)?Q( x) ∨ (?y )( P( y ) ∨ Q( y )) ? (?x)(?y )(?P( x) ∧ ?Q( x) ∨ Q( y )) ? (?x)(?y )((?P( x) ∨ Q( y )) ∧ (?Q( x) ∨ Q( y )))（2） (?x)( P ( x) → (?y )((?z )Q ( x, z ) → ?(?z ) R ( x, y ))) 解：前束析取范式(?x)( P( x) → (?y )((?z )Q( x, z ) → ?(?y ) R( x, y ))) ? (?x)(?P( x) ∨ (?y )((?z )Q( x, z ) → ?(?y ) R( x, y ))) ? (?x)(?P( x) ∨ (?y )(?(?z )Q( x, z ) ∨ ?(?y ) R( x, y ))) ? (?x)(?P( x) ∨ (?y )(?(?z )Q( x, z ) ∨ ?(?u ) R( x, u ))) ? (?x)(?P( x) ∨ (?y )((?z )?Q( x, z ) ∨ (?u )?R( x, u ))) ? (?x)(?y )(?z )(?u )(?P( x) ∨ (?Q( x, z ) ∨ ?R( x, u ))) ? (?x)(?y )(?z )(?u )(?P( x) ∨ ?Q( x, z ) ∨ ?R( x, u ))由于 ?P ( x) ∨ ?Q ( x, z ) ∨ ?R ( x, u ) 是基本和，因此前束合取范式与前束析取范式一样：(?x)( P( x) → (?y )((?z )Q( x, z ) → ?(?z ) R( x, y ))) ? (?x)(?y )(?z )(?u )(?P( x) ∨ ?Q( x, z ) ∨ ?R( x, u ))（3） (?x) P ( x) → (?x)((?z )Q( x, z ) ∨ (?z ) R ( x, y, z )) 前束主析取范式：(?x) P( x) → (?x)((?z )Q( x, z ) ∨ (?z ) R( x, y, z ))? ?(?x) P( x) ∨ (?x)((?z )Q( x, z ) ∨ (?z ) R( x, y, z )) ? (?x)?P( x) ∨ (?u )((?z )Q(u , z ) ∨ (?v) R(u , y, v)) ? (?x)(?u )(?z )(?v)(?P( x) ∨ Q(u , z ) ∨ R(u , y, v))前束主合取范式与前束主析取范式相同。 （4） (?x)( P ( x) → Q ( x, y )) → ((?y ) P ( y ) ∧ (?z )Q( y, z )) 解：前束析取范式：(?x)( P ( x) → Q( x, y )) → ((?y ) P( y ) ∧ (?z )Q( y, z )) ? ?(?x)( P ( x) → Q( x, y )) ∨ ((?y ) P ( y ) ∧ (?z )Q( y, z )) ? ?(?x)(?P ( x) ∨ Q( x, y )) ∨ ((?y ) P( y ) ∧ (?z )Q( y, z )) ? (?x)( P( x) ∧ Q( x, y )) ∨ ((?y ) P( y ) ∧ (?z )Q( y, z )) ? (?x)( P( x) ∧ Q( x, u )) ∨ ((?y ) P( y ) ∧ (?z )Q(u, z )) ? (?x)(?y )(?z )(( P( x) ∧ Q( x, u )) ∨ ( P( y ) ∧ Q(u, z )))前束合取范式：(?x)( P( x) → Q( x, y )) → ((?y ) P( y ) ∧ (?z )Q( y, z )) ? (?x)(?y )(?z )(( P( x) ∧ Q( x, u )) ∨ ( P( y ) ∧ Q(u , z ))) ? (?x)(?y )(?z )(( P( x) ∨ ( P( y ) ∧ Q(u , z ))) ∧ (Q( x, u ) ∨ ( P( y ) ∧ Q(u , z )))) ? (?x)(?y )(?z )(( P( x) ∨ P( y )) ∧ ( P( x) ∨ Q(u, z )) ∧ (Q( x, u ) ∨ P( y )) ∧ (Q( x, u ) ∨ Q(u , z )))3.将下列公式化为斯柯林范式。 （1） (?x)( P ( x) → (?y )Q ( x, y ))? (?x)(?P( x) ∨ (?y )Q( x, y )) ? (?x)(?y )(?P( x) ∨ Q( x, y )) ? (?u )(?x)(?y )((?P( x) ∨ Q( x, y )) ∧ (G (u ) ∨ ?G (u ))) ? (?u )(?x)(?y )((?P( x) ∨ Q( x, y )) ∧ (G (u ) ∨ ?G (u ))) ? (?u )(?x)(?y )((((?P( x) ∨ Q( x, y )) ∧ (G (u ) ∨ ?G (u ))) ∧ ?H (u , x)) ∨ (?z ) H (u , z )) ? (?u )(?x)(?y )(?z )((((?P( x) ∨ Q( x, y )) ∧ (G (u ) ∨ ?G (u ))) ∧ ?H (u , x)) ∨ H (u , z ))（2） (?x)(?y )((?z )( P ( x, z ) ∧ P ( y, z )) → (?u )Q( x, y, u ))? (?x)(?y)(?(?z )( P( x, z ) ∧ P( y, z )) ∨ (?u )Q( x, y, u )) ? (?x)(?y)((?z )(?P( x, z ) ∨ ?P( y, z )) ∨ (?u )Q( x, y, u )) ? (?x)(?y)(?z )(?u )(?P( x, z ) ∨ ?P( y, z ) ∨ Q( x, y, u )) ? (?v)(?x)(?y)(?z )(?u )((?P( x, z ) ∨ ?P( y, z ) ∨ Q( x, y, u )) ∧ (G(v) ∨ ?G(v))) ? (?v)(?x)(?y)(?z )(?u )((((?P( x, z ) ∨ ?P( y, z ) ∨ Q( x, y, u )) ∧ (G(v) ∨ ?G(v))) ∧ ?H (v, x)) ∨ (?a) H (v, a)) ? (?v)(?x)(?y)(?z )(?u )(?a)((((?P( x, z ) ∨ ?P( y, z ) ∨ Q( x, y, u )) ∧ (G (v) ∨ ?G(v))) ∧ ?H (v, x)) ∨ H (v, a)) ? (?v)(?x)(?y)(?z )(?u )(?a)((((((?P( x, z ) ∨ ?P( y, z ) ∨ Q( x, y, u )) ∧ (G(v) ∨ ?G(v))) ∧ ?H (v, x)) ∨ H (v, a)) ∧ ?I (v, x, y)) ∨ (?b) I (v, x, b)) ? (?v)(?x)(?y)(?z )(?u )(?a)(?b)((((((?P( x, z ) ∨ ?P( y, z ) ∨ Q( x, y, u )) ∧ (G (v) ∨ ?G (v))) ∧ ?H (v, x)) ∨ H (v, a )) ∧ ?I (v, x, y )) ∨ I (v, x, b)) ? (?v )(?x )(?y )(?z )(?u )(?a )(?b)((((((((?P ( x, z ) ∨ ?P ( y , z ) ∨ Q ( x, y , u )) ∧ (G (v ) ∨ ?G (v ))) ∧ ?H (v, x )) ∨ H (v, a )) ∧ ?I (v, x, y )) ∨ I (v, x, b)) ∧ ?J (v, x, y , z )) ∨ (?c ) H (v, x, y , c )) ? (?v )(?x )(?y )(?z )(?u )(?a )(?b)(?c )((((((((?P ( x, z ) ∨ ?P ( y , z ) ∨ Q ( x, y , u )) ∧ (G (v ) ∨ ?G (v ))) ∧ ?H (v, x )) ∨ H (v, a )) ∧ ?I (v, x, y )) ∨ I (v, x, b)) ∧ ?J (v, x, y , z )) ∨ H (v, x, y , c ))第三章 集合论P451.解： (1) 集合可表示为 {x | ax + b = 0, a, b ∈ R} (2) 集合可表示为 {1, x ? 1, x + 1, x ? x + 1, x + x + 1, x ? 1, x + 1, x ? 1}2 2 3 3 6(3) 集合可表示为 {& x, y &| x + y & 0}2 2(4) 集合可表示为 {& x, y &| x & cos θ , y & sin θ , θ ∈ [0,2π ]} (5) 集合可表示为 {x | x = 5n, n ∈ I } 2.解： 设戏剧、音乐、广告分配的时间分别为 x, y, z (1) 可表示为 {& x, y, z &| x + y + z = 30, x, y, z = 5n, n ∈ I } (2) 可表示为 {& x, y, z &| x + y + z = 30, x & y, x, y, z = 5n, n ∈ I } (3) 可表示为 {& x, y, z &| x + y + z = 30, z = x ∨ z = y, x, y, z = 5n, n ∈ I } (4) 可表示为 {& x, y, z &| x + y + z = 30, y = 5, x, y, z = 5n, n ∈ I }P463. 给出集合 A 、 B 和 C 的例子，使得 A ∈ B ， B ∈ C 而 A ? C 。 解：A = {a} B = {{a}, b} C = {{{a}, b}, c}4. (1) 该命题为假命题 (2) 该命题为假命题 (3) 该命题为真命题 证明：任取 x ∈ A ，由于 A ? B ，所以必有 x ∈ B 。又 B ? C ，所以必有 x ∈ C 。 即对于任意的 x ∈ A ，都有 x ∈ C ，所以如果 A ? B 且 B ? C ，则 A ? C 。 (4) 该命题为假命题 (5) 该命题为假命题。 5. 解：可能。若 A = {1}, B = {1,2,{1}} ，则 A ? B 且 A ∈ B 。 6.(1) {a,{a}} 解：设 A = {a,{a}} 则 ρ ( A) = {?,{a},{{a}},{a,{a}}} (2) {{1,{2,3}}} 解：设 A = {{1,{2,3}}} 则 ρ ( A) = (3) {?, a,{b}} 解：设 A = {?, a,{b}} 则 ρ ( A) = {?,{?},{a},{b},{?, a},{?,{b}}, {a,{b}}, {?, a,{b}}} (4) ρ (?) 解：设 A = ρ (?) = {?} 则 ρ ( A) = {?,{?}} (5) ρ ( ρ (?)) 解：设 A = ρ ( ρ (?)) = {?,{?}} 则 ρ ( A) = {?,{?},{{?}}, {?,{?}}}{?,{{1,{2,3}}}}7. 解： A = {?}ρ ( A) = {?,{?}} B = ρ ( ρ ( A)) = {?,{?},{{?}},{?,{?}}}(1) ? ∈ B ， ? ? B (2) {?} ∈ B ， {?} ? B (3) {{?}} ∈ B ， {{?}} ? B8.证明：充分性： ?{{a},{a, b}} = {{c},{c, d }} ，∴{a} = {c},{a, b} = {c, d } ∴ a = c, b = d充分性得证。 必要性：? a = c, b = d∴{a} = {c},{a, b} = {c, d } {{a},{a, b}} = {{c},{c, d }}, b} = {c, d }必要性得证。 9. （1）解：子集个数 21012101 （2）解：元素的奇数的子集个数为 = 2100 2（3）解：不会有 102 个元素的子集。 10. 解：把 17 化为二进制，是 ， B17 把 31 化为二进制，是 ， B31= {a4 , a8} ； = {a4 , a5 , a6 , a7 , a8}{a2 , a6 , a7 } ，编码为 ，为 B70 {a1 , a8 } ，编码为 ，为 B129P531.解： A = {0,1,2,3,4}B = {2,4,6}A ? B = {0,1,2,3,4,6} A ? B = {2,4}2. 解： A = {b, o, k}B = {b, l , a, c, k}A ? B = {b, l , a, c, k , o} A ? B = {b, k}3.解： A = {1,2,7,8}B = {1,2,3,4,5,6,7} D = {1,2,4,8,16,32,64}C = {0,3,6,9,12,15,18,21,24,27,30}(1) A ? ( B ? (C ? D)) = {0,1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64} (2) A ? ( B ? (C ? D)) = ? (3)A ? C = {0,1,2,3,6,7,8,9,12,15,18,21,24,27,30} B ? ( A ? C ) = {4,5}~ A ? B = {3,4,5,6} (4) ~ ( A ? B) ? D = {1,2,3,4,5,6,8,16,32,64}P534.证明：充分性：由于 ( A ? B ) ? C = A ? ( B ? C ) = ( A ? B ) ? ( A ? C ) 所以 C = A ? C ，即 C ? A 充分性得证。 必要性：由于 C ? A 所以 C = A ? C 所以 ( A ? B ) ? C = ( A ? B ) ? ( A ? C ) 必要性得证。 5. （1） ( A ? B ) ? C = A ? ( B ? C ) 证明：( A ? B) ? C = ( A? ~ B ) ? C = ( A? ~ B )? ~ C = A ? (~ B? ~ C ) = A? ~ ( B ? C ) = A ? (B ? C)上面是一种简单的方法，还可以利用文字叙述，任取 x 属于 ( A ? B ) ? C ，。。。。。证明。还有一种方法，就是利用第五章的特征函数证明，下面给出过程ψ ( A? B ) ?C= ψ ( A? B ) ? ψ ( A? B ) *ψ C = (ψ A ? ψ A *ψ B ) ? (ψ A ? ψ A *ψ B ) *ψ C = (ψ A ? ψ A *ψ B )(1 ? *ψ C ) = ψ A (1 ? ψ B )(1 ? *ψ C )ψ A ? ( B ?C )= ψ A ? ψ A *ψ B?C = ψ A ? ψ A * (ψ B + ψ C ? ψ B *ψ C ) = ψ A (1 ? (ψ B + ψ C ? ψ B *ψ C )) = ψ A (1 ? ψ B )(1 ? *ψ C )所以，ψ ( A? B )?C 从而可得， （2） ( A ? B ) ? C = ( A ? C ) ? B 证明：= ψ A ? ( B ?C )。( A ? B) ? C = ( A? ~ B ) ? C = A? ~ B? ~ C = A? ~ C ? ~ B = ( A ? C )? ~ B = ( A ? C) ? B（3） ( A ? B ) ? C = ( A ? C ) ? ( B ? C ) 证明：( A ? C) ? (B ? C) = ( A? ~ C ) ? ( B? ~ C ) = ( A? ~ C )? ~ ( B? ~ C ) = ( A? ~ C ) ? (~ B ? C ) = ( A? ~ C ? ~ B ) ? ( A? ~ C ? C ) = A? ~ B? ~ C = ( A ? B )? ~ C = ( A ? B) ? C因此，6.解: ? ? {?} = ?{?} ? {?} = {?} {?,{?}} ? ? = {?,{?}} {?, {?}} ? {?} = {{?}}7. (1) 证明： ① 证明 A ? B ? 。充分性：若 A ? B ，则若 x ∈ A ，那么必有 x ∈ B 。因此，若 x ? B ，则必有 x ? A ， 即若 ，则有 ，即 ，则若 ； ，则有 ，即若 x ? B ，则必有 x ? A 。那么，必要性：若若 x ∈ A ，那么必有 x ∈ B ，即 A ? B ； 由以上两点可知： A ? B ? ② 证明： A ? B ? 充分性：若 x ∈ A ? B ，那么有 x ∈ A 或 x ∈ B 。 若 x ∈ A ，则由 A ? B 可知，必有 x ∈ B ，所以若 x ∈ A ? B ，必有 x ∈ B ，即 A? B ? B ； 若 x ∈ B ，那么必有 x ∈ A ? B ，即 B ? A ? B ，所以 必要性：因为 要性得证； 由以上两点可知： ③ 证明： A ? B ? 充分性：若 x ∈ A ? B ，那么必有 x ∈ A ，即 A ? B ? A ； 若 x ∈ A ，那么由 A ? B 可知，必有 x ∈ B ，所以 x ∈ A ? B ，即 A ? A ? B ， 所以， 必要性： 因为 由以上两点可知， 由以上三点可知， ； ， 所以对于任意的 x ∈ A ， 必有 x ∈ A ? B ， 。 。 ， 所以 A ? B ； ，所以，对于任意的 x ∈ A ? B ，必有 ，充分性得证； ，所以 A ? B ，必 。(2) ① 证明: A ? B = ? ? 充分性：因为 A ? B = ? ，所以对于任意的 x ，若 x ∈ A ，则必有 x ? B ，即 所以 ； ，所以对于任意的 x ，若 x ∈ A ，则必有 ，即 x ? B ，所以 ，必要性：因为A? B = ? ；由以上两点可知： A ? B = ? ? ② 证明： A ? B = ? ? 充分性：因为 A ? B = ? ，所以对于任意的 x ，若 x ∈ B ，则必有 x ? A ，即 所以 ； ，所以对于任意的 x ，若 x ∈ B ，则必有 ，即 x ? A ，所以 ，必要性：因为A? B = ? ；由以上两点可知： A ? B = ? ? 由上可知： . .(3) ① 证明： 充分性：因为 所以 ； ，必有 ； ，所以若 x ? A ，则必有 x ∈ B ，即若 ，则必有 x ∈ B ，必要性：因为 由以上两点可知： ② 证明： 充分性：因为 所以 ；，所以若 x ? B ，则必有 x ∈ A ，即若，则必有 x ∈ A ，必要性：因为，必有；由以上两点可知： 由上可知：. .。(4) 证明： 充分性：由于 所以 必要性： 所以 因为 又 所以 由上可知： 。 。 ，所以 ，所以 ，所以8. (1) 解：不一定。 若 B ? A, C ? A ，此时有 A ? B = A ? C = A ，但 B ≠ C 。 (2) 解：不一定。 若 A ? B, A ? C ，此时有 A ? B = A ? C = A ，但 B ≠ C 。 (3) 解：一定有。 9. （1） ( A ? B ) ? ( A ? C ) = AA 。也就是 A ? B 解：由于 ( A ? B ) ? ( A ? C ) = A且 A ? C = A ，因此必有 A ? B =并且 A ? C=?= ?。（2） ( A ? B ) ? ( A ? C ) = ? 解：由于?且 A?C = ? 。也就是 A ? ，因此必有 A ? B =B 并且A?C。（3） ( A ? B ) ? ( A ? C ) = ? 解：( A ? B) ? ( A ? C ) = ( A? ~ B ) ? ( A? ~ C ) = A? ~ B? ~ C = A? ~ ( B ? C )因此， （4） ( A ? B )
( A ? C ) = ? 解： 意味着 A ? ( B ? C )( A ? B)
( A ? C ) = ( A? ~ B )
( A? ~ C ) = ( A? ~ B? ~ ( A? ~ C )) ? ( A? ~ C ? ~ ( A? ~ B )) = ( A? ~ B ? (~ A ? C )) ? ( A? ~ C ? (~ A ? B)) = ( A? ~ B ? C ) ? ( A ? B? ~ C ) = A ? (B
C)? ，即 B=C； 两种可能，第一种 B
C =第二种， A ?B ? C 或者 A ? ~ ( B ? C )因此，此题答案为 B E E (2)= C或者A ? B ? C或者A ? ~ ( B ? C ) 。10. (1)B A A C C11. （1） A ? ( B
= C ) ( A ? B)
( A ? C ) 证明：( A ? B)
( A ? C ) = ( A ? B? ~ ( A ? C )) ? ( A ? C ? ~ ( A ? B)) = ( A ? B ? (~ A? ~ C )) ? ( A ? C ? (~ A? ~ B)) = ( A ? B? ~ A) ? ( A ? B? ~ C ) ? ( A ? C ? ~ A) ? ( A ? C ? ~ B ) = ( A ? B? ~ C ) ? ( A ? C ? ~ B) = A ? (( B? ~ C ) ? (C ? ~ B )) = A ? (B
C)因此， （2） A ? ( B
= C ) ( A ? B)
( A ? C ) 注意：这个题目本身不正确，举例如下：全集为{1，2，3}，A={1}，B={2},C={3} 则 A ? (B
C) = {1, 2,3} ， ( A ? B)
( A ? C ) = {2,3} ，不相等。 。P571.解： 设 A，B，C 分别表示参加足球队、篮球队和棒球队的队员的集合A? B ?C = 3A ? B ? C = A + B + C ? | A ? B | ? | A ? C | ? | B ? C | + | A ? B ? C |? | A ? B | + | A ? C | + | B ? C |= A + B + C + | A ? B ? C | ? A ? B ? C = 38 + 15 + 20 + 3 ? 58 = 18即同时参加两个对的队员共有 18 个。 2. 解：设 A，B，C 分别表示读甲种、乙种、丙种杂志的学生的集合。 (1) A ? B ? C = 10%A = 60%B = 50% B = 50% A ? C = 30%A ? B = 30%B ? C = 30%A ? B? ~ C + | A ? C ? ~ B | + | B ? C ? ~ A |= A ? B + B ? C + A ? C ? 3 A ? B ? C = 30% + 30% + 30% ? 3 *10% = 60%所以确定读两种杂志的学生的百分比为 60%。 (2)~ A? ~ B ? ~ C = 100% ? ( A ? C ? ~ B | + | B ? C ? ~ A | + | A ? B? ~ C | + A ? B ? C ) = 100% ? (60% + 10%) = 30%所以不读任何杂志的学生的百分比为 30%。 3.解：设 A，B，C 分别表示骑木马、坐滑行轨道和乘宇宙飞船的儿童集合。 由公园的总收入知， |A | + | B | + |= C | 70 / 0.5 = 140| A ? B ? C |= 20 | A ? B ? ~ C | + | A? ~ B ? C | + |~ A ? B ? C | + | A ? B ? C |= 55| A? B|+| A?C |+| B ?C | = 3 | A ? B ? C | + | A ? B ? ~ C | + | A? ~ B ? C | + |~ A ? B ? C | 因此， = 55 + 2 | A ? B ? C | = 55 + 40 = 95没有坐过任何一种的儿童总数为|~ A? ~ B ? ~ C | = 75? | A ? B ? C | = 75 ? (| A | + | B | + | C | ? | A ? B | ? | A ? C | ? | B ? C | + | A ? B ? C |) = 75 ? (140 ? 95 + 20) = 10答：一共 10 个儿童没有坐过其中任何一种游乐设备。 4.解：用 A，B 分别表示在第一次考试和第二次考试中得 A 的学生的集合。 (1) A = 26| B |= 21又 ~ A? ~ B + | A ? B |= 50 ，则~ A? ~ B = 50? | A ? B |= 50 ? (| A | + | B | ? | A ? B |) = 50 ? (26 + 21? | A ? B |) = 17 ?| A ? B |= 14所以有 14 个学生两次考试都取得 A。 (2) A = 40B = 40~ A? ~ B = 4又 ~ A? ~ B + | A ? B |= 50 ，则| A ? B |= 46 =| A | + | B | ? | A ? B | ?| A ? B |= 34所以有 34 个学生在两次考试中都取得 A。A =| A? ~ B | + | A ? B | ?| A? ~ B |=| A | ? | A ? B |= 40 ? 34 =6所以有 6 个学生仅在第一次考试中取得 A。B =| B? ~ A | + | A ? B |?| B? ~ A |=| B | ? | A ? B | = 40 ? 34 =6所以有 6 个学生仅在第二次考试中取得 A。 5. 解：设 A，B，C 分别是学习数学、物理、生物的大一学生集合。 由题意可知，| A | 67,| = = B | 47,| = C | 95, | A ? B | 28,| A ? C | 26,| B ? C | 27, = = = |~ A? ~ B? ~ C |= 50|~ A? ~ B ? ~ C | = 200? | A ? B ? C | = 200 ? (| A | + | B | + | C | ? | A ? B | ? | A ? C | ? | B ? C | + | A ? B ? C |) = 200 ? (67 + 47 + 95 ? 26 ? 27 ? 28+ | A ? B ? C |) = 50解方程，得| A ? B ? C | =22因此，一共有 22 人三门功课都学。数学 35 6 14 物理 22 5 64 生物 4E 50P591. （1） A × {1} × B 解： A × {1} × B ={&0,1,1&,&0,1,2&,&1,1,1&,&1,1,2&} （2） A × B2解A2 × B = {& 0, 0,1 &, & 0,1,1 &, & 1, 0,1 &, & 1,1,1 &, & 0, 0, 2 &, & 0,1, 2 &, & 1, 0, 2 &, & 1,1, 2 &}（3） ( B × A)2解： B × A = {& 1, 0 &, & 1,1 &, & 2, 0 &, & 2,1 &}( B × A) 2 = {&& 1, 0 &, & 1, 0 &&, && 1, 0 &, & 1,1 &&, && 1, 0 &, & 2, 0 &&, && 1, 0 &, & 2,1 &&, && 1,1 &, & 1, 0 &&, && 1,1 &, & 1,1 &&, && 1,1 &, & 2, 0 &&, && 1,1 &, & 2,1 &&, && 2, 0 &, & 1, 0 &&, && 2, 0 &, & 1,1 &&, && 2, 0 &, & 2, 0 &&, && 2, 0 &, & 2,1 &&, && 2,1 &, & 1, 0 &&, && 2,1 &, & 1,1 &&, && 2,1 &, & 2, 0 &&, && 2,1 &, & 2,1 &&}P602. 解： X× Y 表示在在笛卡尔坐标系中， ?3 ≤ x ≤ 2 且 ?2 ≤ y ≤ 0 的矩形区域内的点集。12．第 60 页第 3 题 （1） ( A ? B ) × (C ? D ) = ( A × C ) ? ( B × D) 证明：任取 &x, y &∈ ( A ? B) × (C ? D) ,有& 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) ?& x, y &∈ A × C ∧ & x, y &∈ B × D ?& x, y &∈ ( A × C ) ? ( B × D)由&x, y & 取值的任意性知，。（2）当且仅当才，才有 ( A ? B ) ? C = A ? ( B ? C ) 证明： 当 C ? A 时， A ? C = A ，于是 = ( A ? B) ? C (= A ? C) ? (B ? C) A ? (B ? C) 。当 ( A ? B ) ? C = A ? ( B ? C ) 时， 任取 x ∈ C ，可知 x ∈ ( A ? B ) ? C ，由 于是得到 x ∈ A 。所以， 。 知 x ∈ A ? (B ? C) ，3. (1) 证明： 任取 & x, y &?& x, y &∈ ( A × C ) & (B × D )? (& x, y &∈ A × C ) ∧ (& x, y &∈ B × D )? (x ∈ A ∧ y ∈ C ) ∧ ( x ∈ B ∧ y ∈ D)& x, y &∈ ( A & B) × (C & D) ? ( x ∈ A & B ) ∧ ( y ∈ C & D ) ? (x ∈ A ∧ x ∈ B ) ∧ ( y ∈ C ∧ y ∈ D )所以 ( A ? B ) × (C ? D) ? ( A × C ) ? (B × D )? x, y &∈ ( A × C ) ? (B × D ) ? (? x, y &∈ A ? C ) ∧ (? x, y &∈ B ? D) ? ( x ∈ A ∧ y ∈ C ) ∧ ( x ∈ B ∧ y ∈ D) 任取 ? ( x ∈ A ∧ x ∈ B ) ∧ ( y ∈ C ∧ y ∈ D) ? (x ∈ A ? B ) ∧ ( y ∈ C ? D) ?? x, y &∈ ( A ? B) × (C ? D)所以 ( A × C ) ? (B × D ) ? ( A ? B ) × (C ? D ) 故 ( A ? B ) × (C ? D ) = ( A × C ) ? (B × D ) (2) 证明： 充分性：由于 ( A ? B ) ? C = A ? ( B ? C ) = ( A ? B ) ? ( A ? C ) 所以 充分性得证。 必要性：由于 所以 所以 ( A ? B ) ? C = ( A ? B ) ? ( A ? C ) 必要性得证。 4.证明： 必要性：若 A = ? ， A × B = B × A = ? ； 同理，若 B = ? ， A × B = B × A = ? ； 若 A = B ，则显然有 A × B = B × A ； 必要性得证。 ，即充分性性：由于 A × B = B × A 所以对于任意的 & x, y &∈ A × B ,必有 & x, y &∈ B × A& x, y &∈ A × B ? x ∈ A ∧ y ∈ B& x, y &∈ B × A ? x ∈ B ∧ y ∈ A即若 x ∈ A 则必有 x ∈ B ； 若 y∈B， 则必有 y ∈ A ， 所以当 A ≠ ?, B ≠ ? 时，A= B；充分性得证。 5, （1） ( A ? B ) × (C ? D ) = ( A × C ) ? ( B × D) 解：任取 &x, y &∈ ( A ? B) × (C ? D) ,有& x, y &∈ ( A ? B) × (C ? D) ? x ∈ ( A ? B ) ∧ y ∈ (C ? D) ? ( x ∈ A ∨ x ∈ B) ∧ ( y ∈ C ∨ y ∈ D) ? ( x ∈ A ∧ ( y ∈ C ∨ y ∈ D )) ∨ ( x ∈ B ∧ ( y ∈ C ∨ y ∈ D )) ? ( x ∈ A ∧ y ∈ C ) ∨ ( x ∈ A ∧ y ∈ D) ∨ ( x ∈ B ∧ y ∈ C ) ∨ ( x ∈ B ∧ y ∈ D) ?& x, y &∈ ( A × C ) ? ( A × D) ? ( B × C ) ? ( B × D)选择 A={1}，B={2}，C={a}，D={b} 则 ( A ? B ) × (C ? D ) = {& 1, a &, & 1, b &, & 2, a &, & 2, b &}( A × C ) ? ( B × D) = {& 1, a &, & 2, b &}因此该等式不成立。 （2） ( A ? B ) × (C ? D ) = ( A × C ) ? ( B × D ) 解：任取 &x, y &∈ ( A ? B) × (C ? D) ,有& x, y &∈ ( A ? B) × (C ? D) ?& 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) ? ( x ∈ A ∧ y ∈ C ) ∧ ( x ? B ∧ y ? D) ? ( x ∈ A ∧ y ∈ C ) ∧ ?( x ∈ B ∨ y ∈ D)选择 A={1，2}，B={1}，C={a，b}，D={a}( A ? B) × (C ? D) =& { 2, b &} ( A × C ) ? ( B × D) = {& 1, b &, & 2, a &, & 2, b &}因此，该等式不成立。 （3） ( A
D ) = ( A × C )
( B × D ) 解：设 A={1，2}，B={2}，C={3，4}，D={4} 则 ( A
D ) =& { 1,3 &}( A × C )
( B × D) = {& 1,3 &, & 1, 4 &, & 2,3 &}因此，该等式不成立。 （4） ( A ? B ) × C = ( A × C ) ? ( B × C ) 解：取 &x, y &∈ ( A ? B) × C ,有& x, y &∈ ( A ? B) × C ?& x, y &∈ ( A? ~ B) × C ? x ∈ ( A? ~ B) ∧ y ∈ C ? x ∈ A ∧ x ? B) ∧ y ∈ C ? (x ∈ A ∧ y ∈C) ∧ (x ? B ∨ y ?C) ? ( x ∈ A ∧ y ∈ C ) ∧ ?( x ∈ B ∧ y ∈ C ) ? (& x, y &∈ A × C ) ∧ (& x, y &? B × C ) ?& x, y &∈ ( A × C ? B × C )因此，该等式成立。 （5） ( A
B ) × C = ( A × C )
( B × C ) 解：任取取 &x, y &∈ ( A × C )
( B × C ) ,有& x, y &∈ ( A × C )
( B × C ) ? (( x ∈ A ∧ y ∈ C ) ∧ ?( x ∈ B ∧ y ∈ C )) ∨ (( x ∈ B ∧ y ∈ C ) ∧ ?( x ∈ A ∧ y ∈ C )) ? (( x ∈ A ∧ y ∈ C ) ∧ ( x ? B ∨ y ? C )) ∨ (( x ∈ B ∧ y ∈ C ) ∧ ( x ? A ∨ y ? C )) ? ( x ∈ A ∧ y ∈ C ∧ x ? B) ∨ ( x ? A ∧ x ∈ B ∧ y ∈ C ) ? (( x ∈ A ∧ x ? B) ∨ ( x ? A ∧ x ∈ B)) ∧ y ∈ C ? x ∈ (( A? ~ B) ? (~ A ? B)) ∧ y ∈ C ? x ∈ A
B ∧ y ∈C ?& x, y &∈ ( A
B) × C因此，该等式成立。第四章 二元关系P631． 给出下列关系 R 的所有序偶。 （1） A = {0,1,2}, B = {0,2,4}R = {? x, y &| x, y ∈ A ? B}解： A ? B = {0,2}R = {& 0,0 &, & 0,2 &, & 2,0 &, & 2,2 &} 1,2,3,4,5}, B = { 1,2,3} （2） A = {R = & x, y &| x ∈ A ∧ y ∈ B ∧ x = y 2解： R = {& 1,1 &, & 4,2 &}{}1,2,3,4} 到 B = {2,3,4}的二元关系，并且 2． 设 R1 和 R 2 都是从 A = {R 1 = {& 1,2 & ， & 2,4 & ， & 3,3 &} R 2 = {& 1,3 &, & 2,4 &, & 4,2 &}求 R1 ? R2 、 R1 ? R2 、 D(R1 ) 、 D(R2 ) 、 R (R1 ) 、 R (R2 ) 、 D(R1 ? R2 ) 、 R (R1 ? R2 ) 。 解： R1 ? R2 = {& 1,2 &, & 2,4 &, & 3,3 &, & 1,3 &, & 4,2 &}R1 & R2 = {& 2,4 &} D(R1 ) = { 1,2,3} D ( R2 ) = { 1,2,4} R(R1 ) = {2,3,4} R(R2 ) = {2,3,4}D(R1 ? R2 ) = { 1,2,3,4} R(R1 ? R2 ) = {4,4}。L 和 D 都定义于 3． 用 L 表示“小于或等于” ，D 表示“整除” ，这里 xDy 表示“x 整除 y” 集合{1,2,3,4,5,6}上。试把 L 和 D 表示成集合，并求出 L ? D 。 解：?& 1,1 && 1,2 &, & 1,3 &, & 1,4 &, & 1,5 &, & 1,6 &, & 2,2 &, & 2,3 &, & 2,4 &, & 2,5 &, & 2,6 &,? ? ? L = ?& 3,3 &, ? ?& 3,4 &, & 3,5 &, & 3,6 &, & 4,4 &, & 4,5 &, & 4,6 &, & 5,5 &, & 5,6 &, & 6,6 & ? ? ??& 1,1 &, & 1,2 &, & 1,3 &, & 1,4 &, & 1,5 &, & 1,6 &, & 2,2 &, & 2,4 &, & 2,6 &, & 3,3 &, & 3,6 &,? D=? ? ? ?& 4,4 &, & 5,5 &, & 6,6 & ?& 1,1 &, & 1,2 &, & 1,3 &, & 1,4 &, & 1,5 &, & 1,6 &, & 2,2 &, & 2,4 &, & 2,6 &, & 3,3 &, & 3,6 &, & 4,4 &,? L&D = ? ? ? ?& 5,5 &, & 6,6 &4． 如果关系 R 和 S 都是自反的。证明： R ? S ， R ? S 也是自反的。 证明：设 R 是集合 A 上的二元关系，S 是集合 B 上的二元关系。 因为 R 和 S 都是自反的， 都有 & x, x &∈ R ， 所以对于 ?x ∈ A， 对于 ?x ∈ B， 都有 & x, x &∈ S 。 （1）设 x ∈ A ? B ，那么 x ∈ A 或 x ∈ B 。 若 x ∈ A ，有 & x, x &∈ R ，那么必有 & x, x &∈ R ? S 。 若 x ∈ B ，有 & x, x &∈ S ，那么必有 & x, x &∈ R ? S 。 因此，当 x ∈ A ? B 时，必有 & x, x &∈ R ? S ， 所以 R ? S 也是自反的。 （2）设 x ∈ A ? B ，那么 x ∈ A且x ∈ B 因此 & x, x &∈ R 且 & x, x &∈ S ，即 ? x, x &∈ R ? S 。 所以 R ? S 也是自反的。5． 如果关系 R 和 S 都是自反的、对称的、可传递的，证明： R ? S 也是自反的、对称的和 可传递的。 证明：设 R 是集合 A 上的二元关系，S 是集合 B 上的二元关系。 ①自反性的证明如题 4。 ② 对于任意的 x, y ∈ A ? B ，若 ? x, y &∈ R ? S ， 那么 & x, y &∈ R 且 & x, y &∈ S 因为 R 和 S 都是对称的，所以 & y, x &∈ R 且 & y, x &∈ S ， 所以 ? y, x &∈ R ? S 。 即对于任意的 x, y ∈ A ? B ， 若 ? x, y &∈ R ? S ， 则必有 ? 所以 R ? S 是对称的。 ③ 对于任意 x, y, z ∈ A ? B ，若 ? x, y &∈ R ? S 且 ? y, z &∈ R ? S ，y , x &∈ R ? S，& y, z &∈ S 。 那么有 & x, y &∈ R, & y, z &∈ R且 & x, y &∈ S，因为 R 和 S 都是可传递的， 所以有 & x, z &∈ R 且 & x, z &∈ S ，即 ? x, z &∈ R ? S 。 即对于任意 x, y, z ∈ A ? B ，若 ? x, y &∈ R ? S 且 ? y, z &∈ R ? S ，都有? x, z &∈ R ? S 。所以 R ? S 是可传递的。1,2,3,4} 和 S 中的关系 R，证明 R 是不可传递的。求出一个关系 R1 ? R ， 6． 给定集合 S = {而 R1 是可传递的，能否再求出另外一个关系 R2 ? R 且 R2 是可传递的。 解：此题不正确，关系 R 没有给出1,2,...,10} 和 S 中的关系 R ， R = {& x, y &| x + y = 10}，关系 R 有哪几 7． 给定 集合 S = {种性质。 解：R 是不自反的，对称的，不可传递的。 不自反性： 当 x=5 时， & x, x &∈ R ；当 x 是集合 S 中的其他数时， & x, x &? R 因此，R 不是自反的，也是反自反的。 对称性：对于任意的 x, y ∈ S ，若有 & x, y &∈ R ， 那么 x + y = 10 ，则必有 y + x = 10 即 & y, x &∈ R 。 即对于任意的 x, y ∈ S ，若有 & x, y &∈ R ，则必有 & y, x &∈ R 。 所以 R 是对称的。 不可传递性：举反例即可。 由此可知， & 4,6 &∈ R 且 & 6,4 &∈ R ，但是 & 4,4 &? R 。 所以 R 是不可传递的。 8． 给出满足下列要求的二元关系的实例。 （1） 既是自反的又是反自反的。 （2） 既不是自反的又不是反自反的。 （3） 既是对称的又是反对称的。 （4） 既不是对称的又不是反对称的。 解： （1）空集上的二元关系。1,2} , R = 1,1 ，R 是集合 A 上的二元关系。 （2） A = {（3）空集上的二元关系。{ }1,2,3} , R = {& 1,1 &, & 1,2 &, & 2,1 &, & 1,3 &},R 是集合 A 上的二元关系。 （4） A = {P691． 给定集合 X = {0,1,2,3} ，R 是 X 中的关系，并可表示成R = {& 0,0 &, & 0,3 &, & 2,0 &, & 2,1 &, & 2,3 &, & 3,2 &}试画出 R 的关系图，并写出对应的关系矩阵。0 1 2 3 0 ?1 ? 解： M R = 1 0 ? 2 ?1 ? 3 ?0关系图如下：0 0 1? 0 0 0? ? 1 0 1? ? 0 1 0?01 321,2,3}，则集合 X 中有多少个二元关系。 2. 设集合 X = {解：有 232= 512 个二元关系。3.设 X 是具有 n 个元素的有穷集合，证明:X 中有 2 个二元关系。 证明：集合 X 中的每个二元关系都是 X × X 的子集， X 有 n 个元素， X × X 有 n 个元素，2n2ρ ( X × X ) 有 2n 个元素，每一个元素都是 X × X 的一个子集，也是一种二元关系，因而，2在 X 中有 2 个不同的二元关系。n21,2,3}。图 4-6 给出了 X 中的关系 R 的 12 个关系图。对于每个关系图， 4．给定集合 X = {写出相应的关系矩阵， 并证明被表达的关系是否是自反的或反自反的； 是否是对称的或反对 称的；是否是可传递的。 （a）自反的、不对称的、不可传递的； 其对应的关系矩阵为：1 1 0 MR =1 1 1 1 0 1（b）不自反的、反对称的、不可传递的； 其对应的关系矩阵为：1 1 0 MR = 0 0 1 1 0 0（c）自反的、对称的、可传递的；其对应的关系矩阵为：1 1 1 MR =1 1 1 1 1 1（d）自反的、不对称的、不可传递的； 其对应的关系矩阵为:1 1 0 MR = 0 1 1 1 1 1（e）不自反的、不对称的、不可传递的； 其对应的关系矩阵为：0 1 0 MR = 1 1 1 1 1 0（f）不自反的、对称的、不可传递的； 其对应的关系矩阵为：1 1 1 MR =1 0 0 1 0 0（g）自反的、反对称的、可传递的； 其对应的关系矩阵为：1 0 1 MR = 1 1 1 0 0 1（h）自反的、不对称的、不可传递的； 其对应的关系矩阵为：1 1 0 MR = 1 1 1 0 0 1（i）不自反的、对称的、可传递的；此题图有错误 其对应的关系矩阵为：0 1 1 MR = 1 1 1 1 1 1（j）自反的、反对称的、不可传递的； 其对应的关系矩阵为：1 0 1 MR = 1 1 0 0 1 1（k）自反的、反对称的、可传递的； 其对应的关系矩阵为：1 0 0 MR =1 1 0 1 0 1（l）不自反的、反对称的、可传递的。 其对应的关系矩阵为：0 0 1 MR = 1 1 1 0 0 15.给定集合 X = {0,1,2,3} ， R1 和 R2 是 X 中的关系，分别为R1 = {& i, j &| j = i + 1 ∨ j = i / 2} R2 = {& i, j &| i = j + 2}求出下列合成关系 。 （1） R1 ? R2 （2） R2 ? R1 （3） R1 ? R2 ? R1 （4） R13（5） R2 解： R13= {& 0,1 &, & 1,2 &, & 2,3 &, & 0,0 &, & 2,1 &} ，R2 = {& 2,0 &, & 3,1 &}（1） R1 ? R2 （2） R2= {& 1,0 &, & 2,1 &}? R1 = {& 2,0 &, & 2,1 &, & 3,2 &}（3） R1 ? R2 （4） R13? R1 = {& 1,0 &, & 1,1 &, & 2,2 &}= {& 0,0 &, & 0,1 &, & 0,2 &, & 0,3 &, & 1,2 &, & 2,1 &, & 2,3 &} =?（5） R236.设 R1 和 R2 是集合 X 中的二元关系。试证或反证下列命题： （1）如果 R1 和 R2 是自反的，则 R1 ? R2 也是自反的。 （2）如果 R1 和 R2 是反自反的，则 R1 ? R2 也是反自反的。（3）如果 R1 和 R2 是对称的，则 R1 ? R2 也是对称的。 （4）如果 R1 和 R2 是反对称的，则 R1 ? R2 也是反对称的。 （5）如果 R1 和 R2 是可传递的，则 R1 ? R2 也是可传递的。 由于 R1 和 R2 是自反的， 因此 & 解： （1） 证明： 任取 x ∈ X ， 可得 &x, x &∈ R1 ，& x, x &∈ R2 ，x, x &∈ R1 ? R2 ，由 x 取值的任意性可知， R1 ? R2 是自反的。{& 1,1 &} ，不是反 = {1,2,3}, R1 = {& 1,3 &}, R2 = {& 3,1 &} ，则 R1 ? R2 =（2）设 X 自反的。 （3）设 X= {1,2,3}, R1 = {& 1,2 &, & 2,1 &}, R2 = {& 3,2 &, & 2,3 &} ，则R1 ? R2 = {& 1,3 &} ，不是对称的。（4）设 X= {1,2,3}, R1 = {& 1,2 &, & 3,1 &}, R2 = {& 1,1 &, & 2,3 &} ，则R1 ? R2 = {& 1,3 &, & 3,1 &} ，不是反对称的。（5）设 X= {1,2,3,4,5}, R1 = {& 1,2 &, & 2,3 &, & 1,3 &, & 5,4 &}, R2 = {& 2,3 &,& 3,5 &, & 2,5 &, & 4,4 &} ，则 R1 ? R2 = {& 1,3 &, & 1,5 &, & 2,5 &, & 5, 4 &} ，不可传递。7.设 R1 ， R2 和 R3 是集合 X 中的二元关系。试证明：若 R1 ? R2 ，则有 （1） R1 ? R3 ? R2 ? R3（2） R3 ? R1 ? R3 ? R2 证明： （1）任取 &x, z &∈ R1 ? R3 ，则一定存在某一个 y ∈ X，使得 &x, y &∈ R1 ，& y, z &∈ R3 ，由 R1 ? R2 知，(?y )(& x, y &∈ R1 ∧ & y, z &∈ R3 ) ? (?y )(& x, y &∈ R2 ∧ & y, z &∈ R3 ) ?& x, z &∈ R2 ? R3根据 &x, z & 取值的任意性，问题得证， R1 ? R3 ? R2 ? R3 。x, z &∈ R3 ? R1 ，则一定存在某一个 y ∈ X，使得 &（2）任取 &x, y &∈ R3 ，& y, z &∈ R1 ，由 R1 ? R2 知，(?y )(& x, y &∈ R3 ∧ & y, z &∈ R1 ) ? (?y )(& x, y &∈ R3 ∧ & y, z &∈ R2 ) ?& x, z &∈ R3 ? R2根据 &x, z & 取值的任意性，问题得证， R3 ? R1 ? R3 ? R2 。8.试证明定理 4.4.1 的（2），（3），（4）。 （2）见书本 67 页 （3）当且仅当存在某一个 y ∈ Y ，使得 & x, y &∈ R2 ? R3 且 & y, z &∈ R4 ，才有& x, z &∈ (R2 ? R3 ) ? R4 ，而(?y )(& x, y &∈ R2 ? R3 ∧ & y, z &∈ R4 ) ? (?y )((& x, y &∈ R2 ∨ & x, y &∈ R3 )∧ & y , z &∈ R4 ) ? (?y )((& x, y &∈ R2 ∧ & y , z &∈ R4 ) ∨ (& x, y &∈ R3 ∧ & y, z &∈ R4 )) ? (?y )(& x, y &∈ R2 ∧ & y, z &∈ R4 ) ∨ (?y )(& x, y &∈ R3 ∧ & y, z &∈ R4 )?& x, z &∈ R2 ? R4 ∨ & x, z &∈ R3 ? R4 ?& x, z &∈ (R2 ? R4 ) ? (R3 ? R4 )（4）当且仅当存在某一个 y ∈ Y ，使得 & x, y &∈ R2 ? R3 且 & y, z &∈ R4 ，才有& x, z &∈ (R2 ? R3 ) ? R4 ，而(?y )(& x, y &∈ R2 ? R3 ∧ & y, z &∈ R4 ) ? (?y )((& x, y &∈ R2 ∧ & x, y &∈ R3 )∧ & y, z &∈ R4 ) ? (?y )((& x, y &∈ R2 ∧ & y, z &∈ R4 ) ∧ (& x, y &∈ R3 ∧ & y, z &∈ R4 )) ? (?y )(& x, y &∈ R2 ∧ & y, z &∈ R4 ) ∧ (?y )(& x, y &∈ R3 ∧ & y, z &∈ R4 )?& x, z &∈ R2 ? R4 ∧ & x, z &∈ R3 ? R4 ?& x, z &∈ (R2 ? R4 ) ? (R3 ? R4 )P751． 设 X = {0,1,2,3} ， R1 和 R2 是 X 中的关系，R1 = {& i, j &| j = i + 1 ∨ j = i / 2} R2 = {& i., j &| i = j + 2}试求出关系矩阵： M R1 ；M R2 ； M R ? M R12； M R2? M R1 ；M R1 ? M R2 ? M R1 ； M R13 。解：R1 = {& 0,0 &, & 0,1 &, & 1,2 &, & 2,3 &, & 2,1 &} R2 = {& 2,0 &, & 3,1 &}由此可得： R1 ? R2 = {& 1,0 &, & 2,1 &}R2 ? R1 = {& 2,0 &, & 2,1 &, & 3,2 &} R1 ? R2 ? R1 = {& 1,0 &, & 1,1 &, & 2,2 &}R13 = {& 0,0 &, & 0,1 &, & 0,2 &, & 0,3 &, & 1,2 &, & 2,1 &, & 2,3 &}所以：M R11 0 = 0 01 0 1 00 1 0 00 0 1 00 0 0 0 M R2 = 0 0 0 0 1 0 0 0 0 1 0 0M R1 ? M R20 1 = 0 00 0 1 00 0 0 00 0 0 0M R2 ? M R10 0 = 1 00 0 1 00 0 0 10 0 0 00 0 0 0 M R1 ? M R2 ? M R1 = 1 1 0 0 0 0 1 0 0 0 0 01 1 1 1 M R3 =10 0 1 0 0 1 0 1 0 0 0 02． 此题有错误 3． 试证明定理 4.4.6 的（3）、（4）、（5）、（7）和（8）式。~ ? x, y &∈ R1 ? R2 } ?? y, x &∈ R1 ? y, x &∈ R1 ? R2(3) 证明：?? y, x &∈ R1 ∧ ? y, x &∈ R2 ~ ~ ?? x, y &∈ R1 ∧ ? x, y &∈ R2 ~ ~ ?? x, y &∈ R1 ? R2~ ~所以 R1 ? R2 = R1 ? R2 。~~ Y ?& y, x &∈ X × Y & x, y &∈ X × ? y ∈ X ∧ x ∈Y (4) 证明： ? x ∈Y ∧ y ∈ X ?& x, y &∈ Y × X ~Y =Y × X 。 所以 X ×(5) 证明： (7) 证明：见书上 P74 页(8) 证明：~ & x, y &∈ R2 ?& y, x &∈ R2 ~ ?& x, y &∈ R2 ? R1 ?& x, y &∈ R2 → R1所以 R2 = R2 → R1 同理 R1 = R2 → R1 得证。4． 试证明：如果关系 R 是自反的，则 R 也是自反的；如果 R 是可传递的、非自反的、对称~的或反对称的，则 R 亦然。 证明：设 R 是 A 上的二元关系， （1）若 R 是自反的，则 I A 的； （2）若 R 是反自反的，则 I A~? R ，由于 I A 的转置仍是 I A ，因此， I A ? R ，故 R 是自反? R = ? 。把 I A 和 R 都取转置，由于 I A 的转置仍是 I A ，因~~此， I A ∩ R = ? ，故 R 是反自反的； 则& （3） 若 R 是对称的， 任取 & y, x &∈ R ，~~~由 R 的对称性可知， x, y &∈ R ， & y, x &∈ R ，于是 & x, y &∈ R 。由 x，y 取值的任意性知， R 是对称的； （4）若 R 是反对称的，任取 & y, x &∈ R ，则 &~~~x, y &∈ R ，由 R 的反对称性可知，~& y, x &? R ，于是 & x, y &∈ R 。由 x，y 取值的任意性知， R 是反对称的；（5） 若 R 是可传递得， 任取 & x, y &∈ R ，& y, z &∈ R ， 则& 由 R 的可传递性，可知 &~~~y, x &∈ R ，& z , y &∈ R ，~~ z , x &∈ R ，于是 & x, z &∈ R 。故 R 是可传递的。5． 如果 R 是反对称的关系，则在 R ? R 的关系矩阵中有多少个非零值？ 解： R 的关系矩阵上， 主对角线有多少个非零值，R ? R 的关系矩阵中就有多少非零记入值。~~P791． 设 X 是一个集合， R1 和 R2 是 X 中的二元关系，并设 R1 ? R2 ，试证明： （1） r (R1 ) ? r (R2 ) （2） s (R1 ) ? s (R2 ) （3） t (R1 ) ? t (R2 ) 2．在图 4-11 中给出的三个关系图，试求出每一个的自反的、对称的闭包，并画出闭包的关 系图。 a）解：由关系图可知，R=?则： r (R ) = {& a, a &, & b, b &}s (R ) = ? t (R ) = ?b）解：由关系图可知，R = {& a, a &, & a, b &}则： r (R ) = {& a, a &, & b, b &, & a, b &}s(R ) = {& a, a &, & a, b &, & b, a &}t (R ) = {& a, a &, & a, b &}c）解：由关系图可知，R = {& a, b &, & b, c &, & c, a &}则： r (R ) = {& a, a &, & b, b &, & c, c &, & a, b &, & b, c &, & c, a &}s(R ) = {& a, b &, & b, a &, & b, c &, & c, b &, & c, a &, & a, c &} t (R ) = {& a, b &, & b, c &, & c, a &, & a, c &, & b, a &, & c, b &, & a, a &, & b, b &, & c, c &}3． R1 和 R2 是集合 X 中的关系。试证明： （1） r (R1 ? R2 ) = r (R1 ) ? r (R2 ) （2） s (R1 ? R2 ) = s (R1 ) ? s (R2 ) （3） t (R1 ? R2 ) = t (R1 ) ? t (R2 ) 4．设集合 X = {a, b, c, d , e, f , g , h} ， R 是 X 中的二元关系，图 4-12 给出了 R 的关系图。 试画出可传递闭包 t (R ) 的关系图，并求出 tsr (R ) 。 解：由关系图可知，R = {& a, b &, & b, c &, & c, a &, & d , e &, & e, f &, & f , g &, & g , h &, & h, d &}则：?& a, b &, & b, c &, & c, a &, & d , e &, & e, f &, & f , g &, & g , h &, & h, d &, & a, a &, & b, b &, ? ?& c, c &, & d , d &, & e, e &, & f , f &, & g , g &, & h, h &, & b, a &, & c, b &, & a, c &, & d , f &, ? ? ? t (R ) = ? ? ?& d , g &, & d , h &, & e, g &, & e, h &, & e, d &, & f , h &, & f , d &, & f , e &, & g , d &, & g , e &,? ? ? ?& g , f &, & h, e &, & h, f &, & h, d & ??& a, b &, & b, c &, & c, a &, & d , e &, & e, f &, & f , g &, & g , h &, & h, d &, & a, a &, & b, b &, ? ?& c, c &, & d , d &, & e, e &, & f , f &, & g , g &, & h, h &, & b, a &, & c, b &, & a, c &, & d , f &, ? ? ? tsr (R ) = ? ? ?& d , g &, & d , h &, & e, g &, & e, h &, & e, d &, & f , h &, & f , d &, & f , e &, & g , d &, & g , e &,? ? ? ?& g , f &, & h, e &, & h, f &, & h, d & ?5. 设 R 是集合 X 中的任意关系。试证明： （1） R( ) ( )+ += R+* + *（2） R ? R = R = R ? R （3） R* *= R*P851.设 {A1 , A2 ,..., An } 是集合 A 的划分。试证明： 划分。 证明：因为 {A1 , A2 ,..., An } 是集合 A 的划分， 所以 Ai ? A(i = 1,2,..., n ) 是集合 A ? B 的Ai ? A j = ?(i ≠ j )?Ai =1ni=A（1）因为 Ai ? A 所以 Ai ? B ? A ? B (i = 1,2,...n ) （2） ( Ai ? B ) ? A j ? B = Ai ? A j ? B = ? ? B = ?() ()（3） i =1? A ? B = (A ? B) ? (Ai 1n2? B ) ? .... ? ( An ? B )= ( A1 ? A2 ? ... ? An ) ? B = A ? B是集合（1），（2），（3）构成满足划分的条件，因此A ? B 的划分。2. 把 n 个元素的集合划分成两个类，共有多少种不同的分法？ 解：n 1 2 Cn + Cn + .... + C n 2n ? 2 = = 2 n ?1 ? 1 2 23.有一个集合公式，它仅包含集合变元 X 和 Y，还有集合运算 ?,?和? 。试证明：能够求出 另外一个公式，它等价于给定公式且仅由极小项的并组成。4.证明：对于集合公式来说，运算集合 {~,?} 是全功能的。 证明： A ? B = ~ (~ A? ~ B ) 所以，? 可以由 {~,?} 表示；A → B =~ A ? B)所以，→ 可以由 {~,?} 表示；所以，A ? B =~ (~ (~ A ? B ))? ~ (~ B ? A)))所以，运算集合 {~,?}? 可以由 {~,?} 表示；是全功能的。1,2,3}中的两个关系图，判断这两个关系是否是等价关系。 5.在图 4-16 中给出了集合 {解：左侧的关系不是等价关系，因为不满足可传递性；右侧的关系是等价关系。 6.在等价关系图中，应如何识别等价类？ 解：如果两个元素之间有两条连线，那么说明这两个元素是等价类。 7.设 R 是集合 X 中的关系。对于所有的 xi , x j , x k ∈ X ，如果 xi Rx j , x j Rxk ，就有 x k Rxi ，则称关系 R 是循环关系。试证明：当且仅当 R 是一个等价关系，R 才是自反的和循环的。 证明： （1）当 R 是个等价关系时，由等价关系的定义知，等价关系满足自反性，即 R 是自反的。 任取 x, y , z ∈ X ， & 由 R 的对称性，知 &x, y &∈ R, & y, z &∈ R ，由 R 的可传递性，知 & x, z &∈ R ，再z , x &∈ R 。根据 x，y，z 取值的任意性，知 R 是循环的。 x, x &∈ R 。 任取 y ∈ X， 使得 && （2） 当 R 是自反的， 可知对任意 x ∈ X ，因为 R 是循环的，故当 &x, y &∈ R ，x, x &∈ R ， & x, y &∈ R 时， & y, x &∈ R 。由 x，y 取值的x, y &∈ R, & y, z &∈ R ，由 R 的循环性知，任意性知， R 是对称的； 任取 x, y , z ∈ X ，&& z , x &∈ R ，因为 R 是对称的，因此 & x, z &∈ R ，由 x，y，z 取值的任意性，知 R 是可传递的。因为 R 是自反的、对称的和可传递的，因此 R 是一个等价关系。8.设 R1 和 R2 是集合 X 中的等价关系。试证明：当且仅当 C1 中的每一个等价类都包含于 C 2 的某一个等价类之中，才有 R1 ? R2 。 证明：设等价关系 R1 造成的集合 X 的划分为 C1 的集合 X 的划分为 C2= {C11 , C12 ,?, C1m } ，等价关系 R2 造成= {C21 , C22 ,?, C2 n }（1） 当 C1 中的每一个等价类都包含于 C2 的某一个等价类之中时，任取 C1 中的一个等价 类 C1i ，则必包含在 C2 的一个等价类里，设包含在 C2 j 中， C1i ? C2 j 。任取 C1i 中 两元素 x，y，由等价类的性质知， xR1 y 。由 C1i ? C2 j ，可知若 & 则&x, y &∈ R1 ，x, y &∈ R2 ，即 xR2 y 。由 i,j,x,y 取值的任意性知， R1 ? R2 。 x, y &∈ R1 → & x, y &∈ R2 永真，& x, y &∈ R1 x, y &∈ R2 等价于 x,y 落入 C2 的某个（2） 如果 R1 ? R2 ， 那么对任意的 &等价于 x,y 落入 C1 的某个等价类 C1i 中， &等价类 C2 j 中，即若 x, y ∈ C1i ，则 x, y ∈ C2 j ，由 x,y 的任意性可知，C1i ? C2 j , 由 i 的任意性可知， C1 中的每一个等价类都包含在 C2 的某一个等价类之中。 综上所述， 当且仅当 C1 中的每一个等价类都包含于 C2 的某一个等价类之中， 才有 R1 ? R2 。9.设 R1 和 R2 是集合 X 中的等价关系，并分别有秩 r1 和 r2 。试证明： R1 ? R2 也是集合 X 中 的等价关系，它的秩至多为 r1r2 。还要证明 R1 ? R2 不一定是集合 X 的一个等价关系。 证明： (1) ① 因为 R1 , R2 是自反的，所以对于任意的 x ∈ X ，都有对于任意的& x, x &∈ R1 , & x, x &∈ R2 ，故 ? x, x &∈ R1 ? R2 ，所以 R1 ? R2 是自反的；② 对于任意的 x, y ∈ X ，若 ? x, y &∈ R1 ? R2 ，则 & x, y &∈ R1 且 & x, y &∈ R2 。又 R1 , R2 是对称的，所以有 & y, x &∈ R1 ， & y, x &∈ R2 ，故 ? y, x &∈ R1 ? R2 ，即 R1 ? R2 是对称 的；③ 对于任意的 x, y, z ∈ X ，若 ? x, y &∈ R1 ? R2 ， ? y, z &∈ R1 ? R2 ，则 & x, y &∈ R1 ，& y, z &∈ R1 且 & x, y &∈ R2 ， & y, z &∈ R2 。又 R1 , R2 是可传递的，所以有 & x, z &∈ R1 ， & x, z &∈ R2 ，故 ? x, z &∈ R1 ? R2 ，即 R1 ? R2 是可传递的；综上， R1 ? R2 是等价关系。 (2) ① 因为 是自反的，所以对于任意的 x ∈ X ，都有对于任意的& x, x &∈ R1 , & x, x &∈ R2 ，故 & x, x &∈ R1 ? R2 ，所以 R1 ? R2 是自反的；② 对于任意的 x, y ∈ X ，若 & x, y &∈ R1 ? R2 ，则可能有三种情况： 若 & x, y &∈ R1 且 & x, y &∈ R2 ，那么因为 是对称的，所以有 & y, x &∈ R1 ，& y, x &∈ R2 ，故 & y, x &∈ R1 ? R2 ，即 R1 ? R2 是对称的；若 & x, y &∈ R1 但 & x, y &? R2 ，那么有 & y, x &∈ R1 且 & y, x &? R2 ，此时& y, x &∈ R1 ? R2 ，即 R1 ? R2 是对称的；所以 是对称的；若 & x, y &∈ R2 但 & x, y &? R1 ，那么有 & y, x &∈ R2 且 & y, x &? R1 ，此时& y, x &∈ R1 ? R2 ，即 R1 ? R2 是对称的；③ 对于任意的 x, y, z ∈ X ，若 & x, y &∈ R1 ? R2 ， & y, z &∈ R1 ? R2 ，当 & x, y &∈ R1 ，& y, z &∈ R2 时，不能确定 & x, z &∈ R1 ? R2 ，故由上可知， 不是等价关系。不是可传递的。P891. 解：x1x2x6x3x5x4（1） {x5 , x6 } （2） {x5 , x6 } ， {x4 , x5 } （3） {x5 , x6 } ， {x4 , x5 } ， {x3 , x4 } ， {x3 , x5 } ， {x3 , x6 } ，合并后，有{x3 , x4 , x5} ， {x3 , x5 , x6 }（4） {x3 , x4 , x5 } ， {x3 , x5 , x6 } ， {x2 , x3} （5） {x3 , x4 , x5 } ， {x3 , x5 , x6 } ， {x2 , x3} ， {x1 , x2 } ， {x1 , x3} ， {x1 , x6 } ，合并，得{x1 , x2 , x3} ， {x1 , x3 , x6 } ， {x3 , x4 , x5} ， {x3 , x5 , x6 }综上， 最大相容类有四个， 分别是 {x1 , x2 , x3} ，{x1 , x3 , x6 } ，{x3 , x4 , x5 } ，{x3 , x5 , x6 } 。 2.给定集合 S = {A1 , A2 ,... An }的覆盖，如何才能确定此覆盖的相容关系。解：相容关系是具有反对称性的关系，集合 S 的任何一个覆盖 X 均能确定一个相容关系，反之亦然。 设 X = {S1 , S 2 ,...S k } 是集合 S = {A1 , A2 ,... An }的一个覆盖，则由此覆盖确定的 S 上的 相容关系是：( S1 ×, S1 ) ? ( S 2 × S 2 ) ? ... ? ( S k × S k ) ，其中 S k × S k 指 S 的子集 S k 的笛卡尔积。1,2,3} 如 X = {{1,2},{2,3}} 是 S = {的一个覆盖，则此覆盖确定的S 上的相容关系是：{1,2} × {1,2} ? {2,3} × {2,3} = {& 1, ,1 &, & 1,2 &, & 2,1 &, & 2,2 &, & 2,3 &, & 3,2 &, & 3,3 &}1,2,3,4,5,6} ，R 是 X 中的关系。图 4-23 给出了 R 的关系图。试画出 R 和R 3.设集合 X = {56的关系图。 解：R 5 = {& 1,5 &, & 1,6 &, & 2,5 &, & 3,6 &, & 4,5 &, & 5,4 &} R 6 = {& 1,4 &, & 1,6 &, & 2,4 &, & 3,6 &, & 4,4 &, & 5,5 &}~4.假定 I x 是集合 X 中的恒等关系，R 是 X 中的任何关系。试证明： I x ? R ? R 是相容关系。 证明：设 S = I x ? R ? R~ ~ ~ x, x &∈ S 。知 I x ? R ? R 是自反的；（1）由于 I x ? I x ? R ? R ，因此 ?x ∈ X ， & （2） 任取 x, y ∈ X ，& 若& 若&则 & x, y &∈ I X 或者 & x, y &∈ R 或者 & x, y &∈ R 。 x, y &∈ S ，~x, y &∈ I X ，则 x = y ， & y, x &∈ I X ， & y, x &∈ S ；x, y &∈ R ，则 & y, x &∈ R ， & y, x &∈ S ；~~若 & x, y &∈ R ，则 & y, x &∈ R ， & 可知无论任何情况，若 &y, x &∈ S 。~ 是对称的。 x, y &∈ S ，则 & y, x &∈ S 。故 I x ? R ? R ~综上所述， I x ? R ? R 既是自反的又是对称的，因此， I x ? R ? R 是相容关系。 5.给定集合 X = {a, b, c}，R 是集合 X 中的二元关系，R 的关系矩阵 M R 为~1 0 1 MR =1 1 0 1 1 1试求出 R , R 2 , R 3 和 R ? R 的关系矩阵。 解：~~?1 1 1? ?0 1 1? = MR ? ?= ? , M R2 ? ?1 0 1? ??1 1 1? ?= ? ?1 1 1? , M R3 ? ?1 1 1? ??1 1 1? ?1= ? ? ? 1 1? , M R? R ? ?1 1 1? ??1 1 1? ?1 1 1? ? ? ? ? 1 1 1 ? ?6.给定等价关系 R 和 S，它们的关系矩阵是1 1 0 MR = 1 1 0 0 0 1试证明： R ? S 不是等价关系。 证明：1 1 0 MS = 1 1 1 0 1 1M R?S?1 1 1? ? =? ?1 1 1? ? ?0 1 1? ?可知 R ? S 不是对称的，因此， R ? S 不是等价关系。1,2,3}。求出 X 中的等价关系 R1 和 R2 ，使得 R1 ? R2 也是个等价关系。 7.设集合 X = {解： 设 R1 = {& 1,1 &, & 2,2 &, & 3,3 &, & 1,2 &