离散数学第9章-命题逻辑.pptVIP

* * 数理逻辑（符号逻辑）：用数学的方法研究演绎推理的规律。 数学方法：引进一套符号体系简洁地表达出各种推理关系。 为什么要研究数理逻辑？ 程序＝算法＋数据结构 算法＝逻辑＋控制 * 北京是中国的首都； 中国是世界上人口最多的国家； 1＋1＝10； 3能被2整除； 地球外的星球上也有人； 命题 9.1 命题和命题联结词 一、命题 第9章 命题逻辑 命题 命题 命题 命题 1. 定义：能分辨真假的陈述句称为命题。 * 把门关上！ 滚出去！ 你要出去吗？ 今天天气真好啊！ 非命题 非命题 非命题 非命题 注意： 一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句等。 * 命题非真即假， 用“1”表示真，“0”表示假,称作命题的真值。 2.命题的真值 命题用大写字母A、B、…、P、Q、…表示。 3.命题的符号化 P：北京是中国的首都； Q：中国是世界上人口最多的国家； * ① 原子命题(原始命题) 4. 命题的分类 C: 1+1=3当且仅当太阳从西边升起. B: 如果明天下雨，那么我就宅家里. A: 我上网或睡觉. ② 复合命题 例如：张谦是大学生； * 二、 命题联结词 设命题P,Q表示两个命题,则最常见的命题联结词有： 联接词 记号 复合命题 读法 记法 真值结果 3.析取 ? P或者Q P与Q的析取 P?Q P∨Q=1?P=1或Q=1 2.合取 ∧ P并且Q P与Q的合取 P∧Q P∧Q=1?P=1且Q=1 1.否定 ┐ 非P P的否定 ┐P ┐P=1? P=0 4.蕴涵 → 若P,则Q P蕴涵Q P→Q P→Q=0 ? P=1,Q=0 ? 5.等值 P当且仅当Q P等价于Q P?Q P?Q=1?P=1,Q=1 或P=0,Q=0 * 真值表总结 P Q ┐P P∧Q P∨Q P→Q P?Q 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 * 说明 1、联结词是命题(句子)与命题(句子)之间的联结，而非单纯的名词、形容词、数词等联结； 例如：2+2=4 ?雪是白的。 2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何的内在联系； * （1）四川不是人口最多的省份； 符号化下列命题 设Ｐ：四川是人口最多的省份； 则命题（1）可表示为┐Ｐ。 * （2）王超是一个德智体全面发展的好学生； 符号化下列命题 设Ｐ：王超是一个思想品德好的学生； Ｑ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生； 则命题（2）可表示为 Ｐ∧Ｑ∧R。 * （3）教室的灯不亮可能是灯管坏了或者是停电了； 符号化下列命题 设Ｐ：教室的灯不亮可能是灯管坏了； Ｑ：教室的灯不亮可能是停电了； 则命题（3）可表示为Ｐ∨Ｑ。 * （4）如果周末风和日丽，那么学院将组织我们到木兰天池春游； 符号化下列命题 设Ｐ：周末风和日丽； Ｑ：学院将组织我们到木兰天池春游。 则命题（4）可表示为Ｐ→Ｑ。 * （5）两个三角形全等当且仅当三角形的三条边全部对应相等。 符号化下列命题 设Ｐ：两个三角形全等； Ｑ：三角形的三条边全部对应相等； 则命题（5）可表示为Ｐ?Ｑ。 * 命题联结词之优先级如下： 否定→合取→析取→蕴涵→等值 约 定 同级的联结词，按其出现的先后次序(从左到右) 若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。 * 例 设P:雪是白色的;Q:2+2=4。将下列命题符号化： （1）除非雪是白色的，否则2+2≠4； ? P→? Q Q→P （2）如果2+2=4，雪（肯定）是白色的； * 命题联结词的应用 例 用复合命题表示如下图所示的开关电路： A∧B A∨B A 设Ａ：开关Ｐ闭合；Ｂ：开关Ｑ闭合。 * 9.2 命题公式 4. 有限次使用规则1-3产生的符号串是命题公式。 命题常元：具有确定真值的命题。 命题变元：真值不确定的命题。 命题变元与命题常元是命题公式； 3. 若 A、B是命题公式，则 (A∧B)、(A∨B)、(A→B)、(A?B)也是命题公式； 2. 若A是命题公式，则(┐A)也是命题公式； 一、命题公式递归定义 * 1. ((P∧(Q∨R))→(Q∧(┐S∨R)))； 2. (┐P∧Q)； 3. (P→(┐(P∧Q)))； 4. (((P→Q)∧(R→Q))?(P→R)) 下列符号串是命题公式 * (P→Q)∧┐Q)； (P→Q； (┐P∨Q∨(R； P∨Q∨ 下列符号串不是命题公式 * 若a和b是偶数，则a+b是偶数