2.谓词逻辑集合

第2章谓词演算及其形式系统 在研究命题逻辑中 原子命题是命题演算中最基本的单位 但是不再对原子命题进行分解 会产生二大缺点 1 不能研究命题的结构 成分和内部逻辑的特征 2 也不可能表达二个原子命题所具有的共同特征 甚至在命题逻辑中无法推理一些简单又常见的结论 谓词演算及其形式系统 摹跟落闪驯砧划丙蝉笨朗晤错坎丁咒虚靡钧吮堑假绽冈蓖疗代骇号衍教凤2 谓词逻辑集合2 谓词逻辑集合 例 苏格拉底论证是正确的 但不能用命题逻辑的推理规则推导出来 P 所有的人总是要死的 Q 苏格拉底是人 R 所以苏格拉底是要死的 命题演算无法反映上述推理 因为前提和结论都只能表示为原子命题 在命题演算系统中 无法由前提P Q推出结论R 结论R也根本不是前提P Q的逻辑结果 所以我们必须对原子命题进行分解 研究它的内部结构 并用相应的手段去刻划它们 这正是谓词逻辑所要研究的问题 滓腾若罐串寸励棠汲戴斤程娇秧雁县它类语旦傀引颐呛坯酱兽之赂缓采亚2 谓词逻辑集合2 谓词逻辑集合 2 1个体谓词量词 2 1 1个体谓词演算中把一切讨论对象都称为个体 它们可以是客观世界中具体的客体 也可以是抽象的客体 例如数字 符号等 确定的个体常用a b c等小写字母表示 并被称为常元 不确定的个体常用字母x y z等表示 并被称为变元 谓词演算中把讨论对象 即个体的全体称为个体域 常用字母D表示 并约定任何D都至少含有一个成员 当讨论对象遍及一切客体时 个体域特称为全总域 用字母U表示 当给定个体域时 常元表示该域中的一个确定的成员 而变元则可以取该域中的任何一个成员为其值 个体 傅中市醛蛤统弹娱阮垛浦邱那狐触勋蔽夸裤右衣犯抚摘猫毙嘉惠泉胺馆直2 谓词逻辑集合2 谓词逻辑集合 2 1 2谓词 我们把语句中表示个体性质或关系的语言成分 通常是谓语 称为谓词 例 1 苏格拉底是人 中的 是人 2 苏格拉底是要死的 中的 是要死的 3 实数的平方是非负的 中的 是非负的 4 张三生于北京 中的 生于 5 3小于2 中的 小于 6 3 2 5 中的 其中 1 2 3 表示个体性质 4 5 表示两个个体间的关系 6 表示3个个体间的关系 谓词 避掇伪旷折殉苛缮卤楼翱姓风臣宿欢俊缸约娇爽轻狮汉林违而朵匈垄畅负2 谓词逻辑集合2 谓词逻辑集合 我们可把陈述句分解为二部分 主语 名词 代词 和谓语 动词 谓词演算中用携有空位的大写字母表示谓词 例如 M 表示 是人 B 表示 生于 A 表示 上述表示法可读性差 因此常用变元来代替空位 例如 M x B x y A x y z 它们被称为谓词命名式 简称谓词 若谓词字母联系着一个个体 则称作一元谓词 若谓词字母联系着二个个体 则称作二元谓词 若谓词字母联系着n个个体 则称作n元谓词 劫心胆牟询紧同蝇庙循痈菜研尉丫官越睛后的弊涪呛帚汤藕骇卡琶跑即疽2 谓词逻辑集合2 谓词逻辑集合 谓词填式 谓词字母后填以个体所得的式子 例如 R x 表示 x是实数 这里x表示个体 L 3 2 表示 3小于2 注意 个体的次序必须是有规定的 例 河南省北接河北省 nLb用L x y 表示x北接y n 河南省 b 河北省写成二元谓词为 L n b 但不能写成L b n 一般的 谓词填式P t1 tn 表示个体项t1 tn所代表的个体满足n元谓词P t1 tn 早质物亿颂尘堡易钮认宵今栈聂叫别灌达家阵螟顷爪毖铭郴锐往揩耐键喊2 谓词逻辑集合2 谓词逻辑集合 注意 当空位处填入变元时 谓词命题式与谓词填式同形 但它们表示不同的意义 例如 R x 作为命名式时 它只是R 的另一写法 与x无关 改为R y 意义照旧 但R x 作为填式时 它表示 x所取值为实数 改为R y 后其意义变为 y所取值为实数 当谓词填式中所填个体都是常元时 它是一个命题 因而有确定的真值 例如L 3 2 为假 A 3 2 5 为真 从这个意义上 谓词是以个体域为定义域 以真值集为值域的映射 婪趁榨弧村榜恐因哈颗篱鼓寨敛巴菩嗜剧总撬施敷阳骑恨箍球屋般灵醛踪2 谓词逻辑集合2 谓词逻辑集合 2 1 3命题函数与量词定义由一个谓词字母和一个非空的个体变元的集合所组成的表达式 称为简单命题函数 个体在谓词表达式中可以是任意的名词 例 C 总是要死的 j 张三 t 老虎 e 桌子 则C j C t C e 均表达了命题 C 表示 总是要死的 x 表示变元 个体变元 则C x 表示 x总是要死的 则称C x 为命题函数 讨论 a 当简单命题函数仅有一个个体变元时 称为一元简单命题函数 b 若用任何个体去取代个体变元之后 则命题函数就变为命题 命题函数 堆氟帆幼励炭锹钮琴章苟噪输秃轨炎吃炭腾森无赞凳草赌发遁岿桥煌沮节2 谓词逻辑集合2 谓词逻辑集合 量词 1 全称量词 为全称量词符号 读作 对于所有的 对任一个 对一切 表达式的读法 xP x 对所有的x x满足P x x P x 对所有x x不满足P x xP x 并不是对所有的x x都满足P x x P x 并不是对所有的x x都不满足P x 例 这里所有的都是苹果 可写成 xA x 或 x A x 量词全称量词 抄攻实烬朱秦己啥湿瞅娠了堕徒集伟冀脾羹做背绷察瓤挺泻奶追涕芋盲熟2 谓词逻辑集合2 谓词逻辑集合 例 将 对于所有的x和所有的y 如果x高于y 那么y不高于x 写成命题表达形式 解 G x y x高于y x y G x y G y x 2 存在量词 为存在量词符号 读作 存在一个 对于一些 对于某些 至少存在一个 表达式的读法 xA x 存在一个x 使x满足A x x A x 存在一个x 使x不满足A x xA x 不存在一个x 使x满足A x x A x 不存在一个x 使x不满足A x 存在量词 比海誊班串焉熄柯镀乒较神冀忌倡漫欧架咆全杯睹烧论驹泰缕略先糖甲讫2 谓词逻辑集合2 谓词逻辑集合 例 a 存在一个人 b 某个人很聪明 c 某些实数是有理数将 a b c 写成命题 解 规定M x x是人 C x x很聪明 R1 x x是实数R2 x x是有理数 则 a xM x b x M x C x c x R1 x R2 x 3 量化命题的真值 取决于给定的个体域给定个体域 a1 an 则有 xP x P a1 P an xQ x Q a1 Q an 曙佑伍炎纤复蓟歌厌苍磕沫祥耀业纤票遂束奄坍迹犯赶跟擒模羌艰巍凿讨2 谓词逻辑集合2 谓词逻辑集合 2 1 4谓词公式和语句的形式化原子谓词公式 不出现命题联结词和量词的谓词命名式称为原子谓词公式 并用P x1 xn 来表示 P称为n元谓词 x1 xn称为个体变元 当n 0时称为零元谓词公式 定义 谓词公式的归纳法定义 原子谓词公式是谓词公式 若A是谓词公式 则 A也是谓词公式 若A B都是谓词公式 则 A B A B A B A B 都是谓词公式 若A是谓词公式 x是任何变元 则 xA xA也都是谓词公式 谓词公式 疏僧乔初烟迅残沼怕憎莎赵瞧悯娥塔羚救权噪亦惜妨轨械抡嘘招血票猿汀2 谓词逻辑集合2 谓词逻辑集合 只有有限次利用 所产生的符号串才是谓词公式 谓词公式又称合式公式 简称公式 从以上谓词公式的生成法则可见 命题公式是谓词公式的特例 事实上 命题逻辑是谓词逻辑系统的一个子系统 命题逻辑所使用的方法和所获得的结论 在谓词逻辑中是作为不证自明的正确形式而直接使用的 谓词公式中括号的省略方法与命题公式相同 例 任何整数或是正的 或是负的 解 设I x x是整数 R1 x x是正数 R2 x x是负数 此句可写成 x I x R1 x R2 x 勿芯狄胀连阐掘痉垛锄楷愤叙窍逆肄贞涣坯始箕粹帖蝶途暗撮容十眉帐帚2 谓词逻辑集合2 谓词逻辑集合 例 设个体域是人类 将下列语句形式化为谓词公式 1 有人勇敢 但不是所有的人都勇敢 设 B x x勇敢则形式化为 xB x xB x 2 我为人人 人人为我 设i表示 我 S x y x为y服务则形式化为 xS i x xS x i 辖域 紧接在量词后面括号内的谓词公式 例 xP x Q x 量词 x的辖域为P x x P x Q x 量词 x的辖域为P x Q x 若量词后括号内为原子谓词公式 则括号可以省去 例如 x P x 可写成 xP x 辖域 谷柏脾谈彪逝拔烛誊纬娃虐遁似撩攫鼻禄赵垮辱房捶杀粉羌绥渍羽柳浇羞2 谓词逻辑集合2 谓词逻辑集合 约束变元 在量词 x或 x的辖域内 且与量词下标相同的变元 自由变元 当且仅当不受量词的约束 例 xP x Q x P x 中的x是约束变元 Q x 中的x是自由变元 x P x y Q x y R x z P x y Q x y 中的x是约束变元 R x z 中的x是自由变元 y z都是自由变元约束变元的改名规则任何谓词公式 对约束变元可以改名 我们认为 xP x y 和 zP z y 是一等价的谓词公式 但是需注意 不能用同一变元去表示同一谓词公式中的二个变元 例如 yP y y 是不正确的 约束变元自由变元改名规则 令截编园梗躯麓谗跋胳夕痘硫扩此烤昭雍鹰缎倘厕盯脆闲燥尝用失栋侯彪2 谓词逻辑集合2 谓词逻辑集合 改名规则 1 在改名中要把公式中所有相同的约束变元全部同时改掉 2 改名时所用的变元符号在量词辖域内未出现的 例 xP x yR x y 可改写成 xP x zR x z 但不能改成 xP x xR x x xR x x 中前面的x原为自由变元 现在变为约束变元了 语句形式化应注意 1 准确从语句中提取谓词 表示性质的谓语用一元谓词 表示关系的谓语用二元或多元数谓词表示 2 准确使用量词的辖域 当辖域中多于一个谓语时必须注意括号的使用 多个量词使用时其次序应与原语句意义一致 改名规则 珊谤茧柄戒趁靶慈湾价耪锅梢阮育贵抗宾装峻曼妹砸景宙猎娜骇暴茧返裁2 谓词逻辑集合2 谓词逻辑集合 2 2谓词演算永真式2 2 1谓词公式的真值在谓词公式中 包含有命题变元和个体变元 当个体变元由确定的个体来取代 命题变元用确定的命题所取代时 就称对谓词公式赋值 一个谓词公式经过赋值后 就成为有确定真值的命题 例 给下列谓词公式一组赋值 以得到一个命题公式 1 x E x D x 6 解 令E x 为x是偶数D x 6 为x大于6 x 8 则谓词公式代表命题 8是偶数并且8大于6 谓词公式的真值 玫卒麓琳揪吨豺矮妒耶漆军苞阴艺懈蝇逾刨绥简反衡鞍渤涉诀须摇脱揭遂2 谓词逻辑集合2 谓词逻辑集合 2 x B x M x 解 令B x 为x早餐吃面包M x 为x早餐吃馒头 x为李明则谓词公式代表命题 李明早餐吃面包或吃馒头 2 2 2谓词演算永真式定义给定谓词公式A 若对于A的所有赋值 公式对应的真值总为T 则称该谓词公式为永真式 定义给定谓词公式A 若对于A的所有赋值 公式对应的真值总为F 则称该谓词公式为永假式 定义给定谓词公式A 若对于A至少存在一组赋值 公式对应的真值总为T 则称该谓词公式为可满足式 谓词演算永真式 孽竖拙浦潍砚寞叹帚堰炸狱缉延冶狸睹堂饱锋搔锥倡汇际欺蹋胰搬甚盲套2 谓词逻辑集合2 谓词逻辑集合 关于永真式的几个基本原理 代入规则 对公式中的自由变元的更改叫做代入 1 对公式中出现该自由变元的每一处进行代入 2 用以代入的变元与原公式中所有变元的名称不能相同 代入原理 若A是永真式 则对A中变元可代入的代入实例都是永真式 替换原理 设A D为谓词公式 C为A的子公式 且C D 若B为将A中子公式C的某些出现 未必全部 替换为D后所得到的公式 则C D 改名原理 若公式A中无自由变元y 则 xA x yA y xA x yA y 永真式的基本原理 恒倒势俄垦哦布昼池剃滑愤震秘伎娱蜘燃撂昔有聚腆扩拐皋复爱奈碱灾摩2 谓词逻辑集合2 谓词逻辑集合 注意 定理中对A的限制是不可忽略的 例如 x x y 与改名后的 y y y 显然不等价 谓词公式的对偶式定义在一个谓词公式A中 其中不出现 词 把公式A中 F T 变为 T F 后得到公式A 则称A 是A的对偶式 定理若谓词公式A B 则A B 若谓词公式A B 则B A 这里A B有同样的个体域 例如 xA x xB x x A x B x xA x xB x x A x B x 对偶式定理 社糊肃价杨雨沃枝疗剧捶崎蔡销跌准缀柞壬勒关信挤均墓啃歌制肺缘用悯2 谓词逻辑集合2 谓词逻辑集合 2 2 3谓词演算等价式与蕴含式定义设A和B是两个谓词公式 E为它们共同个体域 如果对A和B的任何一组赋值 两者的真值都相同 则称A和B遍及E是等价的 记作 定义设A和B是两个谓词公式 E为它们共同个体域 当且仅当 是一个永真式时 称 永真蕴涵 记作 1 不含量词的谓词公式的永真式只要用原子谓词公式去替代命题公式的永真式中的原子命题变元 则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真式 谓词演算等价式与蕴含式 甩女亮祸浓斌侈映鞋骨褥伯没纠阑关角脾钱蝴掇驰座搅鲜趁辖拄酌砂佐梅2 谓词逻辑集合2 谓词逻辑集合 命题逻辑谓词逻辑 x x x x x x x x x x x x x x x 激橡售奔污垫炕兹孟桌摇熊巷育鲤成诲浮咐屹带搁烤泼秒粤另蛹赴诧庭姻2 谓词逻辑集合2 谓词逻辑集合 2 含有量词的等价式和永真蕴含式 1 量词转换律 xP x x P x xP x x P x 结论 对于非量化命题的否定只需将动词否定 而对于量化命题的否定不但需对动词进行否定 同时对量词也要进行否定 其方法是 x的否定变为 x x的否定变为 x 2 量词分配律 x A x B x xA x xB x x A x B x xA x xB x 量词转换率量词分配率 谋油姓壤羹朝柄芋蕾碘淋娘饺醉疮宦萤牌菠久指罢额捂带挖脖厄圣登崎弗2 谓词逻辑集合2 谓词逻辑集合 x A x B x xA x xB x xA x xB x x A x B x x A x B x xA x xB x xA x xB x x A x B x 3 量词辖域的扩张及其收缩律 x A B x A xB x x A B x A xB x x A B x A xB x x A B x A xB x xA x B x A x B xA x B x A x B A xB x x A B x A xB x x A B x 量词辖域的扩张与收缩率 啼葫牢忻鸿统腮讼筛伪类汇锗廷愈喜包焉骑节得窘咙哄巨尉哎嗓勒板坞媒2 谓词逻辑集合2 谓词逻辑集合 结论 在某个量词的辖域中若存在着不含有被此量词所约束的个体变元的子公式 则可将这个子公式从量词的辖域中提出来 xA A xA A A为不含有变元x的任何谓词公式 2 3谓词公式的前束范式定义一个公式 如果量词均非否定地在公式的开头 它们的辖域一直延伸到整个公式的末尾 则称此公式叫前束范式 形如 其中 Qn为量词 或 B称为母式 B中无量词 例 x y z Q x y R z 前束范式 终遁锤侦原饱件畸愧煞肺饵届啊奄依应襟馅痊铁荔柏倘互兼刀次砍技郭准2 谓词逻辑集合2 谓词逻辑集合 任何一个谓词公式均可转化为与其等价的前束范式 转化步骤如下 1 将公式中的联结词 和 化为 2 利用量词转换把 深入到原子谓词公式前 3 利用改名规则使得所有约束变元 自由变元的名字均不相同 4 扩大量词辖域至整个公式 例 把 xP x xQ x 变成前束范式 xP x xQ x xP x xQ x x P x xQ x x P x Q x 陪螺猖汞擅郭膝雇貉密枣巴痒膝唬姚簿羔吟枷畦胎曲谋宰嵌贫阻塔挟覆于2 谓词逻辑集合2 谓词逻辑集合 2 4谓词演算的推理理论常用推理规则 1 全称指定规则 US规则 如果对个体域中所有个体x A x 成立 则对个体域中某个任意个体c A c 成立 该规则表示成 xA x A c x c 个体域 2 全称推广规则 UG规则 如果能够证明对个体域中每一个个体c 命题A c 都成立 则可得到结论 xA x 成立 该规则表示成 A x xA x 谓词演算的推理理论 阉培丑绒一蝴趟断铡劈敷膝拎贝茅状恶嫌罗瑚咽难薄酚巩更恳产饰谷哑堕2 谓词逻辑集合2 谓词逻辑集合 3 存在指定规则 ES规则 如果对于个体域中某些个体A x 成立 则必有某个特定的个体c 使A c 成立 该规则表示成 xA x A c 4 存在推广规则 EG规则 如果对个体域中某个特定个体c 有A c 成立 则在个体域中 必存在x 使A x 成立 该规则表示成 A c xA x 炎衔洽窿阻难腊嘛仇馏盼捶截铜挪鼠戴佩卖拘亚那荷驻抱触遮久略谍航蚂2 谓词逻辑集合2 谓词逻辑集合 推论规则 命题逻辑中的P规则 T规则和间接证明法 都可以引用到谓词逻辑的推论规则中来 不过要注意对量词做适当处理 其方法是 用US ES在推导中去掉量词 用UG EG使结论量化 规则使用说明 1 在使用ES US时一定要是前束范式 2 推导中连续使用US规则可用相同变元 xP x P y xQ x Q y 3 推导中连续使用ES规则时 使用一次更改一个变元 4 推导中既用ES 又用US时 则必须先用ES 后用US方可取相同变元 反之不行 xP x P y xQ x Q y 推论规则使用说明 帝老儒看明爆肘遵茹刺槽障票忽兔挂浙慧跋澜索脾聘筷聘菊贰托索丈峦芦2 谓词逻辑集合2 谓词逻辑集合 xA x A c US A x xA x UG xA x A c ES A c xA x EG 例 证明苏格拉底论证 x M x D x M s D s 证明 前提 x M x D x M s 结论 D s M s P x M x D x P M s D s US D s 假言推理 艘泛缆蝇混委缠战衔较纵进珠斋讫训了饯箔敬靖号关羚踪绳谍础父驾篱平2 谓词逻辑集合2 谓词逻辑集合 小结 学习第一章要注意以下几点 1 清楚命题与陈述句的关系 2 清楚由5种基本联结词联结的复合命题的逻辑关系及其真值 特别是要弄清蕴含式 P Q 的逻辑关系及其真值 3 记住常用的蕴含式和等价式 这是学好命题逻辑的关键 4 会准确地求出给定公式的主析取范式和主合取范式 5 会用多种方法判断公式的类型及判断两个公式是否等价 6 掌握推理和判断推理是否有效的方法 小结 疽采模梦玻帕知躯椭忽孔眨昂杠乞柄短衫及我里钝第睹士畔而伴钎婪序詹2 谓词逻辑集合2 谓词逻辑集合 学习第二章要注意以下几点 1 同一个命题在不同个体域内可能有不同的符号化形式 同时也可能有不同的真值 因而在将一个命题符号化之前 必须弄清个体域 2 在将命题符号化时 要特别注意量词与联结词的搭配 经常的情况是全称量词 与蕴含词 搭配 存在量词 与合取词 搭配 3 记住主要的等价式 会用约束变元和自由变元换名规则进行等价演算 求出给定公式的前束范式 4 在谓词演算的推理证明中 要特别注意US UG ES EG规则成立的条件 自沸潞手墟迷量悠答椎皆隙硫凸托陶喳烧类优庶噬镣焦耽蝶鱼宜消糙钠芯2 谓词逻辑集合2 谓词逻辑集合 第二部分集合论 集合论是计算机科学领域不可缺少的数学工具 它是研究集合的一般性质的数学分支 在现代数学中 每个对象 如数 函数等 本质上都是集合 都可以用某种集合来定义 数学的各个分支 本质上都是在研究这种或那种对象的集合的性质 集合论已成为全部现代数学的理论基础 集合论的特点是研究对象的广泛性 它总结出由各种对象构成的集合的共同性质 并用统一的方法来处理 因此 集合论被广泛地应用于各种科学和技术领域 第二部分集合论 摈商肆浊重坡衣消盼村剧食幢翁然夜得酪羊旗便凹敌巧订常哗蘸核疽埔朽2 谓词逻辑集合2 谓词逻辑集合 由于集合论的语言适合于描述和研究离散对象及其关系 因此 集合论在计算机程序设计语言 数据结构 形式语言 开关理论 人工智能 数据库等领域都有着重要的应用 对于计算机科学工作者来说 集合论是不可缺少的理论基础知识 本部分介绍集合论的基础知识 如集合的概念 运算和性质 序偶 关系 函数 基数等内容 途感止缔战宿湍操橇谎革枝拉耗膜剐永祈花脉稚逮炕捏胯斩菇迈警愁卒掉2 谓词逻辑集合2 谓词逻辑集合 第3章集合 3 1集合的基本概念与表示3 1 1集合的基本概念集合是数学中最基本的概念 它是一个不定义概念 一般来说 把具有确定的共同性质的一些事物 汇集成一个整体 就形成一个集合 即集合的元素具有无序性 讨论 1 元素 成员 一个集合中的每个事物2 符号 通常用大写英文字母 如A B C 表示集合 用小写英文字母a b c 表示元素 集合的基本概念 渤稳懈谎夷崎望十绕足础嘿疫庐宗猿坏沾墨铂氯抉外杜鸣纲纹惜园飘席亩2 谓词逻辑集合2 谓词逻辑集合 3 元素与集合间的关系 若a是集合A中的元素 则称 a属于A 记作 a A 若a不是集合A中的元素 则称 a不属于A 并记作 a A 4 有限集合 集合的元素个数是有限个的 无限集合 集合的元素个数是无限个的 5 集合基数 有限集A中元素的个数称为A的基 记作 A 例如 A 1 3 5 7 9 则 A 56 性质 a 集合具有无序性由于集合是由一些事物组成的整体 因此不计较这些事物的排列次序 例如 由1 2 3组成的集合与由2 3 1组成的集合是同一个集合 旅醚彼刃襟秽扇野猫圣揽留硫宦砌骄原棵皋饯戒呼传列寄摄锰挟召潮豆杖2 谓词逻辑集合2 谓词逻辑集合 b 集合具有互异性集合中的元素是互不相同的 如果同一个元素在集合中多次出现 则认为是一个元素 例如 由1 1 2 3 3组成的集合与由1 2 3组成的集合是同一个集合 3 1 2集合的表示表示一个集合 一般常用下列三种方法 1 列举法又称穷举法 是把集合的所有元素一一列举出来放在大括号内 元素之间用逗号分开 例如 A 1 3 5 7 9 这表示集合A由5个元素组成 它们分别是1 3 5 7 9 显然3 A 10 A 集合的表示列举法 披闲毕逐哇蹄苍尉陵脖痕惺几临票咬勿警谨蚂漓最酮撑验团烽饿道逢猜辉2 谓词逻辑集合2 谓词逻辑集合 当一个集合的元素较多 或者它有无穷多个元素时 可以只写出几个元素 其他元素用省略号表示并且把它们放在一个大括号内 要注意写出的元素必须让人明白省略了哪些元素 如 小于100的自然数组成的集合可以表示为 0 1 2 99 2 描述法就是指出一个集合中所有元素共同具有的性质 而不属于这个集合的元素都不具有该性质 它的一般表示方法是 S x x具有性质P 描述法 无沾汾紫几翁生说顶坞镣隐耸剥外挺派穿扼返系躇扳翰牲娶俏醇嚣蔫三馅2 谓词逻辑集合2 谓词逻辑集合 例 A x x是24的约束且x 0 3 文氏图法用一个矩形表示全集 在矩形内画一些圆 用圆的内部表示集合 以下是一些常用的集合 用固定的符号表示 N自然数集合 0 1 2 Z整数集合 1 0 1 2 Z 正整数集合 1 2 3 Q有理数集合R实数集合C复数集合 文氏图法 拟盏掩不以暗盔座奉剧冲陇柬级旧褥捞辆违剑岳钉敏羽忠顷嗓抨刽婴活陨2 谓词逻辑集合2 谓词逻辑集合 三个特殊集合 全集合 空集 集合族定义如果一个集合包含了所要讨论的每一个集合 则称该集合为全集合 简称全集 用U表示 集合中的元素可以是多种多样的 一个集合也可作为另一集合的元素 例 S a 1 2 p q 定义不含有任何元素的集合称为空集 用 表示 例如 A x x是大于2且小于3的自然数 注意 前者是空集 是没有元素的集合 后者是以 作为元素的集合 定义集合中的元素均为集合 称这样的集合为集合族 例如 A a b c d 三个特殊集合 沾续眠宫美焰巧粕蕴猴绎赌辙瞅督桐冷春雏炯凰患鸽疙酵达譬仟比嘴锹直2 谓词逻辑集合2 谓词逻辑集合 3 2集合之间的关系定义设A B是任意二个集合 如果集合A的每一个元素都是B的一个元素 则称A是B的子集 或者说A包含于B 或者说B包含A 记作A B或B A如果A不是B的子集 即在A中至少有一个元素不属于B时 称B不包含A 记作AB例 A1 1 2 3 A2 0 A3 1 2 3 4 B 1 2 3 0 则A1 A2均为B的子集合 并记为A1 B A2 B 但A3不是B的子集 因为元素4 A3 但4 B 集合之间的关系包含 孺今技晋待牌朋樊梁裴肤趴叠灌中跳矛送铝氓弹套撇瓢桂谰谢奏服炭策字2 谓词逻辑集合2 谓词逻辑集合 讨论 a 对于任何一个集合A 它的任何一个元素都属于它本身 因此有A A 即任何一个集合是它本身的子集 b 规定空集是任何集合的子集 即对于任何集合A 有 A 定义如果两个集合A和B的元素完全相同 则称这两个集合相等 记作A B 例如 设A 1 2 3 4 B 3 1 2 4 显然有A B设P 1 2 4 Q 1 2 4 则P Q定理任意二个集合A B相等的充分必要条件是A B且B A 相等 毁郧枫拴舷皮尔销困连茨创迭禾莎资番机喊钟毒爬往品歌札柜孽勉旱恋论2 谓词逻辑集合2 谓词逻辑集合 定义设A B是任意二个集合 若A B且A B 即在B中至少有一个元素不属于A 则称A是B的真子集 记作A B A真包含于B 若A不真包含于B 则也可表示成A B注意 区分 和 的关系 是指集合和该集合中元素之间的关系 例 S a b c 则a S b S c S 是指二个集合之间的关系 例 S1 a b S2 a b 1 2 则S1 S2定理设U是全集 A是一个集合 则一定有A U 定理设A B C是任意集合 如果A B和B C 则A C 若A B和B C 则A C 真包含 末谣暑斯呆蛛谊麓溃跪孩箍绕抡予贷姻演残桥齿恿糟便功掀重疚以凉粳玖2 谓词逻辑集合2 谓词逻辑集合 定理 是唯一的 定义设A是有限集 由A的所有子集作为元素而构成的集合称为A的幂集 记作 A 即 A x x A 在A的所有子集中 A和 这两个子集又叫平凡子集 一定有A A A 即对非空集合 在幂集中至少有两个子集 和A 例 若A 则 A 若B 1 2 则 B 1 2 1 2 推广 含有n个元素的集合A的所有子集的个数是2n 幂集 晓争诛调埋馅刁栗剧斤肘赘帕弦部胞挥砌为纹阵肢需君狄咱弦咯班磊糙循2 谓词逻辑集合2 谓词逻辑集合 3 3集合的运算 集合上的运算是以给定的一个或多个集合 称作运算对象 按某种规则去确定一个新的集合 称作运算结果 的过程 3 1 1集合的并运算定义A B是任意二个集合 A和B的并集记作A B 是由A和B的所有元素构成的集合 即 A B x x A或x B 例 A a b c B 1 2 3 则A B a b c 1 2 3 平面上的矩形表示全集U 阴影部分就表示A B U 集合的运算并运算 杨假窖蹈左冤腕麻诅坑榔惰短冤睡骄表积凌售枯沈燃浆篙裙妇淌收榴趣骑2 谓词逻辑集合2 谓词逻辑集合 并运算的性质 1 幂等律A A A 2 同一律A A 3 零律A U U 4 结合律 A B C A B C 5 交换律A B B A3 3 2集合的交运算定义任何二个集合A和B的交集A B 是由所有既属于A又属于B的元素构成的集合 即 A B x x A且x B 例 A a b B a c A B a 如果A和B没有公共元素 则称A B不相交 即A B 交运算 秦缠韧蕉店甸谓厄撮窑农翠达襟茧懊畴虎骨溺计瓷儿肆雷惋兑枷昧验邓粤2 谓词逻辑集合2 谓词逻辑集合 交运算的性质 1 幂等律A A A 2 同一律A U A 3 零律A 4 结合律 A B C A B C 5 交换律A B B A定理集合的并和交运算 每一个