杨圣洪 yangshenghong8@tom.com 13007432216 第一章 命题逻辑 杨圣洪 yangshenghong8@tom.com 13007432216

引言 逻辑学是推理的基础，在社会学、自然科学尤其计算机学科中得到普遍应用。 数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。 命题逻辑是数理逻辑的基础部分， 但究竟什么是命题？ 如何表示命题？ 如何构造出复杂的命题？ 在本章将讨论这些问题。

1.1 命题及联结词 对错确定的陈述语句称为命题。如： (1)湖南大学是一本学校。 (2)命题逻辑是计算机科学的基础课程。 (3)命题及联结词是命题逻辑的最基础的内容。 (4)4是素数。 (5)湖南大学坐落于湘江以东。 (6)2011年湖南长沙轻轨通车。 其中(1)、(2)、(3) 与事实相符，是对的、正确的，称为真命题，或者称命题的值为“真”，简记为T或数字1。 而(4)、(5)明显与事实不相符，是错的、不正确，称为假命题，或称命题的值为“假”，简记为F或数字0。 陈述句(6)的正确性，到2011年12月时能确定的，若届时开通了则它是对的、为真命题，否为假命题。

1.1 命题及联结词 对错确定的陈述语句称为命题。如： (7) x与y之和为100，其中x为整数，y为整数 (8)1加1等于10 (8)的对错是不确定的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句不是命题。 (9)岳麓山的红叶真美呀！ (10)动作快点！ (11)你是离散数学老师吗？ 这三个语句不是陈述语句，因此不是命题。

1.1 命题及联结词 对错确定的陈述语句称为命题。如： (12)我在说假话。 (13)我只给自己不能理发的人理发。 (14)派出所说:必须先房子再能上户口 单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗? 这是一个悖论，其真值不能确定，故不是命题。。

1.1 命题及联结词 对错确定的陈述语句称为命题。如： (13)我既要学程序设计，又要学离散数学。 (14)我们早餐在公寓食堂或外面早点摊上吃。 (15)我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命题，其值为真(T/1)。 其中(13)与(14)可分解为另外二句话的组合， 而(15)是对“我是数学院学生”的否定，这些语句称为“复合命题”，不能再分解的语句称为“简单命题”或“原子命题”，为了便于推理与书写，常用小写字母表示简单命题或原子命题。

1.1 命题及联结词 简单命题组合成复杂命题时所使用的辅助词称为“联结词”。 命题逻辑中的联结词归纳为以下5种。 合取：C语言中 && and 并且 析取：C语言中 || or 或 否定：C语言中 ! not 非,不是,否定 条件式：C语言中 if () 如果…那么 如p则q 双条件式： 如p则q且如q则p,当且仅当

1.1 命题及联结词 定义1.1合取： 当p、q都对，即取值为真(T或1)时，“p合取q”的值为真.

1.1 命题及联结词 定义1.1合取： 当p、q都对，即取值为真(T或1)时，“p合取q”的值为真，其他情况为假。 逻辑运算符“合取”，与汉语中“并且、而且、同时”含义相当

1.1 命题及联结词 定义1.2析取： 当p、q都不对，即取值为假(F或0)时，“p析取q”的值为假，其他情况为真。 逻辑运算符“析取”，与汉语中“或”含义相当，但有细微的区别

1.1 命题及联结词 逻辑运算符“析取” 与汉语的“或”几乎一致但有区别： (16)“讲离散数学的老师是杨老师或刘老师”，可以表示为“讲离散数学的老师是杨老师”“讲离散数学的老师是刘老师”，这两个原子命题有可能都是对的，这种“或”称为“可同时为真的或”，或简称为“可兼或”。 (17)“离散数学的教室是102或302”，不可以表示为“离散数学的教室是102”“离散数学的教室是302”，因为这两个原子命题不可能都对，只能这二种情况之一，这种“或”称为“不可同时为真的或”，或简称为“不可兼或”、“排斥或”. 这种“或”表示不能简单表示为“析取”，需要联合使用下面将要介绍的“否定”与“析取”符号，才能准确表达。

