【正文】 （ 1），（ 9） P→ ? Q， ? P→ R， R→ ? S =S→ ? Q 證明： （ 1） S 附加前提 （ 2） R→ ? S 前提 （ 3） ? R （ 1），（ 2） （ 4） ? P→ R 前提 （ 5） P （ 3），（ 4） （ 6） P→ ? Q 前提 （ 7） ? Q (5），（ 6） （ 8） S→ ? Q CP，（ 1），（ 7） P→ (Q→ R) = (P→ Q)→ (P→ R) 證明： (1) P→ Q 附加前提 (2) P 附加前提 (3) Q (1),(2) (4) P→ (Q→ R) 前提 (5) Q→ R (2),(4) (6) R (3),(5) (7) P→ R CP,(2),(6) (8) (P→ Q) → (P→ R) CP,(1),(7) P→ (? Q→ ? R)， Q→ ? P,S→ R,P =? S 證明： （ 1） P 前提 （ 2） P→ (? Q→ ? R) 前提 （ 3） ? Q→ ? R (1)， (2) 20 （ 4） Q→ ? P 前提 （ 5） ? Q (1)， (4) （ 6） ? R (3),(5) （ 7） S→ R 前提 （ 8） ? S (6)， (7) 1 A， A→ B， A→ C， B→ (D→ ? C) = ? D 證明： （ 1） A 前提 （ 2） A→ B 前提 （ 3） B (1)， (2) （ 4） A→ C 前提 （ 5） C (1)， (4) （ 6） B→ (D→ ? C) 前提 （ 7） D→ ? C (3)， (6) （ 8） ? D (5)， (7) 1 A→ (C? B)， B→ ? A， D→ ? C = A→ ? D 證明： （ 1） A 附加前提 (2) A→ (C? B) 前提 (3) C? B （ 1），（ 2） (4) B→ ? A 前提 (5) ? B （ 1），（ 4） (6) C （ 3），（ 5） (7) D→ ? C 前提 (8) ? D （ 6），（ 7） (9) A→ ? D CP，（ 1），（ 8） 1 (P?Q)? (R?Q) ? （ P? R） ?Q 證明、 (P?Q)? (R?Q) 21 ? (? P? Q)? (? R? Q) ? (? P? ? R)? Q ? ? （ P? R） ? Q ? (P? R)?Q 1 P?(Q?P)? ? P?(P? ? Q) 證明、 P?(Q?P) ? ? P? (? Q? P) ? ? (? P)? (? P? ? Q) ? ? P?(P? ? Q) 1 （ P?Q） ? （ P?R）， ? (Q? R)， S? P?S 證明、 (1) （ P?Q） ? （ P?R） 前提 （ 2） P? (Q? R) (1) （ 3） ? (Q? R) 前提 （ 4） ? P （ 2）， (3) (5) S? P 前提 (6) S (4),(5) 1 P? ? Q， Q? ? R， R? ? S? ? P 證明、 (1) P 附加前提 （ 2） P? ? Q 前提 （ 3） ? Q （ 1），（ 2） （ 4） Q? ? R 前提 (5) ? R （ 3），（ 4） (6 ) R? ? S 前提 （ 7） R （ 6） （ 8） R? ? R （ 5），（ 7） 1用 真值表法證明Ｐ ?Ｑ ? (Ｐ ?Ｑ )? (Ｑ ?Ｐ ) 22 證明、 列出兩個公式的真值表： P Q P? Q （ P?Q） ? （ Q?P） F F F T T F T T T T F F F F T T 由定義可知，這兩個公式是等價的 。 1用先求主范式的方法證明 (P→ Q)? (P→ R) ? (P→（ Q? R） 證明、 先求出左右兩個公式 的主合取范式 (P→ Q)? (P→ R) ? (? P? Q)? (? P? R) ? (? P? Q? (R? ? R)))? (? P? (Q? ? Q)? R) ? (? P? Q? R)? (? P? Q? ? R)? (? P? Q? R)? (? P? ? Q? R) ? (? P? Q? ? R)? (? P? Q? R)? (? P? ? Q? R) (P→（ Q? R） ) ? (? P? （ Q? R） ) ? (? P? Q)? (? P? R) ? (? P? Q? (R? ? R))? (? P? (Q? ? Q)? R) ? (? P? Q? R)? (? P? Q? ? R)? (? P? Q? R)? (? P? ? Q? R) ? (? P? Q? ? R)? (? P? Q? R)? (? P? ? Q? R) 它們有一樣的主合取范式，所以它們等價。從而 P也為 F，即 ? P為 T。 (4) A 隊獲第一 。C: C 隊獲亞軍 。 （ 1） A 前 提 （ 2） A?（ B? C）前提 （ 3） B? C （ 1），（ 2） （ 4） C? ? A 前提 （ 5） ? C （ 1），（ 4） （ 6） B （ 3），（ 5） （ 7） D? ? B 前提 （ 8） ? D （ 6），（ 7） 2用推理規(guī)則證明 P?Q, ? (Q? R),P? R不能同時為真。 25 A? B = A? C， A? B=A? C，則 C=B 證明： B=B? (A? B)= B? (A? C)= (B? A)? (B? C) = (A? C)? (B∩ C)= C? (A? B) = C? (A? C) =C A? B=A? C， A ? B=A ? C，則 C=B 證明： B=B? (A? A )=(B? A)? (B? A ) =(C? A)? (C? A )=C? (A? A ) =C A－ (B? C)＝ (A－ B)－ C 證明： A－ (B? C)= A? CB? =A? (B ? C )=(A? B )? C =(AB)? C =(AB)C (A－ B)? (A－ C)=A－ (B? C) 證明： (AB)? (A－ C) =(A? B )? (A? C ) =(A? A)? (B ? C ) =A? CB? =A－ (B? C) AB=B，則 A=B=? 證明： 因為 B=AB，所以 B=B? B=（ AB） ? B=? 。而 A(B? C)= (AB)? (AC)， 所以 A=(AB)? (AC)。 1 (AB)? (BA)=A ? B=? 證明： ? 因為 (AB)? (BA)=A，所以 BA? A。從而 (AB)? (BA)=A。 從而 S? A? B，故 S?P(A? B)。 27 ? S?P(A? B)， 有 S? A? B，所以 S? A且 S? B。 證明： ?當(dāng) B=? 時，因為（ AB） ? B=（ A? ） ? ? =A，（ A? B） B=（ A? ? ） ? =A，所以（ AB） ? B=（ A? B） B。而顯然 b?（ AB） ? B。 (3) ? x? y (xy=0)。 (7) ? x? y? z (xy=z) 答： （ 1）存在自然數(shù) x，對任意自然數(shù) y滿足 xy=1。 （ 5）對每個自然數(shù) x，存在自然數(shù) y滿足 xy=x。將下列命題符號化： （ 1）沒有小于 0的自然數(shù) 。 （ 5）對任意 x，存在 y使 x+y=x。 解 ： (1) R={0,0,0,2,2,0,2,2} (2) R={1,1,1,2,2,1,2,2,3,1}。從而 A?A =? 。從而 A?A ?? 。故 B? A。 29 證明： 若 B=? ，則 A?B=? 。 若 B ?? ，則 A?B ?? 。從而 x?C。 設(shè) A={a,b}, B={c}。 （ 2） B2?A={c,c,a,c,c,b}。求下列各集合： （ 1） A? B? C ； （ 2） CBA ?? ；（ 3） (A? B )? C。 解 ： (1) A? B? C ={a}。 (5) (AB)? (BC)={d,c,a}。 對 ? x?A, 因為 A? B，所以 x?B。反例如下： A={a}, B={a,b},C={a,b,c}。雖然 A?B，且 B?C，但 A?C。 證明： ? a， b∈ A，則 {a,b}是 A的一個非空子集。 若 R和 S都是非 空集 A上的 等價關(guān)系，則 R? S 是 A上的 等價關(guān)系。 ? a,b∈ A， aR? Sb，即 aRb 且 aSb。 ? a,b,c∈ A， aR? Sb 且 bR? Sc，即 aRb， aSb,bRc 且 bSc。 故 R? S是 A上的 等價關(guān)系。 ? ? x?A， ?IA? R， ?x,x?R。即 y,x?R，故 x,y?R_1 。即 y,x?R， R_1? R。即 yRx，故R是對稱的。從而 R? (S? T)?（ R? S） ?（ R? T）。從而 x， y?R且 y， z?S且 y， z?T，即 x， z?R? S 且 x， z?R? T。 證明： 設(shè) a,b都是 B 的最大元，則由最大元的定義 a? b， b? a。MR=??????????001101000 。MR=??????????100001110 。 （ 2） C={{1,5,7},{2,4,8,9},{3,5,6,10}}。 1 R是 A={1,2,3,4,5,6}上的等價關(guān)系， R=IA ? {1,5,5,1,2,4,4,2,3,6,6,3} 求 R誘導(dǎo)的劃分。 (b) {b,d}。無上確界，下確界是 c。 (c)的極大元為 e,極小元為 b。最大元是 e，無最小元； 上界是 e，下界是 c。 求下列置換的運(yùn)算： 解： （ 1） ???????? 14334221? ???????? 14233241= ???????? 24433211 （ 2） 3163564235241 ????????= ???????? 163564235241 ? 2163564235241 ???????? = ???????? 163564235241 ? ???????? 462514533261 = ???????? 665544332211 34 2 試求出 8階循環(huán)群的所有生成元和所有子群。 因為循 環(huán)群的子群也是循環(huán)群，且子群的階數(shù)是 G 的階數(shù)的因子，故 G的子群只能是 1 階的、 2 階的