第1章-命题逻辑.ppt

４.主范式的应用 利用主范式可以求解判问题或者证明等价式成立。 （1）判定问题 根据主范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式Ａ；其次按下列条件判定之： (a)若A?Ｔ，或A可化为与其等价的、含2n个小项的主析取范式，则A为永真式。 (b)若A?Ｆ，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。 (c)若A不与Ｔ或者Ｆ等价，且又不含2n个小项或者大项，则A为可满足的。 （2）证明等价式成立 由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。 1.8 命题逻辑的推理理论 在逻辑学中，把从前题（又叫公理或假设）出发，依据公认的推理规则，推导出一个结论，这一过程称为有效推理或形式证明。所得结论叫做有效结论，这里最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据。但是，如果前提全是真，则有效结论也应该真而绝非假。 在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。 提请注意，必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。 可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。 １.推理的基本概念和推理形式 推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论。 在数理逻辑中，前提H是一个或者n个命题公式H1,H2,···Hn；结论是一个命题公式C。由前提到结论的推理形式可表为H1,H2,···,Hn?C，其中符号?表示推出···。可见，推理形式是命题公式的一个有限序列，它的最后一个公式是结论，余下的为前提或假设。 定义1.8.1 如果存在H1，H2，…，Hn，C的一个指派，使得每个Hi(1≤i≤n)为真而C为假推理形式H1，H2，…，Hn?C是无效的；否则，推理是有效的，此时称C是H1，H2，…，Hn的有效结论，或称C是从前提H1，H2，…，Hn逻辑推出的结论。 定理1.8.1 推理形式H1，H2，…，Hn?C是有效的，当且仅当命题公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)?C。 判别有效结论的过程就是论证过程，一般来说，论证的方法千变万化，但基本方法有如下几种： （1）真值表法 （2）直接推理法(演绎法) （3）间接推理法 下面我们还会介绍。 ２.推理规则 在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规则，它们是： ①Ｐ规则(也称前提引入规则)：在推导过程中，前提可视需要引入使用。 ②Ｔ规则(也称结论引入规则)：在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入。 此外，在从前提推出的结论为条件式时，还需要下面规则： ③ＣＰ规则(也称条件证明引入规则)：若推出有效结论为条件式R→C时，只需将其前件R加入到前提中作为附加前提且再去推出后件C即可。 ＣＰ规则的正确性可由下面定理得到保证： 定理1.8.2 若H1，H2，…，Hn，R?C，则H1，H2，…，Hn?R→C。 证明：设H1∧H2∧…∧Hn=S，即证S ?(R→C)或S ?(?R ∨C)，故S →(?R ∨C)为永真式。 因为S →(?R ∨C) ??S ∨(?R ∨C) ?(?S ∨?R) ∨C ??(S∧R)∨C ?(S∧R)→C . 因此若将R作附加前提，如有(S∧R)?C ，即证得S ?(R→C)。■ ３.推理定律 在推理过程中，除使用推理规则后，还需要使用许多条推理定律，这些定律可由以前讲过的命题定律、蕴含式及运用定理1.8.1而得到。下面只给出了由蕴含式得出的推理定律，它们是： (1) P，Q?P (2) P，Q?Q (3) P?P∨Q (4) ?P?P→Q (5) Q?P→Q (6) ?(P→Q)?P (7) ?(P→Q)??Q (8) P，(P→Q)?Q (9) ?Q，(P→Q)??P (10) ?P，(P∨Q)?Q (11) (P→Q)，(Q→R)?P→R (12) (P?Q)，(Q?R)?P?R (13) (P→Q)，(R→S)，(P∧R)?Q∧S (14) (P→Q)，(R→S)，(P∨R)?Q∨S 特别当Q=S时，有 (P→Q)，(R→Q)，(P∧R)?Q (P→Q)，(R→Q)