离散数学是研究离散对象的结构以及他们之间相互关系的科学
离散数学可以培养学生的数学修养和逻辑思维能力。正如著名的物理学家劳厄所说：
重要的不是获得知识，而是发展思维能力。教育是一切已学过东西都遗忘的时候，剩下的就是思维能力，它可以长期起作用。
常用数字上标：123
常用数字下标：：
常用字符上标：：˙
常用字符下标：：
常用小写字母上标：
常用大写字母上标：：
常用符号下标：
逻辑学起源于2000多年前的古希腊。
“逻辑”是英语Logic的译音，源于古希腊文，愿意主要指言语、思想、理性、规律性等。
逻辑学也称为形式逻辑，是关于“思维形态的结构”及其规律的科学。
思维形态是人们在思考过程中用以反映客观现实的具体形式，即概念、判断、推理。
由若干个已知的判断（前提）,推出新的判断（结论）的思维过程。
由一般规律推出个别事实的推理
数理逻辑（符号逻辑），数理逻辑是用“数学的方法”研究形式逻辑。
建立一套有严格定义的符号体系，即建立一套形式语言，来研究形式逻辑
数理逻辑分为“命题逻辑”和“谓词逻辑”两部分
命题是表达判断的陈述句。
一个判断只有两种可能：正确的判断或者错误的判断。
把这种“正确”或者“错误”赋予命题，就得到命题的真值。
命题的真值只有两个：“真”或“假”。
命题的真值为真：一个命题所表达的判断与客观情况一致，记作T(True)。
命题的真值为假：一个命题所表达的判断与客观情况不一致，记作F(False)。
判断一句话是否是命题有两个关键：
不能再分解成更简单陈述句的命题。
由若干个连接词、标点符号及原子命题复合构成的命题。
p->Q读成"P则Q".
称P是P->Q的前件,Q是P->Q的后件。也可以说P是Q的充分条件，Q是P的必要条件。
P->Q有一个善意的规定:当P为F时P->Q为T
用"->"表达必须前件是后件的充分条件，即若前件成立，后件一定成立。这一点需要特别注意！！！它决定了哪个作为前件，哪个作为后件
比较下面二表
先看一个命题公式:
P:3是素数。
该公式中有三种数值
在命题公式中有三种数据类型：
将一个命题常项或常值命题赋予命题变元的过程称为给命题变元赋值，也称为对命题变元作指派。
为了简化命题公式，约定：
一个含有命题变元的命题公式不是命题，因为它没有固定真值，但是给其中的所有命题变元赋值以后它就有了唯一的真值。将所有各种赋值情况汇列成表，即为该命题公式的真值表
例：命题公式(P->Q)∨Q的真值表如下所示
例：构造P->(Q-R)的真值表
例如：
等价的性质
P∨P为重言式(永真式);
P∧P为矛盾式(永假式);
可描述为:P->Q,P=>Q(假言推理规则)2.如果一个人是单身汉,则他不幸福;如果一个人不幸福,则他死的早;所以单身汉死的早.
可描述为:P->Q,Q->R=>P->R(假言三段论)3.若你发电子邮件告诉我密码,则我将完成程序的编写;我没有完成程序的编写.所以,你没有发电子邮件告诉我密码.
可描述为:P->Q,Q->P(否定后件式)4.这个案件的凶手肯定是王某或陈某;经过调查,王某不是凶手.所以,陈某是凶手.
可描述为:P∨Q,P=>Q(选言三段论)重言蕴含式的性质：范式范式的概念:命题变项及其否定统称作文字.仅有有限个文字构成的析取式称作简单析取式.仅有有限个文字构成的合取式称作简单合取式.
命题公式A如果可等价地写成如下形式：A1∨A2∨...∨An(n>=1)。其中每个项Ai(i=1,2,...,n)是命题变元或其否定形式的合取式，称该公式为A的析取范式。
命题公式A如果可等价地写成如下形式：A1∧A2∧...∧An(n>=1)。其中每个项Ai(i=1,2,...,n)是命题变元或其否定形式的析取式，称该公式为A的合取范式。
从定义可以看出：在析取范式与合取范式中只含有连接词“，∧，∨”。“”在命题变元之前。
注：P∧Q既是合取范式，也是析取范式。
是n个命题变元的合取式，其中每个变元出现且仅出现一次（以本身或否定形式），称这个合取式为小项。
例如：含有两个变元的小项：P∧Q、P∧Q，P∧Q、P∧Q;
若有n个变元，则有2n个小项。
例：
若一个命题公式的析取范式为A1∨A2∨...∨An(n>=1)。其中每个Ai（i=1,2，...，n）都是小项，则称之为该命题公式的主析取范式。
定理：在真值表中，一个使公式的真值为T的赋值所对应的小项的析取，即为此公式的主析取范式。
是n个命题变元的析取式，其中每个变元必出现且仅出现一次（以本身或否定形式），称该析取式为大项。
若有n个变元，则有2n个大项。
若一个命题公式的合取范式为A1∧A2∧...∧An(n>=1)。其中每个Ai（i=1,2，...，n）都是大项，则称之为该命题公式的主合取范式。
定理：在真值表中，一个使公式的真值为F的赋值所对应的大项的析取，即为此公式的主合取范式。
推理的过程就是证明永真蕴含式的过程。
令H1，H2，...，Hn是已知的命题公式（前提），若有H1∧H2∧...∧Hn=>C
则称C是H1，H2，...，Hn的有效结论，简称结论。
mindmap推理的方法直接推理间接推理条件论证反证法直接推理：直接推理是由一组前提，利用P规则、T规则直接推演得到有效结论的方法。
推理实际上就是证明永真蕴含的过程。为了使推理过程更加简单、明确，推理会采用另外一种书写格式
例1求证P->Q,Q->R,P=>R证明：
例2如果马会飞或羊吃草,则母鸡就会是飞鸟;如果母鸡是飞鸟,那么烤熟的鸭子还会跑;烤熟的鸭子不会跑。所以羊不吃草;
证明：解设P:马会飞;Q:羊吃草;R:母鸡是飞鸟;S:烤熟的鸭子会跑
(P∨Q)->R,R->S,S=>Q
如果要证明的结论是R->S的形式，则可以把结论中R->S的前件R作为附加前提，与给定的前提一起推出后件S即可。
定理如果H1∧H2∧...∧Hn∧R=>S，则H1∧H2∧...∧Hn=>R->S
证明:因为H∧H∧...∧H∧R=>S则
(H∧H∧...∧H∧R)->S是永真式而
(H∧H∧...∧H∧R)->S
我们把上述定理写成如下规则
CP规则(ConditionalProof):
不相容定义:
设H1，H2，...，Hn是命题公式，P1，P2，...，Pm是公式中的命题变元。如果P1，P2，...，Pm，至少有一组赋值使得H1，H2，...，Hn的真值为T，则称公式集合{H1，H2，...，Hn}是相容的（也称是一致的）；
如果对P1，P2，...，Pm的每一组赋值，都使得H1，H2，...，Hn的真值为F，则称公式集合{H1，H2，...，Hn}是不相容的（也称是不一致的）。
反证法
若要证明H1，H2，...，Hn=>C，只要证明{H1，H2，...，Hn,C}是不相容的即可。即：若要证明H1，H2，...，Hn=>C，只要证明H1∧H2∧...∧Hn∧C是个矛盾式即可。
定理如果H∧H∧...∧H∧C是个矛盾式，则H∧H∧...∧H=>C成立
证明:设H∧H∧...∧H∧C是矛盾式则
(H∧H∧...∧H∧C)是永真式而
(H∧H∧...∧H∧C)
所以H∧H∧...∧H=>C成立
问题的提出：所有的人都会死，苏格拉底是人，所以苏格拉底是会死的。A：所有的人都会死。B：苏格拉底是人。C：苏格拉底会死。该推理符号化为：A，B=>C这是著名的三段论推理，A是大前提，B是小前提，C是结论。显然，这个推理是有效的，但是这个推理用命题逻辑是无法推证的。因为命题A、B、C在句子的内部是有联系的，而仅把命题表示成一个大写字母，就掩盖了这种联系。也就是说一个命题仅用一个大写字母表示的方式太粗了，我们必须加以细化，用另外的表示方式来表达命题。命题是表达判断的陈述句，将其细分，表达出主语、谓语及宾语（若有的话），而一个句子中“谓语”最重要，这就提出了谓词的概念。基本概念个体：能够独立存在的具体或抽象的事物，称之为个体，也称之为客体。通常用小写英文字母a、b、c、...表示。
例如：小张，小李，8，a，沈阳，社会主义等等都是客体。
个体常项：具体或特定的个体。常用小写英文字母a、b、c、...表示。
个体变元：泛指某一个个体。常用小写英文字母x、y、z、...表示。
谓词：用以刻化个体属性或者表达个体之间关系的词，即为谓词。谓词用大写字母表示。
例：令S：是大学生，a：小张，b：小李命题：小张是大学生可以表示成S(a)。命题：小李是大学生可以表示成S(b)。从符号S(a)、S(b)可看出小张和小李都是大学生的共性。设Q：大于，命题3>7表示为Q(3,7)。设B：表示...在...与...之间,命题点a在点b与点c之间表示为B(a,b,c)一个命题若其中的个体是个体常项，则该命题用谓词后边加括号，括号内是若干个体表示。
谓词也有常项与变项之分。
一般的，含有n(n>0)个个体变元x1，x2，...，xn的谓词P称为n元谓词，记作P(x1，x2，...，xn)。
约定:
当谓词是常项时,0元谓词是命题；否则当谓词是变项时,0元谓词是命题变元。
命题函数：含有n个变元的命题函数是以个体域为定义域,以{F,T}为值域的n元函数。
命题函数是一个更广泛的概念，它可以是0元（即没有个体变元，直接表达一个命题）、1元、2元或多元谓词。命题函数可以由一个或多个简单命题函数通过逻辑联结词组合而成，形成更复杂的表达式。因此，3元谓词是命题函数的一个特例，它是具有3个个体变元的特殊类型的命题函数。这种分类有助于我们更精确地分析和构建涉及多个对象的逻辑表达式
例：A(x)：x身体好。(一元谓词)G(x,y)：x>y。(二元谓词)B(x,y,z)：点x在点y与点z之间。(三元谓词)这些也都是命题函数。例：A(x)：x身体好。B(x)：x学习好。C(x)：x工作好。A(x)->(B(x)∧C(x))表示：如果x身体不好，则x的学习与工作都不会好这也是命题函数注意：命题函数本身并不是命题，只有在括号内填入足够的具体客体，或用足够的量词约束后才变成命题。
量词：在命题中，表示对个体量化的词，称之为量词。
例如：有些人是大学生。所有事物都是发展变化的。"有些","所有的",就是对个体量化的词。有两种量词
量词的指导变元：量词后边要有一个个体变元，指明对哪个个体变元进行量化，称此个体变元是指导变元。
例如：x(读作:"任意x"),x(读作:"存在x"),其中的x就是指导变元例1.所有的自然数都是整数。解1:设I(x):x是整数,个体域:{自然数}。此命题可以写成x(I(x)):也表示对于任意的自然数x,x都是整数。解2：若没设个体域，即个体域为全总个体域，则需用特性谓词加以限定。设N(x):x是自然数(特性谓词).I(x):x是整数.此命题可以写成x(N(x)->I(x))也表示对于任意的x,只要x是自然数的话那么x就是整数例2.有些大学生吸烟.解1:令A(x):x吸烟,个体域:{大学生}则命题的表达式为xA(x)解2:若没设个体域,个体域即为全总个体域,则需用特性谓词加以限定.设S(x):x是大学生(特性谓词)A(x):x吸烟命题可以表达为x(S(x)∧A(x))为什么x后要加括号x则不需要
对于表达式x(I(x))需要加括号，而xA(x)不需要加括号的原因在于它们所表达的量词和逻辑的不同。
总的来说，是否需要加括号取决于表达式的逻辑结构和量词的使用。全称量词需要明确指出其作用范围，而存在量词则因其自身的语义清晰而不需要额外的括号
特性谓词：一般来说,特性谓词是描述个体特征的谓词,往往就是给定命题中量词后边的那个名词.
特性谓词的添加规则
例题3.每个人都有一个生母.解1:设个体域为:{人},M(x,y):y是x的生母.此命题可以表达为:xyM(x,y)解2:设P(x):x是人,M(x,y):y是x的生母.此命题可以写成x(P(x)->y(P(y)∧M(x,y)))谓词公式原子谓词公式函数为何需要函数符号
周红的父亲是教授
解1(函数):若令f(x):x的父亲,P(x):x是教授,c:周红P(f(c))
解2:P(x):x是教授,F(x,y):x是y的父亲,C:周红(x)(F(x,c)->P(x))
定义
为了方便,最外层的括号可以省略.
在谓词公式中,量词的作用范围称之为量词作用域,也叫量词的辖域.
一般地,
例:x(F(x,y)->yP(y))∧Q(z)F(x,y)中的x在x的辖域内,受到x的约束而y不受x的约束.P(y)中的y在y的辖域内,受y的约束.Q(z)中的z不受量词约束.定义:如果个体变元x在x或者x的辖域内,则称x在此辖域内约束出现,并称x在此辖域内是约束变元.否则x是自由出现,并称x是自由变元.
例:x(F(x,y)->yP(y))∧Q(z)F(x,y)中的x和P(y)中的y是约束变元.而F(x,y)中的y和Q(z)中的z是自由变元.说明
可见每当给z指定某个整数a后,xyP(x,y,z)就变成了一个命题.所以谓词公式xyP(x,y,z)是只含有个体变元z的一元谓词.
约束变元的换名规则:
例:(1)x(F(x,y)->yP(y))∧Q(z)
对约束变元y进行改名,谓词公式变为x(F(x,y)->tP(t))∧Q(z)
例:(2)x(P(x)->Q(x,y))∨(R(x)∧A(x))
对约束变元x进行改名,谓词公式变为z(P(z)->Q(z,y))∨(R(x)∧A(x))
自由变元的代入规则:(对自由变元也可以换名,此换名叫代入.)
对自由变元x进行代入,谓词公式变为(2)x(P(x)->Q(x,y))∨(R(z)∧A(z))
在谓词演算中，命题的符号化比较复杂。命题的符号化表达式与个体域有关系。而个体域的指定需随题目而定。能指定个体域的当然要指定，这样会使表达式变的简单。若不能指定个体域，则为全总个体域。在谓词演算中，最基本的命题符号化就三种类型：
给定谓词公式A,如果不论对其作任何赋值,都使得谓词公式A的真值为真,则称A为永真式.
证明:若一个赋值使得xA(x)为T,则个体域中每个个体均为T.于是A(a1)为T,A(a2)为T,...,A(an)为T,所以
A(a1)∧A(a2)∧...∧A(an)为T.
若一个赋值使得xA(x)为F,则个体域中一定存在着某个个体A(ai),使得A(ai)为F,于是A(a1)∧A(a2)∧...∧A(an)为F.
量词转换率.
直观解释:
"并不是所有的x都有性质A"与"存在x没有性质A"是一个意思.
"不存在有性质A的x"与"所有x都没有性质A"是一个意思.
例如:令A(x)表示:x是天才,个体域:{我们班}xA(x):不是我们班所有同学都是天才.xA(x):我们班有些同学不是天才.xA(x):我们班没有同学是天才xA(x):我们班所有的同学都不是天才三、量词辖域的扩充与收缩(量词与"∨,∧"的关系,其中一个运算对象不受该量词约束)我们以有限个体域证明公式
证明:设个体域为{a1,a2,...,an}
x(A(x)∨B)
设个体域为D.
若一个赋值使得x(A(x)∧B(x))为T,则对任意个体x∈D均有A(x)∧B(x)为T,于是对任意个体x∈D均有A(x)为T,并且对任意个体x∈D均有B(x)为T,所以xA(x)∧xB(x)为T
若一个赋值使得x(A(x)∧B(x))为F,则至少有一个个体a∈D使得A(a)∧B(a)为F,即A(a)为F或者B(a)为F,于是xA(x)为F或者xB(x)为F,所以xA(x)∧xB(x)为F
可以用公式1来证明公式2:
x(A(x)∨B(x))
举例说明公式3:x(A(x)∧B(x))=>xA(x)∧xB(x)
设A(x):x在联欢会上唱歌,B(x):x在联欢会上跳舞,论域为:{我们班};x(A(x)∧B(x))表示:我们班有些同学在联欢会上既唱歌又跳舞.xA(x)∧xB(x)表示:我们班有些同学在联欢会上唱歌并且有些同学在联欢会上跳舞.可以看出x(A(x)∧B(x))=>xA(x)∧xB(x)证明公式x(A(x)∧B(x))=>xA(x)∧xB(x)
证明:假设前件x(A(x)∧B(x))为T,则个体域中至少有一个个体a,使得A(a)∧B(a)为T,于是A(a)和B(a)都为T,所以xA(x)为T以及xB(x)为T.因此x(A(x)∧B(x))=>xA(x)∧xB(x)
证明公式4:xA(x)∨xB(x)=>x(A(x)∨B(x))
证明公式6:xA(x)->xB(x)=>x(A(x)->B(x))
这里主要介绍前束范式--所有量词都在公式前边.
1.前束范式定义:
如果一个谓词公式符合下面条件,它就是前束范式:
2.求前束范式的步骤:
mindmap实数无理数:无限不循环小数如π有理数:有理数的小数部分是有限或为无限循环的数分数整数:无小数位的数负整数自然数:0,1,2,3,...0正整数正奇数正偶数我们已经讲过命题演算的推理理论,现在我们来研究一下在谓词演算中如何进行推理我们知道谓词逻辑与命题逻辑的最大区别就在于命题表达的不同,实际上也就是多了量词的处理问题,所以对谓词演算的推理也是增加了量词的处理.我们增加了四个规则:US,ES,EG,UG,用于脱掉和添加量词.
推理方法:
US、ES、EG、UG规则用于处理量词.因为推理时要使用不含量词的命题公式,所以US、ES规则脱掉量词;如果结论中有量词,还把量词添上,EG、UG规则用于添加量词.
1.全称特指规则US(UninversalSpecialization)
形式:xA(x)=>A(c);(其中c是个体域内任意指定个体)
含义:如果xA(x)为真,则个体域内任意指定个体C,有A(c)为真.
作用:去掉全称量词
2.存在特指规则ES(ExistentialSpecialization)
形式:xA(x)=>A(c);(其中c是个体域内使A(c)为T的某个个体)
含义:如果xA(x)为真,则个体域内一定有某个个体c,使得A(c)为真
作用:去掉存在量词
要求:用ES指定的个体c,不应该是在此之前用US规则或者用ES规则指定过的个体.
3.存在推广规则EG(ExistentialGeneralization)
形式:A(c)=>xA(x);(其中c是个体域内某个个体)
含义:如果在个体域内某个个体c使得A(c)为真,则xA(x)为真.
作用:添加存在量词.
4.全称推广规则UG(UniversalGeneralization)
形式:A(c)=>xA(x);(其中c是个体域内任意某个个体)
含义:如果个体域内任意个体c均使得A(c)为真,则xA(x)为真.
作用:添加全称量词.
要求:c是个体域内任意的某个个体,否则不可全称推广.
由于US、ES、UG、EG规则都是蕴含式,所以必须对整个公式用这些规则,绝不可以对一个子公式用这些规则.
小杨、小刘和小林为高山俱乐部成员。该俱乐部每个成员都是滑雪者或登山者。没有一个登山者喜欢雨。所有的滑雪者都喜欢雪。凡是小杨喜欢的，小刘都不喜欢。小杨喜欢雨和雪。问：该俱乐部是否有个成员是登山者而不是滑雪者。如果有，他是谁？
解令：M(x):x是高山俱乐部成员,H(x):x是滑雪者,D(x):x是登山者,L(x,y):x喜欢y,a:小杨,b:小刘,c:小林,d:雨,e:雪;
问:该俱乐部是否有个成员是登山者而不是滑雪者。如果有，他是谁？x(D(x)∧H(x))
M(a),M(b),M(c),x(M(x)->(H(x)∨D(x))),x(D(x)∧L(x,d)),x(H(x)->L(x,e)),x(L(a,x)->L(b,x)),L(a,d)∧L(a,e)是否重言蕴含x(D(x)∧H(x))
(1)L(a,d)∧L(a,e)p(2)L(a,d)T(1)I(3)L(a,e)T(1)I(4)x(L(a,x)->L(b,x))p(5)L(a,e)->L(b,e)US(4)(6)L(b,e)T(3)(5)I(7)x(H(x)->L(x,e))p(8)H(b)->L(b,e)US(7)(9)H(b)T(6)(8)I(小刘不是滑雪者)(10)x(M(x)->(H(x)∨D(x)))p(11)M(b)->(H(b)∨D(b))US(10)(12)M(b)p(13)H(b)∨D(b)T(11)(12)I(14)D(b)T(9)(13)I(小刘是登山者)(14)H(b)∧D(b)T(9)(14)I(15)x(D(x)∧H(x))EG(14)第二篇集合论集合论初步基本概念与集合的表示方法集合:是由确定的对象(客体)构成的集体.用大写的英文字母表示
这里所谓"确定"是指:论域内任何客体,要么属于这个集合,要么不属于这个集合,是唯一确定的--集合的"确定性".
元素:集合中的对象,称之为元素.
∈:表示元素与集合的属于关系.
例如,N表示自然数集合,2∈N;1.5不属于N写成(1.5∈N),或写成1.5N2.集合的表示方法
列举法:将集合中的元素一一列出,写在大括号内.
例如,N={1,2,3,4,...},A={a,b,c,d}描述法:用句子(或谓词公式)描述元素属性.
例如,B={x|x是偶数}C={x|x是实数且2≤x≤5}一般的,A={x|P(x)},其中P(x)是谓词公式.如果论域内客体a使得P(a)为真,则a∈A,否则aA.
说明
定义:A、B是集合，如果A中的元素都是B中的元素，则称B包含A，A包含于B，也称A是B的子集。记作AB
包含关系的谓词公式定义
定义:A,B是集合,如果它们的元素完全相同,则称A与B相等.记作A=B.
集合相等关系的谓词公式定义
定理:A=B,当且仅当AB且BA证明:充分性:已知AB且BA求证A=B假设A≠B则至少有一个元素使得a∈A而aB,或者aA而a∈B如果a∈A而aB则与AB矛盾,如果aA而a∈B则与BA矛盾所以A=B必要性:已知A=B求证AB且BA根据集合包含关系的自反性AA,又因为A=B,则有AB同理BA性质
(1)有自反性,对任何集合A,有A=A.(2)有传递性,对任何集合A,B,C,如果有A=B且B=C,则A=C(3)有对称性,对任何集合A,B,如果有A=B则B=A3.真包含关系(真子集关系)
定义:
A,B是集合,如果AB且A≠B,则B真包含A,或A真包含于B,也称A是B的真子集,记作AB集合真包含关系的谓词公式定义
传递性:对任何集合A,B,C,如果有AB且BC,则AC特殊集合定义:
包含所讨论的所有集合的集合,称之为全集,记作E.实际上就是论域
由于讨论的问题不同,全集也不同.所以全集不唯一.
全集E的谓词公式描述法表示形式:
由于论域内任何可以x都属于E,所以x∈E为永真式.
E={x|P(x)∨P(x)}
性质
对于任何集合A,都有AE.
没有元素的集合,称之为空集,记作.
空集的谓词公式描述法表示形式:
因为论域内任何可以x∈是矛盾式,所以要用一个矛盾式定义.
={x|P(x)∧P(x)}
证明:假设有两个空集1,2,则因为1空集,则由性质1得12.因为2空集,则由性质1得21.所以2=1
A,B是集合,由既属于A,也属于B的元素构成的集合,称之为A与B的交集,记作A∩B
集合交运算的谓词公式定义
A∩B={x|x∈A∧x∈B},x∈A∩B=x∈A∧x∈B.如果A∩B=,则称A与B不相交.性质
A,B是集合,由或者属于A,或者属于B的元素构成的集合,称之为A与B的并集,记作A∪B.
集合并运算的谓词公式定义
A,B是集合,由属于A,而不属于B的元素构成的集合,称之为A与B的差集,或B对A的相对补集,记作A-B
例如:A={1,2,3},B={2,3,4},则A-B={1}
集合差运算的谓词公式定义
A-B={x|x∈A∧xB}x∈A-B=x∈A∧xB性质
∪运算对-(差运算)是不可分配的.例如:A∪(A-B)=A(A∪A)-(A∪B)=包含排斥定理有限集合的计数问题:
一,序偶与有序n元组
一,集合的笛卡尔积
证明:由笛卡尔积的定义及排列组合中的乘法原理得证.
证明:以A*=为例,根据集合笛卡尔积的定义,A*由A的元素为第一元素,中的元素为第二元素组成序偶的集合.由于中没有任何元素,因此A*=.
设A,B,C是任意集合,则A*(B∪C)=(A*B)∪(A*C),A*(B∩C)=(A*B)∩(A*C),(A∪B)*C=(A*C)∪(B*C),(A∩B)*C=(A*C)∩(B*C)
集合笛卡尔积运算的应用
一,关系的基本概念
定义1:设A,B是集合,如果RA*B,则称R是一个从A到B的二元关系.如果RA*A,则称R是A上的二元关系.二元关系简称为关系.
枚举法
矩阵表示法
设有限集A={a1,a2,...,am}和B={b1,b2,...,bn},RA*B,定义R的m*n阶矩阵MR=(rij)m*n其中
(1≦i≦m,1≦j≦n)
例如:设A={1,2,3,4},B={a,b,c},R1A*B,R2A*A,
MR1=
MR2=
空关系()
因为A*B(或A*A),所以也是一个从A到B(或A上)的关系,称之为空关系
例如定义在{1,2,3}上的空关系
显然,空关系式没有任何元素的关系.它的关系图中只有结点,无任何边;矩阵中全是0
完全关系(全域关系)
设有限集合A,B,A*B(或A*A)本身也是一个从A到B(或A上)的关系,称之为完全关系.
例如定义在{1,2,3}上的完全关系
显然,完全关系式包括集合笛卡尔积中全部序偶的关系;矩阵中全是1.
恒等关系
由于关系是集合,所以集合的∩,∪,-,⊕和~运算对关系也适用