清华离散数学(第版)教材.ppt

第1章 数学语言与证明方法 第1章 数学语言与证明方法 1.1 逻辑符号 1.2 集合及其运算 1.3 证明方法概述 1.1 逻辑符号 联结词 真值:真, 假 或 1, 0 命题:具有确定真值的陈述句, 通常用p,q,r等表示 真命题:真值为真的命题 假命题:真值为假的命题 例如, p:2+2=4, q:3是偶数 它们都是命题, p是真命题, q是假命题. 否定联结词? 否定式?p: 非p (p的否定) ?p 为真当且仅当p为假 联结词(续) 联结词(续) 蕴涵联结词? 蕴涵式p?q:如果p,则q p?q为假当且仅当 p 为真 q 为假 等价联结词? 等价式p?q:p当且仅当q p?q为真当且仅当p与q同时为真或同时为假 实例 设p:2是偶数, q:1+1=3, 则 实例(续) p?q的真值为 命题公式 命题变项:取值为0或1的变元, 也用p,q,r等表示. 命题公式:用联结词和圆括号把命题和命题变项按照一定 规则连接起来的符号串, 常用A,B,C等表示. 例如, A=(?p?q)?(r?p) 公式的赋值:对公式中每一个命题变项给定一个值(0或1). 公式的成真赋值:使公式为真的赋值. 公式的成假赋值:使公式为假的赋值. 例如, p=1,q=1,r=1是A的成真赋值, p=0,q=1,r=0是A的成假赋值. 重言式,矛盾式与可满足式 重言式(永真式):无成假赋值的命题公式 矛盾式(永假式):无成真赋值的命题公式 可满足式:不是矛盾式的命题公式 例如, A= (?p?q)?(r?p)是可满足式, 但不是重言式, B= (p?q)?(?p?q)?(p??q)?(?p??q)是重言式, C= ?p?(p?q)?(p??q)是矛盾式. A?B:蕴涵式A?B是重言式的简记. A?B:等价式A?B是重言式的简记， 称A与B等值，A?B是等值式. 基本等值式 双重否定律 ??A?A 幂等律 A?A?A, A?A?A 交换律 A?B?B?A, A?B?B?A 结合律 (A?B)?C?A?(B?C) (A?B)?C?A?(B?C) 分配律 A?(B?C)?(A?B)?(A?C) A?(B?C)? (A?B)?(A?C) 德·摩根律 ?(A?B)??A??B ?(A?B)??A??B 基本等值式(续) 吸收律 A?(A?B)?A, A?(A?B)?A 零律 A?1?1, A?0?0 同一律 A?0?A, A?1?A 排中律 A??A?1 矛盾律 A??A?0 蕴涵等值式 A?B? ?A?B 等价等值式 A?B?(A?B)?(B?A) 假言易位等值式 A?B? ?B? ?A 等价否定等值式 A?B? ?A? ?B 归谬论 (A?B)?(A??B) ? ?A 重要推理规则(推理定律) 附加律 A ? (A?B) 化简律 (A?B) ? A 假言推理 (A?B)?A ? B 拒取式 (A?B)??B ? ?A 析取三段论 (A?B)??B ? A 假言三段论 (A?B)?(B?C) ? (A?C) 等价三段论 (A?B)?(B?C) ? (A?C) 构造性二难 (A?B)?(C?D)?(A?C) ? (B?D) 破坏性二难 (A?B)?(C?D)?( ?B??D) ? (?A??C) 谓词与量词 个体域:被研究对象的全体, 如自然数集, 人类等. 个体词:个体域中的一个元素. 全称量词?: 表示任意的, 所有的, 一切的等. 存在量词?: 表示存在, 有的, 至少有一个等. 谓词: 表示个体词性质或相互之间关系的词 例如, 谓词P(x)表示x具有性质P ?x P(x) 表示个体域中所有的x具有性质P ?x P(x) 表示个体域中存在x具有性质P 1.2 集合及其运算 集合及其表示法 包含(子集)与相等 空集与全