离散数学A.ppt

1.6.2 波兰式 以波兰式表达的公式，当计算机识别处理时， 可自左向右扫描一次完成，避免了重复扫描。 同样后置表示（逆波兰式）也有类似的优点。 而且自左向右一次扫描（看起来更合理） 可识别处理一个公式，非常方便，常为计算机 的程序系统所采用。只不过这种表示的公式， 人们阅读起来不大习惯。 1.6.2 波兰式 举例：中置变前置 P∨((Q∨R)∧S) 由里向外： 由外向里： P∨((Q∨R)∧S) P∨((Q∨R)∧S) P∨(∨QR∧S) ∨P ((Q∨R)∧S) P∨∧∨QRS ∨P∧(Q∨R) S ∨P∧∨QRS ∨P∧∨QRS 第一个是波兰表达式，第二个逆波兰表达式 * 本讲提纲 命题形式化 波兰表达式 1.5 命题形式化 举例 考察 IF P THEN Q ELSE R 试将其形式化（用所学的联接词表示） A1 = (P→Q)∧(?P→R) A2 = (P∧Q)∨(?P∧R) 真值表如下 1.5 命题形式化 P Q R P→Q ?P→R A1 P∧Q ?P∧R A2 0 0 0 1 0 ? ? ? ? 0 0 1 1 1 1 ? 1 1 0 1 0 1 0 ? ? ? ? 0 1 1 1 1 1 ? 1 1 1 0 0 0 1 ? ? ? ? 1 0 1 0 1 ? ? ? ? 1 1 0 1 1 1 1 ? 1 1 1 1 1 1 1 1 ? 1 1.5 命题形式化 由上述真值表可得出 A1 = A2 记 A3 = (P∧Q∧?R)∨(?P∧R∧?Q) 但 A3≠A2 注意掌握用不同的形式表示同一命题公式的方法 善于以真值表为工具分析、验证、解决命题演算中的问题 需注意：逻辑联结词是从自然语句中提 炼出来的，它仅保留了逻辑内容； 自然语句本身并不严谨，常有二 义性（歧义），自然会出现同一自然语句的不同形式的逻辑描述。 1.5 命题形式化 这是普通的自然用语，它应是一个命题，以R表示。若形式地规定: 例1: 张三与李四是表兄弟。 P: 张三是表兄弟。 Q: 李四是表兄弟。 那么 R = P∧Q。 1.5 命题形式化-忌生搬硬套 显然，这样的形式化是错误的。 原因很简单：“张三是表兄弟”，“李四是表兄弟”都不是命题。 实际上“张三与李四是表兄弟”才是一个命题，而且是一个简单命 题。 该例说明自然语句中的“与”不一定都能用合取词来表达。 1.5 命题形式化 例2：张三或李四都能做这件事。 这句话中的“或”就并非用析取词来表示。 该命题的内容可以理解为： 张三能做这件事而且李四也能做这件事。 这样，这句话便应以P∧Q的形式表示了。 1.5 命题形式化 A: 今晚我在家里看电视。 例3: 给出三个命题 B: 今晚我去体育场看球赛。 问题是：C与A∨B表达的是否是同一命题？ C: 今晚我在家里看电视或去体育场看球赛。 1.5 命题形式化-注重内在逻辑 因为C同A、B的真值关系可由表1.5.1给出 A B C F F F F T T T F T T T F 表1.5.1 1.5 命题形式化 该表的前三行很容易理解，而第四行是说今晚我在家看电视，又去体育场看球赛。显然对同一个人来说这是不可能的， 从而这时C的真值为F。这就说明了C与A∨B逻辑上是并不相等的。即C中出现的“或”不能以“∨”来表示。 1.5 命题形式化 若以A, B分别表示一位二进制数字, 则C就表 示了A与B的和(不考虑进位)。 C = (?A∧B)∨(A∧?B) 由图1.5.1给出的C同A, B的逻辑关系, 常称为 异或 (也称不可兼或), 不难验证 以▽ 表示, 有 C =A▽B 1.5 命题形式化 1.5 命题形式化 异或（不可兼或）联结词 　　异或（又称不可兼或）词是二元命题联结词。 两个命题P和Q的异或构成一个新的命题，记作P▽Q 。 当且仅当P与Q的真值不相同时， P▽Q为T，否则P▽Q的真值为F。 异或真值表 P Q P▽Q F F F F T T T F T T T F 例4: 今天我上班, 除非今天我病了。 所以可描述成?P?Q。 P：表示今天我生病 Q：表示今天我上班 例4是个因果关系, 意思是 如果今天我不生病, 那么我上班。 1.5 命题形式化 举例：将“除非他通知我，否则我不参加会 议”表为复合命题的