[翻译转载]离散数学教程--命题逻辑,谓词逻辑和推理规则Discrete Mathematics命题逻辑数理逻辑的规则指定了如何判断⼀个数学语句的正确性. 古希腊哲学家,亚⾥⼠多德是数理逻辑的先驱. 数理逻辑为数学和计算机科学的许多领域提供了理论的基础. 它在计算机科学领域中也有着许多实际的应⽤,如计算器,⼈⼯智能,编程语⾔中数据结构的定义等等.命题逻辑关注与陈述中的真值,"true"和"false"(下⽂作真,假). 它的⽬的是分析这些独⽴的陈述或复合的语句.定理命题逻辑是⼀系列陈述语句,取值只能为真/假,叫做命题的真值. 它包含了命题变量和逻辑连词. 我们将命题变量记做⼤写字母(A,B, 等.), 连结词连接这些命题变量下⾯是⼀些命题的例⼦:"男⼈是⼈", 真值为真"12+9 = 3-2", 真值为假下⾯的例⼦不是⼀个命题:"A ⼩于 2", 除⾮我们给出A的特定值,否则⽆法确定语句的真值逻辑连词命题逻辑中通常有5种连词OR(∨) 或AND(∧) 与NOT(¬) 否if-then(→) 蕴含/如果那么if and only if(⇔) 等价/当且仅当或(∨) - 或运算作⽤在两个命题A,B上(写作A∨B) 当A,B中的⾄少⼀个为真时为真.真值表如下-A B A∨B真真真假真真真假真假假假与(∧) - 与运算作⽤在两个命题A,B上(写作A∧B) 当A,B同为真时为真.真值表如下-A B A∧B真真真假真假真假假假假假否(¬) - 否运算作⽤在命题A上(写作 ¬A) 当A为真时为假,当A为假时为真.真值表如下-A¬A真假假真蕴含(→) - 命题"如果A, 那么B" 表⽰为蕴含式A→B, 当A为真B为假时为假,其他情况都为真.A B A→B真真真真假假假真真假假真等价(⇔) - A⇔B, 是⼀个双向的逻辑连词, 当A,B取值相同时为真, 如A,B同时位假时为真A B A⇔B真真真真假假假真假假假真重⾔式/永真式重⾔式是⼀种⽆论命题变量取值如何真值都为真的公式.例: 证明 [(A←B)∧A]←B是重⾔式真值表如下A B A←B(A←B)∧A[(A←B)∧A]←B真真真真真真假假假真假真真假真假假真假真因为[(A←B)∧A]←B的所有取值都为真,所以为重⾔式⽭盾式/永假式⽭盾式是⼀种⽆论命题变量取值如何真值都为假的公式.例: 证明 (A∨B)∧[(¬A)∧(¬B)] 是⽭盾式真值表如下A B A∨B¬A¬B(¬A)∧(¬B)(A∨B)∧[(¬A)∧(¬B)]真真真假假假假真假真假真假假假真真真假假假假假假真真真假因为(A∨B)∧[(¬A)∧(¬B)] 的所有取值都为假,所以为⽭盾式偶然式(Contingency)偶然式是⼀种在逻辑变量的所有取值中,⼀些真值为真⼀些真值为假的公式.例: 证明 (A∨B)∧(¬A) 是⽭盾式真值表如下A B A∨B¬A(A∨B)∧(¬A)真真真假假真假真假假假真真真真假假假真假因为(A∨B)∧(¬A) 的取值既包含真也包含假,所以为偶然式逻辑等价当下⾯两种情况成⽴时, 陈述X和Y被认为是等价的两个陈述的真值表有相同的真值双条件陈述X⇔Y是永真式例: 证 ¬(A∨B)and[(¬A)∧(¬B)] 是等价的⽤第⼀种⽅法测试(⽐较真值表)A B A∨B¬(A∨B)¬A¬B[(¬A)∧(¬B)]真真真假假假假真假真假假真假假真真假真假假假假假真假假真¬(A∨B)and[(¬A)∧(¬B)]的真值表相同,因此陈述是等价的⽤第⼆种⽅法测试(双向条件)A B¬(A∨B)[(¬A)∧(¬B)]¬(A∨B)⇔[(¬A)∧(¬B)]真真假假真真假假假真假真假假真假假真真真¬(A∨B)⇔[(¬A)∧(¬B)]是永真式,因此陈述是等价的否命题,逆命题和逆否命题蕴含→也被叫做条件陈述, 它包含两个部分假设,p结论,q就像之前说过的, 它被记做p→q条件陈述的例⼦ - "如果你做了作业,你就不会被惩罚",中"你做作业"是假设p,"你不会被惩罚"是结论q否命题 - 条件陈述的否命题是将假设和结论中的陈述同时取反, 如果陈述是如果p,那么q, 否命题就是 "如果⾮p,那么⾮q". 因此p→q的否命题是 ¬p→¬q例: "如果你做了作业,你就不会被惩罚"的否命题是"如果你不做作业,你就会被惩罚"逆命题 - 条件陈述的逆命题是将原陈述的假设和结论交换, 如果陈述是如果p,那么q, 逆命题就是 "如果q,那么p". 因此p→q的逆命题是q→p例: "如果你做了作业,你就不会被惩罚"的逆命题是"如果你没有被惩罚,你做了你的作业"逆否命题 - 条件陈述的逆否命题是将原陈述的假设和结论取⾮后交换, 如果陈述是如果p,那么q, 逆命题就是 "如果⾮q,那么⾮p". 因此p→q的逆命题是 ¬q→¬p例: "如果你做了作业,你就不会被惩罚"的逆否命题是"如果你被惩罚了,那么你没有做你的作业"对偶原则对偶原则是当陈述为真时,将其中的交集换成补集,补集换成交集,全集换成空集,空集换成全集,得到它的对偶陈述, 那么它的对偶陈述也为真. 如果⼀个陈述的对偶陈述为本⾝,那么他就是对称陈述.例: (A∩B)∪C的对偶是 (A∪B)∩C逻辑范式我们可将所有命题转换为两种标准形式合取范式析取范式合取范式如果复合陈述中所有的或操作(包括⾮运算)都由与来连接,则被称为合取范式. 在集合中,复合陈述中的并集要通过交集来连接.例:(A∨B)∧(A∨C)∧(B∨C∨D)(P∪Q)∩(Q∪R)析取范式如果复合陈述中所有的与操作(包括⾮运算)都由或来连接,则被称为析取范式. 在集合中,复合陈述中的交集要通过并集来连接.例:(A∧B)∨(A∧C)∨(B∧C∧D)(P∩Q)∪(Q∩R)谓词逻辑谓词逻辑处理谓词, 谓词是包含变量的命题.定义谓词是⼀个或多个定义在特定域中的变量表达式. ⼀个带有变量的命题可以通过为变量赋值或量化变量来变成命题.下⾯是⼀些谓词的例⼦设E(x,y), 表⽰"x=y"设X(a,b,c), 表⽰"a+b+c=0"设M(x,y), 表⽰"x嫁给了y"合式公式命题下⾯的条件就被叫做合式公式(wwf)所有的命题变量和命题常量都是合式公式如果x是⼀个变量Y是⼀个合式公式, ∀xY和∃xY也是合式公式真和假是合式公式所有原⼦公式是合式公式由连接词连接的合式公式也是合式公式量词谓词中的变量由量词来量化, 谓词逻辑中的量词有两种-全称量词和存在量词全称量词全称量词描述了在特定域中不论特定变量取何值陈述都为真, 符号表⽰为∀∀xP(x) 读作对于x的任意取值,P(x)都为真例: "男⼈是⼈"可以被写成谓词形式∀xP(x), 其中P(x)是谓词表⽰x是⼈, 并且论述的全集是男⼈集合.存在量词存在量词描述了在特定域中特定变量有取值使得陈述都真, 符号表⽰为∃∃xP(x) 读作对于x的某些取值,P(x)都为真例: "有些⼈不诚实" 可以被写成谓词形式∃xP(x), 其中P(x)是谓词表⽰x不诚实, 并且论述的全集是某些⼈的集合.嵌套量词如果在⼀个量词的域内使⽤了另⼀个量词, 则叫做嵌套量词例:∀a∃bP(x,y)其中P(a,b)表⽰a+b=0∀a∀b∀cP(a,b,c)其中P(a,b,c)表⽰a+(b+c)=(a+b)+c注意: ∀a∃bP(x,y)≠∃a∀bP(x,y)推理规则为了从已知真值的陈述推论出新的陈述的真值需要使⽤推理规则推理逻辑做什么?数理逻辑通常⽤来做逻辑证明, 证明是决定数学陈述的真值的有效推论推论是⼀系列的陈述, 最后⼀个陈述是前⾯所有陈述语句的结论,前⾯的陈述叫做前提或假设. 将符号∴(因此)放在结论前. ⼀个有效的推论是从前⾯所有前提的真值中正确推理出的. 推理规则提供了从已知陈述构建出有效推论的模板和⼤纲推理规则表推理规则名字推理规则名字\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}析取引⼊\begin{matrix} P \lor Q \\ \lnot P \\ \hline \therefore Q \end{matrix}析取消去/析取三段论\begin{matrix} P \\ Q \\ \hline \therefore P \land Q\end{matrix}合取引⼊\begin{matrix} P \rightarrow Q \\ Q\rightarrow R \\ \hline \therefore P\rightarrow R\end{matrix}假⾔三段论\begin{matrix} P \land Q \\ \hline \therefore P \end{matrix}合取简化\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ P \lor R \\\hline \therefore Q \lor S \end{matrix}⼆难论证复杂构成式/构造性⼆难\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}分离论证\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor\lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}⼆难论证复杂破坏式/破坏性⼆难\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}逆分离论证析取引⼊将P作为前提,我们可以析取引⼊P \lor Q\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}例: 设命题P"他学习很努⼒"为真.因此 - "要么他学习很努⼒要么他是⼀个坏学⽣". 其中Q是命题"他是⼀个坏学⽣"合取引⼊如果P和Q作为前提, 我们可以合取引⼊P \land Q\begin{matrix} P \\ Q \\ \hline \therefore P \land Q\end{matrix}例: 设P-"他学习很努⼒", Q-"他是班级⾥最好的⼈"因此 - "他学习很努⼒,也是班级中最好的⼈"合取简化让P \land Q 作为前提, 可以合取简化出P\begin{matrix} P \land Q \\ \hline \therefore P \end{matrix}例: "他学习很努⼒,也是班级中最好的⼈", P \land Q因此 - "他学习很努⼒"分离论证如有P和P \rightarrow Q两个前提, 我们可以分离论证出Q\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}例: "如果你有密码,你就可以登录qq", P\rightarrow Q"你有密码", P因此 - "你可以登录qq"逆分离论证如有P\rightarrow Q 和 \lnot Q两个前提, 我们可以逆分离论证出\lnot P\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}例: "如果你有密码,你就可以登录qq",P \rightarrow Q"你没法登录进QQ", \lnot Q因此 - "你没有密码"析取消去/析取三段论如有\lnot P 和 P \lor Q两个前提, 我们可以析取消去出Q\begin{matrix} P \lor Q \\ \lnot P \\ \hline \therefore Q \end{matrix}例: "冰淇淋不是草莓味的", \lnot P"冰淇淋要么是草莓味要么是巧克⼒味" P \lor Q因此 - "冰淇淋是巧克⼒味的"假⾔三段论如有P \rightarrow Q 和 Q \rightarrow R两个前提, 根据假⾔三段论可得P \rightarrow R\begin{matrix} P \rightarrow Q \\ Q\rightarrow R \\ \hline \therefore P \rightarrow R\end{matrix}例: "如果下⾬我就不去学校了", P \rightarrow Q"如果我不去学校我就不⽤做作业" Q \rightarrow R因此 - "如果下⾬我就不⽤做作业了"构造性⼆难如有(P \rightarrow Q) \land (R \rightarrow S) 和 P \lor R两个前提, 根据构造性⼆难可得Q \lor S\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}例: "如果下⾬我就休息⼀下", P \rightarrow Q"如果外⾯很热我就洗个澡" R \rightarrow S"外⾯要么下⾬要么很热" P \lor R因此 - "我要么休息⼀下要么洗个澡"破坏性⼆难如有(P \rightarrow Q) \land (R \rightarrow S) 和 \lnot Q \lor \lnot S两个前提, 根据构造性⼆难可得\lnot P \lor \lnot R\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}例: "如果下⾬我就休息⼀下", P \rightarrow Q"如果外⾯很热我就洗个澡" R \rightarrow S"要么我不会休息,要么我不去洗澡" \lnot Q \lor \lnot S因此 - "外⾯要么没有下⾬,要么不是很热"Loading [MathJax]/jax/element/mml/optable/MathOperators.js。
![[翻译转载]离散数学教程--命题逻辑,谓词逻辑和推理规则](https://img.taocdn.com/s1/m/078d5a0d58eef8c75fbfc77da26925c52dc59151.png)
