离散数学课件命题演算数.ppt

课程安排 第一章 命题演算及其 形式系统 1.1 命题与联结词 一、命题 例： 1.雪是白的。 2.雪是黑的。 3.好大的雪啊！ 4. 昨天下雪了吗？ 一、命题 例： 5.陈胜、吴广起义的那天杭州下雨。 6.2006年10月1日天晴。 7.别的星球上有生物。 一、命题 例： 8) 2＋2＝5 9) 1＋101＝110 10) x+y≤0 一、命题 例： 11) 我正在说谎。 12) 我只给那些不给自己刮胡子的人刮胡子。  一、命题 二、原子命题和复合命题 三、命题的表示 为了能用数学方法来研究命题之间的逻辑关系和推理，需要将命题符号化。 原子命题通常记为p，q，r，s等小写拉丁字母。 f表示恒假命题， t表示恒真命题。 三、命题的表示 1 用单个字母表示某一具体命题，这时该符号称为“命题常元”。 2 用单个字母表示任一命题，这时该符号称为“命题变元”。它们是以“真、假”为取值范围的变元。 四、逻辑联结词 1)否定词(negation) 1)否定词(negation) 2)合取词(conjunction)“并且”(and) 2)合取词(conjunction)“并且”(and) 例： 例： 析取词(disjunction)“或”(or) 析取词(disjunction)“或”(or) 例： p: 我选修人工智能。 q: 我选修算法理论。 则p∨q: 我选修人工智能或选修算法理论。 析取词(disjunction)“或”(or) 析取词(disjunction)“或”(or) 命题否定 今天下雨且今天下雪。 否：今天不下雨且今天不下雪。 蕴涵词(implication)“如果……，那么……”(if…then…) 蕴涵词(implication)“如果……，那么……”(if…then…) 蕴涵词(implication)“如果……，那么……”(if…then…) 例： 如果我拿到奖学金，我请客。 双向蕴涵词(two-way implication)“当且仅当”(if and only if)， 双向蕴涵词(two-way implication)“当且仅当”(if and only if)， 例： p:△ABC是等腰三角形 q:△ABC中有两个角相等 命题p q就是△ABC是等腰三角形当且仅当△ABC中有两个角相等。 五、命题公式 五、命题公式 五、命题公式 五、命题公式 五、命题公式 六、语句的形式化 七、重言式 七、重言式 七、重言式 八、逻辑等价式 一些十分重要的逻辑蕴涵式 注意RS与RR的区别 三种证明逻辑等价式及逻辑蕴涵式的方法 例： 十二、范式 十二、范式 (1)析取范式 (1)析取范式 (2)合取范式 (2)合取范式 析取范式和合取范式求取 范式 析取范式和合取范式 范式可用来判断重言式和矛盾式 主析取范式与主合取范式 主析取范式和主合取范式求取 主析取范式和主合取范式求取 主析取范式与主合取范式 主析取范式与主合取范式 主析取范式与主合取范式 指派与两种范式之间的联系 结论： 结论： 结论： 定理1-1 对任意命题公式A，B，C，A，B， （1）A╞╡B当且仅当╞ A?B （2）A╞ B当且仅当╞ A→B （3）若A╞╡B，则B╞╡A （4）若A╞╡B，B╞╡C，则A╞╡C （5）若A╞ B，则┐B╞ ┐A （6）若A╞ B，B╞ C，则A╞ C （7）若A╞ B，A╞╡A ，B╞╡B ， 则A╞ B 性质 定理1-2 设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B后所得的命题公式（称为A的一个代入实例），那么A(B/p)亦为永真式。 定理1-2常被称为代入原理 (rule of substitution)，简记为RS 十、代入原理 定理1-3 设A为一命题公式，C为A的子公式，且C╞╡D。若将A中子公式C的某些（未必全部）出现替换为D后得到的公式记为B，那么A╞╡B。 定理1-3常被称为替换原理 (rule of replacement),简记为RR。 十一、替换原理 任一命题公式 任一子公式 任一与代换对象等价的命题公式 代换子公式的某些出现 与原公式等价 任意永真式 任一命题变元 任一命题公式 代换同一命题变元的所有出现 仍为永真式 使用对象 代换对象 代 换 物 代换方式 代换结果 RR RS （1）真值表法。 （2）对指派进行讨论。 证A╞ B， ?(A)＝1， ?(B)＝1