x本科数理逻辑-命题3-2.ppt

复习 1 命题命题定义 具有真假意义的陈述句被称为命题注 必须是陈述句有确定的真假值 且真假意义必须二者必居其一 2 命题的真值命题若为真 称命题的真值为真 可记为1或T 命题若为假 称命题的真值为假 可记为0或F 3 命题的符号化将命题的实质抽象出来 内容隐去 用字母表示一个具体的命题4 简单命题与复合命题若命题不能分解为更简单的陈述句 称为原子 简单 命题注 复合命题要能分解为若干具体的简单命题的组合5 命题变元用一个字母表示一个具体命题 具有真值 称为命题常元用一个字母表示一个抽象的命题 无确定的真值 称为命题变元 6 命题变元的赋值 命题变元的值域 注 命题变元不是命题 命题的运算 复合命题 是利用自然语言的一些连词将若干简单命题复合构成连词 要将其定义 抽象 为数理逻辑中的运算符号1 否定联结词定义 设P为命题 规定 P是不对的 称为对P的否定记为 P规定 P为真当且仅当P为假注意在自然语言中 对全称的否定 只要个别不成立对个别的否定 要对全称进行否定逻辑上有效真值表 2 合取联结词定义 设p q为二命题 复合命题 p并且q 或 p与q 称为p与q的合取式记作p q 称作合取联结词 规定p q为真 当且仅当p与q同时为真 注 i p q为一个复合命题 由二个命题p q复合构成的命题ii 合取在逻辑中表现为俩个事件同时发生注意自然语言中的连词的词义来判别是否属于此种现象 和 与 即 又 不仅 而且 等均具有合取的意义真值表 3 析取联结词定义 设 为命题 称 或 为 的的析取 记作 规定 为假 当且仅当 同时为假1 析取是自然语言连词 或 的抽象 可兼或 二个判断可同时为真 相容或 排斥或 二个判断不能同时为真 异或 不可兼或 析取联结词 抽象的是可兼或2 从定义可得其真值表 5 蕴涵联结词 定义 设 为命题 称 如果 则 为 的蕴涵式 条件命题 记作 Q规定 Q真值为假 当且仅当P为真时Q为假 并称P为 Q的前提 前件 Q为 Q的结论 后件 2 蕴涵联结词 的真值表注意 条件命题的真值与条件命题中的结论的真值是不同的概念从直值表中可以分析出 i 当前件为假 不论后件如何 则 Q一定为真即 前提不成立 结论不论真假 Q为真命题ii 后件为真 不论前件真假 Q为真命题iii Q的真值仅在 p为真q为假 时为假 其余情况均为真 当 Q的真值为假时 Q为假 则P一定为真 P为真 Q一定为假 当 Q的真值为真 P为真 Q一定为真 P为假时 Q可任意 以上的结论对今后的推理将起到非常重要的作用 对条件命题的理解 将贯穿于我们这五章的主要内容 3 自然语言中将该命题的前件和后件的其他叙述为 p qp是q的充分条件q是p的必要条件前件是后件的充分条件 后件是前件的必要条件而对于充分条件和必要条件的叙述又有各种的表达方式 如果p则q只有q则p只要p就qp仅当q若p就q除非q则p当p则q关键是对此类命题的符号化 双条件 例将下列命题符号化 并指出各复合命题的真值 1 如果3 3 6 则雪是白色的 2 若3 3 6 则雪是白色的 3 只要3 3 6 则雪不是白色的 4 3 3 6是雪不是白色的充分条件 雪不是白色的是3 3 6的必要条件 令p 3 3 6 p的真值为1 q 雪是白色的 q的真值为1 两个命题虽无逻辑上的内在联系 但可用蕴涵式表示 1 表示为p q 2 表示为 p q 3 表示为p q 4 表示为 p q真值为1101 以下命题中出现的a是给定的一个正整数 令r a能被4整除 s a能被2整除 5 只要a能被4整除 则a一定能被2整除 6 a被4整除 仅当a能被2整除 7 除非a能被2整除 a才能被4整除 8 除非a能被2整除 否则a不能被4整除 9 只有a能被2整除 a才能被4整除 10 只要a能被2整除 a才能被4整除 5 到 9 五个命题均叙述的是a能被2整除是a能被4整除的必要条件 只是在叙述上有所不同 因而都符号化为r s是否存在真值 不论a为何整数从逻辑关系可知 不会出现前件真后件假的情况故前五个命题均为真 10 所表示的是s是r的充分条件 即s r 那么结果就不能确定 只能由a的具体值确定来得到 6 等价式 双条件命题 1 定义 P q为命题 称复合命题 P当且仅当q 为P q的等价式 双条件命题 记为P q 规定 P q真值为真 当且仅当P q同时为真或同时为假 2 真值表 3 等价式是自然语言中 p是q的充分且必要条件 p当且仅当q 的抽象4 p q实际上p和q是互为充分必要条件 它的逻辑结构与 p q q p 是相同的 例 将下列命题符号化 并求命题的真值 1 蓝色和黄色可以调配成绿色 2 蓝色和黄色都是常用的颜色 3 王小红虽然没上过大学 但她自学成才 4 2是偶素数 5 李冰选学英语或法语 6 李和平是山西人或陕西人 7 只要4是偶数 则5也是偶数 8 除非4是奇数 否则5不是奇数 9 经一事 长一智 并且不经一事 不长一智 10 2 3 5当且仅当19不是素数 例如 2 3 5的充要条件是美国位于亚洲真值为0若两圆o1 o2的面积相等 则它们的半径相等 反之亦然 真值为1 6 五个联结词将原子命题连接为复合命题 可以将联结词看成对原子命题的运算符1 通过联结词得到的复合命题的真值仅与原子命题的真值有关 与其内容 含义均无关 2 作为运算律来说 均满足交换律和结合律 而 不满足交换律和结合律3 作为运算来说 五个连接词的运算优先级为 括号 4 在开关电路和数字电路 门电路 中 连接词也有其现实意义 串联电路 合取与门 合取并联电路 析取或门 析取反向器 非非门 非 例 令p 北京比天津人口多 q 2 2 4 r 乌鸦是白色的 p q r的真值分别为1 1 0求下列复合命题的真值 1 p q p q r001 2 qVr p r 111 3 pVr p r 010 1 2命题公式及其赋值1 合式公式定义 1 单个的命题变元 是一个合式公式 2 如果A是一个合式公式 则 A也是一个合式公式 3 如果A和B是合式公式 则 A B A B A B 和 A B 都是合式公式 4 经过有限次使用规则 l 2 和 3 从而得到的由命题变元 联结词和圆括号所组成的字符串 是合式公式 注 1 该定义是通过递归得到的 合式公式也简称为命题公式或公式2 定义中用到字母A B等 被称为元语言符号 代表一个公式或子公式 是公式的抽象 可扩展定义 3 而由原子命题所表示的式子称为对象语言符号如 p q r p q 4 公式最外层的括号可以去掉公式中所出现的联结词的运算优先级为 括号 括号可以嵌套 2 公式的赋值定义 设p1 p2 pn是公式A p1 p2 pn 中出现的所有命题变元 分别给定 p1 p2 pn 指定具体的一个真值 称这组真值为给公式A p1 p2 pn 的赋值 或解释 公式A p1 p2 pn 在此组解释下就具有确定的真值 例 公式A p q r qVr p r 给定 1 0 1 为该公式的一组赋值 相当于自变量的值 公式在此组赋值下具有相应的真值A 1 0 1 的真值为01 公式A p1 p2 pn 的所有赋值组数与公式所含变元有关 共有2n组 2 若公式AA p1 p2 pn 在此组解释下的真值为真 1 则称此组赋值为成真赋值 3 若公式AA p1 p2 pn 在此组解释下的真值为假 0 则称此组赋值为成假赋值 如对于公式A p q q p 当均为0时 A的真值为1 故 0 0 为公式A的成真赋值当p为0且q为1时 A的真值为0 故 0 1 为公式A的成假赋值该公式含有二个变元 该公式共有22 4组赋值 1 0 为公式A的成假赋值 1 1 为公式A的成真赋值 3 公式的真值表将公式的所有赋值及其相应公式的真值用表格形式给出确定公式 Q P Q 的真值表 公式的所有赋值均为成真赋值再看公式 Q与 Q P Q 的真值表 公式 p p q q 的真值表pq p qp p q q p p q q 001100101100011001001100001该公式的所有赋值均为成真赋值公式 p q q r的真值表 pqrp q p q p q q p q q r00010000011000010100001110001000100101010011010001111000所有赋值均为成假赋值 3 命题公式的分类 根据公式在赋值下的真值情况进行分类 1 若命题公式在它的各种赋值下取值均为真 则称命题公式是重言式或永真式 2 若命题公式在它的各种赋值下取值均为假 则称命题公式是矛盾式或永假式 3 若命题公式不是矛盾式 则称命题公式是可满足式 或公式至少有一组成真赋值 例 判断公式的类型 现在只能用真值表方法 p q qp p q r p q q p q q p 对于形似于条件命题的公式即A B如 Q Q P可利用条件联结词的性质来给予证明分析1 若要得出 当设A为真 B为假的情况不会出现 那么A B为永真式 可证明 设前件为真分析2 还可以从设B为假 推出A为真的情况不会出现 A为假 那么A B为永真式 证明 设后件为假 4 不同真值表的公式1 当命题变元确定后 通过连接词及其公式构成的定义可以形成成无数个命题公式 如 若变元仅有两个p q那么关于这两个变元的公式的赋值仅有4组 则任何关于这两个变元的公式的所有真值表只能是一组4位二进制数 而4位二进制数的不同状态共有16 24 所以关于2个变元的不同真值表的公式仅有16种 以此推断 2 当命题变元确定后 由于其公式的赋值组数是确定的 共2n组 公式在一组赋值下是一个真值 一位二进制 在2n组赋值下对应为2n位二进制 不同n个变元的不同真值表的公式仅有 2 2n 种例 2个变元的16种不同真值表 基本要求1 分清简单命题 即原子命题 与复合命题 2 深刻理解五种常用联结词司 的涵义 并能准确地应用它们3 将复合命题符号化