离散数学教学课件-第一章.pptVIP

第一部分 数理逻辑 主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理 第一章 命题逻辑的基本概念 主要内容 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值 定义：一个或真或假但不能两者都是的陈述句称为命题，用小写英文字母表示. 命题的判断结果称为真值，用“1”表示真，用“0”表示假. 注：命题必须满足两个条件： （1）命题是表达判断的陈述句； （2）命题有确切的真值. 命题概念 蕴涵联结词 定义 设p, q为命题， “如果p, 则q”称作p与q的蕴涵式，记作p?q，并称p是前件，q为后件，?称作蕴涵联结词. 注：（1）p?q为假当且仅当p为真q为假. （2） p与 q可以无任何内在联系. 蕴涵联结词 定义 设 p, q为命题， “p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词. 注：p?q为真当且仅当p与q同时为真或同时为假. 注:（1）常用的联结词有5个：否定?、合取∧、析取∨、蕴涵?、等价?. （2）由一个联结词联结的一个或两个原子命题而成的复合命题称为基本复合命题. 例 将下列论述符号化,并求所得复合命题的真值. (1) 若2和3是素数，则5是奇数. 2是素数，3也是素数. 所以，5或6是奇数. 1.2 命题公式及其赋值 命题变项与合式公式 命题变项 合式公式 合式公式的层次 公式的赋值 公式赋值 公式类型 真值表 命题变项与合式公式 由于简单命题真值唯一确定，所以简单命题也称为命题常项（命题常元）. 取值1（真）或0（假）的变元称作命题变项（命题变元）. 命题常项与命题变项均用 p, q, r, …, pi, qi, ri, …, 等表示. 注：命题常项与命题变项的关系类似初等数学中常量与变量的关系. 问：命题常项是命题吗？ 命题变项是命题吗？ 命题变项与合式公式 注：（1）设A是合式公式，B为A中一部分，若B也为合式公式，则称B为A的子公式. （2）定义中A，B等符号（用来表示任意的合式公式）, 称作元语言符号；而某个具体的合式公式, 称作对象语言符号. （3）公式中不影响运算次序的括号可以省去. 例1. 判断下列符号串中哪些是合式公式. （1）( p?q )∧r （2） pq?r （3） p?q?r （4） p∧q∧r 定义 设p1, p2, … , pn是出现在公式A中的全部命题变项, 给p1, p2, … , pn各指定一个真值, 称为对A的一个赋值（解释）. 若指定的一组真值使A的真值为1, 则称其为A的成真赋值; 若指定的一组真值使A的真值为0, 则称其为A的成假赋值; 例：设 A= ( p??q)?r 011是成真赋值 100是成假赋值. 问：含n个命题变项的公式有多少种赋值？ 定义 将命题公式A在所有赋值下取值情况列成表, 称作A的真值表. 构造真值表的步骤: (1) 确定公式中全体命题变项, 赋值从00?0开始, 按二进制加法依次写出赋值, 直到11?1. (2) 从低到高写出公式的各个层次. (3) 按照赋值计算各层次真值, 直至计算出公式的真值. 例3 写出A= ( p??q)?r的真值表, 并求其成真赋值和成假赋值. 定义 设A是命题公式， 若A在所有赋值下真值为1，则称A是重言式（永真式） 若A在所有赋值下真值为0，则称A是矛盾式（永假式） 真值表的作用： （1）准确地给出公式的成真赋值和成假赋值. （2）判断公式的类型. 第一章 小结 主要内容 命题、真值、简单命题与复合命题、命题符号化 联结词?, ?, ?, ?, ?及复合命题符号化 命题公式及层次 公式的类型 真值表及其应用 基本要求 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值深刻理解合式公式及重言式、矛盾式、可满足式等概念 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型 * 第一部分 数理逻辑 逻辑是什么？ 逻辑就是思维的规律 逻辑学是探索、阐述和确立有效推理原则的学科 用数学的方法研究关于推理、证明等问题的学科就称为数理逻辑（符号逻辑） 程序=算法+数据 算法=逻辑+控制 Let’s go! 1.1 命题与联结词 例1 下列句子中哪些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 我正在说谎. (6) 1+101=110. (7) 1是奇数，而2是偶数. 假命题 真命题 不是命题 不是命题