1、 2）归纳推理 凡前提和结论不存在必然联系的推理 归纳推理。 为了严格的进行正确的推理过程我们给出如下定义： 定义：设1，2n，都是命题形式，称推理1n 推出是有效的，如果对1，2n，中出现的 命题变元的任一指派，若1，2n都真，则亦 真，称为有效的。 否则称为无效的（不合理的）。 记为：1，2，n 其中这个表达式称为矢列 Note：通过证明规则应用于前提而得到更多的公式，再将规 则用于这些公式，最终得到结论。 *16 2.2.1自然演绎规则 在证明矢列时每一步使用正确的规则是十分重 要的，也就是说给出正确的前提按照正确使用规则 来推出有效的结论。 否则就会出现不合理的结论。 例如 p：金是金
2、属 q：银是金属 p，qpq 若推出这样结论是不合理的 ，它的意思是“金是金属且银不是金属” 下面讲证明规则共15个 *17 合取规则（i） 定义：这个规则在已知分别得到结论和的 前提下，推导出结论 我们将这个规则记为： 前提 i 合取引入 结论 其中：横线上面是该规则的两个前提，横 线下面表示结论，i读作合取引入 Note：上式的结论不一定是最终结论 ，为了得 到最终结论，有可能用到更多的结论。 Note：逻辑联结词，一个或多个引用它的规 则，同理也有一个或多个消去它的规则。 *18 合取消去规则（e1，e2） 已证明 e1 e2 合取消去 结论 其中e1表示：如果有 的证明，通过该规 则可
3、以得到一个证明。 e2表示：如果有 的证明，通过该规则 可以得到一个证明。 Note：e1中的必须匹配前提的第一合取项 e2中的必须匹配前提的第一合取项 *19 例：用规则证明pq，r qr是有效的。 解题思路：开始写下前提留一些空行，（构 造证明的任务应用一系列适当证明规则填充 前提与结论间的空行中）写出结论 pq 前提 r 前提 空行 qr 结论 *20 为了证明及阅读方便，将每行都标有行号，并写出证明理 由。 1 pq 前提 理由 说明 2 r 前提 3 q e21 e2利用1得出3把q看作 4 qr i3.2 i 利用3与2根据合取引入得 到4 Note：第四行引用时注意合取项的顺序i
4、3，2是对的， 但i2，3就不对。 上述的证明过程是引用了规则ei与i得到证明结 论。 Note：上述规则不仅可以用在原子命题（语句），也可以 用在复合语句中。 *21 例：（pq）r根据 e1 看作（pq）推 出pq 而上例中在计算机实现中就必须使用指针，若逐字逐 句证明实际上是树状结构。 （pq）e2 e2 q r i i qr 结论 *22 双重否定规则（否定之否定） 我们知道=在这里我们称之为双重否 定。同类合取引入与合取消去，我们给出双重 引入规则。 e 双重消去规则 i 双重引入规则 *23 例：证明矢列p，（qr） pr是有效的。 1 p 前提 理由 说明 2 （qr）前提 3
5、p i1 i 利用第一行使 用双重否定规则，得到第三行 4 qr e2 e 利用第二行使用双重 消去规则，得到第四行 5 r e24 e2 利用第四行使用双重消 去规则，得到第五行 6 pr i3，5 利用第三行与第五行使用合 取引用规则，得到第六行 Note：上述证明过程分别4次引用规则而合理的推出结论，其中2次 用了引规则一次双重取消和一次双重引用。 *24 又例：证明矢列（pq）r，stqs是有效的。 1 pq）r 前提 理由 说明 2 st 前提 3 pq e11 利用1行使用e1 e1 合取消去规则得3行， 其中（pq ）= 4 q e23 利用3行使用e2 合 e2 取消去规则得4
6、行， 其中q = 5 s e22 利用2行使用规则e1 e1 得到5行= s 6 qs i 4，5 利用4，5行使用合取 i 引入规则得第6行 同上例类同4次使用规则，最后将结论推出。 *25 蕴涵消去规则（也称分离规则） 定义：这个规则表示：已知及蕴涵，我们可 以正确的得到。 此规则表示为： 前提 e 蕴涵消去 结论 例：如果下过雨那么街道是湿的。 p：下过雨 q：街道是湿的 pq：如果下过雨，那么街道是湿的 Note：如果我们知道下雨，而且知道是湿的两个前 提结合起来看得出结论“街道确实是湿的，可见蕴涵消去 规则的合理性。（但不具有一般性只是应用常识） *26 例：一个编程的例子 p：程序
7、的输入值是一个整数 q：程序的输出值是一个布尔值 pq：如果程序输入值是一个整数，那么输出一个布尔值。 Note：如果程序满足pq但不满足p（如输入一个姓名）那么不 能推出q。 总之这个例子说明一定要求有效的，并注意其前件。 例： e蕴涵消去规则不仅可用原子命题也可以用在复合命题中。 证明：pq ，pqrp rp 1 pq 前提 理由 说明 2 pqrp前提 将2行与1行利用 e e 规则得到3这里= pq = rp 3 rp e2，1 这里一次使用e规则完成。 *27 又例：不计次数地使用任意规则 已知p ，pq和p（qr）我们可以推出r： 1 p（qr） 前提 理由 说明 2 pq 前提
8、3 p 前提 4 qr e1，3 p p（qr） 利用1行3行得4行， qr 其中= p，= qr 5 q e2，3 p pq 利用2行3行得5行， q 其中= p，= q 6 r e4，5 p p r 利用4行5行得6行， r 其中=q ，= r e *28 Note：这就是不计次数的使用任意规则，当然这里 e 规则用前提及证过的中间结论而推出最终结论。 Note：这个规则是充分不必要，（不是充要）的，所以 说我们有反证规则。 例如：反证：如路是干的，刚下过雨是不对的。 证： 如果下过雨则路是湿的，但路是干的，所以未下 雨。 反证规则MT（modus tollens） 表示为： 例如：林肯是
9、俄比亚人，那么他是非洲人。林肯不是 非洲人，因此他不是俄比亚人。（将前提否定，证出矛 盾） MT （反证规则） *29 例：矢列式p（qr），p，r q 的有效性 1 p（qr） 前提 理由 说明 2 p 前提 3 r 前提 4 qr e1，2 p p（qr） 用1行2行利用 qr 规则e得到4行 5 q MT4，3 qr r MT 用4行3行使用 q MT规则得5行 e *30 例：将MT规则与e或i（双重消去或双重引入） 结合的两个示例性证明： （1）证明矢列式pq，q p是有效的 1 pq 前提 理由 说明 2 q 前提 3 p MT1，2 pq q 用1行2行使用 MT规 p 则得3行
10、，其中=p 4 p e3 3行使用双重否定消去 规则得4行，其中= p Note：该例使用了MT，e规则 MT MT e *31 （2）证明矢列式pq， q p是有效性 1 pq 前提 理由 说明 2 q 前提 3 q i2 用2行使用双重否定引入 规则得3行，其中= q 4 p MT1，3 用1行和3行使用MT规 则得4行， pq q 其中= p ，=q， p =q Note：规则使用次序由要证明的具体矢列而决定。 蕴涵引入规则：规则MT使我们证明了矢列pq，q p的 有效性，而pq qp也是有效的。 即：pq，q p等于pq q p 根据分离规则有pq，pq pqqp （参见数理逻辑徐永森
11、主编 高教出版社一书第36页） i MT1.3 MT *32 现我们给出用假设方法来证明其公式 pq q p的论证： 1 pq 前提 理由 说明 2 q 假设 假设结论的前件 3 p MT1.2 利用1行和2行 用MT规则得 3行，其中= p，= q 4 q p i2-3 ： Note：证明矩形表示临时假定的范围：从q开始利用规则得到p； Note：在矩形框内的证明依赖于假定的q（可多次使用规则） Note：最后我们用i规则得到结论q p。 i 利用2-3行引用如果规则得4 行。 MT *33 上述例子相当于 1 下雨地湿 1 pq 前提 2 地不湿 2 q 假设 3 未下雨 3 p 用规则M
12、T 4 地干未下雨 4 qp 用规则i Note：框内是假设范围。 * 例：用i规则证明qp pq是有效的。 1 qp 前提 理由 说明 2 p 假设 假设结论前件 3 p i2 用2行使用双重否定引入 规则得3行，其中= p 4 q MT1.3 用1行和3行使用MT 规则得4行，其中=q =p 5 pq i2-4 使用2-4行用i规则得到5行。 34 给出蕴涵引入规则表示形式为： ： i 称为蕴涵引入规则 note：紧跟在关闭的矩形框后的行必须与使用该矩形框的规则 所得到的结论模式相匹配。 i MT1. 3 *35 Note：这里，在假设的前题下证明共用了两个规则，在引 用i的这个例中 =
13、qp ：= p，p = q = pq i规则的特例： p p 1 p 假设 2 p p i 1-1 这种情况不依赖于任何前提。 *36 定义：若逻辑公式具有有效的矢列，则称是 定理 （任意一个公式经过有效的证明，就是定理） 例:使用多种规则证明一个公式是定理。 证明（qr）（qp）（pr） 是定理 Note：（首先均作前件假设然后推出后件，因为该 公式形如pq） *37 1 qr 假设 理由 说明 2 qp 假设 该公式形如pq 3 p 假设 4 p i3 利用3行使用双重否定引入规则得4行， 其中= p 5 q MT2，4 利用2行和4行引用MT规则得5行， 其中=q =p 6 q e5 利用5行使用双否消去规则得6行， 其中=q 7 r e1.6 利用1行6行蕴涵消去规则得7行， 其中=q = r 8 pr r3-7 ： 利用3行到7行使用蕴涵引入规则得8行 其中= p
