3 映　　 射 现实世界中的许多运动变化现象都表现出变量之间的依赖关系。数学上,我们用映 射模型描述这种依赖关系,并通过研究映射的性质了解变化的规律。映射是数学中最基 本且最重要的概念之一。映射的基本知识在经济学等学科以及现实生活中有着广泛的应 用。在高等数学中,映射的概念是从变量的角度提出来的,并且仅在实数集合上讨论,这 种映射一般是连续或间断连续的。 在高中阶段,读者应已学习了运用集合和对应的集合语言描述函数的概念,了解建立 函数模型的过程和方法,并能初步运用函数的思想理解和处理生活中的简单问题。而函 数是两个数集间的一种确定的对应关系,是特殊的映射。所以,当我们将数集扩展到任意 的集合时,就可以把函数的概念加以推广,得到映射的概念。 本章主要将连续映射的概念推广到对离散领域的讨论,即将映射看作一种特殊的二 元关系。映射的概念是运动变化和对立统一等观点在数学中的具体表现。 本章主要介绍映射的基本内容,通过本章学习,读者将掌握以下内容: (1)映射的基本概念; (2)映射的单射、满射和双射性质; (3)映射的复合运算; (4)映射的逆运算。 3.映射的基本概念 1 定义3.1.1 设 X 和 Y 是任意两个集合 , 如果 f 满 f 是一个从 X 到 Y 的二元关系, 足对于每一个x∈X,都有唯一的y∈ Y 使得∈f, mappinf: X → Y 或Xf →Y。 当∈ f 时,通常记为y=f(x), 且记f(X)={f(x)|x∈X}。这时称 x 为 映射的原像, y 为 x 在 f 下的映像。集合 X 称为 f 的定义域,记作domf= X 。由所有映 像组成的集合称为映射的值域,记作ranf.Y,即 )∧(f( ranf={y|(.x)(x∈Xy=))}。 由定义3.1可知,映射与关系的区别在于:映射的定义域(x) 为A,而关系不一定是;映 射要求 A 中每个元素只对应一个像,而关系则可以一个元素对应多个像。因而,一个关 1. 78 离散数学 系 f 是映射,则 f 应满足: (1)Df =A; (2)若f(=b1 且f(=b2, b2, a)a)则b1=即映射具有单值性 。 由于映射的单值性是不能倒过来的,因而,映射的逆关系不一定是映射 。 例3.1 1. 判断下列关系中哪个能构成映射 。 c,1,3,5,f2, (1)集合Xd},6},f3 分别是 X 到 Y 的二元关 系,其中 ={a,b,Y={2,4,f1, f1={,,,}, f2={,,}, f3={,,,, }。 (2)f={x2>|x2∈ N ,且x1+x2<10 } 。 (1,3,5,7,9},1} , ∈f,否则∈f。 解(1)f1 是 X 到 Y 的映射;f2 不是 X 到 Y 的映射,因为 X 中的元素 c 与 Y 中的 元素都不相关;因为 X 中的元素 d 与 Y 中的两个元素有关。 f3 也不是 X 到 Y 的映射, (2) f 不能构成映射,因为x1 不能取定义域中所有的值,且x1 可对应很多x2。 (3) f 能构成映射,因为对于每一个x∈ X ,都有唯一y∈ Y 与之对应。 例3.1.2 设A={1,2,3}, f={<1,1>,<2,1>,<3,2>}, g={<1,2>,<2,3>,<3,1>,<3,2>}, h={<1,2>,<2,3>}, 试判断f、 g 和 h 是否为 A 到 A 的映射。 解因为Df = A 且 f 具有单值性,所以 f 是映射。 对于g,因为<3,1>∈ g 且<3,2>∈g,所以 g 不具有单值性,因而 g 不是映射。 定义3.1.2 对于关系h,Dh ={1,2}≠A,所以 h 不是映射。 设映射f:A→B,如果XA,且对于所有的x∈ X 和 x∈A,有 X →Y,g:=Y=B, 则称映射 f 和 g 相等,记作f=g。 f(x)=g(x), 对集合 A 和B,从 A 到 B 的所有映射的集合记为BA ,即 BA ={f|f:A→B}。 定理3.若 A 和 B 是有限集合,n,则 定义3.1.3 1.1 |A|=m,|B| = |BA|=nm 。 证 明 设A={a2,…,}, f 是 A 到 B 的任意映射,则Df =A,于 是 a1,am >,f(>,…,f()>} 。 f={,<3, a>,<2,c>}。 令S={1,T={c}, 则 f(S)a,={1,2,3},a, ={c},f-1(T)3}。 定理3.设 f 是 A 到 B 的映射,、、则: ( 1.2 )。 A1 A2.A,B1 B2.B, 1)f(A1∪A2)=f(A1)∪f(A2 (2)f(A1∩A2).f(A1)∩f(A2) 。 (3)f(A1-A2).f(A1)-f(A2) 。 (4)f-1(B1∪B2)=f-1(B1)∪f-1(B2)。 (5)f-1(B1∩B2)=f-1(B1)∩f-1(B2)。 (6)f-1(B1-B2)=f-1(B1)-f-1(B2)。 (7)A1.f-1(f(A1))。 (8)f(f-1(B1)).B1。 证明仅证(2), 其他证明留给读者。 对任意的y∈f(A1∩A2), 存在x∈A1∩A2 使得f(x)=y,则有x∈A1 且f(x)= y,x∈A2 且f(x)=y,于是y∈f(A1)且y∈f(A2), 即有y∈f(A1)∩f(A2), 所以 f(A1∩A2).f(A1)∩f(A2) 。 下面通过一个例子说明(2)中的等号不一定成立 。 例如,A={2},a},A→B,1)f(=a, 1,B={f:f(=2) 取A1={1},A2={2}, 则A1∩A2=. , 从而f(A1∩A2)=., A1)∩f(={} 。 但f(A2) a 习题3. 1 (A) 设 X ={b},2,求从 X 到 Y 和从 Y 到 X 的映射数目。 1.a,Y={1,3}, 1,3},a,求BA 。 2.设A={2,B={b}, 3.设 f 指定世界各国的首都, 求 (1) f 的定义域 ; 80 离散数学 (2)f(法国); (3)f(加拿大); (4)f(俄罗斯)。 4.设A={1,3,4},a,c,e}, 请问下列二元关系哪些属于A→B( A 到 B 映射的集合)? 2,B={b,d, (B) (1)R1={<1,b>,<3,d>} a>,<2,c>,<4, (2)R2={<2,e>,<3,d>,<4, b> } (3)R3={<1,b>,<3,d> } a>,<2,c>,<1, (4)R4={<1,2>,<2,c>,<4,d> } b>,<3, (5)R5={<1,c>,<3,c> } c>,<2,c>,<4, (6)R6={<3,d> } e>,<4, 5.(参考北京大学2000 年硕士生研究生入学考试试题) ={b,d},B={ γ}, 则|BA|。 (C) 设Aa,c,α, β,= 3.映射的性质 2 2.单射 3.1 定义3.2.1 设映射f: X →Y,如果对于 X 中的任意两个元素x1 和x2,当x1≠x2 时,都有f(x1)≠f(x2), 则称 f 为 X 到 Y 的单射,也称入射。 由定义3.1可得: 2. f:A→ B 是单射当且仅当对任意的x1、x2∈A,若x1≠x2,则有f(x1)≠f(x2), 当 且仅当对任意的x1、x2∈A,若f(x1)=f(x2), 则有x1=x2。 例如,集合X={b,Y={2,4},且有: a,c},1,3, f 是 X 到 Y 的映射, 1,b)2,c)3, 则 f 就是从 X 到 Y 的单射。 f(a)=f(=f(= 2.满射 3.2 定义3.2.2 设映射f: X →Y,如果f(X)=Y,即 Y 中的每一个元素是 X 中一个或 多个元素的映像,则称 f 为 X 到 Y 的满射。设f:X→ Y 是满射,即对于任意的y∈Y,必 存在x∈ X 使得f(x)= y 成立。 由定义3.2可得: 2. f:A→ B 是满射.对任意的y∈B,存在x∈A,使f(x)=y 。 例如,集合X={2,Y={b},且 有 1,3},a, f 是 X 到 Y 的映射, f(1)a,2)b,3)b, =f(=f(= 第3章映射 81 则 f 是 X 到 Y 的满射,但显然不是单射。 2.双射 3.3 定义3.2.3 设映射f: X →Y,如果 f 既是单射又是满射,则称 f 为 X 到 Y 的双射, 也称一一对应映射。 a,c},1,3},且有例如,集合X={b,Y={2, f 是 X 到 Y 的映射, 1,b)3,c)2, 则 f 是从 X 到 Y 的双射。 f(a)=f(=f(= 特别地,.:.→ Y 是单射,.:.→. 是双射。 例3.2.1 确定如下关系是否是映射,若是映射,是否是单射、满射、双射。 1,3,5},a,c,e} , f1={<1,c>,<3, (1)设X={2,4,Y={b,d, a>,<2,e>} , f2={<1,a>,<2,e>,<3,b>,<5, c>,<4,c>} , f3={<1,a>,<2,e>,<3,c>,<5, (2)设X=Y=R(实数集合) b>,<4,d>}。 f1={ | f2={|x∈R} , f3={ | 解(1)f1 不是 X 到 Y 的映射,因为domf1={1,2,3}≠X; f2 是从 X 到 Y 的映射,但f2(=5)c,af2={b,e}≠Y, 3)f2(=rna,c,因此f2 既非 单射也非满射; f3 是从 X 到 Y 的双射。 (2)f1 是从 X 到 Y 映射,但f1(1)=f1(-1)=1,因此它不是单射,又因为该映射的 最小值是0,所以ranf1 是区间[0,+∞), 不是整个实数集,因此它也不是满射; f2 是从 X 到 Y 的单射; f3 是从 X 到 Y 的双射。 设映射IX :X→ X 满足IX (x)=x,则称IX 为 X 上的恒等映射。 则称 定义3.2.4 定义3.2.5f 为常映射。 (1)设f: X →Y,如果存在y∈ Y 使得对所有的x∈ X 都有f(x)=y, (2) X 上的恒等关系Ix 就是 X 上的恒等映射,对于所有的x∈X,都有Ix (x)=x。 X→X, x2∈X, x2), 为单调递增的;如果x1),并说明f 是否为单射、满射、双射。 3.3 映射的复合运算 由于映射是一种特殊的关系,下面讨论两个映射的复合关系。 定理3.3.1 设X ,Y,Z 是集合,f 是X 到Y 的二元关系,g 是Y 到Z 的二元关系,当 f 和g 都是映射时,则复合关系f..g 是X 到Z 的映射。 定义3.3.1 设映射f:X →Y,g:Y→Z,经f 和g 复合后的映射称为复合映射,记 作g..f,它是X 到Z 的映射,若x∈X ,Y∈Y,z∈Z,且 f(x)=y, g(y)=z, 则 第3章映射 83 g..f(x)=z。 需注意的是,当复合关系是一个复合映射时,在其表示标记中颠倒 f 和 g 的位置而 写成g..f,这是为了与通常意义下复合映射的表示方法保持一致。 例3.3.1 x,z},a,c,Z={2, f 是 X 到 Y 的映射, 设集合X={y,Y={b,d},1,3}, g 是 Y 到 Z 的映射,其中 f(x)c,y)b,z)=c,=f(=f( 2,b)1,c)3,d) 求复合映射g..f。 g(a)=g(=g(=g(=1, 解易知g.. f 是 X 到 Z 的映射,且 g..f(x)g(x))g(=3, =f(=c) g..f(=f(=g(= y)g(y))b)1, g..f(=f(g(= z)g(z))=c)3。 定理3.3.2 若映射g:A→ B 和f:B→ C 是双射,则f..g:A→ C 是双射。 证明对任意的z∈C,由f: B → C 是双射,即f: B → C 是满射,则存在y∈ B 使 f(=。 y) z 对于y∈B,由g:A→ B 是双射,即g:A→ B 是满射,则存在x∈ A 使g(x)=y,于 是有f..g(x)=f(g(x))=z。所以f.. g 是满射。 对任意的x1、若x1≠x2, A→ B 是双射,即g:A→ B 是单射, x1)≠ g()。 x2∈A, 由g:则g( x2 又由f:B→ C 是双射, B→ C 是单射, g(g(于是f..g(x1)≠ f..g()。所以f.. 即f:则f(x1))≠f(x2)), x2 g 是单射 。 综上可知 , f.. g 是双射。 由于映射的复合仍是一个映射,因此同样可求3个映射的复合,并且和二元关系的合 成一样,映射的复合运算也满足结合律。 定理3.3 A→B,B→C= , ( C→D,。(则) 3. 设映射f:g:h: h..(g..f)h..g).. f 证明因为f:g:h:由定理3.1可知,g..f) h..g).. f 都是 A 到 D 的映射 A 。 →B,B→C,C→D,3.h..(和( 对任意的a∈A,有 a)h..(a))h(f(= ( h..(g..f)(=g..f(=g(a)))h..g)..f(a) , 所以 h..(g..f)h..g)..f 。 设 R 是实数集,g, = ( 例3.3.2 f, h 都是 R 到 R 的映射,其 中 f(x)x+2,x)x-h(=x, h..(g..f),(..f。 =g(=2,x) 3 求g..f,h..g) 解g..f(x)=g(x+2)=(x+2)-2=x, h..(g..f)(x)=h(g..f(x))=h(x)=3x, (x)h..g)x)h(f(x)) ) h..g)..f(= ( f(=g( 84 离散数学 =h(g(x+2))=h((x+2)-2)=h(x)=3x 。 定理3.3.4 g.. f 是 f 和 g 的复合映射 , 设 f 和 g 为映射,则: (1)若 f 和 g 是满射,则g.. f 是满射; (2)若 f 和 g 是单射,则g.. f 是单射; (3)若 f 和 g 是双射,则g.. f 是双射 。 证明(X→Y,Y→Z,则g..f: X →Z。由于 g 是满射 , 1)设f:g:对于 Z 中任意元 素z∈Z,必有y∈Y, y)。 使得g( = 对于y∈Y,又因为 f 是满射,所(z) 以也必有x∈ X ,使得f(x)=y 。 因此,对于 Z 中任意元素z,必有x∈X,使得g..f(x)=z, 所以g.. f 是满射 。 (2)由于 f 和 g 都是单射, x2),f( x2∈X, 必有 因此对于任意x1,当x1≠x2 时, f(x1)≠f(g(x1))≠g(f(x2)), 即当x1≠x2 时,必有 g..f(x1)≠g..f(x2), 所以g.. f 是单射。 (3)由(1)、(2)证明结果即可得证 。 定理3.5 g.. f 是 f 和 g 的复合映射, X →Y,Y→ 3.设 f 和 g 为映射,若设映射f:g: Z,g.. f 是 f 和 g 的复合映射,则: (1)若g.. f 是满射,则 g 是满射; (2)若g.. f 是单射,则 f 是单射; (3)若g.. f 是双射,则 f 是单射, g 是满射 。 证明设g:f:由定理3.1知 , A→B,B→C,3.f.. g 为 A 到 C 的映射。 (1)对任意的z∈C,因f.. g 是满射,则存在x∈ A 使f..g(x)=z,即f(g(x))=z。 由g:A→ B 可知g(x)∈B,于是有y=g(x)∈B,使得f(y)=z。 因此, f 是满射。 (2)对任意的x1、x2∈A,若x1≠x2,则由f.. g 是单射得f..g(x1)≠f..g(x2), 于是 f(g(g(必有g(x1)≠g(x2 g 是单射。 x1))≠f(x2)), )。所以, (3)由(1)、(2)得证。 在定理3.5中, g 不一定是满射;f.. g 是单射时, f 不一定是单射。 3.f.. g 是满射时, 例如,设A={B={d},c}, a},b,C={ g:A→B,B→C,,c>}。 f:g={b>},},但 g 不是满射, 习题3. 3 1.下列命题正确的有()。 (A) A.若g,则g.. f 是满射。若g.. f 是满射, f 都是满射。 f 是满射,B. 则g, 第3章映射 85 C.若g.. f 是单射,则g, f 都是单射。D.若g.. f 是单射,则 f 是单射。 设映射f:定义为f=, 3.给定f:A→ B 和g:B→C。试证明:若g.. f 是满射,则 g 是满射。 4.若T→U, f 是单射,g:h:满足f..g=f..h,试证明:g=h。 S→T,S→T, 5.给出映射f, h 的实例:f:T→U,S→T,S→T,f..但g≠h(B)。 g,g:h:f..g=h, (B) 6.设f:A→B,g:B→C,若g.. f 是单射,则 f 是单射,并举例说明 g 不一定是单射。 (C) 7.(参考北京大学1993 年硕士生研究生入学考试试题)设映射f:N→N×N,定义为 f(x)=,请判断 f 是否为单射、满射或双射,并说明理由。 3.映射的逆运算 4 任何关系都存在逆关系,一个关系的逆关系不一定是映射,一个映射的逆关系也不一 定是映射。 定理3.1 设f:X→ Y 是一个双射,则 f 的逆关系f-是 Y 到 X 的双射。 证明对任意的y1、y2∈B,若f-1(y1)=f-1(y2)=x,则f(x)=y1,f(x)=y2。 因为f:A→ B 是映射,则y1=y2。所以f-1是单射。 对任意x∈A,必存在y∈ B 使f(x)=y,从而f-1(y)=x,所以f-1是满射。 综上可得,1:B→ A 是双射。 4.1 f 例如,设Xx,z},a,c}, X →Y, ={y,Y={b,f: 且 f={,c>,b>}, 则 定义3.4.1 f-1={,y>,z>}。 设f: X → Y 是一个双射,其逆关系f-1称为 f 的逆映射,也记作f-1。 若映射 f 使得f(a)b, 1,使得f-1(=。即∈f, ∈f-1,因此f-1逆映射是 f 的逆关系。 定理3.2 设f:X→ Y 是一个双射, 4. (f-1)-(则) 1=f。 证明由定理3.1可知,Y→X, 因此它的逆映射(-1必然存在, 而且也是双射。 4.f-1:且是双射, f-1) 并且对于任意x∈X, x),f(→x,(x→f( f:x→ff-1:x)f-1)-1:x)。((有) 显然,(f-1)-1= f 成立。 定理3.4.3 设f:X→ Y 是一个双射,则 (1)f-1..f=IX (2)f..f-1=IY 。 86 离散数学 (3)f=IY..f=f..IX 。 证明(1)因为f:X→ Y 是一个双射,所以f-Y→X,故f-1..f: X → X 。对于任 1: 意x∈X,必存在y∈Y,使得f(x)=y,且 1( f-1(y)=x1, ( 因此, 故f-1..f=IX 成立。 f-1..f(x)=f-f(x))=f-y)=x, 例3.1 设X={2,a,c},且 1,3},b, f 是 X 到 Y 的双射, a>,<2,b>}, 求f-1和f..f-1和f-1..f。 f={<1,c>,<3, 解由于 f 是双射,因此由逆映射的定义可得 f-1={,, }。 4.Y={ 同理可得 1a >,} , f-1..f={<1,1>,<2,2>,<3,3>} 。 定理3.4.4 X→Y,Y→ Z 均为双射, 则 f..f-={,,,s,x, 对于A={t},z}, 已知f: A →B,其中f={}, 判断 f 是否可逆,若可逆则求其逆。 3.设f:R→ R 定义为f(x)=2x-3,现在 f 是一对一且满足满射。因此, 逆映射f-1,求f-1的一个表达式。 f 有一个 87 第3章映射 4.证明f(x)=2x 是一个可逆映射。 5.设f,g, h 均为实数集 R 上的映射,且g..f=h..f,则若f=( ), 一定能推出 g=h。 A.x2>|B.x>| {|x∈R}D.{|x∈R} (B) 6.设f:A→ B 是一个映射,记f-1为 f 的逆关系,f.. g 为 f 和 g 的复合关系,试证 明:当且仅当f-1..f=IB..f=IB 时, f 是满射。 (C) 7.(参考北京大学1997 年硕士生研究生入学考试试题)设 A ={1,2,3},f∈AA ,且 f(1)=f(2)=1,f(3)=2,定义G:A→P(A),G(x)=f-1(x)。计算ranG。 *3.映射的思维导图 5 *3.映射的算法思想 6 映射是集合论中的一个十分重要的概念。通过该组实验,学生应能更加深刻地理解 映射的概念和性质,并掌握映射性质的判定等。 3.1 映射的判定 6. 判断任意一个关系是否为映射,若是映射,判定其是否为单射、满射或双射。 设 A 和 B 为集合,f. A ×B,若对任意的x∈A,都存在唯一的y∈ B 使得xfy 成 立,则称 f 为从 A 到 B 的映射。 设 f 是 A 到 B 的映射,若ranf=B(或f(A)=B), 则称 f 是 A 到 B 的满射;若对任 意的x1、x2∈A,x1≠x2,都有f(x1)≠f(x2), 则称 f 是 A 到 B 的单射;若 f 既是满射 88 离散数学 又是单射,则称 f 是 A 到 B 的双射。 在程序中集合用列举法表示,关系用集合表示。 例如,2,3},a,c}, A 到 B 上的关系 A={1,B={b, a>,<2,c>}。 f={<1,b>,<3, 3.2 求满射 6. 设有限集合 A 和B,且|A|=m,|B|=n,求有多少映射满足从 A 到 B 上的满射。 根据映射的定义可知,从 A 到 B 上的映射必有m≥n,否则不是映射。利用公式: Cn Cn-1 m +Cn-2 n-1C1 m · nm -·(1)·(2) m -…+(1)· 其解即为所(n) 求。 F=nn-nn-- n 1 3.本章小结 7 本章介绍了映射的基本概念,并给出映射作为特殊二元关系的不同之处。然后,讲述 了具有不同性质的3种特殊映射:单射、满射和双射,以及如何从定义入手,判断和证明 映射具有某种特殊性质,并给出了几个常用的映射。之后,介绍了复合映射和逆映射,给 出了相关的定理以及证明。最后给出映射的思维导图和部分算法思想描述。通过本章的 学习,读者应能够进一步加强对映射和相关知识的理解,为后续的学习和应用打下很好的 基础。 逻辑是研究推理的科学。早在17 世纪,莱布尼茨就提出一种设想: 能否使人们的推理不依赖对推理过程中命题含义的思考,而用计算代替 思维来完成推理过程。莱布尼茨希望能用数学方法来研究思维,数理逻 辑就是在这种思维下产生的。用希尔伯特的话来说,数理逻辑是把数学 上的形式化方法应用到逻辑领域的结果。 所谓数学的方法,就是用一套数学的符号系统来描述和处理思维的 形式与规律,避免歧义性。因此,数理逻辑又称为符号逻辑。推理是研究 前提和结论之间的关系以及思维的规律,即符号化的过程。 数理逻辑和电子计算机的发展有着密切的联系,它为机器证明、自动 程序设计、计算机辅助设计等计算机应用和理论研究提供了必要的理论 基础。 从本章开始,我们用两章的篇幅介绍数理逻辑最基本的内容:命题 逻辑和谓词逻辑。 第 二 部 分 数 理 逻 辑 4 命题逻 辑 任何基于命题分析的逻辑统称为命题逻辑,命题是研究思维规律的科学中一项基本 要素,它是一个判断的语言表达。 本章主要介绍命题逻辑的基本内容。通过本章学习,读者将掌握以下内容: (1)命题的基本概念; (2)否定、合取、析取、不可兼析取、条件、双条件、与非、或非和条件否定联结词; (3)命题公式的定义、符号化、解释、真值表和类型; (4)命题公式的逻辑等值的定义、基本的逻辑等值式、等值演算和对偶定理; (5)析取(合取)范式、主析取(主合取)范式及其应用; (6)命题公式的逻辑蕴涵的定义、证明方法和基本的逻辑蕴涵式; (7)全功能联结词; (8)命题逻辑推理理论和规则、判断有效结论的常用方法。 4.命题 1 在数理逻辑中,为了表达概念,陈述理论和规则,常常需要应用语言进行描述,但是日 常使用的自然语言往往在叙述时不够确切,也易产生二义性,因此就需要引入一种目标语 言,这种目标语言和一些公式符号就形成了数理逻辑的形式符号体系。所谓目标语言就 是表达判断的一些语言的汇集,而判断就是对事物有肯定或否定的一种思维形式,因此能 表达判断的语言是陈述句,它称作命题。一个命题具有一个“值”,称为真值。真值只有 “真”和“假”两种,分别记作True(真)和False(假), 符号表示为T和F。 数理逻辑研究的中心问题是推理,而推理的前提和结论都是表达判断的陈述句。在 自然语言中,只有具有确定真值的陈述句才是命题,一切没有判断内容的句子,以及无所 谓是非的句子,如感叹句、疑问句、祈使句等都不能作为命题。 不能再被分解成更简单的语句的命题称为原子命题。原子命题是命题逻辑中最基本 的单位。当命题变元表示原子命题时,该变元称为原子变元。所有这些命题都应具有确 定的真值。一个命题变元不是命题,因为它的真值不能确定。但一旦我们用一个具体的 命题取代它时,它的真值就确定了,这时称对命题变元进行指派。 人的思维活动是靠自然语言来表达的。然而,由于自然语言易产生二义性,用它来表 示严格的推理就不合适了。为了解决这一问题,人们在数理逻辑中引进了符号语言。 92 离散数学 如果一个句子是命题,它必须满足以下条件: (1)该句子是具有判断性的陈述语句; (2)它有确定的真值,非真即假。 判定一个语句是否是命题,并不是一定要知道其真假值,我们只关心它“是否具有真 假值”这个事实。也就是说,对一个语句,有时可能无法确定它的真假,但是它的确有真 假,那么这个语句就是命题。例如下面4个语句都是命题。 (1)珠海是中国最大的城市。 (2)今天是星期一。 (3)所有素数都是奇数 。 (4)1+1=2 。 例4.1 判断下列语句是否为命题,若是命题,判断其真值 。 1. (1)10 是素数 。 (2)f(x)=在闭区间[b]上连续 。 x2 a, (3)北京是中国的首都 。 (4)1001+11=1100 。 (5)请勿喧哗! (6)你记住了吗? (7)这个风景真美呀 ! (8)x+y=7 。 解(1)~(4)是命题,因为它们都是具有真假意义的陈述句。(1)是假命题,(2)(3) 是真命题,(4)在二进制中为真,在十进制中为假,故需要根据所处环境才能确定真值。 (5)~(8)都不是命题,(5)是祈使句,(6)是疑问句,(7)是感叹句。在(8)中,x, y 是 变量,无法判断其真值。 由于命题只有真、假两个真值情况,所以命题逻辑也称为二值逻辑。如果一个命题是 真的,它的真值就是1;如果一个命题是假的,它的真值就是0。 同理,人们也用“1代(”) 表一个抽象的真命题,用“0”代表一个抽象的假命题。 例4.2 判断下列语句是否为命题。 1. (1)其他星球上有生命存在。 (2)我正在说谎。 解(1)语句在目前可能无法确定其真值,但从本质而论,这句话是有真假值的,所 以也被认为是命题。 (2)语句不是命题,是悖论。在判断一个句子是否为命题时,首先从语法上判断它是 否为陈述句。但是,有一些“自指谓”的陈述句不属于命题,因为这种“自指谓”的陈述句产 生悖论。所谓“自指谓”指其结论对自身而言真假矛盾。对于(2)语句,当它为假时,它便 是真;当它为真时,它便是假。 命题通常使用大写字母A,B,…, Z 及其带下标的大写字母或数字表示,如A1, R 等,例如A1:我是一名大学生。 表示命题的符号称为命题标识符,在这个例子中,A1 即为命题标识符。 93 第4章命题逻辑 一个命题标识符如表示确定的命题,则称它为命题常元。一个仅表示任意命题位置, 没有指定具体内容的命题标识符称为命题变元。 例如,如果 P 表示“今天有雨”,则 P 是命题常元。 习题4. 1 1.下列语句是命题的有() (A) x+y>0 。 A.明年中秋节的晚上是晴天。B. C.y>0,当且仅当 x 和 y 都大于0。D.我正在说谎 。 2. 各命题中真值为真的命题有() 下列(x) A.2+2=4当且仅当3是奇数。 B.2+2=4当且仅当3不是奇数。 C.2+2≠4 当且仅当3是奇数。 D.2+2≠4 当且仅当3不是奇数。 3.下列语句不是命题的有() A.x=13 。 B.离散数学是计算机系的一门必修课。 C.鸡有3只脚。 D.太阳系以外的星球上有生物。 E.你打算考硕士研究生吗? 4.下列语句是命题的有() A.2是素数。B.x+5>6 。 C.地球外的星球上也有人。D.这朵花多好看呀! 5.设S={ N ,Q,R}, 下列命题正确的是() A.2∈ N , N ∈S,则2∈S。B. N .Q,Q∈S,则 N .S。 C. N .Q,Q.R,则 N .R。D... N ,..S,则.. N ∩S。 6.给定语句如下。 (B) (1)15 是素数(质数) 。 (2)10 能被2整除,3是偶数 。 (3)你下午有会吗? 若无会,请到我这儿来 ! (4)2x+3>0 。 (5)只有4是偶数,3才能被2整除。 (6)明年5月1日是晴天。 以上6个语句中,是原子命题的为( ), 是复合命题的为( ), 是真命题的为 ( ), 是假命题的是( ), 真值待定的命题是( )。 94 离散数学 (C) 7.(参考北京大学1990 年研究生入学考试试题)下列句子哪些是命题? 是命题的句 子哪些是原子命题(简单命题)? 哪些是复合命题? (1)你喜欢看电影吗? (2)大熊猫主要分布在我国东北 。 (3)2+x=5 。 (4)2+3>1 。 (5)小王和小李是同学。 (6)别讲话了! (7)这朵花真美丽。 (8)李梅能歌善舞。 (9)只要我有时间,我就来看你。 (10)只要你不怕困难,你才能战胜困难。 4.联词 2 结 在自然语言中,由一些简单的陈述句,通过“或”“与”“但是”等一些联结词组成较复杂的 句子称为复合语句。这种联结词的使用一般没有很严格的定义,因此有时显得不很确切。 在命题逻辑中,由原子命题通过特定的联结词构成的陈述句称为复合命题,联结词是 复合命题中的重要组成部分。原子命题和复合命题都是命题。 例如,P:今天晚上我在家看电视或出去看电影。 4.1 否定联结词.. 2. 定义4.2.1 设 P 是一个命题,命题“ P 是不对的”称为 P 的否定,记作“..P”,读作 “非P”。.. P 是真的,当且仅当 P 是假的。 例如,P:吉林大学是中国最大的大学。 ..P:吉林大学不是中国最大的大学。 命题 P 取值为真时,命题.. P 取值为假;命题 P 取值为假时,命题.. P 取值为真。 命题.. P 的取值也可以用一个表4.1来定义,其构造类似于集合的成员表。表中 2. “1”和“0别标记该列命题取值为真和为假,“..”相当于自然语言中的“非”“不”“没有” 等否定词。分(”) 表4.1 2... P 运算表 P .. P 0 1 1 0 95 第4章命题逻辑 4.2 合取联结词∧(与) 2. 定义4.2.2 设P, Q 是两个命题,命题“ P 并且Q”称为P, Q 的合取,记作P∧Q,读 作“ P 且Q”。虽然P∧ Q 是真的,当且仅当 P 和 Q 都是真的。 “∧”是自然语言中“并且”“既…… 又……”“和”“以及”“不仅…… 而且……”虽(“) 然…… 但是……” 等词的逻辑抽象。命题P∧ Q 的取值可以用表4.2定义。 2. 表4.2 P∧ Q 运算表 2. P Q P∧ Q 0 0 0 0 1 0 1 0 0 1 1 1 在自然语言中,用联结词连接的两个陈述句在内容上总是存在着某种联系,也就是说 整个句子是有意义的。在数理逻辑中,我们关心的是复合命题与构成复合命题的各原子 命题间的真值关系,即抽象的逻辑关系,并不关心各语句的具体内容。因此,内容上毫无 联系的两个命题也能组成具有确定真值的复合命题。 例如,P:2×2=5。 Q:雪是黑的。 则P∧Q:2×2=5并且雪是黑的。 4.3 析取联结词∨(或) 2. 定义4.2.3 设P, Q 是两个命题,命题“ P 或者Q”称为P, Q 的析取,记作P∨Q, 作“ P 或Q”。规定P∨ Q 是真的,当且仅当P, Q 中至少有一个是真的。命题 P ∨ Q 的(读) 取值可以用表4.3定义。 2. 表4.3 P∨ Q 运算表 2. P Q P∨ Q 0 0 0 0 1 1 1 0 1 1 1 1 例如,P:今天下雨。 Q:今天刮风。 则P∨Q:今天下雨或者刮风。 96 离散数学 .............................................................................. .. .............. .. ★在很多情况下,自然语言中的“或者”一词包含了“不可兼”的意思。例如,“我 到北京出差或者到广州度假”表示的是二者只能居其一, 不会同时成立。 ............ .. 非此即彼, “ 按照联结词“∨” 的定义,当P, Q 都为真时,P∨ Q 也为真,因此, 不可兼或”,我们不可以用∨来表示。 .... .. .. .. .............................. .. .. .. ................................ ∨”所表示的“或” 是“可兼或”,对于“ 4.4 不可兼析取联结词∨(异或) 2. 定义4.2.4 设P, Q 是两个命题,则复合命题P∨ Q 称为 P 和 Q 的不可兼析取,也 称为异或,当且仅当 P 与 Q 的真值不相同时,P∨ Q 的真值为1,否则, P ∨ Q 的真值为 假。命题P∨ Q 的取值可以用表4.4表示。 2. 表4.4 P∨ Q 运算表 2. P Q P∨ Q 0 0 0 0 1 1 1 0 1 1 1 0 例如,设P:今天晚上我在家看电视。 Q:今天晚上我在家看电影 。 则P∨Q:今天晚上我在家看电视或出门看电影 。 在数理逻辑中用联结词“∨”(异或)表示“不可兼或”。由 于 P∨Q.(P∧..Q)∨(..P∧Q), 所以,∨可以用∨,∧,..表示,故我们不把它当作基本联结词。 联结词“∨”有以下性质。 (1)交换律:P∨Q.Q∨P。 (2)结合律:(P∨Q)∨R.P∨(Q∨R)。 (3)分配律:P∧(Q∨R).(P∧Q)∨(P∧R)。 (4)(P∨Q).(P∧..Q)∨(..P∧Q)。 (5)(P∨Q)...(P.Q)。 (6)P∨P.0;0∨P.P;1∨P...P。 例4.1 设P、Q、 R 为命题公式。如果P∨Q.R,则P∨R.Q,Q∨R.P。 证明 2. 如果P∨Q.R,则 P∨R.P∨P∨Q.F∨Q.Q, Q∨R.Q∨P∨Q.Q∨Q∨P.F∨P.P。 P∨Q∨R=R∨R.F。