1.1 命题及联结词 定义1.3否定:当p是1 ，p的否定p即为0。 逻辑运算符“否定”，与汉语中“否定”含义相当. “我不是数学院的学生”可表示为“我是数学院的学生” “离散数学的教室是102或302”,表示 离散数学的教室是102不是302" 或 "离散数学的教室是302不是102" p:离散数学的教室是102 q:离散数学的教室是302 上面的语句表示: (pq)(pq)

1.1 命题及联结词 定义1.4条件:当p是1 ,q是0时,pq为0,即10为0,其他情况为1。 逻辑运算符“如果…那么”，它是用单个运算符表示一个复合语句。 如老妈说：“如果期终考了年级前10名，那么奖励1000元”。 p:期终考了年级前10名 q:奖励1000元 则上面的语句表示为pq。 当p为1即“期终考了年级前10”， 且q为0即“没有奖励1000元” 这时老妈的话是假话空话， 故pq为0

1.1 命题及联结词 定义1.4条件式(蕴含式):当p是1 ,q是0时,pq为0,即10为0,其他情况为1。 p为前件,q为后件

1.1 命题及联结词 定义1.5双条件:当p与q值相同0时,pq为1,不同为0。 称p与q的等价式 “我明年赚了10万当且仅当我买彩票中了大奖”， 可以表示为“我明年赚了10万我买彩票中了大奖”

1.2公式及其赋值 对错明确的陈述语句称为命题，其真值确定，又称为命题常元或命题常项，相当于初等数学中的“常数”。 数学的运算符号为“加+、减-、乘x、除、幂”， 命题逻辑的符号“合取、析取、否定、条件、双条件” 数学中用变量x表示某些数，如x2+x+10是代数式， 命题逻辑用变量表示任意一个命题，如p,q,r,这时由符号与变量所构成命题表达式，简称为“命题公式”。 代数式的书写有规律，命题公式也有规律与约束，称满足这些规则的公式为“合式公式”，也称为“命题公式”，简称为“公式”。

1.2公式及其赋值 定义1.2.1 合式公式的生成规则 (1)单个命题变元、命题常元为合式公式(原子公式)。 (2)若A是合式公式，则A、(A)也是合式公式。 (3)若A、B是合式公式，则AB、AB、AB、AB是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 如：(p1)q是合式公式。 因为p、1是合公式，则(p1)是合式公式，而r是合式公式，故(p1)q是合式公式。 (p1)r不是合式公式。 因为p、1是合公式，则(p1)是合式公式，而r是合式公式，但(p1) r不是合法公式。

对于代数式x2+y+10，当x与y的值不确定时，该代数式的值是不确定的。 1.2公式及其赋值 对于代数式x2+y+10，当x与y的值不确定时，该代数式的值是不确定的。 对于公式 (p1)q，由于p与q值不确定时，公式(p1)q的值不确定，因而不是命题。 只有当p与q的值确定后，公式(p1)q的值才能确定，我们可能像表1.2到表1.5一样，给出公式在各种情况下的取值，即得到这个公式的真值表。 p与q每一种取值称为p、q的一种解释

公式(pq)、pq的真值表如下表。 1.2公式及其赋值 公式(pq)、pq的真值表如下表。 真值表的构造方法： (1)命题变元的取值从全0开始，依次加1，直到全1，当有n个变元时，则共有2n种不同的取值情况。 (2)分步骤计算公式的值 (3)见黑板上写 成真赋值:如pq为(0,0),(0,1),(1,1) 成假赋值:如pq为(1,0)

1.2公式及其赋值 公式(pq)(qp)、pq的真值表。 无论p/q取何值，这两个公式的值总相等。

1.2公式及其赋值 公式 (pq)、 p  q的真值表。 无论p/q取何值，这两个公式的值总相等。

无论p/q取何值，这两个公式的值总相等。 1.2公式及其赋值 公式pq、 pq的真值表。 1 无论p/q取何值，这两个公式的值总相等。

无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题 1.2公式及其赋值 公式pq、qp的真值表。 1 无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题

