离散数学教学课件-ch1.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * 第一部分 数理逻辑 逻辑是什么？ 逻辑就是思维的规律 逻辑学是探索、阐述和确立有效推理原则的学科 用数学的方法研究关于推理、证明等问题的学科就称为数理逻辑（符号逻辑） * 程序=算法+数据 算法=逻辑+控制 Let’s go! * 主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理 第一部分 数理逻辑 * 第一章 命题逻辑的基本概念 主要内容 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值 * 定义：一个或真或假但不能两者都是的陈述句称为命题，用小写英文字母表示. 命题的判断结果称为真值，用“1”表示真，用“0”表示假. 注：命题必须满足两个条件： （1）命题是表达判断的陈述句； （2）命题有确切的真值. 1.1 命题与联结词 * 例1 下列句子中哪些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 我正在说谎. (6) 1+101=110. (7) 1是奇数，而2是偶数. 假命题 命题概念 真命题 不是命题 不是命题 悖论，不是命题 不是命题 真命题 * 命题分类 命题 复合命题 原子命题 （简单命题） 不能分解成更简单的命题 由原子命题通过联结词联结而成的命题 * 否定联结词 定义 设 p为命题， “非p”(或“p的否定”)称为p的否定式，记作?p，符号?称作否定联结词. 注：?p 为真当且仅当p为假. 例：p: 4是素数 ?p：4不是素数 p ?p 0 1 1 0 * 合取联结词 定义 设p,q为命题， “p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词. 注：p∧q为真当且仅当p与q同时为真. 例：p: 4是素数 q ：4是偶数 p∧q：4是偶素数 p q p∧q 0 0 0 0 1 0 1 0 0 1 1 1 * 析取联结词 定义 设p, q为命题， “p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词. 注：（1）p∨q为假当且仅当p与q同时为假. （2）“p或q”有两种可能：相容或、排斥或 p与q可以同时为真 p与q不能同时为真 例：数列{an}收敛或发散. p : 数列{an}收敛 q : 数列{an}发散 p q p∨q 0 0 0 0 1 1 1 0 1 1 1 1 * 定义 设p, q为命题， “如果p, 则q”称作p与q的蕴涵式，记作p?q，并称p是前件，q为后件，?称作蕴涵联结词. 注：（1）p?q为假当且仅当p为真q为假. （2） p与 q可以无任何内在联系. 蕴涵联结词 例： p：刘翔是奥运冠军. q：4是素数. p?q：如果刘翔是奥运冠军，则4是素数. 1 0 0 * 蕴涵联结词 注：(3) p?q 的常见形式： 若p，就q 只要p，就q 因为p，所以q p仅当q 只有q，才p 除非q，才p 除非q，否则非p p q p?q 0 0 1 0 1 1 1 0 0 1 1 1 * 定义 设 p, q为命题， “p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词. 注：p?q为真当且仅当p与q同时为真或同时为假. 等价联结词 p?q ：4是素数当且仅当 是无理数. 例：p: 4是素数. q: 是无理数. p q p?q 0 0 1 0 1 0 1 0 0 1 1 1 * 注:（1）常用的联结词有5个：否定?、合取∧、析取∨、蕴涵?、等价?. （2）由一个联结词联结的一个或两个原子命题而成的复合命题称为基本复合命题. p q ?p p