《02-面向计算机的数理逻辑(ch2-1).ppt》由会员分享，可在线阅读，更多相关《02-面向计算机的数理逻辑(ch2-1).ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、*面向计算机的数理逻辑面向计算机的数理逻辑主讲：李伟刚西北工业大学软件与微电子学院*第二章第二章 命题逻辑命题逻辑*32.1 判断语句：为了做严格的论证开发一种语言该语言能够反 映其逻辑结构命题逻辑基于命题。即：我们从最基本的概念“命题”和“真值联结词”开始讲述 数理逻辑。定义：凡能分辨真假的语句称为命题。定义：一个语句如果不能再进一步分解成更简单的语句，且又是一个命题，则称此命题为原子命题（或原子）。例8）判断下面句子是否为命题 1：银是白的 （真）2：雪是黑的 （假）3：9为质数 （假）4：天气多么好啊！（无真假）感叹句不能做命题 5：明天是否开会？（无真假）疑问句不能做命题*4 6：5大
2、于3 （真）7：太阳系外有宇宙人（现在的技术不能判别 真假，但将来总有一天能判别真假）8：全体立正！（无真假）是祈使句不能做命题 9：如果天气好，那么我们去散步（有真假）复合 命题 10：1+101=110 （根据上下文（=，+进制）才知 道真假）11：他是工人 （他是谁确是后才知真假）否 12：我正在说谎 （无真假）13：3和5的和等于8（真）14：Jane对Jack的指控反映激烈（有真假）*5 15：每个大于2的偶数自然数是两个素数之和（有真假，但目前尚未证明）16：所以火星人都喜欢在比萨饼上放意大利香肠（有真 假）总结：只有具有确定真假值的陈述句才是命题，一切没有 判断内容的句子，无所谓
3、是非的句子，如感叹句、疑 问句、祈使句等均不能作为命题。Note：命题分二类，一类是原子命题，一类是复合命题，原子命题是不能分解更为简单的陈述句，复合命题是由 联结词标点符号和原子命题复合构成，即：复合命题是 由旧命题组成的新命题，而新命题的真假完全由旧命题 决定的，故也称旧命题为成份命题。约定：在数理逻辑中我们用大写字母A，B，表示公 式，用小写字母p，q，r，s等表示命题。*6下面介绍数理逻辑中的真值联结词（，）定义：“非”利用真值联结词可以由原子命题a组成复合命题，读做“非a”记为a，其真假值关系定义如下：a 真 当且仅当 a假 即：a a T F F T 我们称a为a的否定式，从逻辑学
4、角度看与日常用 语的“不”，“无”，“没有”“非”相当。例如：a：上海是座大城市 a：上海不是座大城市（上海是一座不大的城市）p：上周我没有中彩（上周我中彩不是真的）Note：“否定”的意义仅是修改了命题的内容，我们仍把它作为 真值联结词，它是一元运算，因为只有一个运算对象 （或叫单目运算）*7 定义：“且”（合取）利用真值联结词可以由原子命题a与b组成复合 命题，“ab”记为ab，读作a合取b，真假之间关系定义如下：ab真 当且仅当 a与b均真 即：a，b ab T T T T F F F T F F F F Note：ab称为a与b的合取项，合取也可以将若干个 原子命题联结在一起，ab为二
5、元运算（双目运 算）与日常生活用语“并且”，“以及”，“和”，“不 仅而且”“虽然但是”“尽管仍然”等词汇相当。*8 例如：a：今天下雨 b：明天下雨 ab：今天下雨且明天下雨 （今天明天都下雨，这两天都下雨）a：上周我中了彩 b：中了宝马大奖 ab：上周我中了彩和宝马大奖 Note：合取的概念与日常语言中的“与”意义相似，但并不完全 相同。例如：a：我去看电影 b：房子有十张桌子 ab：我去看电影与房子有十张桌子 这个例子在日常语言中是没有意义的，因为a与b没 有任何的内在联系，但做为数理逻辑而言真假值的取得 只能根据定义来判断。*9 定义：“或”（析取）利用真值联结词将原子命题组成复合命题
6、a或b 记为ab，它们的真假之间关系定义如下：ab 假 当且仅当 a与b均假 即：a b ab T T T T F T F T T F F F ab称为a与b的析取式，a，b为析取项。*10 例如：a：今天下雨 b：今天打雷 ab：今天下雨或打雷 Note：从析取的定义分析，联结词与自然语言 （日常语言）的“或”的意义也不完全相同。因为自然语言中的“或”1）“排斥或”可以表示为 如：今天晚上我在家看电视或去同学家 2）“可兼或”如：他可能是100米或400米的冠军 显然1）是排斥或，2）可兼或。而数理逻辑用的是 “可兼或”。*11 定义：“”如果则 （条件）利用真值联结词将原子命题a，b组成复
7、合命题“如果a 则b”记作ab，它们的真假值之间的关系 定义如下：ab 假 当且仅当 a真且b假 即：a b ab T T T T F F F T T F F T 其中ab称为a与b蕴涵式，a称为该蕴涵式的前件，b 称为该蕴涵式的后件。（也可以称a为前提，b为结论）基本逻辑关系：b是a的必要条件，或a是b的充分条件。Note：从逻辑学角度讲，与自然语言的“如果a则b”，“只要a就b”，“a仅当b”，“只有b才a”等词汇相当。*12 例：如果某动物为哺乳动物，则它必胎生。a：如果某动物为哺乳动物，b：它必胎生。表示为：ab 例：如果我得到这本小说，那么今晚就看它。ab 例：只要不下雨，我就骑自行
8、车上学 只有不下雨，我才骑自行车上学 Note：在自然语言中，常常是因果有内在联系的，而逻辑学中则不然，它的真假值只是根据定义来 判断。例：如果我出差则教室多了十张桌子 又例:如果今天打雷则教室花开了。abb a*13 约定：优先级 1）2），3）其中蕴涵是右结合的 例如：pqr 表达式 p（qr）总结：数理逻辑是用数学方法来解决问题的，那么就应当有 这门科学的计算系统。1)运算符 （真假联结词）计算系统 2）运算对象（命题）3）优先级 （约定）4）运算规则（公式）例如：小学、中学、高中、大学，均有自己的运算系统。又例如：图论、集合论、数论，也均有自己的运算系统（化学、生物学、仿生学等）。*1
9、42.2 自然演绎自然演绎 上节我们从直观背景中抽象出命题形式的概念。例如：如果火车晚点了，而且车站没有出租车，那 么John参加会迟到。John没有迟到，火车的确晚 点，因此，车站有出租车。p：火车晚点了 q：有出租车 r：迟到了 r：没有迟到 q：没有出租车 根据题意有：pqr，r，p q 前提1 前提2 前提3结论*15 这就存在推理问题，数理逻辑中的推理主要分两类 1）演绎推理 推理 凡前提和结论存在必然联系的推理为演绎推理。2）归纳推理 凡前提和结论不存在必然联系的推理 归纳推理。为了严格的进行正确的推理过程我们给出如下定义：定义：设1，2n，都是命题形式，称推理1n 推出是有效的，
10、如果对1，2n，中出现的 命题变元的任一指派，若1，2n都真，则亦 真，称为有效的。否则称为无效的（不合理的）。记为：1，2，n 其中这个表达式称为矢列 Note：通过证明规则应用于前提而得到更多的公式，再将规 则用于这些公式，最终得到结论。*162.2.1自然演绎规则自然演绎规则 在证明矢列时每一步使用正确的规则是十分重要的，也就是说给出正确的前提按照正确使用规则来推出有效的结论。否则就会出现不合理的结论。例如 p：金是金属 q：银是金属 p，qpq 若推出这样结论是不合理的，它的意思是“金是金属且银不是金属”下面讲证明规则共15个 *17 合取规则合取规则（i）定义：这个规则在已知分别得到
11、结论和的 前提下，推导出结论 我们将这个规则记为：前提 i 合取引入 结论 其中：横线上面是该规则的两个前提，横 线下面表示结论，i读作合取引入 Note：上式的结论不一定是最终结论，为了得 到最终结论，有可能用到更多的结论。Note：逻辑联结词，一个或多个引用它的规 则，同理也有一个或多个消去它的规则。*18 合取消去规则（e1，e2）已证明 e1 e2 合取消去 结论 其中e1表示：如果有 的证明，通过该规 则可以得到一个证明。e2表示：如果有 的证明，通过该规则 可以得到一个证明。Note：e1中的必须匹配前提的第一合取项 e2中的必须匹配前提的第一合取项*19 例：用规则证明pq，r
12、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：第四行引用时注意合取项的顺序i3，2是对的，但i2，3就不对。上述的证明过程是引用了规则ei与i得到证明结 论。Note：上述规则不仅可以用在原子命题（语句），也可以 用在复合语句中。*21 例：（pq）r根据 e1 看作（p
13、q）推 出pq 而上例中在计算机实现中就必须使用指针，若逐字逐 句证明实际上是树状结构。（pq）e2 e2 q r i i qr 结论*22 双重否定规则双重否定规则（否定之否定）（否定之否定）我们知道=在这里我们称之为双重否 定。同类合取引入与合取消去，我们给出双重 引入规则。e 双重消去规则 i 双重引入规则*23 例：证明矢列p，（qr）pr是有效的。1 p 前提 理由 说明 2（qr）前提 3 p i1 i 利用第一行使 用双重否定规则，得到第三行 4 qr e2 e 利用第二行使用双重 消去规则，得到第四行 5 r e24 e2 利用第四行使用双重消 去规则，得到第五行 6 pr i
14、3，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行，其中q=5 s e22 利用2行使用规则e1 e1 得到5行=s 6 qs i 4，5 利用4，5行使用合取 i 引入规则得第6行 同上例类同4次使用规则，最后将结论推出。*25 蕴涵消去规则蕴涵消去规则
15、（也称分离规则）（也称分离规则）定义：这个规则表示：已知及蕴涵，我们可 以正确的得到。此规则表示为：前提 e 蕴涵消去 结论 例：如果下过雨那么街道是湿的。p：下过雨 q：街道是湿的 pq：如果下过雨，那么街道是湿的 Note：如果我们知道下雨，而且知道是湿的两个前 提结合起来看得出结论“街道确实是湿的，可见蕴涵消去 规则的合理性。（但不具有一般性只是应用常识）*26 例：一个编程的例子 p：程序的输入值是一个整数 q：程序的输出值是一个布尔值 pq：如果程序输入值是一个整数，那么输出一个布尔值。Note：如果程序满足pq但不满足p（如输入一个姓名）那么不能推出q。总之这个例子说明一定要求有效
16、的，并注意其前件。例：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 前提 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
17、e*28 Note：这就是不计次数的使用任意规则，当然这里 e 规则用前提及证过的中间结论而推出最终结论。Note：这个规则是充分不必要，（不是充要）的，所以 说我们有反证规则。例如：反证：如路是干的，刚下过雨是不对的。证：如果下过雨则路是湿的，但路是干的，所以未下 雨。反证规则反证规则MT（modus tollens）表示为：例如：林肯是俄比亚人，那么他是非洲人。林肯不是 非洲人，因此他不是俄比亚人。（将前提否定，证出矛 盾）MT（反证规则）*29 例：矢列式p（qr），p，r q 的有效性 1 p（qr）前提 理由 说明 2 p 前提 3 r 前提 4 qr e1，2 p p（qr）用1行
18、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行，其中=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 MT
19、1，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 （参见数理逻辑徐永森主编 高教出版社一书第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：证明矩形表示临时假定
20、的范围：从q开始利用规则得到p；Note：在矩形框内的证明依赖于假定的q（可多次使用规则）Note：最后我们用i规则得到结论q p。i 利用2-3行引用如果规则得4 行。MT*33 上述例子相当于 1 下雨地湿 1 pq 前提 2 地不湿 2 q 假设 3 未下雨 3 p 用规则MT 4 地干未下雨 4 qp 用规则iNote：框内是假设范围。*例：用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
21、行用i规则得到5行。34 给出蕴涵引入规则表示形式为给出蕴涵引入规则表示形式为：i 称为蕴涵引入规则 note：紧跟在关闭的矩形框后的行必须与使用该矩形框的规则所得到的结论模式相匹配。iMT1.3*35Note：这里，在假设的前题下证明共用了两个规则，在引 用i的这个例中 =qp ：=p，p =q =pq i规则的特例：p p 1 p 假设 2 p p i 1-1 这种情况不依赖于任何前提。*36定义：若逻辑公式具有有效的矢列，则称是 定理 （任意一个公式经过有效的证明，就是定理）例:使用多种规则证明一个公式是定理。证明（qr）（qp）（pr）是定理 Note：（首先均作前件假设然后推出后件，
22、因为该 公式形如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行行
23、其中其中=p =r 9 （qp）（pr）i 2-8 公式同上公式同上 利用利用2行到行到8行使用蕴涵引入规则得行使用蕴涵引入规则得9行行 其中其中=qp，=pr 10 （qr）（qp）（pr）i1-9 公式同上公式同上 利用利用1行到行到9行使用蕴涵引入规则得行使用蕴涵引入规则得10行行 其中其中=qr=（qp）（pr）i MTeei*38 Note：这是一个嵌套形式。该公式证明结构为（二叉树）qr qp p r注意：这个公式可推广为一般形式。可将1，2n 的任何证明变换为定理。1（2（3（n）通过i规则依次用于n1逐次的证明每一 步，如上例所述。*39例：使用规则i，可以证明矢列pqr p（
24、qr）的有效性（充分性，当 且）1 pqr 前提 理由 说明 2 p 假设 3 q 假设 4 pq i 2，3 用2行3行使用合取引入规则得4行，其中=p，=q 5 r e 1，4 用1行到4行 用蕴涵消去规则得5行，其中=pq，=r 6 qr i 3-5 ：用3行到5行用蕴涵引入规则得6行，其中=q，=r 7 p（qr）i 2-6 同理 同理得7行。Note：p，q为公式前件假设e ii*40例：运用消去规则e1，e2证明上例矢列的“逆”的有效性。即：p（qr）pqr的有效性（必要性，仅当）1 p（qr）前提 理由 说明 2 pq 假设 3 p e12 用合取消去 略 4 q e22 用合取
25、消去 略 5 qr e1，3 用蕴涵消去规则 6 r e5，4 略 7 pqr i2-6 略即：pqr p（qr）其中“”表示等价e1规则e2规则e*41 析取规则析取规则 析取规则表示为：X X i1 i2 X Note：假设证明某一个命题X，已知假设。因为不知道 和哪个为真，所以必须给出两个单独证明，再结合成一 个论断。1）首先，假设是真，得出X的证明 2）其次，假设是真，得出X的证明 3）已知两个证明，然后从为真推出X为真，记为 e也就是说：如果是真，不管假设还是，都可以推出X的 证明，既X是成立。*42例：给出pq qp的有效证明（注意pq qp是 等价公式交换律）1 pq 前提 2
26、p 假设 3 qp i22 假设 X的证明 4 q 假设 5 qp i1 4 假设 X的证明 6 qp e 1，2-3，4-5 结合推出 的证明Note：第6行的规则e的理由包括3点出现在第一行的 析取两种情况的矩形位置行，2-3和4-5。*43 总结：使用规则e要注意：1）首先证明两种形式的结论X实际上是同一公式;2）两种推理由e结合起来;3）两种情况都不能使用其他情况的临时假设;4）注意前提与两种情况的位置行;5）在推理中只使用做前提或假设会丢失某 些信息，因为有的两种可能性。再举一些更复杂一些例子：*44 例：证明矢列qrpqpr的有效性 1 qr 前提 理由 说明 2 pq 假设 3
27、p 假设 4 pr i13 利用3行使用i2得4行 其中=p，=r 5 q 假设 6 r e1，5 利用1行5行使用e规则得6行 其中=q ，=r 7 pr i26 利用6行使用i2得7行 其中=p，=r ：8 pr e2，3-4，5-7 X X 利用2行假计及3-4，5-7 X 结论合并得8行，：9 pqpri 2-8 X 利用2行8行使用i得9行，其中=pq，=prei1i2ei*45 Note：4，7，8行中的命题相同的，因此，e的应 用是合法的 又例：证明矢列（pq）rpqr的有效 性 Note：（pq）r=p（qr）是数理逻辑的等价 公式（结合律）（pq）r=p（qr）（参考书等价公
28、式 部分）Note：证明等价公式最简单的方法是应用真值表来证。*46证明此例的思想：1）用消去规则把（pq）r分解为基本成分p，q，r 2）再由引入规则建构公式p（qr）1 （pq）r 前提 2 （pq）假设 3 p 假设 4 p（qr）i13 5 q 假设 理由及说明略 6 qr i15 7 p（qr）i26 8 p（qr）e 2，3-4，5-7 9 r 假设 10 qr i29 11 p（qr）i210 12 p（qr）e 1，2-8，9-11*47 又例：在布尔代数或电路理论中知道，析取对合取满足分配律。Note：p（qr）=（pq）（pr）分配律，这是一个等价公式，参 见参考书等价公式
29、部分。因为等价既有重要性质。证明：p（qr）（pq）（pr）1 p（qr）前提 理由 说明 2 p e11 利用1行使用e1得2行 其中=p 3 q r e21 利用1行使用e2得3行 4 q 假设 5 pq i 2，4 利用2行4行使用i 得5行 6 （pq）（pr）i1 5 利用5行使用i1得6行 7 r 假设 8 pr i 2，7 利用2行7行使用i 得8行 9 （pq）（pr）i28 10 （pq）（pr）e 3，4-6，7-9 在3行的基础上利用4-6，7-9 的结论用e 得出结论。i2i1ie2e1*48 否定规则否定规则 我们知道规则i与e的引入去消去规则只是为了证明过程中的需要
30、，目的是为了使推理保持真值。不能给出时，直接推出。定义：矛盾是形如或的表达式，其中是任意公式。例：pp，（pq）（pq），（rsq）（rsq）等 矛盾是逻辑中非常重要的，它的特点是：1）就真值而言，所有的矛盾式均是等价的 如：（rsp）（rsq）（pq）（pq）即：F F 2）任一合取式中只要有矛盾式出现则该式为矛盾式 如：12n，若i（1in）为矛盾式，则 公 式12n为矛盾式。3）矛盾式不仅能推出矛盾，矛盾还可以推导出任何公式*49例如：pp q p：月亮由绿色干酪构成 q：我喜欢撤有胡椒的比萨 即：比萨的口味与月亮的物质没有关系，日常生活 中很可笑，但在自然演艺中有此性质，即矛盾能 推导
31、出任何公式，所以说上述论断是有效的。同理：p：我去散步 q：教室里有十张桌子总结：如果前提是矛盾的，我们不关心前提是什么，那么我们从这个矛盾前提出发，可以得出任何想要的结论。Note：这至少有下列优点：1）可以与真值表示相匹配;2）（矛盾）可以证明论证中的任何编码公式。*50 注意：公式代表矛盾 形式为：（矛盾）可以证明论证中的任何编码公式。本身表示由非-消去证明规则编码的一 个矛盾。例：应用规则证明pqpq是有效的 Note：（pq=pq是等价公式，该公式称为联结词化归等价公式）1 pq 2 p 前提 q 前提 3 p 假设 p 假设 4 e3，2 q 复制2 5 q e4 pq i3-4
32、6 pq i3-5 7 pq e1，2-6ee*51 所以我们有：矛盾的假设不是真的，因此它必须是假的，规则i ：例：证明矢列pq，pq p是有效的 1 pq 前提 2 pq 前提 3 p 假设 4 q e1，3 5 q e2，3 6 e4，5 7 p i，3-6 Note：3-6行包含了规则i的全部信息。ie*52 例：使用矛盾公式作为唯一的前提，证明：矢列pp p是有效性 1 pp 前提 （注意：pq假，当且仅当 p真且q 假，所以pp永假）2 p 假设 3 p e1，2 .说明略 4 e2，3 5 p i，2-3 ：eei*53 例：不使用规则MT（反证规则），证明矢列。p（qr），p，
33、r q的有效性 1 p（qr）前提 2 p 前提 .说明略 3 r 前提 4 q 假设 .5 qr e1，2 6 r e5，4 7 e6，3 8 q i，4-7 ：eei*54 例：论证例1.1和1.2的论证 pqr，r，pq 1 pq r 前提 2 r 前提 说明略 3 p 前提 4 p 假设 .5 pq i 3，4 6 r e 1，5 7 e 6，2 8 q i，4-7 9 q e 8 派生规则：ieee*55 例：我们知道MT（反证规则）不是自然演绎的原始规则，而是由规则e，e和i推导出来的，下面我们对MT规则进行证明：即：MT 证：1 前提 2 前提 3 假设 4 e1，3 蕴涵消去
34、说明略 5 e4，2 6 i，3-5 ：eei*56 又例：证明派生规则（注意：它可以从规则i和e得到）证：1 前提 2 假设 略 3 e 1，2 4 i 2-3 现在派生反证法pBC（proof by contradiction）即：pBC（个规则与否定引入规则相反）ii*57 Note：pBC这个规则看起来与i类似，除了否定出现在不同位 置。这是从基本的证明规则出发得到了pBC的思路。即：假设我们有一个从到的证明，由i，可以把这个证 明转化为的一个证明。过程如下：1 已知 2 假设 3 e1，2 .4 i2-3 ：5 e4 总结：这说明pBC可以由i，i，e与e导出。下面介绍这节的最后一个
35、派生规则（排中律）LEM。eie*58 例：pq=T 也就是说是永真（真的）Note：排中律是十分重要的导出规则，也就是说是真的，不管它一定是什么，只能是真或假，当是假时，是真，没有第三种情况，所以说矢列 是有效的。在程序语言中if B C1 else C2 就是依赖BB为真这样 一个逻辑。例：证明排中律 1 （）假设 2 假设 3 i12 4 e3，1 5 i2-4 略 ：6 i25 7 e6，1 8 （）i1-7 9 e8 i1eii2e*59 例：使用LEM（排中律）证明pq pq是有效的 1 pq 前提 2 pp LEM （永真）3 p 假设 4 pq i13 5 p 假设 6 q e
36、1，5 .说明略 7 pq i26 8 pq e2，3-4，5-7i1ei2*602.2.3自然演绎总结自然演绎总结 1.i表示：证明，必须首先分别证明和，然后用i规则；2.e1表示：为了证明尝试证明，然后用e1 规则；3.i表示：为了证明，试着证明；4.e表示：如果已知道，要证明某个X，依次由和证明X；5.i表示：要证明，试从出发证明；6.i表示：为了证明，从出发证明。总之：要构建一个证明 前提 1）写出前提 （顶部）：2）结论 （底部）如：3）试着填充空白（规则使用部分）：前提 ：假设 ：i 结论*612.2.4逻辑等价逻辑等价 定义：设和是命题逻辑公式，我们说和是逻辑等价当 且仅当矢列和都是有效的。即：可以从出发证明，反之亦然，我们用“”表示 和是逻辑等价的。Note：有些教科书用“”表示 Note：就是指矢列式（）（）是有 效的。例如：（pq）pq （pq）pq pq qp pq pq pqp rr pq r p（qr）*62 Note：数理逻辑的等价公式的种类共有24种之多。1.双重否定律 2.等幂律 3.交换律 4.结合律 5.德.摩根律 6.分配律 7.零律 8.同一律 9.排中律 10矛盾律 ：24假言易位 这里就不作列举（同学们可以查数理逻辑的等价公式部分）