公式p(qr)、(pq)(pr)的真值表。 1.2公式及其赋值 公式p(qr)、(pq)(pr)的真值表。 无论p/q取何值，这两个公式的值，与前面各例不同，此表是将运算结果写在联结词的下方！

p(qr)、(pq)(pr) 1.3 等值式 一、复习 由前节可知： pq与pq、 qp pq与(pq)(qp) 、(pq)(pq) (pq)与p  q p(qr)、(pq)(pr) 的真值表完全一样，称为等值。 定义1.3.1 设A、B是两个合法的命题公式，无论其中的命题变元取何值，这两个公式的总相等，称为两个公式等值，记为AB

由定义及前节习题有： (1)pqpqqp 条件式的等值式 (2)pq(pq)(qp)(pq)(pq) 双条件 (3)pp 双重否定律 (4)ppppp 幂等律 (5)pq qp，pq qp 交换律 (6) p(qr) (pq)  r 结合律 p(qr)  (pq)  r (7) p(qr) (pq)(pr) 分配律 p(qr)  (pq)(pr) (8) p(pr) p 吸收律(多吃少) p(pr) p (9) (pq) pq 德摩律 (pq) pq 将以上等值式中的变元换成合式公式仍等值！

如：pq  pq 则有 AB  AB

置换规则：当将公式A中的子公式B换成C得到公式D后，若BC，那么AD。 因为A、D除了“A中B所在之处、D中C所在之处”外，其他地方均相同，而不同之处的B与C等值，所以公式A、公式D的真值表应该完全他相同，故AD。 当将一个公式的局部进行等值替换后， 仍与原公式等值，这也是数学中最常见的方法，不断对局部进行等值替换的操作，称为“等值演算”。 利用该规则及前述的等值式，可进行等值演算，从而推导出新的公式。

求证 (pq)r(pr)  (qr) r (pq) 交换律 (rp)( rq) 分配律 (p  r)( qr) 交换律 (pr)  (qr) 条件式等值式

等值演算的基本套路 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) 确保公式只保留  联结词 (3)否定到底 ： A, (AB), (AB) (4)恰当使用分配律、吸收律。

利用等值演算，判断公式的类型 ((pq)p)q AA (A= (pq)) 1 称为永真式或重言式， 即利用等值演算，可以判断公式的类型。

利用等值演算判断公式类型：(p(pq))r 解： (p(pq))r (p(pq))r (条件式的等值式) ((pp)q) r (结合律) (1q) r (析取的性质即析取定义真值表) 1r (析取的性质即析取定义真值表) 0r (否定的定义) 0 (析取的性质即析取定义真值表) 永假式或矛盾式。 问题：尽管有套路可行，但是随意性还是比较大，能否有某种方式肯定能成功呢？

1.4 析取范式与合取范式 文字：命题变项(变元)及其否定称为文字. 如:p,q,r, p, q, r 简单析取式:仅由有限个文字构成的析取式. 如:pq, pq,pq, p q,pqr 简单合取式:仅由有限个文字构成的合取式. 如:pq, pq,pq, pq,pqr 定理：简单析取式与简单合取式 (1)一个简单析取式Ai是重言式 含有某个命题变元及其否定式，如Ai=pp… (2)一个简单合取式Ai是矛盾式 含有某个命题变元及其否定式，如Ai=pp…

1.4 析取范式与合取范式 析取范式：由有限个简单合取式的析取构成的命题公式称为析取范式。 总体是析取式，每对括号内是合取式 A=(pq)(pr) 合取范式：由有限个简单析取式的合取构成的命题公式称为合取范式。 总体是合取式，每对括号内是析取式 A=(pq)(pr)

1.4 析取范式与合取范式 总体是析取式，每对括号内是合取式 A=(pq)(pr) 析取范式 总体是合取式，每对括号内是析取式 定理：析取范式与合取范式 (1)一个析取范式A是矛盾式 每个简单合取式是矛盾式。 A=(pq)(pr) (2)一个合取范式A是重言式 每个简单析取式是重言式。 A=(pq)(pr)

