第编数理逻辑.pptVIP

6.1 命题的概念与表示 真值：命题的判断结果称为真值。只有“真”和“假”两种，记为“T”和“F”，或“1”和“0”。 例： 命题常量：一个命题标识符表示确定的命题。 6. 2 命题联结词 合取∧(并且) 与自然语言不同。 析取∨(或者) 日常语言中的“或者”可分“可兼或”与“不可兼或”两种： 不可兼析取?? (排斥析取) 蕴含→(条件) 例2: “如果我得到这本小说，那么我今天就读完它”。将命题符号化，并求命题的真值。 例3: “如果雪是黑的，那么太阳从西方出”。将命题符号化，并求命题的真值。 P→Q中P称为前件，Q称为后件。 等价(双条件) 例2: “燕子飞回南方，春天来了”。将命题符号化，并求命题的真值。 复合命题：设 A1,A2,…An是命题,用五种逻辑联结词将这n个命题联结起来，得到一个新命题，称为复合命题。 练习1. 设命题P，Q的真值为1，命题R，S的真值为0，试确定下面命题的真值： (P∧Q∧R)∨?((P∨Q)∧(R∨S)); 6.3 命题公式的翻译与解释 命题公式：由命题变项、联结词、括号按一定规则组成的合式公式为命题公式。 定义 设G是公式，A1, A2,…, An 是出现在G中的所有原子, 指定 A1,A2,…..An 一组真值, 则这组真值称为G的一组赋值(解释、指派）, 记作I。 例: 求G ? P ? (Q ? ?R) 的真值表。 有时赋值 {0, 0, 0} 写成 {?P, ?Q, ?R}, {0, 0, 1} 写成 {?P, ?Q, R}, {0, 1, 0} 写成 {?P, Q, ?R}, ? ? {1, 1, 1} 写成 { P, Q, R}, 逻辑等价 例：用真值表证明公式 P→Q 和 ?P∨Q等值. 共学了六个联结词：?,∨,∧,??,→,? 并非所有联结词都是必要的，公式中有些联结词可由其它联结词代替。 常用的逻辑等价式 ⑾ ? ?A ? A (双重否定律) 以上公式的证明有两种方法：(1)真值表；(2)利用公式。 证二：A ? (A ? B) ? (A ? 1) ? (A ? B) 6.5 重言式与蕴含式 例：① G ? P? ?P?Q ? 1 重言蕴含式的三种等价定义 例1 证明 (1) (P∧Q)∨(P∧?Q) ? P (2) P→(Q→R) ? (P∧Q)→R 例2 化简 ((A→B)?(?B→?A))∧C. 例3 判别下列公式的类型:(1) Q∨?((?P∨Q)∧P). (2) (P∨?P)→((Q∧?Q)∧R). 对偶式 析取范式的对偶式称为合取范式；合取范式的对偶式称为析取范式。 定理 (范式存在定理)：对于任意公式，都存在等值于它的析取范式和合取范式。 例2：将P?(Q?R)化为析取范式和合取范式。 定义：n个命题变项P1,P2,…,Pn , 每个变项与它的否定不同时出现，但是两者必须出现一个, 且排列顺序与 P1,P2,…,Pn的顺序一致, 这样的简单合取式称为关于P1,P2,…,Pn 的一个极小项或布尔合取。 例：公式G中包含P,Q,R三个命题变项： 定义：对于含有n个命题变项的命题公式，如果有一个仅由极小项的析取构成的等值式, 则该等值式称为原命题公式的主析取范式。 例3 用真值表法求 P→Q, P∧Q, ?(P∧Q) 的主析取范式。 2. 等值演算法： 例：求公式G ? ?(R?P) ? (Q ? (P ? R)) 的主析取范式。 ? (?P?Q?R)?(?P??Q?R)?(P?Q?R) ?(P?Q??R) 主合取范式 例：公式G中包含P,Q,R三个命题变项： 定义：对于含有n个命题变项的命题公式，如果有一个仅由极大项的合取构成的等值式, 则该等值式称为原命题公式的主合取范式。 例5 用真值表法求 (R→(P∨Q))∧(P→(?Q ∧R)) 的主合取范式。 等值演算法： 主合取范式的求法与主析取范式的求法类似。 主析取范式、主合取范式和真值表之间的关系： 例: G ? ?(R?P) ? (Q ? (P ? R)), 求G的主析取范式，主合取范式和真值表。 同一赋值对应的极小项和极大项不相同。如公式G中包含P,Q二个原子。 主范式的用途： 6.7 命题逻辑的推理理论 判断推理的五种方法： 真值表法 等值演算法 主析取范式法 直接证法 间接证法 例1：C是否是前提A1和A2的有效结论。(1) A1: P→Q A2: P C: Q (2) A1: P→Q A2: ?P C: Q (3