离散数学命题逻辑--.ppt

数理逻辑的主要内容 数理逻辑内容丰富，但其主要包括“两个演算” 加“四论”，即： 逻辑演算。包括命题演算和谓词演算 证明论。主要研究数学理论系统的相容性（即不矛盾、协调性）的证明。 递归论（能行性理论）。自从电子计算机发明后，迫切需要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论，它为能行可计算的函数找出各种理论上精确化的严密类比物。 模型论。主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系。 公理集合论。主要研究在消除已知集合论悖论的情况下，用公理方法把有关集合的理论充分发展下去。 第一篇 数理逻辑 第一章 命题逻辑研究的内容 命题逻辑也称为命题演算 研究以命题为基本单位构成的前提和结论之间的可推导关系。 第一章 命题逻辑 学习要求 请看下面给出的两个陈述句： （1）2是个素数。 （2）雪是黑色的。 这两个陈述句都表示对事件性质的判断。 第一句话表示的判断是正确的， 第二句话表示的判断是错误的。 像(1),(2)这样能够唯一确定所表达的判断是正确的还是错误的陈述句称为命题。 判断语句是否为命题要注意的问题： 1、目前无法确定真值，但从本质而言，真值存在的语句是命题。 例： (1) 别的星球上有生物。 (2) 2046年世界杯在中国举行。 2、真值因时因地而异的判断性陈述句是命题。 例：(1) 2011年的元旦是晴天。 (2) 今天下雨。 3、含有未确定内容的代词，不能判断真假的语句不是命题。 例： (1) 1+101=110。 当1和101是二进制数，语句为真，为十进制数，语句为假。 (2) x+y10。 4、悖论不是命题。语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。 例：我正在说慌。 如何判断一个句子是否为真命题？ 1、是否为陈述句？ 2、其真值是否唯一？ 3、其真值是否为真。 下列语句不是合取联结词组成的命题 1）张丽和王芳是好朋友。 2）他打开箱子然后（而后）拿出一件衣服来。 区分“可兼或”与“不可兼或” 例1-2.3 灯泡有故障或者线路有故障。 今晚写字或看书。 今天下雨或打雷。 以上例子为可兼或。 析取为可兼或。 例：下面均为双条件联结词 平面上二直线平行，当且仅当这二直线不相交。 春天来了，燕子飞回来了。（春天来了当且仅当燕子飞回来了） 2+2=4当且仅当雪是白的。 示例 一位父亲对儿子说：“如果星期天天气好，就一定带你 去动物园。”问：在什么情况下父亲食言？ 父亲的可能情况有如下四种： (1) 星期天天气好，带儿子去了动物园； (2) 星期天天气好，却没带儿子去动物园； (3) 星期天天气不好，却带儿子去了动物园； (4) 星期天天气不好，也没带儿子去动物园。 举例： 令：P：天气好。Q：我去公园。 析取和异或示例 指出下列命题中的“或”是析取还是异或。 今晚我去看演出或在家里看电视现场转播。 他是一百米冠军或跳高冠军。 派小王或小赵出差去上海。 派小王或小赵中的一个出差去上海。 2、3为析取，1、 4为异或 命题公式的子公式 定义 如果X是合式公式A的一部分，且X本身也是一合式公式，则称X为公式A的子公式。 如：A： (P ∧ Q) ∨R中P、Q、R、 P ∧ Q 举例 例1.说离散数学无用且枯燥无味是不对的。 例2.如果小张与小王都不去，则小李去。 构造真值表的步骤 ①找出给定命题形式中的所有命题变元，列出所有可能的赋值; ②按计算从前到后的顺序列出命题公式的子公式； ③计算各子公式的值，直至最后计算命题形式的值。 命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。 * 4、 等价公式的证明方法-怎样证明公式是等价的 方法1：用真值表。 方法2：用重言式证明（见下一节） 方法3：用公式的等价变换。 定义1-4.3 如果X是合式公式A的一部分，且X本身也是一合式公式，则称X为公式A的子公式。 如：A： (P ∧ Q) ∨R中P、Q、R、 P ∧ Q * 定理1-4.1 置换定律（等价代换定理）： 设X是合式公式A的子公式，Y是一命题公式，若X?Y，如果将A中的X用Y来置换，则所得到公式B与公式A等价，即A?B。 从定理可见，一个命题公式A，经过多次的置换，所得到的新公式与原公式等价。 等价代换定理的用途。 1、验证两个命题公式等价。 2、化简命题公式。 3、判断命题公式的类型。（见第五节） * 等价代换定理用于证明公式的等价 例题1. 求证吸收律 P∧(P∨Q)?P 证明 P∧(P∨Q)