1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 经过第1步、第2步转换后，公式中只有、、三种运算符。 经过第3步后，从括号外深入到变元的前面，与变元结合成文文字，文字之间只有、。

1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 如果外层运算符全部是，而内层子公式全部是简单析取式，则已经是合取范式。 如果内层某子公式形如A(BC)，不是简单析取式，则转换为(AB)(AC)。

1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 如果外层运算符全部是，而内层子公式全部是简单合取式，则已经是析取范式。 如果内层某子公式形如A(BC)，不是简单合取式，则转换为(AB)(AC)。因此有： (1)不是永假的命题公式，存在析取范式。 (2)不是永真的命题公式，存在合取范式。

1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 如析取式范式：(pq) r (pq) r ((pq)r)((pq)r) (p r)(qr)(pqr)

1.4 析取范式与合取范式 求(pq) r的析取范式、合取范式 解：(1)求析取范式。即外层是，内层是，所以转换模式为AB (AB)(AB) (pq) r ((pq) r)(  (pq)  r) (整体为析取) ((pq) r)(  (pq)  r) (ABAB) ((pq) r)( (pq)  r) (德摩律) ((p r )(qr))( (pq)  r) (分配律) (p r )(qr)( pq  r) (结合律)

1.4 析取范式与合取范式 解：(1)求合取范式。所以转换模式为AB(AB)(AB) (pq) r ( (pq)r)( (pq) r) (整体为合取) ( (pq)r)( (pq) r) (条件等价式) ((pq)r)( (pq) r) (德摩律) ((pr) (qr))( (pq) r) (分配律) (pr) (qr)( pq r) (结合律)

1.4 析取范式与合取范式 小项：在含有n个变元的简单合取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单合取式为(极)小项。 如：pqr, pqr, pqr, pqr (p r), (qr) 非小项 大项：在含有n个变元的简单析取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单析取式为(极)大项。 如：pqr, pqr, pqr, pqr (pr), (qr) 非大项

1.4 析取范式与合取范式 主析取范式：一个析取范式中，如果所有简单合取式均为(极)小项，则称为主析取范式。 (pq) r (p r)(qr)(pqr) 不是 (pqr)(pqr) (pqr)(pqr) 是主析取范式

1.4 析取范式与合取范式 主合取范式：一个合取范式中，如果所有简单析取式均为(极)大项，则称为主合取范式。 (pq)r (pr)(qr)(pqr) 不是 (pqr) (pqr) (pqr) (pqr) 是主合取范式

1.4 析取范式与合取范式—获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp1，1r1，可在缺少变元的小项中加入形如“pp”的公式。 如小项(pr)缺少变元q，加入qq，即 pr p1r p(qq)r (pqr)(pqr)。

1.4 析取范式与合取范式—获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp1，1r1，可在缺少变元的小项中加入形如“pp”的公式。 (pq) r (pr)(qr)(pqr) (p(qq) r)((pp)qr)(pqr) (pqr )(pqr) (pqr )(pqr) (pqr) (pqr )(pqr) (pqr ) (pqr)

1.4 析取范式与合取范式—获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp0，0pp，可在缺少变元的大项中加入形如“pp”的公式 。 如 pr p0r p(qq)r (pqr)(pqr)

1.4 析取范式与合取范式—获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp0，0pp，可在缺少变元的大项中加入形如“pp”的公式 。 (pq) r (pr)(qr)(pqr) (p(qq)r)((pp)qr)(pqr) (pqr)(pqr)(pqr)(pqr) (pqr) (pqr) (pqr)(pqr)  (pqr)

1.4 析取范式与合取范式 当一个公式比较复杂时，得到其析取范式、合取范式的演算量比较大，再将简单析取式转换为大项，或简单合取式转换为小项，又需要进一步演算，能否直接基于原公式，不进行等值演算直接得到，或者能按某种统一的方式得到其主析取范式、主合取范式呢？ 通过真值表可以实现！为此先研究小项与大项的性质。

1.4 析取范式与合取范式 通过真值表可以实现！为此先研究小项与大项的性质，下表是各小项的真值表。

