1、习题习题主析取范式和主合取范式主析取范式和主合取范式15.试化下列公式为主析取范式和主合取范式，并判断各公式类型试化下列公式为主析取范式和主合取范式，并判断各公式类型1)(P Q)(P Q)(P Q)(P Q)(Q P)(PQ)(P Q)(QP)(PQ)(QP)P)(QP)Q)(PQ)(PQ)(PP)(QQ)(QP)(PQ)(P Q)(PQ)m01m10m11 M00是偶然式是偶然式主析取范式和主合取范式主析取范式和主合取范式15.试化下列公式为主析取范式和主合取范式，试化下列公式为主析取范式和主合取范式，并判断各公式类型并判断各公式类型2)P(P (Q(Q R)P(P (Q(QR)PQR M
2、000 m001m010m011m100m101m110m111是偶然式是偶然式主析取范式和主合取范式主析取范式和主合取范式15.试化下列公式为主析取范式和主合取范式，试化下列公式为主析取范式和主合取范式，并判断各公式类型并判断各公式类型3)(P (QR)(P (Q R)(P(QR)(P (Q R)(PQ)(PR)(PQR)(PQR)(PQR)(PQ R)(P QR)M000 M100 M101 M110 m001m010m011m111是偶然式是偶然式用同一律和互补律用同一律和互补律(A A (B B)，补，补充简单析取式中未出现的命充简单析取式中未出现的命题变元，并用分配律展开题变元，并用
3、分配律展开主析取范式和主合取范式主析取范式和主合取范式15.试化下列公式为主析取范式和主合取范式，试化下列公式为主析取范式和主合取范式，并判断各公式类型并判断各公式类型4)(P Q)R)P (P Q)R)P (P Q)R)P (PQP)(RP)(PQ)(P R)(PQR)(PQ R)(P Q R)M000M001M011 m010m100m101m110m111是偶然式是偶然式主析取范式主析取范式真值表法：真值表法：例例1.37：求：求(P Q)Q 的主析取范式的主析取范式P Qm00m01m10m11 P Q PQP QPQ0 010000 101001 000101 10001P Qm00
4、m01m10m11(P Q)Q P Q PQP QPQ0 0100000 1010011 0001001 100011(P Q)Q (PQ)(PQ)m01 m11主合取范式主合取范式真值表法：真值表法：例例1.40：求：求(P Q)Q 的主合取范式的主合取范式P QM00M01M10M11(P Q)QPQ P Q PQ P Q0 0011100 1101111 0110101 111101(P Q)Q (PQ)(PQ)M00 M10分别用真值表法和公式法求分别用真值表法和公式法求(P(QR)(P(QR)的主析取范式与主合的主析取范式与主合取范式（取范式（10分）分）主析取范式和主合取范式主析取
5、范式和主合取范式命题逻辑命题逻辑已知命题公式已知命题公式 A(P,Q,R)，并且知道只有当赋值，并且知道只有当赋值为为001、110和和111时公式真值为假。求命题公式时公式真值为假。求命题公式A(P,Q,R)的主析取范式为的主析取范式为_。命题逻辑的推理理论命题逻辑的推理理论21.符号化下述论断，并证明其有效性。符号化下述论断，并证明其有效性。如果今天是周一，则进行离散数学或如果今天是周一，则进行离散数学或C语言其中一门考试语言其中一门考试如果如果C语言老师有会，则不考语言老师有会，则不考C语言语言今天是周一今天是周一C语言老师有会语言老师有会所以：进行离散数学考试所以：进行离散数学考试设：
6、设：P：今天是周一，今天是周一，Q：考考C语言，语言，R：考离散数学，考离散数学，S：C语言老师有会，语言老师有会，P Q RS QPSR命题逻辑的推理理论命题逻辑的推理理论前提：前提：P Q R，S Q，P，S 结论：结论：R证明：证明：(1)P P(2)P Q R P(3)Q R T(1)(2)I8(4)(Q R)T(3)(5)Q R T(4)E12(6)Q R T(5)I18(7)S P(8)S Q P(9)Q T(7)(8)I8(10)R T(6)(9)I8命题逻辑的推理理论命题逻辑的推理理论23.符号化下面命题，并推证之符号化下面命题，并推证之。如果厂方拒绝增加工资，则罢工不会停止如
7、果厂方拒绝增加工资，则罢工不会停止除非罢工超过一年，并且工厂厂长辞职除非罢工超过一年，并且工厂厂长辞职因此：若厂方拒绝增加工资，而罢工又刚刚开始，因此：若厂方拒绝增加工资，而罢工又刚刚开始，罢工是不会停止的罢工是不会停止的设：设：P：厂方拒绝增加工资，厂方拒绝增加工资，Q：罢工会停止，罢工会停止，R：罢工超过一年，罢工超过一年，S：工厂厂长辞职，工厂厂长辞职，(P Q)(RS)P R Q习题习题23前提：前提：(P Q)(RS)结论：结论：P R Q证明：证明：(1)Q P（假设前提）假设前提）(2)(P Q)(R S)P(3)(RS)(P Q)T(2)I18(4)(RS)(P Q)T(3)E
8、11(5)Q(P(RS)T(4)E2 E3(6)Q (PR)(PS)T(5)E11 E3(7)(PR)(PS)T(1)(6)I8(8)PR T(7)I1(9)(P R)T(8)E5(10)Q (P R)CP(1)(9)(11)P R Q T(10)E11 习题习题23前提：前提：(P Q)(RS)结论：结论：P R Q证明：证明：(1)P R P（假设前提）假设前提）(2)(P R)(P S)T(1)I3(3)P (R S)T(2)E4(4)P (R S)T(3)E5(5)(R S)T(4)I1(6)(P Q)(R S)P(7)(RS)(P Q)T(6)I18(8)P Q T(5)(7)I18
9、(9)P T(4)I1(10)Q T(8)(9)I8(11)P R Q CP(1)(10)只要今天天气不好，就一定有考生不能提前进入考只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。时进行。所以，如果考试准时进行，那么天气就好。命题逻辑的推理理论命题逻辑的推理理论谓词逻辑的推理理论谓词逻辑的推理理论20.构造证明下列各式构造证明下列各式 x 习题习题20证明：证明：(1)P(2)(x)P(x)(x)Q(x)T(1)E11(3)(x)P(x)(x)Q(x)T(2)Q(
10、4)(x)(P(x)Q(x)T(3)Q(5)T(4)E11 x 习题习题20证明：证明：(1)P(附加前提附加前提)(2)(x)(R(x)P(x)T(1)E11(3)(x)(R(x)P(x)T(2)Q E1 E5(4)R(y)P(y)EI(3)(5)R(y)T(4)I1(6)P(7)R(y)Q(y)UI(6)(8)Q(y)T(5)(7)I8(9)P(10)P(y)Q(y)UI(9)(11)P(y)T(4)I2(12)Q(y)T(10)(11)I8(13)T(8)(12)习题习题20证明：证明：(1)P(附加前提附加前提)(2)P(y)UI(1)(3)P(4)P(y)Q(y)UI(3)(5)Q(
11、y)T(2)(4)I8(6)UG(5)(7)CP(1)(6)谓词逻辑谓词逻辑设论域元素为设论域元素为a1，a2，a3，a4，则则 ；。)()(xAx)()(xAx前束范式前束范式6.在下列公式中，对约束变元进行改名，对自由变元进行代入在下列公式中，对约束变元进行改名，对自由变元进行代入 改名：把第一个约束变元改名：把第一个约束变元x改为改为u，把第二个约束变元把第二个约束变元x改为改为v 把第三个约束变元把第三个约束变元y改为改为w改名：把第一个约束变元改名：把第一个约束变元x改为改为u，把第二个约束变元把第二个约束变元x改为改为v()(P()(Q()R()()(R()()S(,)()(P()
12、Q()()(R()S()前束范式前束范式6.在下列公式中，对约束变元进行改名，对自由变元进行代入在下列公式中，对约束变元进行改名，对自由变元进行代入改名：把第一个约束变元改名：把第一个约束变元x改为改为u，把第四个约束变元把第四个约束变元x改为改为v改名：把第二个约束变元改名：把第二个约束变元x改为改为s，把第三个约束变元把第三个约束变元z改为改为t()P(,y)(x)(Q(x,z)(z)()R(,y,z)()P(,y)()(Q(,z)()()R(,y,)代入：将第一个自由变元代入：将第一个自由变元y代入代入r，将第二个自由变元将第二个自由变元z代入代入w()P(,)()(Q(,)()()R(
13、,)前束范式前束范式6.在下列公式中，对约束变元进行改名，对自由变元进行代入在下列公式中，对约束变元进行改名，对自由变元进行代入改名：把第一个约束变元改名：把第一个约束变元x改为改为u，把第二个约束变元把第二个约束变元z改为改为v 把第三个约束变元把第三个约束变元y改为改为w代入：将第一个自由变元代入：将第一个自由变元y代入代入s，将第二个自由变元将第二个自由变元x代入代入t()(P(,y)()Q(,)()R(x,)(u)(P(u,)(v)Q(u,v)(w)R(,w)等价式等价式量词辖域的扩大与缩小（小结量词辖域的扩大与缩小（小结）前束范式前束范式例例2.11：将公式将公式化为前束范式化为前束
14、范式解：解：公式公式 (x)P(x)(y)Q(y)()R()(z)R(z)(z)R(z)(z)R(z)解：解：（公式（公式）公式公式 (x)P(x)(y)Q(y)()R()(z)R(z)(z)R(z)求下列公式的前束范式求下列公式的前束范式 前束范式前束范式 前束范式前束范式谓词逻辑的推理理论谓词逻辑的推理理论22.符号化下列各命题，并给出构造推理证明。符号化下列各命题，并给出构造推理证明。每一个自然数不是奇数就是偶数每一个自然数不是奇数就是偶数自然数是偶数当且仅当它能被自然数是偶数当且仅当它能被2整除整除并不是所有自然数都能被并不是所有自然数都能被2整除整除所以：有的自然数是奇数所以：有的自
15、然数是奇数设：设：N(x)：x是自然数，是自然数，O(x)：x是奇数，是奇数，E(x)：x是偶数，是偶数，T(x)：x能被能被2整除整除(x)(N(x)O(x)E(x)谓词逻辑的推理理论谓词逻辑的推理理论前提：前提：(x)(N(x)O(x)E(x),结论：结论：证明：证明：(1)P(2)(x)(N(x)T(x)T(1)E11(3)(x)(N(x)T(x)T(2)Q,E1,E5(4)N(y)T(y)EI(3)(5)N(y)T(4)I1(6)P(7)N(y)(E(y)T(y)UI(6)(8)E(y)T(y)T(5)(7)I8(9)E(y)T(y)T(8)I18习题习题22(1)(10)T(y)T(
16、4)I1(11)E(y)T(9)(10)I9(12)P(13)N(y)O(y)E(y)UI(12)(14)O(y)E(y)T(5)(13)I8(15)(O(y)E(y)T(14)(16)O(y)E(y)T(15)E12(17)O(y)T(11)(16)I8(18)N(y)O(y)T(5)(17)(19)EG(18)(4)N(y)T(y)EI(3)(5)N(y)T(4)E1(9)E(y)T(y)T(8)E18谓词逻辑的推理理论谓词逻辑的推理理论22.符号化下列各命题，并给出构造推理证明。符号化下列各命题，并给出构造推理证明。如果一个人怕困难，那么他就不会获得成功如果一个人怕困难，那么他就不会获得
17、成功每个人或者获得成功，或者失败过每个人或者获得成功，或者失败过有些人未曾失败过有些人未曾失败过所以：有些人不怕困难所以：有些人不怕困难设：设：P(x)：x是人，是人，D(x)：x怕困难，怕困难，S(x)：x成功，成功，F(x)：x失败失败(x)(P(x)D(x)S(x)F(x)谓词逻辑的推理理论谓词逻辑的推理理论前提：前提：(x)(P(x)D(x)S(x),F(x)结论：结论：证明：证明：(1)P(2)P(y)F(y)EI(1)(3)P(y)T(2)I1(4)F(y)T(2)I1(5)P(6)P(y)(S(y)F(y)UI(5)(7)S(y)F(y)T(3)(6)I8(8)S(y)T(4)(
18、7)I10习题习题22(2)(9)P(10)P(y)D(y)S(y)UI(1)(11)(P(y)D(y)T(8)(10)I9(12)P(y)D(y)T(11)E5(13)D(y)T(3)(12)I10(14)P(y)D(y)T(3)(13)(15)EG(14)(3)P(y)T(2)I1(8)S(y)T(4)(7)I10谓词逻辑的推理理论谓词逻辑的推理理论22.符号化下列各命题，并给出构造推理证明。符号化下列各命题，并给出构造推理证明。每个科学工作者都是刻苦钻研的每个科学工作者都是刻苦钻研的每个刻苦钻研而又聪明的科学工作者都将获得事业的成功每个刻苦钻研而又聪明的科学工作者都将获得事业的成功华有为
19、是一名科学工作者，并且他是聪明的华有为是一名科学工作者，并且他是聪明的所以：华有为将获得事业上的成功所以：华有为将获得事业上的成功S(x)：x是科学工作者，是科学工作者，H(x)：x刻苦钻研，刻苦钻研，C(x)：x是聪明的是聪明的P(x)：x在获得事业上的成功，在获得事业上的成功，a：华有为华有为(x)(S(x)H(x)C(a)谓词逻辑的推理理论谓词逻辑的推理理论前提：前提：(x)(S(x)H(x),C(a)结论：结论：证明：证明：(1)P(2)S(a)H(a)UI(1)(3)C(a)P(4)S(a)T(3)I1(5)H(a)T(2)(4)I8(6)P(7)S(a)H(a)C(a)P(a)UI
20、(6)(8)T(3)(5)(7)I8谓词逻辑的推理理论谓词逻辑的推理理论22.符号化下列各命题，并给出构造推理证明。符号化下列各命题，并给出构造推理证明。每个资深名士，或是政协委员，或是国务院参事每个资深名士，或是政协委员，或是国务院参事张大为不是政协委员，但他是中科院院士张大为不是政协委员，但他是中科院院士所以：有的中科院院士是国务院参事所以：有的中科院院士是国务院参事K(x)：x是资深名士，是资深名士，Z(x)：x是政协委员，是政协委员，G(x)：x是国务院参事，是国务院参事，S(x)：x是中科院院士，是中科院院士，a：张大为张大为(x)(K(x)Z(a)S(a)习题习题22(4)证明：证
21、明：(1)P(2)K(a)(Z(a)G(a)UI(1)(3)Z(a)S(a)P(4)K(a)T(3)I1(5)Z(a)G(a)T(2)(4)I8(6)Z(a)T(3)I1(7)G(a)T(5)(6)I10(8)S(a)T(3)I1(9)G(a)S(a)T(7)(8)(10)EG(9)前提：前提：(x)(K(x),Z(a)S(a)结论：结论：每个大学生不是文科学生就是理工科学生，有的大每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。生，因而如果小张是大学生，他就是文科学生
22、。谓词逻辑的推理理论谓词逻辑的推理理论集合集合18.设设A、B、C、D是集合，求证：是集合，求证：证明：对于证明：对于(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)AC BD (AC)(BD)集合集合-对于对于-中的任意元素中的任意元素，有，有 ()()集合集合21.求证：若求证：若AA=BB，则：则：A=B假设假设 A B，则必则必AA，且且BB，则则 AA BBBB，且且AA，则则 AA BB综上所述，可知：若综上所述，可知：若AA=BB，则必有则必有A=B集合集合22.求证：若求
23、证：若AB=AC，且且A ，则：则：B=C假设假设 B C，则必则必A ，则必存在，则必存在AB，且且AC，则则 AB ACAB，且且AC，则则 AB AC综上所述，可知：若综上所述，可知：若AB=AC，且且A ，则必有则必有B=C设设A、B、C、D为四个非空集合，则为四个非空集合，则AB CD的充要条件是的充要条件是A C，B D 已知已知A、B、C是三个集合，证明是三个集合，证明(AB)C(AC)(BC)集合集合闭包运算闭包运算。设设G是集合是集合A上二元关系上二元关系R的关系图，给的关系图，给G中所有结点都补中所有结点都补充上有向环，就得到了充上有向环，就得到了R的自反闭包的自反闭包r(
24、R)的关系图。的关系图。定理：定理：证明：证明：因为是因为是IA自反的，因此自反的，因此且且 设设R1是是A上任意的自反关系，且上任意的自反关系，且R R1，由于由于R1是自反的，因此是自反的，因此IA R1，又因为又因为R R1，因此，因此，r(R)=R IA参照定义参照定义闭包运算闭包运算设设G是集合是集合A上二元关系上二元关系R的关系图，将的关系图，将G中所有的弧都画中所有的弧都画成成“有来有往有来有往”（即如果有从（即如果有从a到到b的弧，就有从的弧，就有从b到到a的弧）的弧）就得到了就得到了R的对称闭包的对称闭包s(R)的关系图。的关系图。定理：定理：证明：证明：1)设设R1=R R
25、-1，显然显然。2)因为因为R1-1=(R R-1)-1=R-1 (R-1)-1=R-1 R=R1 所以所以。定理：定理：闭包运算闭包运算3)设设R2是是A上任意的对称关系，且上任意的对称关系，且R R2。对于任意对于任意 R1，或者或者 R，或者或者 R-1 若若 R，则则 R2；若若 R-1，则则 R，则则 R2，又因为又因为R2是对称的，所以是对称的，所以 R2；所以所以综上所述，证得综上所述，证得 闭包运算闭包运算设设G是集合是集合A上二元关系上二元关系R的关系图，如果有从的关系图，如果有从a到到b的弧，的弧，并且有从并且有从b到到c的弧，就补充上从的弧，就补充上从a到到c的弧，就得到
26、了的弧，就得到了R的的传递闭包传递闭包t(R)的关系图。的关系图。定理：若定理：若R AA，则则t(R)=Ri=R R2 R3 证明略（教材证明略（教材P73）定理：若定理：若R AA，|A|=n则则t(R)=Ri=R R2 R3 Rn i=1n证明略（教材证明略（教材P74）闭包运算闭包运算定理：定理：证明：证明：=s(R IA)=(R IA)(R IA)-1=(R IA)(R-1 IA-1)=(R R-1)IA =r(R R-1)定理：定理：定理：定理：闭包运算闭包运算定理：定理：证明：证明：由于由于RIA=IAR=R，且且IA IA=IA；(R IA)2=(R IA)(R IA)=R(R
27、 IA)IA (R IA)=IA R R2 因此，因此，tr(R)=t(R IA)=(R IA)i i=1 用归纳法可证：用归纳法可证：i=1=(IA (Rj)=IA (Rj)=IA t(R)=rt(R)j=1i j=1 R (S T)R S R TR2Rp73关系的闭包运算关系的闭包运算设集合设集合A=a,b,c,d上的关系上的关系R=,，用矩阵运算，用矩阵运算求出求出R的传递闭包的传递闭包 0100101000010000RM关系矩阵：关系矩阵：010010001 100101001001 1 1000010010001 1000000010001RIMM自反闭包：自反闭包：r(R)=R
28、IA关系的闭包运算关系的闭包运算所以，所以，r(R)=,对称闭包：对称闭包：S(R)=MR MR-1关系的闭包运算关系的闭包运算010001000100101010001010,000101000101000000100010RRMM传递闭包：传递闭包：关系的闭包运算关系的闭包运算2341 1 1 11 1 1 1000 10000RMMMMRRRt(R)=,等价关系与划分等价关系与划分23.设集合设集合A=1,2,3,4,5，求求A上的一个划分上的一个划分1,2,3,4,5的等价关系，并画出关系图：的等价关系，并画出关系图：解：解：R=12345等价关系与划分的对应关系等价关系与划分的对应关
29、系已知已知=ab,c是是A=a,b,c的一个划分，由的一个划分，由决定的决定的A上的一个等价关系是上的一个等价关系是 。等价关系的证明等价关系的证明20.设设R和和S是非空集合是非空集合A上的等价关系，试确定下面各式是否为上的等价关系，试确定下面各式是否为等价关系。若是则证明之，若不是则举例说明：等价关系。若是则证明之，若不是则举例说明：证明：证明：1)对于对于 x A，有有xRx。因此有因此有xR2x，2)对于对于 x,y A，若有若有xR2y，则必存在则必存在z A，有有xRz,zRy，因为因为R是对称的，所以必定有：是对称的，所以必定有：yRz,zRx，即有即有yR2x。也就是说：若有也
30、就是说：若有xR2y，则必有则必有yR2x，3)对于对于 x,y,z A，若有若有xR2y,yR2z，则则 a,b A，有：有：xRa和和aRy 以及以及 yRb和和bRz，因为因为R是传递的，所以必定有：是传递的，所以必定有：xRy,yRz。则若有则若有xR2y,yR2z，必有必有xR2z，。等价关系的证明等价关系的证明21.设设R是是A上的二元关系，对于上的二元关系，对于 a,b,c A，若若aRb,bRc，则则cRa，称称R是是。求证：求证：R是自反的和循环的，当且仅当是自反的和循环的，当且仅当R是等价关系是等价关系证明：证明：1)，则，则、对称的和传递的。、对称的和传递的。对于对于 a
31、,b,c A，若若aRb,bRc，因为因为R是传递的，所以有是传递的，所以有aRc又因为又因为R是对称的，所以有是对称的，所以有cRa。所以所以2)，则对于则对于 a,b,c A，若若aRb,bRc，则则cRa因为因为R是自反的，所以有是自反的，所以有aRa，所以有所以有aRc，所以所以若有若有aRb，因为有因为有bRb，则有则有bRa，所以所以，故，故R是等价关系是等价关系cRa,aRa 则则aRc偏序关系的证明偏序关系的证明27.设设R是集合是集合A上的偏序关系，且上的偏序关系，且B A，求证：求证：R (BB)是是B上的偏序关系上的偏序关系证明：证明：1)，一定有：一定有：BB因为因为B
32、 A，所以所以x A，所以一定有：所以一定有：R所以，所以，所以：所以：R (BB)是是偏序关系的证明偏序关系的证明27.设设R是集合是集合A上的偏序关系，且上的偏序关系，且B A，求证：求证：R (BB)是是B上的偏序关系上的偏序关系2)对于对于 x,y B，一定有一定有 BB 且且 BB 因为因为R是反对称的，所以若有是反对称的，所以若有 R且且 R，则有则有x=y所以：所以：，则有：则有：R 且且 R，所以：所以：R (BB)是是偏序关系的证明偏序关系的证明27.设设R是集合是集合A上的偏序关系，且上的偏序关系，且B A，求证：求证：R (BB)是是B上的偏序关系上的偏序关系3)对于对于
33、 x,y,z B，一定有一定有,BB 因为因为R是传递的是传递的,所以若有所以若有 R且且 R,则有则有 R所以：所以：，则有：则有：所以：所以：R (BB)是是。故。故R (BB)是是B上偏序关系上偏序关系设设R1是是A上的等价关系，上的等价关系，R2是是B上的等价关系，上的等价关系，A且且B。关系关系R满足满足,RR1且且R2，证明，证明R是是AB上的等价关系上的等价关系 哈斯图与偏序集中特殊位置的元素哈斯图与偏序集中特殊位置的元素28.图中给出了偏序集图中给出了偏序集的哈斯图，其中的哈斯图，其中A=判断下面各式的真假判断下面各式的真假cbade哈斯图与偏序集中特殊位置的元素哈斯图与偏序集
34、中特殊位置的元素28.图中给出了偏序集图中给出了偏序集的哈斯图，其中的哈斯图，其中A=求求A中最大元和最小元中最大元和最小元求求A中的极大元和极小元中的极大元和极小元cbade28.图中给出了偏序集图中给出了偏序集的哈斯图，其中的哈斯图，其中A=求下面各子集的上界和下界求下面各子集的上界和下界并指出它们的上确界和下确界并指出它们的上确界和下确界哈斯图与偏序集中特殊位置的元素哈斯图与偏序集中特殊位置的元素cbade哈斯图哈斯图设设A=2,5,6,10,15,30，R是是A上的整除关系，上的整除关系，B=2,5,6,10，则，则B的极小元是的极小元是 ，极大元是，极大元是 ，最小元是最小元是 ，最
35、大元是，最大元是 ，上界是，上界是 ，下界，下界是是 ，上确界是，上确界是 ，下确界是，下确界是 。函数函数4.求证：从求证：从NN到到N的函数的函数f(x,y)=x+y，和和g(x,y)=xy是是满射函数，但不是单射函数满射函数，但不是单射函数证明：证明：，f(x,0)=x+0=x，因此，总存在因此，总存在NN且总存在且总存在NN 所以所以f和和g都不是单射的都不是单射的函数函数9.设设 f:A B 是满射函数，且函数是满射函数，且函数 g:B P(A)，定义为：定义为：g(b)=x|x A f(x)=b求证：求证：g是单射的。其逆是否成立？是单射的。其逆是否成立？证明：证明：对于对于 B，且且 由于由于f是满射的，则必存在是满射的，则必存在 A，使得使得f()=b1，f()=b2g(b1)=x|x Af(x)=b1,g(b2)=x|x Af(x)=b2则则，有有f(x)=b1，且有且有f(x)b2，即即即即所以，所以，g是单射的是单射的函数函数设设 f:A B 是满射函数，且函数是满射函数，且函数 g:B P(A)，定，定义为：义为：g(b)=x|x A f(x)=b求证：求证：g是单射的。是单射的。设设g f是复合函数，如果是复合函数，如果g f是双射，那么是双射，那么f是入射而是入射而g是满是满射射
