【正文】 設(shè) g?f是復(fù)合函數(shù)，如果 g?f是雙射，那么 f是入射而g是滿 射 。1=x 因此，總存在 x,0?N N， 使得 f(x, 0) = x， 所以 f是滿射的 且總存在 x,1?N， 使得 g(x, 1) = x， 所以 g是滿射的 2) 因?yàn)橛校?1,3,2,2, 1,4 ? N N ， 且 f(1, 3) = f(2, 2) = 4， 且 g(1, 4) = f(2, 2) = 4 所以 f和 g都不是單射的 2021年 12月 1日星期三 函數(shù) 9. 設(shè) f: A ? B 是滿射函數(shù)，且函數(shù) g: B ? P(A)， 定義為： g(b) = {x|x ? A ∧ f(x)=b} 求證： g是單射的。 2021年 12月 1日星期三 函數(shù) 4. 求證：從 N N到 N的函數(shù) f(x, y)=x+y， 和 g(x, y)=x故 R ? (B B)是 B上偏序關(guān)系 2021年 12月 1日星期三 設(shè) R1是 A上的等價(jià)關(guān)系， R2是 B上的等價(jià)關(guān)系，A≠?且 B≠?。 對于 ?a, b, c ? A， 若 aRb, bRc， 因?yàn)?R是傳遞的，所以有 aRc 又因?yàn)?R是對稱的，所以有 cRa。 2021年 12月 1日星期三 等價(jià)關(guān)系的證明 21. 設(shè) R是 A上的二元關(guān)系，對于 ?a, b, c ? A， 若 aRb, bRc， 則 cRa， 稱 R是 循環(huán)的 。 則若有 xR2y, yR2z， 必有 xR2z， 故 R2是傳遞的 。 因此有 xR2x， 故 R2是自反的 2) 對于 ? x, y? A， 若有 xR2y， 則必存在 z ? A， 有 xRz, zRy， 因?yàn)?R是對稱的，所以必定有： yRz, zRx， 即有 yR2x 。 2021年 12月 1日星期三 等價(jià)關(guān)系的證明 20. 設(shè) R和 S是非空集合 A上的等價(jià)關(guān)系，試確定下面各式是否為等價(jià)關(guān)系。 S ? R 176。 (R ? IA) = IA ? R ? R2 因此， tr(R) = t (R ? IA) =? (R ? IA) i i=1 ? i=1 n 用歸納法可證： (R ? IA)n = IA ? ( ? Ri ) i=1 ? = ? (IA ? (? Rj) ) = IA ? (? Rj) = IA ? t(R) = rt(R) j=1 i j=1 ? R 176。 ( R ? IA ) = R176。 R=R， 且 IA176。 定理：若 R ? A A， 則 t(R)=? Ri=R ? R2 ? R3 ? …… 證明略（教材 P73） 定理：若 R ? A A， |A|= n 則 t(R)=? Ri=R ? R2 ? R3 ? …… ? Rn i=1 n 證明略（教材 P74） i=1 ? 2021年 12月 1日星期三 閉包運(yùn)算 定理： 若 R是 A上的二元關(guān)系，則： rs(R) = sr(R) 證明： sr(R) = s(R ? IA) = (R ? IA) ? (R ? IA)1 = (R ? IA) ? (R 1 ? IA1) = (R ? R 1) ? IA =r (R ? R 1) = rs (R) 定理： 若 R ? A A， 則 r(R)=R ? IA 定理： 若 R ， 則 s( ) R R1 2021年 12月 1日星期三 閉包運(yùn)算 定理： 若 R是 A上的二元關(guān)系，則： rt(R) = tr(R) 證明： 由于 R176。 定理： 若 R ? A A， 則 R是對稱的 ? R=R1 2021年 12月 1日星期三 閉包運(yùn)算 3) 設(shè) R2是 A上任意的對稱關(guān)系，且 R ? R2。 定理： 若 R ? A A， 則 s(R)=R ? R1 證明： 1)設(shè) R1=R ? R1， 顯然 R ? R1 。 設(shè) G是集合 A上二元關(guān)系 R的關(guān)系圖，給 G中所有結(jié)點(diǎn)都補(bǔ)充上有向環(huán)，就得到了 R的自反閉包 r(R) 的關(guān)系圖。 謂詞邏輯的推理理論 2021年 12月 1日星期三 集合 18. 設(shè) A、 B、 C、 D是集合，求證： (A ? B) (C ? D) ? (A C) ? (B D) 證明：對于 (A ? B) (C ? D) 中的任意元素 x, y，有： 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) 2021年 12月 1日星期三 集合 20. 4) (A B) C = (A C) (B C) 證明： 對于 (A B) C中的任意元素 x, y，有 x, y ? (A B) C ? x ? (A B) ∧ y ? C ? (x ? A ∧ x ? B) ∧ y ? C ? (x ? A ∧ y ? C ∧ x ? B )∨ (x ? A∧ y ? C ∧ 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) 2021年 12月 1日星期三 集合 21. 求證：若 A A = B B， 則： A=B 證明： 假設(shè) A ≠ B， 則必 存在 x， 有 x ? A ∧ x ? B，或存在 y，有 y ? A ∧ y ? B 若存在 x， 有 x ? A∧ x ? B， 則 x,x ? A A， 且 x,x ? B B ， 則 A A ≠ B B 若存在 y， y ? A ∧ y ? B ， 則 y,y ? B B， 且 y,y ? A A ， 則 A A ≠ B B 綜上所述，可知：若 A A = B B， 則必有 A=B 2021年 12月 1日星期三 集合 22. 求證：若 A B = A C， 且 A ≠ ?， 則： B=C 證明： 假設(shè) B ≠ C， 則必 存在 y， 有 y ? B ∧ y ? C，或存在 z，有 z ? B ∧ z ? C， 又因?yàn)?A ≠ ?，則必存在 x ? A。 每個(gè)科學(xué)工作者都是刻苦鉆研的 每個(gè)刻苦鉆研而又聰明的科學(xué)工作者都將獲得事業(yè)的成功 華有為是一名科學(xué)工作者，并且他是聰明的 所以：華有為將獲得事業(yè)上的成功 S(x)： x是科學(xué)工作者， H(x)： x刻苦鉆研， C(x)： x是聰明的 P(x)： x在獲得事業(yè)上的成功， a： 華有為 (?x)(S(x) ? H(x)) (?x)(S(x)∧ H(x)∧ C(x) ? P(x)) S(a) ∧ C(a) P(a) 2021年 12月 1日星期三 謂詞邏輯的推理理論 前提： (?x)(S(x) ? H(x)), (?x)(S(x)∧ H(x)∧ C(x) ? P(x)), S(a) ∧ C(a) 結(jié)論： P(a) 證明： (1) (?x)(S(x) ? H(x)) P (2) S(a) ? H(a) UI (1) (3) S(a) ∧ C(a) P (4) S(a) T (3) I1 (5) H(a) T (2)(4) I8 (6) (?x)(S(x)∧ H(x)∧ C(x) ? P(x)) P (7) S(a)∧ H(a)∧ C(a) ? P(a) UI (6) (8) P(a) T (3)(5)(7) I8 2021年 12月 1日星期三 謂詞邏輯的推理理論 22. 符號化下列各命題，并給出構(gòu)造推理證明。 每一個(gè)自然數(shù)不是奇數(shù)就是偶數(shù) 自然數(shù)是偶數(shù)當(dāng)且僅當(dāng)它能被 2整除 并不是所有自然數(shù)都能