1. 3个变元的小项共有8个，它们各不相同。 2.从每一行来看，命题变元的每个指派中，只有一个小项的值为1。 3.从每一列来看，每个小项仅在一个指派中值为1，其余7种指派中均为0。 4.小项值为1(如pqr=1)时，p,q,r均为1，即(p,q,r)=(0,0,0)，取该值为小项编号，如最后一行。

(5)根据小项的编号，可写出小项的具体形式。 如小项m101，其编号为101，表示(p,q,r)=(1,0,1)时该小项的值为1，而小项是文字的合取，故小项的各个文字必须为1,则文字只能是p、q、r,故该小项为pqr。 规则：1对应变元本身(如p)，0对应其否定(如p) 。 如m00为pq、m01为pq、m10为pq、m11为pq。 很重要！

(1)三个变元的大项共有8个。 (2) 每一行:每个指派中，只有一个大项的值为0。 (3)每一列:每个大项仅在一个指派下值为0。 (4)大项值为0(如pqr=0) 时，p、q、r均为0，则(p,q,r)=(1,1,1)，将其记为大项编号,如表最后行。

(5)根据大项的编号，可写出大项的具体形式。 如大项M101,其编号为101，表示(p,q,r)=(1,0,1)时该大项的值为0，而大项是文字的析取，故各个文字必须为0，文字只能是p、q、r，故该大项为pqr。 规则：1对应变元的否定(如p)，0对应变元(如p) 如M00为pq,M01为pq,M10为pq, M11为pq。

1.4 析取范式与合取范式—获取方法 1、先转换析取式或合取式，再合取1或析取0。 2、先建立真值表， 取出所有成真赋值对应的小项，析取所有小项得主析取范式。小项与成真赋值对应。 取出所有成假赋值对应的大项，合取所有大项得主合取范式。大项与成假赋值对应。 如用真值表求主范式: (pq)r, pq, pq, (pq)q,p(pq)

(pqr) (pqr)(pqr)( pqr) 主析取范式 公式值为1的指派对应小项的析取 m001 m011 m100 m111 1变元,0变元否定, 使小项=1 (pqr) (pqr)(pqr)( pqr)

(pq) r的主析取范式、主合取范式 主合取式范式 公式值为0的指派对应大项的合取  M000 M010 M101 M110 1变元否定0变元,使大项=0 (pqr)( pqr)( pqr)( pqr)

(pq)r、与其主析取范式、主合取范式的真值完全一样，说明三者互相等值，一般情况下有如下定理 ： (1)不是永假的命题公式，有等值的主析取范式。 (2)不是永真的命题公式，有等值的主合取范式。 由于永假没有取值为1的解释，故无相应小项，故没有主析取范式。永真无取值为0的解释,故没有主合取范式.

