[数学]北大离散数学chap1.ppt

第一章命题逻辑 第二节 命题公式及分类 第三节 等值演算 第四节 联结词的全功能集 第五节 对偶与范式 第六节 推理规则 第一章 小结与例题 (3) 对应的十进制数为0，1，3。 例5、用真值表求 的主合取范式。 解：(2) 的成假赋值有000，001，011， 所以 的主合取范式： 思考：命题公式 间有什么联系，能否通过其中一个求 另一个？(观察例3，例5) 的主合取范式，主析取范式 由例3、例5知： 2.5、已知命题公式的主析取范式(主合取范式)， 求主合取范式(主析取范式)。 (2) 写出与(1)中极小项角码相同的极大项， 由 的主合取范式步骤： 的主析取范式求 (1) 写出 的主析取范式未出现的极小项， (3) 由以上极大项合取即成 的主合取范式。 例6、(1) 已知命题公式 的主合取范式。( 主析取范式为： 求 含3个命题变项) 解： 的主合取范式为： 例6、(2) 已知命题公式 主合取范式为： 的主析取范式。( 求 含2个命题变项) 解： 的主析取范式为： 3、主范式的用途。 (1) 判断两命题公式是否等值。 (2) 判断命题公式的类型。 重言式 主析取范式含全部的极小项 主合取范式不含任何极大项 (主合取范式记为1) 矛盾式 主析取范式不含任何极小项 (主析取范式记为0) 主合取范式含全部的极大项 3、主范式的用途。 (2) 判断命题公式的类型。 可满足式 主析取范式至少含一个极小项 主合取范式至少缺一个极大项 (3) 求成真(假)赋值。 (4) 求真值表。 例7、已知含3个命题变项的公式： 和 (1) 判断 的类型。 解： 为矛盾式。 为可满足式， (2) 判断 是否等值。 解： 不等值。 的成假赋值有010，011，100，101。 例7、已知含3个命题变项的公式： 和 (3) 求 的成真赋值和成假赋值。 的成真赋值有000，001，110，111。 解： (4) 求 的真值表。 解：真值表 内容： 重点： (1) 理解推理的概念； (2) 掌握8条推理定律； (3) 掌握推理规则； (4) 掌握构造证明法。 了解： 附加前提证明法和归谬法。 推理规则，构造证明法。 推理的概念，推理定律， 一、推理的形式结构。 2、判断推理的方法。 等值演算法，真值表法，主析取范式法。 1、定义： 记作 则称前提 若 为重言式， 推结论 的推理正确， 为 的逻辑结论或有效结论。 。 例1、判断下面各推理是否正确。 (1) 如果天气凉快，小王就不去游泳， 天气凉快，所以小王没去游泳。 结论： 推理形式结构为： 判断此蕴涵式是否为重言式。 前提： ， 解：设 小王去游泳。 ： ：天气凉快， [方法一] 用等值式法。 所以推理正确。 [方法二] 用真值表法。 其真值表中最后一列全为1， 所以推理正确。 [方法三] 用主析取范式法。 主析取范式含全部最小项，所以推理正确。 (2) 如果我上街，我一定去新华书店， 我没上街，所以我没去新华书店。 前提： 结论： 推理的形式结构为： 解：设 ：我去新华书店， ：我上街， [方法一] 其主析取范式中缺极小项 所以推理不正确。 ， [方法二] 蕴涵等值式 吸收律 [方法三] 所以推理不正确。 列出真值表，其最后一列不全为1, 由于01是 推理不正确。 的成假赋值，并非重言式， 二、构造证明法。 1、推理定律有以下8条： (1) 附加 (2) 化简 (3) 假言推理 (4) 拒取式 (5) 析取三段论 二、构造证明法。 1、推理定律有以下8条： (6) 假言三段论 (7) 等价三段论 (8) 构造性二难 2、推理规则。 (1) 前提引入规则 (3) 置换规则 3、构造证明法。 依照推理规则，应用推理规律。 (2) 结论引入规则 例2、构造下列推理的证明。 (1) 前提： 结论： 证明： 前提引入 ② 前提引入 前提引入 ③ ④ ①②③构造性二难 ① 例2、构造下列推理的证明。 (2) 前提： 结论： 证明： ① 前提引入 前提引入 ② ③ ①②拒取式 ④ 前提引入 ⑤ ③④假言推理 例2、构造下列推理的证明。 (2) 前提： 结论： 证明： ⑥ 前提引入 ⑦ ⑤⑥拒取式 ⑧ 前提引入 ⑨ ⑦⑧析取三段论 例3、写出对应下面推理的证明。 (1) 如果今天是星期一，则要进行英语或离散数学考试。 如果英语老师有会，则不考英语， 今天是星期一，英语老师有会， 所以进行离散数学考试。 解： 前提： 结论： ：今天是星期一， ：进行离散数学考试， ：进行英语考