离散数学discrete2C..doc

7. 命题逻辑的推理理论 命题逻辑的推理理论就是利用命题逻辑公式研究什么是有效的推理。 推理是从前提出发推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。 如果前提是真命题，从前提出发推出结论的推理过程严格遵守推理规则，则推出的结论也是真命题。 在命题逻辑中，不注重前提和结论的真假性，而关心从前提推出结论的推理过程的正确性，即主要研究推理的规则。 【定义1.35】称蕴涵式(A1(A2(…(Ak)(B为推理的形式结构，A1, A2, …, Ak为推理的前提，B为推理的结论。若(A1(A2(…(Ak)(B为永真式，则称从前提A1, A2, …, Ak推出结论B的推理正确（或说有效），B是A1, A2, …, Ak的逻辑结论或称有效结论，否则称推理不正确。若从前提A1, A2, …, Ak推出结论B的推理正确，则记为(A1(A2(…(Ak)(B。 直观地看，(A1(A2(…(Ak)(B就是说，如果A1, A2, …, Ak都正确，则B也正确。 判断推理是否正确就是验证相应的蕴涵式是否是永真式，其方法包括： ·使用真值表 ·等值演算法 ·求主析取范式法 【例子1.12】教材p39例1.23，要点：将各种命题符号化，然后使用上述各种方法判断相应的蕴涵式是否是永真式。 【定义1.36】证明是一个描述推理过程的命题公式序列A1, A2, …, An，其中的每个命题公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论，满足这样条件的公式序列A1, A2, …, An称为结论An的证明。在证明中常用的推理规则有3条： [1]. 前提引入规则：在证明的任何步骤都可以引入已知的前提； [2]. 结论引入规则：在证明的任何步骤都可以引入这次已经得到的结论作为后续证明的前提； [3]. 置换规则：在证明的任何步骤上，命题公式中的任何子公式都可用与之等值的公式置换，得到证明的公式序列的另一公式。 使用命题逻辑公式进行推理还有其他一些推理规则，这些规则建立在下面一些推理定律上： 【定理1.37】推理定律是命题逻辑的一些永真蕴涵式，重要的推理定律有： [1]. 附加律： A((A(B) // 或称为析取的引入 [2]. 化简律： (A(B)(A, (A(B)(B // 或称为合取的消除 [3]. 假言推理： (A(B)(A(B // 或称为分离规则 [4]. 拒取式： (A(B)((B((A [5]. 析取三段论：(A(B)((B(A [6]. 假言三段论：(A(B)((B(C)((A(C) // 或称为传递规则 [7]. 等价三段论：(A(B)((B(C)((A(C) [8]. 构造性二难：(A(B)((C(D)((A(C)((B(D) 【注解】 1. 这些推理定律都是永真式，可用判断命题公式是否是永真式的方法加以证明。 2. 这些推理定律之间不是独立的，其中一些定律可从另外一些定律推出，正如我们在命题演算系统中所讨论的，最基本的定律应该命题演算的公理及分离规则。对于上面给出的这些定律，最重要的是附加律、分离规则、传递规则、拒取式等。正如教材p44的例1.24所证明的，构造性二难规则可使用传递规则、置换规则等证明。而拒取式与析取三段论实际上等价，因为(A(B)(((A(B)，那么根据拒取式有((A(B)(B(((A，而((A(A。 3. 实际上这些推理定律中的符号A, B, C可代表任意公式，即将推理定律中某个符号的所有出现用另外一个命题公式代入，那么得到的也是永真式，这个规则可称为代入规则。注意代入规则与置换规则不同。 【定理1.38】根据定理1.37的推理定律得到，在证明中可使用以下一些推理规则： [1]. 假言推理规则（分离规则）：若有A(B和A，则可得到B。（注意证明是命题公式的序列，因此这里的意思是，如果序列中出现A(B和A，则可在该序列中添加公式B，或换句话，按照证明的意思就是，如果有前提A(B和A，则可得到结论B） [2]. 附加规则：若有A，则可得到A(B。 [3]. 化简规则：若有A(B，则可得到A，也可得到B。 [4]. 拒取式规则：若有A(B和(B，则可得到(A。 [5]. 假言三段论（传递规则）：若有A(B及B(C，则可得到A(C [6]. 析取三段论规则：若有A(B和(B，则可得到A。 [7]. 构造性二难规则：若有A(B，C(D和A(C，则可得到B(D。 [8]. 合取引入规则：若有A和B，则可得到A(B。 【注解】 1. 假言推理规则就是最常用的推理方法，例如，如果天下雨(A)，地就是湿的(B)，现在天下雨，所以地是湿的。 2. 附加规则、化简规则及合取引入规则的直观含义很简单。 3. 拒取式规则