设计一个电子评分系统，3位专家打分，如果有2位以上专家打分为“通过”，则总成绩为“通过” 。 对应的主析取范式值为1的指派对应的小项的析取 m011m101m110m111 (x1x2x3) (x1x2x3)(x1x2x3)(x1x2x3) ((x1x2x3)(x1x2x3))((x1x2x3) (x1x2x3)) ( ((x1x2) (x1x2))x3)(((x1x2(x3x3))) (((x1x2) (x1x2))x3)( x1x2) ((x1x2)(x1x2)x3)( x1x2) 与非或门表示

某公司要从曹、乔、宋、黎、邹5人中，选择一些人承包一项工程，考虑到人与人组合优化的问题，需满足如下约束条件： (1)如果曹去，那么乔也去； (2)黎、邹两人中必有一人去； (3)乔、宋两人中去且仅去一人； (4)宋、黎两人同去或同时不去； (5)若邹去，则曹、乔也同去； 解：用小写字母表示： c:曹去， q：乔去 s：宋去 l：黎去 z：邹去时，以上5句话可表示为如下的公式： (cq)、(lz)、((qs)(qs))、(sl)、(z(qc))， 5句话同时成立即每句话的值均为1，也即其合取式(cq)(lz)((qs)(qs))(sl)(z(qc))为1

(cq)(lz)((qs)(qs))(sl)(z(qc))  (cq)(lz)((qs)(qs))((sl)(sl))(z(qc)) (cq)(lz)(z(qc))((qssl)(qssl)(qssl)(qssl)) (cq)(lz)(z(qc))((qsl)(qsl)) (cq)(lz)((zqsl)(zqsl)(qcsl)) (cq)((zqsl)(zqcsl)) (czqsl)(zqcsl) 因(cq)(lz)((qs)(qs))(sl)(z(qc))为1，故1(czqsl)(zqcsl)， 故1(czqsl)或1(zqcsl) 故 方案一是：曹不去、邹不去、乔不去，宋与黎去。 方案二是：曹去、乔去、邹去，宋与黎均不去

在某班班委的选举中，该班的甲、乙、丙学生预言： 甲说：王娟为班长、刘强为生活委员； 乙说：金鑫为班长、王娟为生活委员； 丙说：刘强为班长、王娟为学习委员； 结果公布后，发现甲、乙、丙三人都恰好对了一半，请问王娟、刘强、金鑫各任何职？ 解：p1,q1,r1:表示王娟，刘强，金鑫是班长； p2,q2,r2:分别表示王娟，刘强，金鑫是学习委员； p3,q3,r3:分别表示王娟，刘强，金鑫是生活委员； “每个人说法对一半”将是一个非常复杂的公式(p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)，要构造这9个变元的真值表，将需要29=512行，工作量实在太大了， ！

参考“真值表”，设计如下的判断表

1.6 推理理论 从已知条件、假设、前提或公理出发，根据推理规则推出结论、定理的过程，称为推理 。 定义1 设A与C是两个命题公式，若AC为永真式(重言式)，则称C是A的有效结论，或称A可以逻辑推出C，记为AC. 由“”的定义可知，当A为假时，AC肯定为真，故只要考虑A为真时C是否为真即可，故有: 定义2 设A与C是两个命题公式，若当A为真时C也为真，则称C是A的有效结论，或称A可以逻辑推出C，记为AC。 一般情况下，利用定义2去证明要简单些，我们在其他学科中遇到的证明都是基于定义2的。 判断AC为永真可用等值演算、真值表等方法

例题 求证：A(AB)B (A(AB)) B (A(AB))B (的等值式)   ((AA)(AB))B (分配律)  (0(AB))B (合取的性质)  (AB)B (析取的性质) (AB)B (德摩律) A(BB) (结合律) A1 (析取的性质)  1 (析取的性质) 所以(A(AB)) B是重言式，真值表也证永真 所以A(AB)B。这是有名的“假言推理(modus ponens)”，或“分离原则”

假如我今年进入年级前10名老爸给我买iphone 4; 期末考试后我为年级第8名，所以老爸应该给我买iphone4。这是假言推理。 A(AB)B 从形式上看，结论B是AB的后件，推导的结果是将后件分离出来，故也称为分离原则。 利用假言推理规则或分离规则，结合析取、合取、否定的定义，只要不歉麻烦，几乎可推出所有的结论。 为了提高推理效率，还需要学习、掌握某些推理规则。

例题 求证 AAB 采用定义1来证明，即证明AAB为永真式。 AAB A(AB) (的等值式) (AA)B (结合律) 1B (析取的性质) 1 (析取的性质) 所以AAB

例题 求证 ABA ABA (AB)A (的等值式) (AB)A (德摩律) ABA (结合律) 1B (析取的性质) 1 (析取的性质) 类似 ABB 根据的定义可知AB为真时，A与B均为真，因此由推理定义2可知 ABA， AB B 。 同样由的定义可知A为真时 AB为真，故由推理定义2可知AAB。 然这3个推理式不必记忆！推理定义2效率较高

例题 求证 (AB)(BC)(AC) 根据定义1，要证明下式为永真式。 (AB)(BC)  (AC) ((AB)(BC)) (AC) (的等值式) ((AB)( BC)) (AC) (的等值式) ((AB)  (BC)) (AC) (德摩律) ((A B)(A C )(B  B) (BC)) (AC) (分配律) ((A B)(A C )1(BC)) (AC) (析取的性质) ((A B)(A C )(BC)) (AC) (析取的性质) (A BAC)(A CAC )(BCAC) (分配律) (1 BC)(1 CC )(BA1) (析取的性质) 111 (析取的性质) 1 (析取的性质) 判断公式的类型，除等值演算外，还有真值表与范式等方法。

例题 求证 (AB)(BC)(AC) 这是有名的传递律，要记住呀！

例题 求证 (AB)(CD)(AC)BD 利用定义1证明了假言推理规则(AB)AB,传递规则(AB)(BC)(AC)。 有了这2条规则后,可用定义2来证明推理式了。 由于这2条规则的结论中没有析取式，只有条件式，因此将题中结论转换为 BD,题设中转换为 (1)(AB)(CD)(AC)为真 前提条件(定义2的套路) (2) (AB)为真 (1)及合取的性质 (3) (CD)为真 (1)及合取的性质 (4) (AC)为真 (1)及合取的性质 (5)(BA)为真 (2)及(AB) (BA) (6) (AC)为真 (4)及(AC) (AC) (7) (BC)为真 (5)、(6)及推理传递律 (8) (BD)为真 (7)、(3)及推理传递律 (9) BD为真 (8)及(BD) BD

例题 求证 (AB)(CD)(BD)AC 可用传递律来证明，还有更高效的方法 由定义1只要证((AB)(CD)(BD))(AC)为重言式，而 ((AB)(CD)(BD))(AC) ((AB)(CD)(BD)) (AC) ( ((AB)(CD)(BD))A)C) ((AB)(CD)(BD))A)C) ((AB)(CD)(BD))A)C 故只需证 ((AB)(CD)(BD))A)C为重言式 即只需证明(AB)(CD)(BD))AC A从结论中挪到前提中，这种技巧称为附加条件(CP)法，适合于结论为条件式的情形。

