离散数学18推理理论

第3章命题逻辑的推理理论主要内容1. 推理的形式结构：①推理的前提②推理的结论③推理正确④有效结论2. 判断推理是否正确的方法：①真值表法②等值演算法③主析取范式法3. 对于正确的推理，在自然推理系统P中构造证明4. ①自然推理系统P的定义②自然推理系统P的推理规则：前提引入规则、结论引入规则、置换规则、假言推理规则、附加规则、化简规则、拒取式规则、假言三段式规则、构造性二难规则、合取引入规则。

③附加前提证明法④归谬法学习要求1. 理解并记住推理的形式结构的三种等价形式，即①{A1,A2,…,A k}├B②A1∧A2∧…∧A k→B③前提与结论分开写：前提：A1,A2,…,A k结论：B在判断推理是否正确时，用②；在P系统中构造证明时用③。

2. 熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。

3. 牢记P系统中的各条推理规则。

4. 对于给定的正确推理，要求在P系统中给出严谨的证明序列。

5. 会用附加前提证明法和归谬法。

3.1 推理的形式结构定义3.1设A1,A2,…,A k和B都是命题公式，若对于A1,A2,…,A k和B中出现的命题变项的任意一组赋值，或者A1∧A2∧…∧A k为假，或者当A1∧A2∧…∧A k为真时，B也为真，则称由前提A1,A2,…,A k推出B的推理是有效的或正确的，并称B是有效结论。

二、有效推理的等价定理定理3.1命题公式A1,A2,…,A k推B的推理正确当且仅当(A1∧A2∧…∧A k )→B为重言式。

A k为假，或者A1∧A2∧…∧A k和B同时为真，这正符合定义3.1中推理正确的定义。

由此定理知，推理形式：前提：A1,A2,…,A k结论：B是有效的当且仅当(A1∧A2∧…∧A k)→B为重言式。

(A1∧A2∧…∧A k)→B称为上述推理的形式结构。

从而推理的有效性等价于它的形式结构为永真式。

于是，推理正确{A1,A2,…,A k} B可记为A1∧A2∧…∧A k B其中同一样是一种元语言符号，用来表示蕴涵式为重言式。

第3章命题逻辑的推理理论3.1 推理的形式结构一、有效推理数理逻辑的主要任务是用数学的方法来研究数学中的推理。

所谓推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。

要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。

定义3.1设A1,A2,…,A k和B都是命题公式，若对于A1,A2,…,A k和B中出现的命题变项的任意一组赋值，或者A1∧A2∧…∧A k为假，或者当A1∧A2∧…∧A k为真时，B 也为真，则称由前提A1,A2,…,A k推出B的推理是有效的或正确的，并称B是有效结论。

关于定义3.1还需要做以下几点说明：1．由前提A1,A2,…,A k推结论B的推理是否正确与诸前提的排列次序无关。

因而前提的公式不一定是序列，而是一个有限的公式集合，若将这个集合记为Г，可将由Г推B 的推理记为Г├B。

若推理是正确的，则记为ГB，否则记为ГB。

这里，可以称Г├B和{ A1,A2,…,A k}├B 为推理的形式结构。

2．设A1,A2,…,A k，B中共出现n个命题变项，对于任何一组赋值α1,α2,…,αn(αi =0或者1，i=1,2,…,n)，前提和结论的取值情况有以下四种：(1) A1∧A2∧…∧A k为0，B为0.(2) A1∧A2∧…∧A k为0，B为1.(3) A1∧A2∧…∧A k为1，B为0.(4) A1∧A2∧…∧A k为1，B为1.由定义3.1可知，只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况。

3．由以上的讨论可知，推理正确，并不能保证结论B一定为真，这与数学中的推理是不同的。

例3.1判断下列推理是否正确：(1){p,p→q}q(2){p,q→p}q解只要写出前提的合取式与结论的真值表，看是否出现前提合取式为真，而推论为假的情况。

(1)由表3.1可知，没有出现前提合取式为真，而结论为假的情况，因而(1)中推理正确，即{p,p→q}q.(2)由表3.1可知，在赋值为10情况下，出现了前提合取式为真，而结论为假的情况，因而(2)推理不正确，即{p,q→p}q.表3.1对于本例这样简单的推理，不用写真值表也可以判断推理是否正确。

第一章命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0（3）（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔1(4)（π是无理数。

并且，如果3是无理数，则2也是无理数。

另外6能被2整除，6才能被4整除。

”17．判断下面一段论述是否为真：“π是无理数1答：p:q: 3是无理数02是无理数 1r:s: 6能被2整除1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。

[翻译转载]离散数学教程--命题逻辑,谓词逻辑和推理规则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。