DM-专题1：集合和二元关系.ppt

电子科技大学信息与软件工程学院 School of Information and Software Engineering, UESTC 2016 集合论与二元关系 2 第一部分 集合论 v预备知识 l集合的基本概念 v 属于、包含 v 幂集、空集 v 文氏图等 l集合的基本运算 v 并、交、补、差等 l集合恒等式 v 集合运算的算律、恒等式的证明方法 命题逻辑的基本概念 l命题与联结词 v 命题及其分类 v 联结词与复合命题 l命题公式及其赋值 v命题与真值 v 命题：判断结果惟一的陈述句 v 命题的真值：判断的结果 v 真值的取值：真与假 v 真命题与假命题 v注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不惟一确定的不是命题 命题与联结词 5 例1 下列句子中那些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. 假命题 命题概念 真命题 不是命题 不是命题 不是命题 不是命题 命题，但真值现在不知道 6 v命题分类：简单命题（也称原子命题）与复合 命题 v简单命题符号化 l用小写英文字母 p, q, r, , pi, qi, ri (i1)表示简 单命题 l用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1 vp, q, r可表示命题常元或者变元 v 7 否定、合取、析取联结词 定义1.3 设p, q为两个命题，复合命题“p或q”称作p与q的 析取式，记作pq，称作析取联结词. 规定pq为假当 且仅当p与q同时为假. 定义1.1 设 p为命题，复合命题“非p”(或“p的否定”)称为p 的否定式，记作p，符号称作否定联结词. 规定p 为 真当且仅当p为假. 定义1.2 设p,q为两个命题，复合命题“p并且q”(或“p与 q”) 称为p与q的合取式，记作pq，称作合取联结词. 规定 pq为真当且仅当p与q同时为真. 8 v例2 将下列命题符号化. v (1) 吴颖既用功又聪明. v (2) 吴颖不仅用功而且聪明. v (3) 吴颖虽然聪明，但不用功. v (4) 张辉与王丽都是三好生. v (5) 张辉与王丽是同学. 合取联结词的实例 9 v解 令p:吴颖用功, q:吴颖聪明 v (1) pq v (2) pq v (3) pq v (4) 设p:张辉是三好生, q:王丽是三好生 v pq v (5) p:张辉与王丽是同学 v(1)(3) 说明描述合取式的灵活性与多样性 v(4)(5) 要求分清 “与” 所联结的成分 合取联结词的实例 10 v例3 将下列命题符号化 v(1) 2 或 4 是素数. v(2) 2 或 3 是素数. v(3) 4 或 6 是素数. v(4) 小元元只能拿一个苹果或一个梨. v(5) 王小红生于 1975 年或 1976 年. 析取联结词的实例 11 v解 v(1) 令p:2是素数, q:4是素数, pq v(2) 令p:2是素数, q:3是素数, pq v(3) 令p:4是素数, q:6是素数, pq v(4) 令p:小元元拿一个苹果, q:小元元拿一个梨 v (pq)(pq) v(5) p:王小红生于 1975 年, q:王小红生于1976 年, v (pq)(pq) 或 pq v(1)(3) 为相容或 v(4)(5) 为排斥或, 符号化时(5)可有两种形式，而(4)则不能 析取联结词的实例 12 v定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称作p与q 的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的 后件，称作蕴涵联结词. 规定：pq为假当且仅当p为真q为 假. 蕴涵联结词 (1) pq 的逻辑关系：q为 p 的必要条件 (2) “如果 p, 则 q” 有很多不同的表述方法： 若p，就q 只要p，就q p仅当q 只有q 才p 除非q, 才p 或 除非q，否则非p， (3) 当 p 为假时，pq恒为真，称为空证明 (4) 常出现的错误：不分充分与必要条件 13 v例4 设 p：天冷，q：小王穿羽绒服，将下 列命题符号化 v(1) 只要天冷，小王就穿羽绒服. v(2) 因为天冷，所以小王穿羽绒服. v(3) 若小王不穿羽绒服，则天不冷. 蕴涵联结词的实例 pq pq pq v定义1.5 设 p, q为两个命题，复合命题“p当且仅当q” 称作p与q的等价式，记作pq，称作等价联结词. 规定pq为真当且仅当p与q同时为真或同时为假. vpq 的逻辑关系：p与q互为充分必要条件 等价联结词 例5 求下列复合命题的真值 (1) 2 + 2 4 当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当 3 是偶数. (3) 2 + 2 4 当且仅当 太阳从东方升起. (4) 2 + 2 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在 x0 可导的充要条件是 它在 x0 连续. 1 0 0 1 0 命题公式 v（1）单个命题命题常元或者变元是命题公式 v（2）若A是命题公式，A也是命题公式 v（3）若A,B是命题公式，则AB，AB ， AB ，AB也是命题公式 v（4）有限次应用（1）-（3）规则形成的符 号串才是命题公式，或称命题形式，简称公 式 命题公式 v针对含变元的公式，可进行赋值 成真赋值 成假赋值 重言式（永真式） 矛盾式（永假式） 可满足式 等值式与基本的等值式 v等值式 定义2.1 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式 v几点说明： 定义中，A, B, 均为元语言符号 A或B中可能有哑元出现. 例如，在 (pq) (pq) (rr) 中，r为左边公式的哑元. 基本的等值式 v双重否定律 AA v幂等律 AAA, AAA v交换律 ABBA, ABBA v结合律 (AB)CA(BC), (AB)CA(BC) v分配律 A(BC) (AB)(AC), A(BC) (AB)(AC) v德摩根律 (AB)AB (AB)AB v吸收律 A(AB)A, A(AB)A 基本的等值式 v零律 A11, A00 v同一律 A0A. A1A v排中律 AA1 v矛盾律 AA0 v蕴涵等值式 ABAB v等价等值式 AB(AB)(BA) v假言易位 ABBA v等价否定等值式 ABAB v归谬论 (AB)(AB) A 注意：要牢记各个等值式，这是继续学习的基础 等值演算 v置换规则：设(A)是含公式A的公式，用公 式B替换A，得到(B)。如果A B,则 (A) (B) v由已知等值式，应用置换规则，推演出新的 等值式的过程，称为等值演算 v例：证明p (q r ) 和(p q) r 等值 （教材P2） 21 lp, q, r, 均表示命题. l 联结词集为, , , , ，p, pq, pq, pq, pq为基 本复合命题. 其中要特别注意理解pq的涵义. 反复使用 , , , , 中的联结词组成更为复杂的复合命题. 设 p: 是无理数，q: 3是奇数， r: 苹果是方的， s: 太阳绕地球转 则复合命题 (pq) (rs) p) 是假命题. 命题相关小结 l 联结词的运算顺序：, , , , , 同级按先出现者先运算. 一阶谓词逻辑基本概念 v在命题逻辑中，我们把命题分析到简单命题为止，而简单命 题是不再进行分析的基本元素，因此，当推理涉及到简单命 题的结构时，命题逻辑对此是无能为力的。例如下面的推理 ： 所有的自然数都是实数，3是自然数。所以，3是实数。 根据数学方面的知识，我们知道这个推理是正确的。然而， 在命题逻辑中，这个推理的正确性是无法证明的，这是因为 上述推理中的三句话均是简单命题，且各不相同，如果把它 们形式化为命题逻辑中的公式，以p表“所有的自然数都是实 数”，以q表“3是自然数”，以r表“3是实数”，则推理可以写 为： (pq) r 一阶谓词逻辑基本概念 v而(pq)r是一个可满足式，可知这个推理无法在 命题逻辑推理理论中得到证明。另外，命题“所有的 自然数都是实数”事实上隐含着“0是实数”，“1是实 数”，“2是实数”，等无穷多个命题，单用一个 p表示，很难体现这些。 因此，为了能够进一步深入地研究推理，需要 对简单命题做进一步的分析，将简单命题的结构分 解为个体词、谓词、量词等，并讨论它们与推理之 间的关系，这一部分的内容称为一阶逻辑(谓词逻辑 )。 一阶谓词逻辑基本概念 v首先我们将简单命题的结构分解成个体和谓词。 个体(客体)我们讨论的对象。可以是具体的，也可以是 抽象的。 个体域(论域)个体所构成的非空集合。 全总个体域(无限域)包含宇宙中一切事物的个体域 谓词简单命题中，表示一个个体的性质或多个个体间的 关系的词。 之所以称之为谓词，是因为谓词和个体词一起构成了简单命 题中的主谓结构。如： 小王是学生。 3是素数。 2整除6。 3位于2与5之间。 一阶谓词逻辑基本概念 v上面这些简单命题中，小王、2、3、5、6均是个体，“ 是学生”，“是素数”，“整除”，“位于 与之间”均是谓词。前两个谓词描述的是一个个体的性 质，称为一元谓词； 第三个表示两个个体之间的关系，称为 二元谓词； 第四个表示三个个体之间的关系，称为三元谓词 。以此类推，我们将描述n(n2)个个体之间关系的谓词称为 n元谓词。通常用大写字母F、G、H(可加下标)来表示谓词 。如： F表示“是学生”； G表示“整除”； H表示“位于与之间”。 一阶谓词逻辑基本概念 v这时F、G、H表示的是具体的谓词，称为谓词常元，否则， 称为谓词变元。 v显然，单独的一个谓词(即使是谓词常元)并不能构成一个完 整的句子，必须以个体词取代“”方能构成一个句子。 v通常用小写的英文字母a、b、c(可加下标)等表示个体： “小王是学生”可符号化为F(a)，其中a表示小王。若用b表示 小李，则F(b)就表示“小李是学生”。若用c1表示2，用c2表 示6，则G(c1，c2)就表示“2整除6” 一阶谓词逻辑基本概念 v这里，a、b、c1、c2均是具体的个体，称为个体常元。一 般我们用F(x)表示“x是学生”，其中的x称为个体变元(简称变 元，亦称个体词)。类似地，我们也可用G(x，y)表示“x整除 y”。 v由谓词符和变元符组成的符号串称为命题函数。只有谓词为 常元并将其中的变元代以具体的个体后，才能构成命题。例 如： “G(x，y)：x整除y。” 并不是命题，但若取a：2，b：6，则 G(a，a)，G(a，b)以及G(b，a)均是命题，前两个是真命题 ，第三个是假命题。G(a，a)、G(a，b)等称为0元谓词，它 们不含个体变元，0元谓词即命题。 一阶谓词逻辑基本概念 v注意 (1) 多元谓词中变元的顺序不同，表示的意义也不同。如 G(x，y)表“x整除y”，而G(y，x)表“y整除x”。 (2) 在谓词逻辑中， 、 仍是联结词，其 含义和用法与命题逻辑中的相同。 【例】将下列语句形式化为谓词逻辑中的命题或命题函数。 (1) 小王是二年级大学生。 (2) 小王是李老师的学生。 (3) 如果xy且yx，则x=y。 一阶谓词逻辑基本概念 v解： (1) 令F(x)：x是大学生；G(x)：x是二年级的； a：小王 。则原句形式化为： F(a)G(a) (2) 令F(x，y)：x是y的学生；a：小王；b：李老师。则 原句形式化为： F(a，b) (3) 令F(x，y)：xy；G(x，y)：x=y。则原句形式化为 (F(x，y)F(y，x)G(x，y) 一阶谓词逻辑基本概念 v 此外，在一般的简单命题中，常有一些表 示数量的词语，诸如“所有的”、“有一些”等 等，用来表示谓词中的变量取自论域中的全 体或部分个体，例如下面的两个陈述句： “对所有的xD，论断F(x)为真。” “对某些xD，论断F(x)为真。” 在谓词逻辑中，我们用量词把它们形式化。 一阶谓词逻辑基本概念 v1 全称量词 “” 全称量词用来表示个体域中的全体。表自然 语言中的“所有的”、“任意的”、“每一个”等等。 如： “任意偶数均能被2整除。” 句子可改写成：“在偶数集合中的任意的x，x能 被2整除。” 取个体域为偶数集，用F(x)表示“x能被2整除” ，用 x表示“任意的x”，则原句形式化为： xF(x) 一阶谓词逻辑基本概念 v注意 xF(x)表示的是“在个体域中，任意的x均 有F(x)这个性质”，这是一个可以确定真值 的命题。当个体域D为有穷集时： xF(x)的真值为1，当且仅当对于每一 个xD，均有F(x)真值为1； xF(x)的真值为0，当且仅当至少有一个 x0D，使得F(x0)真值为0。 一阶谓词逻辑基本概念 v2 存在量词词 “” 存在量词词 用来表示论论域中的部分个体。表自 然语语言中的“存在着一些”、“至少有一个”、“有”等 等。如： “我们们班有人会吸烟。” 句子可改写成：“在我们们班有一些x，x会吸烟。” 取个体域为为“我们们班的同学”，用G(x)表示“x会吸 烟”，用 x表示“有些x”，则则原句形式化为为： xG(x) 一阶谓词逻辑基本概念 v注意 xG(x)表示的是“在个体域中，至少有一个x具有 G(x)这个性质”，这是一个可以确定真值的命题。 当个体域D为有穷集时，不妨设D=a1，a2， an： xG(x)的真值为0，当且仅当对于每一个xD，均 有G(x)真值为0； xG(x)的真值为1，当且仅当至少有一个x0D，均 有G(x0)真值为1。 一阶逻辑谓词概念总结 v基本概念个体词、谓词、量词 v个体（个体词）所研究对象中可以独立存在的 具体或抽象的客体（名词或代词充当） v个体常项：具体的事务，用a, b, c表示 v个体变项：抽象的事物，用x, y, z表示 v各体域个体变项的取值范围 有限个体域，如a, b, c, 1, 2 无限个体域，如N, Z, R, 全总个体域宇宙间一切事物组成 一阶逻辑谓词概念总结 v谓词表示个体词性质或相互之间关系的词 v谓词常项：F: 是人，F(a)：a是人 v谓词变项：F: 具有性质F，F(x)：x具有性质F vn（n1）元谓词 v n=1，一元谓词表示性质 v n2，多元谓词表示事物之间的关系 vL(x,y)：x与y有关系L，L(x,y)：xy， v（4）0元谓词不含个体变项的谓词命题常项或变项 v3. 量词表示数量的词 v全程量词：“”，x v存在量词：“”，x 一阶逻辑谓词概念总结 例： 在一阶逻辑阶逻辑 中将下面命题题符号化 人都爱爱美 有人用左手写字 个体域分别为别为 (a) D=“人类类集合”=x | x是人 (b) D为为全总总个体域 解：(a) （1）xG(x), G(x)：x爱爱美 （2）xG(x), G(x)：x用左手写字 (b) F(x)：x为为人，G(x)：同(a)中 一阶逻辑谓词概念总结 v例 在一阶逻辑中将下面命题符号化 正数都大于负数 有的无理数大于有的有理数 解 注意：题目中没给个体域，一律用全总个体域 （1）令F(x)：x为正数，G(y)：y为负数 L(x,y)：xy x(F(x)y(G(y)L(x,y) xy(F(x)G(y)L(x,y) （以后讨论） （2）令F(x)：x是无理数，G(y)：y是有理数， L(x,y)：xy x(F(x)y(G(y)L(x,y) xy(F(x)G(y)L(x,y) （以后讨论） 39 集合的基本概念 v1. 集合定义 v 集合没有精确的数学定义 v 理解：由离散个体构成的整体称为集合，称这些个体 为集合的元素 v 常见的数集：N, Z, Q, R, C 等分别表示自然数、整数 、有理数、实数、复数集合 2. 集合表示法 枚举法-通过列出全体元素来表示集合 谓词表示法-是将集合中元素的共同属性描述出来 文氏图 -用于示意性地表示集合及其包含元素间的关系 实例： 枚举法 自然数集合 N=0,1,2,3, 谓词法 S= x | x是实数，x21=0 40 元素与集合 1. 集合的元素具有的性质 无序性：元素列出的顺序无关 相异性：集合的每个元素只计 数一次 确定性：对任何元素和集合都 能确定这个元素是否 为该集合的元素 任意性：集合的元素也可以是 集合 2元素与集合的关系 隶属关系：或者 3集合的树型层次结构 d A , a A 41 集合与集合 v集合与集合之间的关系：, =, , , , 定义1.1 A B x ( xA xB ) 定义1.2 A = B A B B A 定义1.3 A B A B A B A B x ( xA xB ) v思考： 和 的定义 v注意 和 是不同层次的问题 42 空集、全集和幂集 1定义1.4 空集 ：不含有任何元素的集合 v 实例： x | xR x2+1=0 v 定理1.1 空集是任何集合的子集。 v 证 对于任意集合A， v A x (xxA) T (恒真命题) v 推论 是惟一的 3. 定义1.6 全集 E：包含了所有集合的集合 全集具有相对性：与问题有关，不存在绝对的全集 2. 定义1.5 幂集：P(A)= x | x A 实例：P()=, P()=, 计数：如果 |A|=n，则 |P(A)|=2n. 43 集合的运算 v初级运算 v集合的基本运算有 定义1.7 并 AB = x | xA xB 交 AB = x | xA xB 相对补 AB = x | xA xB 定义1.8 对称差 AB = (AB)(BA) = (AB)-(AB) 定义1.9 绝对补 A = EA 44 文氏图 集合运算的表示 AB ABAB AB A B AB AB AB AB A 45 几点说明 l并和交运算可以推广到有穷个集合上，即 A1 A2 An = x | xA1 xA2 xAn A1 A2 An = x | xA1 xA2 xAn l A B AB = l AB = AB = A 46 广义运算 v1. 集合的广义并与广义交 定义1.10 广义并 A = x | z ( zA xz ) 广义交 A= x | z ( zA xz ) v实例 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a 47 关于广义运算的说明 v2. 广义运算的性质 (1) =，无意义 (2) 单元集x的广义并和广义交都等于x (3) 广义运算减少集合的层次（括弧减少一层） (4) 广义运算的计算：一般情况下可以转变成初级运算 A1, A2, , An=A1A2An A1, A2, , An=A1A2An v3. 引入广义运算的意义 可以表示无数个集合的并、交运算，例如 x | xR=R 这里的 R 代表实数集合. 48 运算的优先权规定 v1 类运算：初级运算, , , ， 优先顺序由括号确定 v2 类运算：广义运算和运算， 运算由右向左进行 v混合运算：2 类运算优先于1 类运算 例1 A=a,a,b，计算A(AA). 解： A(AA) = a,b(a,ba) = (ab)(ab)a) = (ab)(ba) = b 49 有穷集合元素的计数 v1. 文氏图法 v2. 包含排斥原理 v定理 设集合S上定义了n条性质，其中具有第 i 条性质的 v元素构成子集Ai, 那么集合中不具有任何性质的元素数为 v 推论 S中至少具有一条性质的元素数为 50 实例 v例2 求1到1000之间（包含1和1000在内）既不能被5和 6整除，也不能被8整除的数有多少个？ 解 尝试方法一：文氏图 定义以下集合： S= x | xZ 1x1000 A= x | xS x可被5整除 B= x | xS x可被6整除 C= x | xS x可被8整除 画出文氏图，然后填入相应的 数字，但是A,B,C之间有交集， 所以难以计算 A B C 200166 125 8 33 2541 51 实例 v方法二利用容斥原理 |S| = 1000 |A|=1000/5=200, |B|=1000/6=166, |C|=1000/8=125 |AB| = 1000/lcm(5,6) = 1000/30 = 33 |AC| = 1000/lcm(5,8) = 1000/40 = 25 |BC| = 1000/lcm(6,8) = 1000/24 = 41 |ABC| = 1000/lcm(5,6,8) = 1000/120 = 8 = 1000(200+166+125)+(33+25+41)8 = 600 52 集合恒等式 v集合算律 v1只涉及一个运算的算律： v 交换律、结合律、幂等律 交换AB=BAAB=BAAB=BA 结合(AB)C =A(BC) (AB)C= A(BC) (AB)C =A(BC) 幂等AA=AAA=A 53 集合算律 v 2涉及两个不同运算的算律： v 分配律、吸收律 与与 分配A(BC)= (AB)(AC) A(BC)= (AB)(AC) A(BC) =(AB)(AC) 吸收A(AB)=A A(AB)=A 54 集合算律 v3涉及补运算的算律： v DM律，双重否定律 D.M律A(BC)=(AB)(AC) A(BC)=(AB)(AC) (BC)=BC (BC)=BC 双重否定A=A 55 集合算律 v4涉及全集和空集的算律： v 补元律、零律、同一律、否定律 E 补元律AA=AA=E 零律A=AE=E 同一律A=AAE=A 否定=EE= *集合论与图论第3讲56 对偶原理(dual principle) v对偶式(dual): 一个集合关系式, 如果只含有 , , E,=, , 那么, 同时把与互换, 把 与E互换, 把与互换, 得到的式子称为原 式的对偶式. v对偶原理: 对偶式