例题 求证 (AB)(CD)(BD)AC (1)(AB)(CD)(BD)A为真 CP规则及前提 (2)AB为真 (1)及合取的性质 (3)A为真 (1)及合取的性质 (4)B为真 (2)(3)及假言推理式(AB)AB (5)BD为真 (1)及合取的性质 (6)BD为真 (5)及BDBD (7)D为真 (4)(6)及假言推理式(BD)BD (8)CD为真 (1)及合取的性质 (9)DC为真 (8)及原命题逆否命题 (10)C为真 (7)(9)假言推理式(DC)DC 提示：熟练后可不写(1)式，直接引用(2)(3)(5)(8)！

例题 求证 (AB)(CD)(BD)AC (3)B为真 (1)(2)及假言推理式(AB)AB (4)BD为真 前提条件 (5)BD为真 (4)及BDBD (6)D为真 (3)(5)及假言推理式(BD)BD (7)CD为真 前提条件 (8)DC为真 (7)及原命题逆否命题 (9)C为真 (6)(8)假言推理式(DC)DC

求证 (WR)V, V(CS),SU,C,UW 提示：此处用逗号简写前述各例中的合取式，从而鼓励大家直接引用前提。 利用假言推理、传递律及前面所学的等值式，可以推出结论。在黑板上演示一番 考虑到本题的结论是W，可采用反证法。 根据定义2可知“当前提为真时结论也为真”， 反证法是“前提为真时，假设结论不为真即结论的否定为真”。 即基于前提、结论否定进行推理。 如果推出了一个矛盾的结论出来，则说明“假设结论不为真”是错误的，即表示结论只能为真了

求证 (WR)V, V(CS),SU,C,UW (1)W为真 假设结论W为0即  W为1(真) (2)W为真 (1)与否定的性质 (3)(WR)为真 (2)与析取的性质 (4)(WR)V为真 前提条件 (5)V为真 (4)(3)假言推理((WR)V)(WR) V (6)V(CS)为真 前提条件 (7) (CS)为真 (5)(6)假言推理(V(CS))V(CS) (8) CS为真 (7)与条件式的等值式CSCS (9)C为真 前提条件 (10)S为真 (8)(9)与假言推理(CS)( C)S (11) SU为真 前提条件 (12)U为真 (10)(11)假言推理(SU)SU (13) U为真 前提条件 显然(12)与(13)矛盾，故假设有误！

