《[工学]03-数理逻辑》由会员分享，可在线阅读，更多相关《[工学]03-数理逻辑（41页珍藏版）》请在金锄头文库上搜索。
1、 数理逻辑数理逻辑数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。数理逻辑一、命题概念 命题是能分辨真假的陈述句。两个关键要素：(1) 命题必须是陈述句；(2) 命题所陈述的事情必须有确定的真假意义，要么为真，要么为假，二者恰居其一。 一个命题是真或假的情形，称为命题的真值。真用1或T表示，假用0或F表示。数理逻辑例 分析下面自然语句那些是命题(1) 你好吗？ (2)
2、 多好的天气呀！ (3) 我明年就是大学三年级的学生。 (4) 外星上一定有生命。 (5) x 1。 (6) 我正在说的是谎话。 数理逻辑若一个命题的真值是真，则称其为真命题，若一个命题的真值是假，则称其为假命题。命题符号化。 一般地用大写字母来表示命题。例如用P, Q, R等来表示命题，P：武松喝酒 R: x喝酒Q: 老虎吃人数理逻辑二、命题联结词 设 P 为一个命题，则定义“ P ”为一个命题 ，其真值为：当P为真时，P为假；当P为假时 ，P为真。并称 P 为P 的否定式，读作“非P ” ，其中“ ”称为否定联结词。数理逻辑由于 只是联系一个命题，因此又称为一个一元 联结词。 “P ”的真
3、值可列表如下：该表又称为P 的真值表。在自然语言中，对 应于 的联结词为否定词“非”，“不”等。数理逻辑设P, Q为命题，则定义“PQ”为一个命题， 其真值为：当P, Q都为真时，PQ为真；其余 情形，PQ皆为假。并称PQ为P与Q的合取式 ，读作“P合取Q”，或“P且Q”，其中“”称作合取联结词。联系两个命题，故称为一个二元联结词。数理逻辑也称为一个布尔积。PQ 的真值表如下:在自然语言中，对应于“并且”，“既又 ”，“和”，“与”等联结词。数理逻辑例1 设P：李明大于20岁，则P：李明不大于20岁。例2 设P：李明会唱歌，Q：李明会跳舞， 则 PQ ：李明既会唱歌又会跳舞。数理逻辑设P, Q
4、为命题，则定义“PQ”为一个 命题，其真值为：当P, Q都为假时， PQ 为假；其余情形， PQ皆为真。称PQ 为P与Q的析取式，读作“P析取Q”，或“P 或Q”，其中“”称作析取联结词。为一个对称的二元联结词。数理逻辑叫做布尔和。PQ的真值表如表：在自然语言中， 对应于联结词是“或者”。例 设 P：李明是大学生，Q：李明是歌手，则PQ：李明是大学生或者是歌手。在自然语言中，“或者”联结的两个命 题可以都为真, 并不意味着所联结的两个 命题互相对立，叫可兼或， 对应的正是 这个可兼或。数理逻辑设P, Q为命题，则定义“PQ”为一个命题，其真值为：当P真Q假时，PQ为假；其余情形，PQ为真。称P
5、Q为P与Q的条件式，读作“P条件Q”，或“若P则Q”，并称P和Q分别为P Q的前件和后件，“”称为条件联结词。为一个非对称的二元联结词。数理逻辑例 如果我中五百万大奖，我就请客。试问在什么情 况下，我没有履行承诺。解 存在以下四种情况： (1)我没有中奖，我没有请客. (2)我没有中奖，我有请客 (3)我中奖，我没有请客. (4)我中奖，我有请客.数理逻辑真真假真P Q 的真值表如表：在自然语言中，对应于联结词“如果，那么 ”, “若，则”, “只要，就”等。数理逻辑命题演算构造证明法1、推理定律有以下8条： (1) 附加(2) 化简(3) 假言推理(4) 拒取式 (5) 析取三段论 构造证明
6、法 1、推理定律有以下8条： (6) 假言三段论 (7) 等价三段论 (8) 构造性二难 2、推理规则。 (1) 前提引入规则 (3) 置换规则 3、构造证明法。 依照推理规则，应用推理规律。 (2) 结论引入规则 例2、构造下列推理的证明。 (2) 前提： 结论： 证明： 前提引入 前提引入 拒取式 前提引入 假言推理 例2、构造下列推理的证明。 (2) 前提： 结论： 证明： 前提引入 拒取式 前提引入 析取三段论 例3、写出对应下面推理的证明。 (1) 如果今天是星期一，则要进行英语或数学考试。 如果英语老师有会，则不考英语， 今天是星期一，英语老师有会，所以进行数学考试。解：前提： 结
7、论： ：今天是星期一，：进行数学考试，：进行英语考试，：英语老师有会。证明： 前提引入 前提引入 假言推理 前提引入 前提引入 假言推理 析取三段论 前提： 结论： (2) 如果6是偶数，则2不能整除7； 或者5不是素数，或者2整除7；5是素数。 因此，6是奇数。 解：前提： 结论： ：6是偶数，：5是素数。：2整除7，证明： 前提引入 置换规则 前提引入 假言推理 前提引入 拒取式 前提： 结论： (3) 如果乙不参加篮球赛，那么甲就不参加； 如果乙参加篮球赛，那么甲和丙就参加。 因此，如果甲参加篮球赛，那么丙就参加。 解： 前提： 结论： ：乙参加篮球赛，：丙参加篮球赛。 ：甲参加篮球赛，
8、(3) 如果乙不参加篮球赛，那么甲就不参加； 如果乙参加篮球赛，那么甲和丙就参加。 因此，如果甲参加篮球赛，那么丙就参加。 解： 前提： 结论： ：乙参加篮球赛，：丙参加篮球赛。 ：甲参加篮球赛，证明： 前提引入 置换规则 前提引入 假言三段论 前提： 结论： 一、命题与联结词。 1、基本概念。 2、应用。 (1) 选择适当的联结词将命题符号化。 (2) 判断命题(简单或复合)的真假。 命题与真值；简单命题和复合命题； 命题常项和变项；五个联结词真值表。 ，小结与例题(3)解：我进城当且仅当我有空。(4)解：天不下雪且我没空。例2、 设：天正在下雪； ：我将进城；：我有空。用自然语言写出下列命
9、题。 (1)解：设 p、q 的真值为 0 ，r 的真值为 1， 试求下列命题的真值例4、简化下列命题公式。(4)解：例8、判断下列推理是否正确。 解：可用多种方法(如真值表法，等值演算法，主范式法)验证，并非重言式， 故推理不正确。 (1) 前提：结论： ，例8、判断下列推理是否正确。 (2) 如果今天是星期二，则明天是星期四。 今天是星期二，所以明天是星期四。 以上推理即假言推理，所以是正确的。 解：明天是星期四，：今天是星期二，前提：结论： ，例9、写出对应下面推理的证明。有红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四；或者白队不是第一，或者红队第三；事实上，黄队
10、第二。因此，如果白队第一，那么蓝队第四。 证明：设 ：红队第三， ：黄队第二，：蓝队第四， ：白队第一。前提：结论：前提：结论：前提引入 附加前提引入析取三段论前提引入 假言推理前提：结论：假言推理前提引入假言推理由附加前提证明法知推理正确。 例10、一公安人员审查一件盗窃案，已知的事实如下： (1) 甲或乙盗窃了录音机； (2) 若甲盗窃了录音机，则作案时间不能发生在午夜前；(3) 若乙的证词正确，则午夜时屋里灯光未灭； (4) 若乙的证词不正确，则作案时间发生在午夜之前； (5) 午夜时屋里灯光灭了。 问是谁盗窃了录音机。 ：乙盗窃了录音机， ：作案时间发生在午夜前， ：乙的证词正确， ：午夜灯光未灭。 解：设：甲盗窃了录音机， 前提：，结论： 或者 前提引入 前提引入 拒取式 前提引入 假言推理 前提：， 拒取式 前提引入 析取三段论 所以是乙盗窃了录音机。 前提引入 假言推理 前提：，
