离散数学集合的笛卡儿积与二元关系

注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。

也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。

选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。

关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。

当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。

蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。

第七章二元关系§1 有序对与笛卡尔积定义两个元素x与y按一定顺序排列构成的二元组称为一个有序对（或序偶），记为〈x,y〉，称x 为第一元素，y为第二元素。

性质 (1) ,,x y x y y x≠⇒〈〉≠〈〉(2) ,,x y u v x u y v〈〉=〈〉⇔=∧=例25 2,45,242xx x yx y+=⎧〈+〉=〈+〉⇒⎨=+⎩3,2x y⇒==−定义：设A、B为两个集合，称{},x y x A y B〈〉∈∧∈为集合A与B的笛卡尔积，记为A×B。

性质：(1) ,A A×=×=∅∅∅∅(2)笛卡尔积不满足交换律与结合律(3)笛卡尔积对并、交满足分配律×=××∪∪A B C A B A C()()()×=××∪∪B C A B A C A()()()×=××∩∩A B C A B A C()()()×=××∩∩B C A B A C A()()()(4)A C B D A B C D⊆∧⊆⇒×⊆×例A={1,2}，求P(A)×A。

§2 二元关系定义设R是集合，若R=∅或A≠∅且A中元素均为有序对，则称R为一个二元关系。

若〈x,y〉∈R，则称x与y有关系R，记为xRy。

定义：设A与B是两个集合，由A×B的子集定义的二元关系称为A到B的二元关系；当A=B 时，称之为A上的二元关系。

例 设A ={0,1}，则R 1={〈0,0〉,〈1,1〉}，R 2=∅， R 3=A ×A 都是A 上的二元关系。

例 设A 是n 元集，则A ×A 有n 2个元素，于是A ×A 有22n 个子集，由此得A 上有22n 个二元关系。

例 设A 是任一集合① 称∅是A 上的空关系 ② 称A ×A 是A 上的全域关系③ 称{},A I x x x A =〈〉∈是A 上的恒等关系。

离散数学中二元关系的性质判定【摘要】关系的性质是关系中的基本内容，对理解关系有着重要的意义。

文中对二元关系性质的四种判定方法进行了分析和探讨，即，根据定义判定、根据定理判定、根据关系图判定、根据关系矩阵判定。

以加深学生理解，方便灵活运用。

【关键词】离散数学；二元关系；性质；判定【中图分类号】g64 【文献标识码】a 【文章编号】2095-3089（2013）4-0-02离散数学是现代数学的一个重要分支，是计算机科学的理论基础和核心课程。

关系是离散数学中非常重要的一个基本概念，关系的概念在计算机科学是也是最基本的，它在形式语言、编译程序设计、信息检索、数据结构、算法分析、数据库和有限自动机等方面起着重要作用。

关系是一个使用得很频繁的词，如数集上大于关系、小于关系；平面集上的直线平行关系、三角形相似关系；人群集合上的父子关系、同乡关系等，这些都是离散数学中的关系研究的范畴。

所以，离散数学中的关系是一个抽象的概念，定义为笛卡尔积a1×a2×…×an的任意一个子集。

二元关系是我们讨论的重点内容，定义为笛卡尔积a1×a2的任意子集。

关系的性质是关系的基本属性，是认识和分析关系的关键。

关系的基本性质主要包括自反、反自反、对称、反对称以及传递性。

如何判定关系的性质是我们必须要掌握的方法。

关系基本性质的判定主要有四种方法：第一是直接根据定义判定；第二是根据定理判定；第三是根据关系图判定；第四是根据关系矩阵判定。

本文将对这四种方法进行讨论。

1 根据定义判定定义：设ρ是集合a上的二元关系，1）若对于所有的a∈a，有（a，a）∈ρ，则称ρ是自反的。

否则，称ρ是非自反的。

2）若对于所有的a∈a，有（a，a）?ρ，则称ρ是反自反的。

3）对于所有的a，b∈a，若每当有（a，b）∈ρ时就有（b，a）∈ρ，则称ρ是对称的。

否则，称ρ是非对称的。

4）对于所有的a，b∈a，若每当有（a，b）∈ρ和（b，a）∈ρ时，就必有a=b，则称ρ是反对称的。