应用题 天气情况要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回来后不做饭， 结论是：如果我已做饭那么肯定天下雨了。 解：用M表示天晴， R表示天下雨， C表示爬山， F表示做饭，则问题可表示为 MR，MC，CFFR (MR)(MR) ，MC，CFFR

应用题MR，MC，CFFR (1)F为真 附件前提 (2)CF为真 前提条件 (3)FC为真 (2)的等值式 (4) FC为真 (3)的等值式 (5) C为真 (1)(4)的假言推理 (6) MC为真 前提条件 (7)CM为真 (6)的等值式 (8) M为真 (5)(7)的假言推理 (9) MR为真 前提条件 (10) MR为真 (9)的等值式 (11) R为真 (8)(10)的假言推理

应用题MR，MC，CFFR (1)F为真 附件前提 (2)CF为真 前提条件 (3)FC为真 (2)的等值式 (4) FC为真 (3)的等值式 (5) C为真 (1)(4)的假言推理 (6) MC为真 前提条件 (7)CM为真 (6)的等值式 (8) M为真 (5)(7)的假言推理 (9) (MR)(MR)为真 前提条件 (10)  (MR)  (MR)为真 (9)的等值式 (11)  MR  (MR)为真 (10)的等值式 (12)  MR为真 (8)与析取的定义 (13) (MR)为真 (11)(12)的假言推理 (14) R为真 (13)与合取的定义

定义2证明推理式的规律 (1)利用“条件等值式”，尽可能将前提、中间结论及最终结论中的“析取式”转换为“条件式”，以便可引用假言推理、传递律。 (2)如果结论为条件式，则将条件式的前件做为附加前提。CP原则 (3)如果结论的否定在前提中多次出现，可采 用反证法。 (4)每一步的推理理由可简化，如“前提条件”简写为“P”，“假言推理”可简写“M”，等值式只写“等值”或简写“E”。 (5)这种从前提出发，应用已证明的推理式，不断推出中间结论，最后推出结论的方式，称为自然推理，这是最常见的方式。

1.7消解规则 证明(AC)(BC)AB (1) (AC)为真 前提条件 (2) A C为真 与(1)等值 由于(AC(BC)中互补的公式C、C同时消失了，称“AB”为 “(AC)，(BC)”的消解式。 因此在采用定义2进行推理时，只要(AC)、(BC)同时为真，则可直接写出AB为真，从而节省大量的中间环节，提高了证明效率。

1.7消解规则 例题 (AB)(CD)(BD)AC 利用条件式的等值式，则此题等价于证明 (3) AD为真 当(1)(2)为真消解式AD为真 (4) CD为真 前提条件 (5) AC为真 当(3)(4)为真消解式AC为真 采用假言推理原则时，尽可能将析取转换为条件式。 采用消解法时，尽可能将条件式转换为析取。 消解法是一种高效的方法。 消解法可完成1.6节中所有推理式

1.7消解规则 采用定传递律证明了(AC)(BC)AB (1) A为真 附加前提 (2) (AC)为真 前提条件 因AB AB,故可用假言推理及CP原则证明 (1) A为真 附加前提 (2) (AC)为真 前提条件 (3) A C为真 与(1)等值 (4) C为真 (1)(3)假言推理 (5) B  C 为真 前提条件 (6)CB为真 与(4)等值 (7) B为真 (4)(6)假言推理 用假言推理证明了消解规则，反过来 用消解规则可证明假言推理

1.7消解规则 用假言推理证明了消解规则证明了 (AC)(BC)AB 反过来，用消解规则可证明假言推理 A(AB)B “假言推理”与“消解规则”可以互相推出，因此一方推出的结论另一方也可以推出 因此习题三可由消解规则推导出来呀