$('#loginbar').empty().append("您好，").append(userinfo).append(' 欢迎来到考试点网！ ').append(logout);
已有 10847 位老师主讲了
最新返现： 会员
点评了“”，返点评奖金
最新返现： 会员
点评了“”，返点评奖金
最新返现： 会员
点评了“”，返点评奖金
最新返现： 会员
点评了“”，返点评奖金
最新返现： 会员
点评了“”，返点评奖金
您的位置：&&&&&离散数学
作&&&&者：屈婉玲，耿素云，张立昂编著
出&版&社：高等教育出版社
出版时间：
版&&&&次：1页&&&&数：380字数：550000
包&&&&装：平装I S B N：0纸张：胶印纸
价&&&&格：?35
本书特色：
　　以教育部计算机科学与技术教学指导委员会制订的计算机科学与技术专业规范为指导，内容涵盖计算机科学技术中常用离散结构的数学基础。
　　紧密围绕离散数学的基本概念、基本理论精炼选材，体系严谨，内容丰富；面向计算机科学技术，介绍了很多离散数学在计算机科学技术中的应用。
　　强化描述与分析离散结构的基本方法与能力的训练，配有丰富的例题和习题；例题有针对性，分析讲解到位；习题难易结合，适合学生课后练习。
　　知识体系采用模块化结构，可以根据不同的教学要求进行调整；语言通俗易懂，深入浅出、突出重点、难点，提示易于出错的地方。
　　辅助教学资源丰富，配有用于习题课、包含上千道习题的教学辅导用书《离散数学学习指导与习题解析》，PPT电子教案，教学资源库等。
本书起源于高等教育出版社1998年出版的《离散数学》，是教育部高等学校“九五”规划教材，2004年作为“十五”规划教材出版了修订版。作为“十一五”规划教材，根据教育部计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范》（CCC2005）的教学要求，本教材对内容进行了较多的调整与更新。
　　本书分为数理逻辑、集合论、代数结构、组合数学、图论、初等数论等六个部分。全书既有严谨的、系统的理论阐述，也有丰富的、面向计算机科学技术发展的应用实例，同时选配了大量的典型例题与练习。各章内容按照模块化组织，可以适应不同的教学要求。与本书配套的电子教案和习题辅导用书随后将陆续推出。
　　本书可以作为普通高等学校计算机科学与技术专业不同方向的本科生的离散数学教材，也可以供其他专业学生和科技人员阅读参考。
命题逻辑的基本概念
命题与联结词
命题公式及其赋值
命题逻辑等值演算
析取范式与合取范式
联结词的完备集
可满足性问题与消解法
命题逻辑的推理理论
推理的形式结构
自然推理系统P
一阶逻辑基本概念
一阶逻辑命题符号化
一阶逻辑公式及其解释
一阶逻辑等值演算与推理
一阶逻辑等值式与置换规则
一阶逻辑前束范式
一阶逻辑的推理理论
集合的基本概念
集合的运算
有穷集的计数
集合恒等式
有序对与笛卡儿积
关系的运算
关系的性质
关系的闭包
等价关系与划分
函数的定义与性质
函数的复合与反函数
双射函数与集合的基数
一个电话系统的描述实例
二元运算及其性质
代数系统的同态与同构
群的定义及其性质
子群与群的陪集分解
循环群与置换群
　第十一章
格与布尔代数
格的定义与性质
分配格、有补格与布尔代数
　第十二章
基本的组合计数公式
加法法则与乘法法则
排列与组合
二项式定理与组合恒等式
多项式定理
　第十三章
递推方程与生成函数
递推方程的定义及实例
递推方程的公式解法
递推方程的其他解法
生成函数及其应用
指数生成函数及其应用
Cata1an数与Stir1ing数
　第十四章
图的基本概念
通路与回路
图的连通性
图的矩阵表示
　第十五章
欧拉图与哈密顿图
最短路问题与货郎担问题
　习题十五
　第十六章
无向树及其性质
根树及其应用
　第十七章
平面图的基本概念
平面图的判断
平面图的对偶图
　习题十七
　第十八章
支配集、覆盖集、独立集、匹配与着色
支配集、点覆盖集与点独立集
边覆盖集与匹配
二部图中的匹配
地图着色与平面图的点着色
　第十九章
最大公约数与最小公倍数
一次同余方程
欧拉定理和费马小定理
初等数论在计算机科学技术中的几个应用
名词与术语索引
考试点：?599
考试点：?399
考试点：?0
考试点：?880
考试点：?780
考试点：?880
考试点：?880
考试点：?880
考试点：?880
考试点：?1980
考试点：?1680
考试点：?1680
考试点：?1980
考试点：?1280
考试点：?599
考试点：?399
考试点：?0
考试点：?128
考试点：?0当前位置： >>
左孝凌离散数学课件2.6前束范式-2.7谓词演算的推理理论
离散数学(Discrete Mathematics)1第二章 谓词逻辑2.1谓词的概念与表示 2.2命题函数与量词 2.3谓词公式与翻译 2.4变元的约束 2.5谓词演算的等价式与蕴含式 2.6前束范式 2.7谓词演算的推理理论22. 6前束范式在命题演算中，常常要将公式化成规范 形式，对于谓词演算也有类似情况。一个谓 词公式可以化为与它等价的范式。这里主要 介绍前束范式的基本概念及方法32. 6前束范式前束范式? 定义:任何一个谓词公式A，如果具有如下形式： (□x1) (□x2)… (□xn)B 其中□可能是量词?或量词?，xi（i=1，… n）是客体变 元，B是不含量词的谓词公式，则称A是前束范式。 ? 说明:C 前束范式的量词均在全式的开头 C 前束范式量词的作用域延伸到整个公式的末尾。? 例1: 判断是否是前束范式 ?x?y（（F(x)∧G(y)）∧? H(x,y)） √ ?x?y(F(x,y)∧G(y,z))∨ ?x H(x,y,z) ×42. 6前束范式? 定理:任何一个谓词公式,均和一个前束范式等价。前束范式的求法：? 设谓词公式为W ? 将W等价转化为只含有联结词，∧，∨的谓词公式 ? 否定深入。即利用量词转化公式，把否定联结词深入到命题 变元和谓词填式的前面。 ? 改名。即利用换名规则、代入规则更换一些变元的名称，以 便消除混乱。 ? 量词前移。即利用量词辖域的收缩与扩张把量词移到前面（?x）（A(x)∨B）?（?x）A(x)∨B （?x）（A(x)∨B）?（?x）A(x)∨B （?x）（A(x)∧B）?（?x）A(x)∧ B （?x）（A(x)∧B）?（?x）A(x)∧B这样便可求出与公式等价的前束范式。52. 6前束范式例2:求下列公式的前束范式。(1) (?x) F ( x) ? ?(?x)G ( x) (2) (?x) F ( x) ? ?(?x)G ( x) (3) (?x) F ( x) ? ?(?x)G ( x) (4) (?x) F ( x) ? ?(?x)G ( x) (5) ((?x) F ( x, y ) ? (?y )G ( y )) ? (?x) H ( x, y ) (6) ?(?x){(?y ) A( x, y ) ? (?x)(?y )[B ( x, y ) ? (?y )( A( y, x) ? B ( x, y ))]}62. 6前束范式? 解:(1) (?x) F ( x) ? ?(?x)G( x) ? (?x) F ( x) ? (?x)?G( x)(量词转换律) ? (?x)(F ( x) ? ?G( x))(量词分配)(2) (?x) F ( x) ? ?(?x)G ( x) ? (?x) F ( x) ? (?x)?G ( x)(量词转换律) ?x(A(x)∨B(x)) ≠ ? (?x) F ( x) ? (?y )?G ( y )(换名) ? (?x)(F ( x) ? (?y )?G ( y ))(辖域扩张) ? (?x)(?y )(F ( x) ? ?G ( y ))(辖域扩张)?x A(x)∨ ?x B(x)7(3) (?x) F ( x) ? ?(?x)G ( x) ? ?(?x) F ( x) ? ?(?x)G ( x) ? (?x)?F ( x) ? (?x)?G ( x) ? (?x)?F ( x) ? (?y )?G ( y ) ? (?x)(?y )(?F ( x) ? ?G ( y ))(4) (?x) F ( x) ? ?(?x)G ( x) ? ? (?x) F ( x) ? ?(?x)G ( x) ? (?x)? F ( x) ? (?x)?G ( x) ? (?x)? F ( x) ? (?y )?G ( y ) ? (?x)(?y )(? F ( x) ? ?G ( y ))2. 6前束范式(5) ? ? ? ((?x) F ( x, y ) ? (?y )G ( y )) ? (?x) H ( x, y ) ?(?(?x) F ( x, y ) ? (?y )G ( y )) ? (?x) H ( x, y ) ((?x) F ( x, y ) ? ?(?y )G ( y )) ? (?x) H ( x, y ) ((?x) F ( x, y ) ? (?y )?G ( y )) ? (?x) H ( x, y )自由 变元 谓词不同，变 元名称冲突? ((?x) F ( x, z ) ? (?y )?G ( y )) ? (?x) H ( x, z )(代入) ? ((?x) F ( x, z ) ? (?y )?G ( y )) ? (?t ) H (t , z )(换名)? (?x)(?y )(F ( x, z ) ? ?G ( y )) ? (?t ) H (t , z )(辖域扩张) ? (?x)(?y )((F ( x, z ) ? ?G ( y )) ? (?t ) H (t , z ))(辖域扩张) ? (?x)(?y )(?t )((F ( x, z ) ? ?G ( y )) ? H (t , z ))(辖域扩张)9第二章 谓词逻辑（Predicate Logic）2. 6前束范式(Prenex normal form)?(6) ?(?x ){( ?y ) A( x, y ) ? (?x )(?y )[ B ( x, y ) ? (?y )( A( y , x ) ? B ( x, y ))]}? ? (?x )?{?(?y ) A( x, y ) ? ( ?x )(?y )[ B ( x, y ) ? (?y )(?A( y , x ) ? B ( x, y ))]} (?x ){( ?y ) A( x, y ) ? (?x )(?y )[?B ( x, y ) ? ( ?y )( A( y , x ) ? ?B ( x, y ))]}? (?x ){( ?y ) A( x, y ) ? (?z )(?u )[?B ( z , u ) ? (?r )( A( r , z ) ? ?B ( z , r ))]} ? (?x )(?y )(?z )(?u ){ A( x, y ) ? [?B ( z , u ) ? (?r )( A( r , z ) ? ?B ( z , r ))]} ? (?x )(?y )(?z )(?u )(?r ){ A( x, y ) ? [?B ( z , u ) ? ( A( r , z ) ? ?B ( z , r ))]}102. 6前束范式前束合取范式? 定义 : 任何一个谓词公式 A ，如果具有如下形式则称为 前束合取范式： (□x1)(□x2)…(□xn)[(A11∨A12∨…∨A1k1)∧ (A21∨A22∨…∨A2k2 )∧…∧(Am1∨Am2∨…∨Amkm)] 其中n大于等于1,Aij(j=1, …,ki ,i=1,2,3,…,m)为原子谓词 公式或其否定,□为量词?或量词?， xi（i=1，… n）为 客体变元. 例如：(?x)(?u )(?z )((P (x ) ? P (u )) ? (P (x )? Q ( y , z ))? (?Q (x , y )? P (u ))? (?Q (x , y )? Q (y , z )))(?x)(?z )(?y ){[?P ? (x ? a ) ? (z ? b)] ? [Q ( y ) ? (a ? b )]}112. 6前束范式前束析取范式? 定义 : 任何一个谓词公式 A ，如果具有如下形式则称为 前束析取范式： (□x1) (□x2)…(□xn)[(A11∧A12∧…∧A1k1)∨ (A21∧A22∧…∧A2k2 )∨…∨(Am1∧Am2∧…∧Amkm)] 其中n大于等于1,Aij(j=1, …,ki ,i=1,2,3,…,m)为原子谓词公 式或其否定,□为量词?或量词?， xi（i=1，… n）为客 体变元. 例如： (?x)(?u )(?z )((P (x ) ? ?Q (x , y )) ? (P (u ) ? Q ( y , z ))122. 6前束范式定理:每一个谓词公式都可以转化为与其等价的前束析(合)取范式. (?x)[(?y) P( x) ? (?z)Q( z, y) ? ?(?y) R( x, y)] 例题4 将wff D： 转化为与其等价的前束合取范式。解 第一步取消多余量词D ? (?x)[ P( x) ? (?z)Q( z, y) ? ?(?y) R( x, y)]第二步换名D ? (?x)[ P( x) ? (?z)Q( z, y) ? ?(?w) R( x, w)]第三步消去条件联结词D ? (?x)[?( P( x) ? (?z)Q( z, y)) ? ?(?w) R( x, w)]第四步将否定深入D ? (?x)[?P( x) ? (?z)?Q( z, y)) ? (?w)?R( x, w)]第五步将量词推到左边D ? (?x)(?z)(?w)[(?P( x) ? ?Q( z, y)) ? ?R( x, w)]?(?x)(?z)(?w)[(┐P(x)∨┐R(x,w))∧(┐Q(z,y)∨┐R(x,w))]2. 6前束范式例题4 将wffD： (?x)( P( x) ? Q( x, y)) ? ((?y) P( y) ? (?z)Q( y, z)) 转化为与其等价的前束析取范式。解 D ? ?(?x)(?P( x) ? Q( x, y)) ? ((?y) P( y) ? (?z )Q( y, z ))? (?x)( P( x) ? ?Q( x, y)) ? ((?u) P(u) ? (?z)Q( y, z))? (?x)(?u)(?z)( P( x) ? ?Q( x, y)) ? ( P(u) ? Q( y, z))2. 6前束范式练习:求下列公式的前束析取范式和前束合取范式.(1) ((?x) F ( x, y) ? (?y)G( y )) ? (?x) H ( x, y) (2) ?(?x){(?y) A( x, y ) ? (?x)(?y)[B( x, y ) ? (?y)( A( y, x) ? B( x, y))]}解:152. 6前束范式小结：本节介绍了谓词公式的前束范式、前束 析取范式和前束合取范式.重点掌握前束析 取范式和前束合取范式求法。作业: P75 (2) b，d162.7谓词演算的推理理论2.7谓词演算的推理理论(Inference theory of predicate calculus) 2.7.1推理规则(Rules of inference) 2.7.2证明举例 (Examples of proof)172.7谓词演算的推理理论推理规则在谓词演算中，推理的形式结构仍为 H1?H2?H3?....?Hn?C若 H1?H2?H3?....?Hn?C是永真式，则称由前提H1,H2,H3,.…,Hn逻辑的推出结论C，但在谓词逻辑中, H1,H2,H3,.…,Hn , C均为谓词公式。命题演算中的推理规则，可在谓词推理理论中应用。182.7谓词演算的推理理论与量词有关的四条重要推理规则： 1、全称指定规则（US规则） 2、全称推广规则（UG规则） 3、存在指定规则（ES规则） 4、存在推广规则（EG规则） 注意：只能对前束范式适用上述规则。192.7谓词演算的推理理论? 1. 全称指定规则（ US ）： ?x P(x) ∴P(c) 使用此规则时要注意： （1）P是谓词 ； （2） c是论域中的某个任意的客体.202.7谓词演算的推理理论? 2.全称推广规则（UG）： P(y) ∴ ?x P(x) 使用此规则时注意: (1) y在P(y)中自由出现，且y取任何值时P均为 真。 (2) x不在A(y)中约束出现.212.7谓词演算的推理理论? 3.存在指定规则(ES): ?x P(x) ∴ P(c) 注:c是论域中的某些客体,c并不是任意的使用此规则时应注意：（1）c 是使P为真的特定客体；（2）如果P(x)中有其他自由变元出现，且x是 随其他自由变元变化的，那么不能使用此规则。222.7谓词演算的推理理论(4)存在推广规则(EG): P(c)∴ ?x P(x)使用此规则时注意: (1) c是个体域中某个确定的个体。 (2) 代替c的x不能已在A(c)中出现。232.7谓词演算的推理理论例1证明苏格拉底三段论:凡是人都是要死的。苏格拉底是 人。苏格拉底是要死的。 设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。则： 前提：?x(M(x)?D(x))，M(a）. 结论： D(a) . 证明：① ?x (M(x)?D(x)) P ② M(a)?D(a) US ① ③ M(a) P ④ D(a) T② ③ I11 (直接证法)242.7谓词演算的推理理论例2:前提：?x(F(x)∨G(x))， 结论： ?x F(x) . 证明：① ? ?x G(x) ② ?x ? G(x) ③ ? G(a) ④ ?x(F(x)∨G(x)) ⑤ F(a)∨G(a) ⑥ F(a) ⑦ ?x F(x) ? ?x G(x).P T① 置换规则 US ② P US ④ T③ ⑤,I EG ⑥252.7谓词演算的推理理论例3:前提： ?x (A(x)?B(x))， ?x A(x) 结论： ?x B(x) 证明：① ?x A(x) P前提引入② A(c) ES ① ③ ?x (A(x)?B(x)) P前提引入 ④ A(c)?B(c) US ③ ⑤ B(c) T② ④ ⑥ ?x B(x) EG ⑤ 注意： ① ③引入的顺序不可更改！262.7谓词演算的推理理论例4:前提：?x(F(x)∨G(x)), ?x(? 结论： ?x F(x) .(归谬法) 证明：① ? ?x F(x) ② ?x ? F(x) ③ ? F(a) ④ ?x(F(x) ∨ G(x)) ⑤ F(a) ∨ G(a) ⑥ G(a) ⑦?x(? R(x)∨ ? G(x)) ⑧ ? R(a)∨ ? G(a) ⑨ ? R(a) ⑩ ?x R(x) (11) R(a) (12) ? R(a) ∧ R(a) R(x)∨ ? G(x)), ?x R(x).P结论否定引入 T① ES ② P US ④ T③⑤ P US ⑦ T⑥ ⑧ P US ⑩ 矛盾式272.7谓词演算的推理理论例5:证明: ?x(P(x)∨Q(x))=&?(?x)P(x) ?(?x)Q(x) (附加前提法)证明：(1) ?(?x)P(x)P(附加前提) (2) (?x)?P(x) T(1) (3) ?P(c) ES(2) (4) ?x(P(x)∨Q(x)) P (5) P(c)∨Q(c) US(4) (6) Q(c) T(3)(5) (7)(?x)Q(x) EG(6) (8) ?(?x)P(x) ?(?x)Q(x) CP282.7谓词演算的推理理论小结：本节介绍了谓词演算的推理规则,并举例说明了它 们的应用. 重点:深刻理解四个推理规则,会应用它们推 理证明. 作业: P79 (1)d,(2) a,(3)a29
赞助商链接
-6- 离散数学标准化作业纸 专业班级 学号 姓名 第...一阶逻辑的等值演算与推理一、设个体域 D={a,b,...(x) →?y G(y) 二、求下列公式的前束范式 (1...离散数学重点难点_理学_高等教育_教育专区。第一篇 ...前束范式 第五节.谓词演算的推理理论 本章重点、...第一节集合的概念和表示法 第二节集合间的关系 第...离散数学_数学_自然科学_专业资料。第一章 命题逻辑...蕴 含的性质 1-6 其他联结词 其他联结词:不可兼...化为前束范式的步骤 2-7 谓词演算的推理理论 量词...《离散数学》 左孝凌等编著 上 海科学技术出版社 ...谓词演算的等价式与蕴含式 2.6 前束范式(前束合取...2.7 谓词演算的推理理论 第二章习题讲解 8 4 理论...一阶谓词演算、消解原理 离散数学被分成三门课程进行...2.7 命题演算的推理理论 2.7.1 有效推理的概念 2.7...谓词公式的前束范式 谓词演算推理理论 消解原理 2-5...二、教学基本要求“离散数学”课程共分为四个部分,...谓词演算的推理理论 第五节 前束范式 教学重点: ...(6 学时) 教学方式:课堂多媒体课件教学+传统式...掌握离散数学的的基本推理与证明过程、基本算法及应用...20 2 3 3 2 10 13 17 16 2 48 流媒体课件 ...谓词公式的解释 范式(前束范式)的概念与求法 谓词...离散数学例题2_理学_高等教育_教育专区。离散数学量词...演算简单;但在 中量词辖域可以缩小 先缩小量词辖域,...后两步结果都是前束范式,说明公式的前束范式不惟一....离散数学习题五_理学_高等教育_教育专区。习题五 1...为什么? 解:在前束范式中,否定联结词不能在量词...6 假言推理 7EG 前提引入 1 2 假言推理 5 (F ...离散数学习题整合_理学_高等教育_教育专区。CH01 ...(演算的每一步都要写依据) §1.4 范式 6. (每...2.11(3) 8 求公式 xF(x)G(x) 的前束范式。...
All rights reserved Powered by
www.tceic.com
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。《离散数学（第5版）》(耿素云，屈婉玲，张立昴)【摘要 书评 试读】- 京东图书
离散数学（第5版）
京 东 价 &
[定价 &￥]
PLUS会员专享价
您购买此商品可享受专属价
增值业务 &
重　　量 &
搭配赠品 &
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
商品介绍加载中...
扫一扫，精彩好书免费看
权利声明：京东上的所有商品信息、客户评价、商品咨询、网友讨论等内容，是京东重要的经营资源，未经许可，禁止非法转载使用。
注：本站商品信息均来自于合作方，其真实性、准确性和合法性由信息拥有者（合作方）负责。本站不提供任何保证，并不承担任何法律责任。
印刷版次不同，印刷时间和版次以实物为准。
价格说明：
京东价：京东价为商品的销售价，是您最终决定是否购买商品的依据。
划线价：商品展示的划横线价格为参考价，该价格可能是品牌专柜标价、商品吊牌价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或该商品在京东平台上曾经展示过的销售价；由于地区、时间的差异性和市场行情波动，品牌专柜标价、商品吊牌价等可能会与您购物时展示的不一致，该价格仅供您参考。
折扣：如无特殊说明，折扣指销售商在原价、或划线价（如品牌专柜标价、商品吊牌价、厂商指导价、厂商建议零售价）等某一价格基础上计算出的优惠比例或优惠金额；如有疑问，您可在购买前联系销售商进行咨询。
异常问题：商品促销信息以商品详情页“促销”栏中的信息为准；商品的具体售价以订单结算页价格为准；如您发现活动商品售价或促销信息有异常，建议购买前先联系销售商咨询。
iframe(src='//www.googletagmanager.com/ns.html?id=GTM-T947SH', height='0', width='0', style='display: visibility:')扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
求离散数学的前束范式ExP(x)→VxQ(x) (V表示任取,E表示存在,表示非,我这里符号打不出来）
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
为您推荐：
其他类似问题
扫描下载二维码当前位置： >>
绪言离散数学（又称计算机数学）是现代数学的重要 分支，是计算机专业课程中的核心基础课程之 一。 离散数学以是研究：离散量的结构和相互之间的 关系为主要目标，其研究对象一般为：有限或 可数个元素（例如：自然数、整数、真假值、 有限个结点等），而离散性也是计算机科学的 显著特点。1绪言离散数学与计算机科学的其他课程 如：数据结构、操作系统、编译原理、算法分 析、逻辑设计、系统结构、容错技术、人工智 能等有密切的联系。它是这些课程的先导和基 础课程。2主要参考书n《离散数学》q上海科学技术文献出版社n左孝凌等编著n《离散数学》q电子工业出版社n朱一清编著n《离散数学》q北京大学出版社n耿素云、屈婉玲、方新贵编著3绪言本课程根据大纲的内容和相 关独立性，可分为四大部 分 第一部分 数理逻辑 （书上 第一 篇）包括第一章：命 题逻辑和第二章：谓词逻 辑 第二部分 集合论 （书上 （第二篇）：第三章：集 合与关系；第四章：函 数 ） 第三部分 代数系统 (书上 （第三篇）：第五章:代数 结构； 第六章：格和布尔 代数 ) 第四部分 图 论 （书 （第四篇）：第七章:图 论） 讲课时数：64小时如果时间 允许，我们会增加离散数 学在计算机中的应用（形 式语言与自动机、纠错码 等等）4绪言本课程有二个特点： （１）定义、定理多。 本课内容＝（定义）＋（定理）＋（例题） （２）课外作业较多，没有上机实验。 为了学好这门课，特提出三点要求： 弄懂定义、定理，弄懂例题，加深对定义、定理的理 解； 在复习基础上，做好课外作业。同学之间可以讨论， 但要弄懂弄通后再做。 做好课堂笔记、讲课内容和次序，从系统角度讲和讲 义大致相同，但内容上可能有一些不同。5绪言最后，做两点说明和一个要求： （1）考试内容以课堂上讲的为范围； （2）每次课后均布置作业。希望大家认真完 成。 一要求： 为搞好教学，双方努力。6第一篇 数理逻辑逻辑学：研究思维形式及思维规律的科学。 逻辑学分为二类： 辩证逻辑：是研究事物发展的客观规律。 形式逻辑：对思维的形式结构和规律进行研究。 数理逻辑：是用数学的方法研究概念、判断和推 理的科学，显然数理逻辑是属于形式逻辑 的范畴。7第一篇 数理逻辑在数理逻辑中，用数学的方法是指引进一套符号 体系的方法来研究概念、判断和推理。即对符 号进行判断和推理。 数理逻辑分为四大分支：证明论、模型论、递归 论和公理集合论。我们这里介绍的是属于四大 分支的共同基础――古典数理逻辑(命题逻辑 和谓词逻辑)。8第一章 命题逻辑§1.命题 §2.命题联结词 §3.命题变元与命题公式 §4.等价式 §5.永真蕴含式 §6.命题联结词总结 §7.范 式 和 判 定 §8.推论规则和证明方法1§1命题《定义》： 具有唯一真值的陈述句叫命题。 讨论定义： （１）命题可以是真的，或者是假的，但不 能同时为真又为假。 （２）命题分类： )原子命题（基本命题、本原命题）：一个 命题，不能分解成为更简单的命题。 例：我是一位学生。2§1命题)分子命题（复合命题）：若干个原子命题使用适当的 联结词所组成的新命题 例：我是一位学生和他是一位工人 (3)命题所用符号：常用大写２６个英文字母表示命题。 用Ａ、Ｂ、Ｃ．．．．Ｚ表示。 (4)命题中所有的“真”用“Ｔ”表示， 命题中所有的“假”用“Ｆ”表示。3§1命题例：判断下列语句是否为命题。 ＊ 陈述句一般为命题 （1）十是整数。 （Ｔ） （2）上海是一个村庄。（Ｆ） （3）今天下雨。 （4）加拿大是一个国家。（Ｔ） （5）２是偶数而３是奇数。 （6）她不是护士。 （7）１＋１０１＝１１０ （8）今天是星期天。4§1命题命令句，感叹句，疑问句均不是命题。 （1）把门关上！ （2）你到哪里去？ 语句既为真，同时又包含假的不是命题，这样的 句子称为“悖论”。 （3）他正在说谎。 （在命题逻辑中不讨论这类问题）5§2命题联结词在命题演算中也有类似的日常生活中的联结词称 做：“命题联结词”下面先介绍五个常用的命题 联结词。 １．否定词：（否定运算、非运算） （１）符号 ? ,读作“非”，“否定” 设命题为Ｐ，则在Ｐ的前面加否定词? ，变成? Ｐ， ?Ｐ读做“Ｐ的否定”或“非Ｐ”6§2命题联结词（２）定义：严格由真值表定义 P ?P （３）举例： T F Ｐ：北京是一座城市。 ?Ｐ：北京不是一座城市。 F T Ｑ：每一种生物均是动物。F ?Ｑ：有一些生物不是动物。T 这里?Ｑ不能讲成“每一种生物都不是动物”为假 命题了。 对量化命题的否定，除对动词进行否定外，同 时对量化词也要加以否定。7§2命题联结词２．合取词（“合取”、“积”、“与”运算） 符号 “Λ” 设Ｐ，Ｑ为两个命题，则ＰΛＱ称Ｐ与Ｑ的合 取，读作：“Ｐ与Ｑ”、“Ｐ与Ｑ的合取”、“Ｐ 并且Ｑ”等。 定义（由真值表给出）：8§2命题联结词ＰΛＱ真值表如下 ：P F F T TQ F T F TPΛ Q F F F TQΛP F F F T9§2命题联结词当且仅当Ｐ和Ｑ的真值均为“Ｔ”，则（ＰΛＱ） 的真值为“Ｔ”。否则，其真值为“Ｆ”。 注意：Ｐ和Ｑ是互为独立的；地位是平等的，Ｐ 和Ｑ的位置可以交换而不会影响ＰΛＱ的结 果。10§2命题联结词举例： (a) P：王华的成绩很好 Q：王华的品德很好。 则ＰΛＱ：王华的成绩很好并且品德很好。 (b) P：我们去种树 Q：房间里有一台电视机 则ＰΛＱ：我们去种树与房间里有一台电视 机。11§2命题联结词(c) P：今天下大雨 Q：3+3=6 则ＰΛＱ：今天下大雨和3+3=6 由例(b)(c)可见，在日常生活中，合取词应用在二 个有关系的命题之间。而在逻辑学中，合取词 可以用在二个毫不相干的命题之间。12§2命题联结词(d) 下列语句不是合取联结词组成的命题。 P: 王大和王二是亲兄弟。 Q: 他打开箱子然后（而后）拿出一件衣服来。13§2命题联结词３．析取词（或运算） （１）符号“∨” 设Ｐ、Ｑ为二个命题，则（Ｐ∨Ｑ）称作Ｐ与Ｑ 的“析取”，读作：“Ｐ或Ｑ”。 （２）定义（由真值表给出）：14§2命题联结词当且仅当Ｐ、Ｑ均为“Ｆ”时，（Ｐ∨Ｑ）为 “Ｆ”。否则，其真值为“Ｔ”．Ｐ∨Ｑ真值表 如右：P F F T TQ F T F TP∨ Q F T T T15§2命题联结词区分“可兼或”与“不可兼或（异或，排斥或）” 析取词为可兼或即:P和Q均为“T”时（P∨Q） 为“T” 例如： 灯泡有故障或开关有故障。 今晚写字或看书。 今天下雨或打雷。 以上例句均为可兼或。16§2命题联结词“不可兼或”中当P和Q均为“T”时，则P异或Q为 “F”。 （异或用“”表示） PF F T TQF T F TPQ F T T F17§2命题联结词例： 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。 以上两句均为不“可兼或”。18§2命题联结词４．单条件联结词：（“蕴含”联结词、蕴含词） （１）符号“→”，读作：“如果…则…”、“蕴含” Ｐ、Ｑ为二个命题，（Ｐ→Ｑ）为新的命题，读 作：“如果Ｐ则Ｑ”，“Ｐ蕴含Ｑ”，“Ｐ仅当Ｑ”， “Ｑ当且Ｐ”，“Ｐ是Ｑ的充分条件”。 （２）定义19§2命题联结词（由真值表定义）：P F F T T Q F T F T P→Q T T F T20§2命题联结词当Ｐ为“Ｔ”，Ｑ为“Ｆ”时，则 （Ｐ→Ｑ）为“Ｆ”，否则（Ｐ→Ｑ）均为“Ｔ”。 Ｐ：称为前件、条件、前提、假设 Ｑ：称为后件、结论。 （３）举例： P：我拿起一本书 Q：我一口气读完了这本书21§2命题联结词P→Q：如果我拿起一本书，则我一口气读完了 这本书。 (b) P：月亮出来了 Q：3×3=9 P→Q：如果月亮出来了，则 3×3=9。 通常称：(a)为形式条件命题。 ――前提和结果有某种形式和内容上的联系。22§2命题联结词(b)为实质条件命题。――前提和结果可以有联 系，也可以没有联系，只要满足单条件命题的 定义。 所以,是形式条件命题一定是实质条件命题,反之 不一定。“→”是实质条件命题。 例： Ｐ：我买到了鱼；Ｑ:我吃鱼。23§2命题联结词Ｐ→Ｑ：如果我买到了鱼，则我吃鱼。 但“如果我没买到鱼，则我吃鱼”，这在日常生 活中是不可能的，但在单条件命题的定义中是 允许的。24§2命题联结词可以证明： Ｐ→Ｑ? ? Q →? P 原命题 逆反命题 Ｑ→Ｐ? ?Ｐ→?Ｑ 逆命题 反命题25§2命题联结词列出真值表,由真值表得： 原命题?逆反命题；逆命题?反命题。P Q P→Q ? Q→?P Ｑ→P F F T F T T T F F T T T T T F T T F T T ?Ｐ→?Ｑ T F T T26§2命题联结词５．双条件联结词（“等价”词、“同”联结词、“等 同”词） （１）符号“?” 设Ｐ、Ｑ为二个命题，则Ｐ?Ｑ读作：“Ｐ当且 仅当Ｑ”，“Ｐ等价Ｑ”,“Ｐ是Ｑ的充分必要条 件”。 （２）定义（见真值表）：27§2命题联结词真值表: P 每当Ｐ和Ｑ的真值相同 时，则（Ｐ?Ｑ）的真 值为“Ｔ”，否则（Ｐ? Ｑ）的真值为“Ｆ”。 F F T T Q F T F T P?Q T F F T28§2命题联结词（３）举例： （a）设 Ｐ：△ABC是等腰三角形 Ｑ：△ABC有两只角相等 Ｐ?Ｑ：△ABC是等腰三角形当且仅当△ABC中 有两只角相等。29§2命题联结词（b）下面均为等价联结词： ? 春天来了当且仅当燕子飞回来了。 ?平面上二直线平行，当且仅当这二直线不相 交。 ?２＋２＝４当且仅当雪是白色的。30§2命题联结词（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、 Ｑ交换位置不会改变真值表中的值。 （５）Ｐ当且仅当Ｑ Ｐ?Ｑ Ｐ仅当Ｑ Ｐ→Ｑ Ｐ当且Ｑ Ｑ→Ｐ31§2命题联结词６．命题联结词在使用中的优先级 （１）先括号内，后括号外 （２）运算时联结词的优先次序为： ? → ? （由高到低）Λ∨32§2命题联结词（３）联结词按从左到右的次序进行运算 例 ?Ｐ∨（Ｑ∨Ｒ）可省去括号 因为“Ｖ”运算是可结合的。 （ ?Ｐ∨Ｑ）∨Ｒ可省去括号 因为符合上述规 定 而Ｐ→（Ｑ→Ｒ）中的括号不能省去，因为“→” 不满足结合律。33§2命题联结词（４）最外层的括号一律均可省去 （Ｐ→Ｑ∨Ｒ）可写成Ｐ→Ｑ∨Ｒ ７．命题联结词小结： （１）五个联结词的含义与日常生活中的联结词 的含义大致相同。 （２）“或”可分为可兼或（∨）和异或（
） （不可兼或）34§2命题联结词(3) 除“?”为一元运算外，其余四个均为二元运 算。 (4) “→”分为形式条件和实质条件命题，当前件 为“Ｆ”时，不论后件怎样，则单条件命题的真 值均为“Ｔ”。 (5)命题联结词是命题或命题之间的联结词，而 不是名词之间、数字之间和动词之间的联结 词。35§2命题联结词以上介绍了五种常用的联结词及其相应的复合命 题形式。数理逻辑的特点是把逻辑推理变成类 似数学演算的完全形式化了的逻辑演算，为 此，首先要把推理所涉及到的各命题符号化。 步骤如下： ①找出各简单命题，分别符号化。 ②找出各联结词，把简单命题逐个联结起来。36§2命题联结词例. 将下列命题符号化： （1）李明是计算机系的学生，他住在312室或 313室。 （2）张三和李四是朋友。 （3）虽然交通堵塞，但是老王还是准时到达了 车站。 （4）只有一个角是直角的三角形才是直角三角 形。 （5）老王或小李中有一个去上海出差。37§2命题联结词解： （1）首先用字母表示简单命题。 P：李明是计算机系的学生。 Q：李明住在312室。 R：李明住在313室。 该命题符号化为：P∧（QR） （2）张三和李四是朋友。是一个简单句 该命题符号化为：P38§2命题联结词（3）首先用字母表示简单命题。 P：交通堵塞。 Q：老王准时到达了车站。 该命题符号化为：P∧Q （4）首先用字母表示简单命题。 P：三角形的一个角是直角。 Q：三角形是直角三角形。 该命题符号化为：?P→ ?Q39§2命题联结词（5）首先用字母表示简单命题。 P：老王去上海出差。 Q：小李去上海出差。 该命题符号化为：P
Q 也可符号化为： （P∧?Q）∨（?P∧Q）或者 （P ∨ Q） ∧ ? （P∧Q）40§３命题公式约定：（１）我们只注意命题的真假值，而不再去注意命题的 汉语意义。 （２）对命题联结词，我们只注意真值表的定义，而不 注意它日常生活中的含义。 １．命题公式 命题常元：表示确定的命题｛T，F｝。 命题变元：以真假为其变域之变元，或没有指定真值的 命题。常用大写英文字母Ａ…Ｚ表示。41§３命题公式命题公式：由命题变元、常元、联结词、括 号，以规定的格式联结起来的字符串。 《定义》：命题公式可按下述法则来生成： １）孤立的命题变元是一个命题公式。 ２）若Ａ是命题公式，?Ａ也为命题公式。 ３）若Ａ、Ｂ是命题公式，则（ＡΛＢ）、（Ａ ∨Ｂ）、（Ａ→Ｂ）、（Ａ?Ｂ）均为命题公 式。42§３命题公式４）当且仅当有限次使用 （１）（２）（３）所生成的公式才是命题公式。 例如：(?(P ∨Q))，(P→(Q →R))，((PΛQ)?R)，P都是命 题公式。而(P→)，(P∨?)都不是命题公式 ２．命题公式的真值表 : 命题变元用特定的命题来取代，这一过程称为对该命题变元 进行指派。 命题公式可以看成是一个以真假值为定义域和真假值为值域 的一个函数。 写成ｙ＝ｆ(x)43§３命题公式例如：公式 P →(Q →R) 定义三元函数 Y(P，Q，R)＝ P →(Q →R) 《定义》：命题公式A在其所有可能的赋值下取得的值列成 的表称为A的真值表。 构造真值表的步骤如下： 1)找出给定命题公式中所有的命题变元，列出所有可能的赋 值。 2)按照从低到高的顺序写出命题公式的各层次。 3)对应每个赋值，计算命题公式各层次的值，直到最后计算 出整个命题公式的值。44§３命题公式例１．构造命题公式?（（Ｐ∨Ｑ）Λ Ｐ）的真值表：P ∨Q （Ｐ∨Ｑ）ΛＰ ?（（Ｐ∨Ｑ）ΛＰ）P QFF F FT T TF T TT TF F T TT T F F45§３命题公式P Q R Ｐ∨（ＱΛＲ)F F F F F T F T F F T T T F F T F T T T F T T TF F F T T T T TF F F T F F F T46例２．写出命题公式 Ｐ∨（ＱΛＲ）的真值表§３命题公式由上二例可见，２个命题变元有４组真值指派； ３个命题变元有23＝ ８组真值指派， ｎ个则有个2n个真值指派。 ３．命题公式的永真式、永假式和可满足式 例：举最简单例子：47§３命题公式P F T ?P T F P∨?P T T P∧?P F F《定义》：设公式Ａ中有n个不同的原子变元p1,…pn,(n为正整数)。该变元组的任意一组确定的值（ u1,…un） 称为Ａ关于p1,…pn的一个完全指派，其中ui或为Ｔ， 或为Ｆ。如果对于Ａ中部分变元赋以确定值，其余变 元没有赋以确定的值，则这样的一组值称为公式Ａ的 关于该变元组的部分指派。《定义》：凡使公式Ａ取真的指派称为Ａ的成真指派。48§３命题公式《定义》：如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式。如果一个命题公式的所 有完全指派均为成假指派，则该公式称为永假式。既不 是永真式，又不是永假式，则称此命题公式是可满足 式。 讨论： （１）永真式的否定为永假式（?Ｔ＝Ｆ）；永假式的否 定为永真式（?Ｆ＝Ｔ）。 （２）二个永真式的析取、合取、蕴含、等价均为永真 式。49§4等价式１．等价式《定义》：如果对两个公式Ａ，Ｂ不论作何种指 派，它们真值均相同，则称Ａ，Ｂ是逻辑等价 的，亦说Ａ（Ｂ）等价于Ｂ（Ａ）。并记作：Ａ?Ｂ50§4等价式例：Ｐ∨?Ｐ?Ｑ∨?ＱP F F T T Q F T F T P∨?P T T T T Q ∨?Q T T T T51§4等价式例：判断公式A：(P∨?Q)∧(P∨Q) 与B：(P∨?R)∧(P∨R)是否等价。 解： 列该公式的真值表：52§4等价式P Q R ?Q P∨?Q P∨Q ?R P∨?R P∨R A T T T T F F F F T T F F T T F F T F T F T F T F F F T T F F T T T T T T F F T T T T T T T T F F F T F T F T F T T T T T F T F T T T T T T F T F T T T T F F F F B T T T T F F F F53§4等价式《定理》：命题公式Ａ?Ｂ的充要条件是Ａ?Ｂ为永真式。 说明： “?”为等价关系符，Ａ?Ｂ表示Ａ和Ｂ有等价关系。 Ａ?Ｂ不为命题公式 “?”为等价联结词（运算符），Ａ、Ｂ为命题公式，则 （Ａ?Ｂ）也为一命题公式。54§4等价式证明：（１）充分性：Ａ?Ｂ为永真式，即Ａ、Ｂ有相同的真 值，所以Ａ?Ｂ。 （２）必要性：Ａ?Ｂ，即Ａ、Ｂ有相同的真值表，所 以Ａ?Ｂ为永真式。例：证明 ??Ｐ?Ｐ； Ｐ→Ｑ??Ｐ∨Ｑ55§4等价式P Q??P ? P F F T T T F T F T T T TP→Q ? ?P∨Q T T F T T T T T T F T TF F T TF T F T由定理可知： Ａ?Ａ 若Ａ?Ｂ，则Ｂ?Ａ 若Ａ?Ｂ，Ｂ?C，则Ａ?Ｃ56§4等价式下面列出１５组等价公式（1）双重否定律 ??Ｐ?Ｐ （2）同等律 Ｐ∨Ｐ?Ｐ；ＰΛＰ?Ｐ （3）交换律 Ｐ∨Ｑ?Ｑ∨Ｐ； ＰΛＱ?ＱΛＰ；Ｐ?Ｑ?Ｑ?Ｐ （4）结合律 （Ｐ∨Ｑ）∨Ｒ?Ｐ∨（Ｑ∨Ｒ）； （ＰΛＱ）ΛＲ?ＰΛ（ＱΛＲ）； （Ｐ?Ｑ） ?Ｒ?Ｐ? （Ｑ?Ｒ）57§4等价式（5）分配律ＰΛ（Ｑ∨Ｒ）?（ＰΛＱ）∨（ＰΛＲ）； Ｐ∨（ＱΛＲ）?（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ）（6）摩根律 ?（Ｐ∨Ｑ）??ＰΛ?Ｑ； ?（ＰΛＱ）??Ｐ∨?Ｑ （7）吸收律 Ｐ∨（ＰΛＱ） ?Ｐ； ＰΛ（Ｐ∨Ｑ） ?Ｐ58§4等价式（8）蕴含律 Ｐ→Ｑ??Ｐ∨Ｑ （9）等价律 Ｐ?Ｑ?（Ｐ→Ｑ）Λ（Ｑ→Ｐ） （10）零 律 Ｐ∨Ｔ?Ｔ；ＰΛＦ?Ｆ （11）同一律 Ｐ∨Ｆ?Ｐ；ＰΛＴ?Ｐ （12）互补律 Ｐ∨?Ｐ?Ｔ；ＰΛ?Ｐ?Ｆ （13）输出律 ＰΛＱ→Ｒ?Ｐ→（Ｑ→Ｒ）59§4等价式（14）归缪律 （Ｐ→Ｑ）Λ（Ｐ→?Ｑ）??Ｐ （15）逆反律 Ｐ→Ｑ ??Ｑ→ ?Ｐ说明：（１）证明上述１５组等价公式的方法可用真值表 法，把?改为?所得的命题公式为永真式，则? 成立。60§4等价式（2） Λ、∨、 ?均满足结合律， 则在单一用Λ、∨、 ?联结词组成的命题公式 中，括号可以省去。 （3）每个等价模式实际给出了无穷多个同类型的具 体的命题公式。 例如：?(P∨Q) ?(?P ∧?Q)， ?((P∧Q) ∨(R∧S)) ?(?(P ∨ Q) ∧ ?(R ∨ S)， ?((P→Q) ∨ ?R) ?(?(P →Q) ∧ ? ?R)61§4等价式２．置换规则 《定义》：给定一命题公式Ｂ，其中P1、P2．．．Pn 是Ｂ中的原子命题变元， 若（1）用某些命题公式代换Ｂ中的一些原子命 题变元Pi （2）用命题公式Ａi代换Pi，则必须用Ａi代换 Ｂ中的所有Pi 由此而得到的新的命题公式Ａ称为命题公式Ｂ的代换实例62§4等价式讨论定义： （１）用命题公式只能代换原子命题变元，而不 能去代换分子命题公式 。 （２）要用命题公式同时代换同一个原子命题变 元。 （３）永真式的代换实例仍为永真式；反之代换 实例为永真式时，则不能断定原公式也一定是 永真式。63§4等价式例：Ｐ∨?Ｐ为一永真式，若用任何命题公式代换Ｐ，则仍为永真式 Ｐ→Ｑ为一个可满足的命题公式，若用Ｐ代换 Ｑ，则得（Ｐ→Ｐ）为永真式，但（Ｐ→Ｑ） 并不是永真式。 （４）一个命题公式的代换实例有许多个，但不 一定都等价于原来的命题公式64§4等价式例１．设Ｂ：Ｐ→（?QΛＰ）若用（Ｒ?Ｓ）代换Ｂ中的 Ｐ， 得Ａ：（Ｒ?Ｓ）→（?QΛ（Ｒ?Ｓ））是Ｂ的代换 实例， 而Ａ’：（Ｒ?Ｓ）→（?QΛＰ）不是B的代换实例。 例２．Ｐ→?Ｑ的代换实例有：（ＲΛ?Ｓ）→?Ｍ， （ＲΛ?Ｓ）→Ｐ，Ｑ→?（Ｐ→?Ｑ）等 所以，一个命题公式的代换实例有无限个。65§4等价式下面讨论取代过程（置换规则）：《定义》：给定一命题公式Ａ，Ａ’是Ａ的任何部分，若Ａ’也是一命题公式，则称Ａ’是Ａ的子命题公式。例：Ａ：（Ｐ∨Ｑ）→（Ｑ∨（ＲΛ?Ｓ））Ａ的子命题公式有：Ｐ、Ｑ、Ｒ、?Ｓ、（Ｐ∨Ｑ）、 （ＲΛ?Ｓ）、（Ｑ∨（ＲΛ?Ｓ））、 （Ｐ∨Ｑ）→（Ｑ∨（ＲΛ?Ｓ））等。66§4等价式《定理》：给定一命题公式Ａ，Ａ’是Ａ的子公式。 设B’是一命题公式，若Ａ’? B’，并用B’取代Ａ中 的Ａ’，从而生成一新的命题公式B，则Ａ?B。 从定理可见：一个命题公式A，经多次取代，所得 到的新公式与原公式等价。 例：证明：Ｐ→（Ｑ→Ｒ）?Ｐ→（?Ｑ∨Ｒ） ??Ｐ∨?Ｑ∨?Ｒ67§4等价式??（ＰΛＱ）∨Ｒ ? （ＰΛＱ）→Ｒ 例：证明： （（Ｐ∨Ｑ）Λ?（?ＰΛ（?Ｑ∨?Ｒ）））∨（? ＰΛ?Ｑ）∨（?ＰΛ?Ｒ）为一永真式68§4等价式证明：原式： （（Ｐ∨Ｑ）Λ?（?ＰΛ（?Ｑ∨?Ｒ）））∨（?ＰΛ?Ｑ）∨（?ＰΛ?Ｒ）?（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）））∨?（Ｐ ∨Ｑ）∨?（Ｐ∨Ｒ） ? （（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨? （（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ）） ?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨?（（Ｐ∨Ｑ） Λ（Ｐ∨Ｒ））?Ｔ ∵它是ＰΛ?Ｐ（永真式）的代换实例，永真式的代 换实例仍为永真式！69§4等价式３．对偶原理（对偶定律）《定义》：给定二个命题公式Ａ和A* ，若用Λ代换∨，用∨ 代换Λ，用Ｔ代换Ｆ，用Ｆ代换Ｔ，其中一个命题公式由 另一个命题公式得来，则称Ａ和A*是互为对偶的，而联结 词Λ和∨也是互为对偶的 例：写出下列命题公式的对偶式： Ｐ∨（ＱΛＲ） ＰΛ（Ｑ∨Ｒ） Ｐ∨Ｆ?Ｐ 对偶式 A* ＰΛＴ?Ｐ Ｐ∨Ｔ?Ｔ ＰΛＦ?Ｆ70§4等价式讨论定义：（１）若命题公式中有联结词→，?，则必须把 化成由联结词Λ， ∨，?组成的等价的命题公 式，然后求它的对偶式； 例：求(P→Q)∧(P→R)的对偶式71§4等价式（２）在写对偶式时，原命题公式中括号不能省 去，必须按优先级的次序画上括号，并在求其 对偶式时仍将保留括号。 例：（ＰΛＱ）∨Ｒ对偶式写成 （Ｐ∨Ｑ）ΛＲ，而不能写成Ｐ∨ＱΛＲ72§4等价式《定理》：（摩根推广定理）设Ａ和A*为对偶式P1,P2．．．Pn 是出现在Ａ和A*中 的所有原子命题变元，，于是有： ?Ａ（P1，P2．．．Pn） ? A* （?P1，?P2．．．?Pn）――（1） Ａ（?P1，?P2．．．?Pn） ? ?A*（P1，P2．．．Pn）――（２）73§4等价式证明：由摩根定理?（Ｐ∨Ｑ）??ＰΛ?Ｑ―（１） ?（ＰΛＱ）??Ｐ∨?Ｑ―（２）∴不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。例：设Ａ（Ｐ，Ｑ，Ｒ）??ＰΛ ? （Ｑ∨Ｒ），验证上述定理：74§4等价式证明：(１)Ａ（Ｐ，Ｑ，Ｒ）??ＰΛ ?ＱΛ ?Ｒ ∴ ?Ａ（Ｐ，Ｑ，Ｒ） ?Ｐ∨Ｑ∨Ｒ A*（Ｐ，Ｑ，Ｒ） ??Ｐ∨ ?Ｑ∨ ?Ｒ A*（ ?Ｐ， ?Ｑ， ?Ｒ）?Ｐ∨Ｑ∨Ｒ （２）Ａ（ ?Ｐ， ?Ｑ， ?Ｒ） ?ＰΛＱΛＲ ? A*（Ｐ，Ｑ，Ｒ） ? ? （ ?Ｐ∨Ｑ∨ ?Ｒ） ?ＰΛＱΛＲ 有Ａ（ ?Ｐ， ?Ｑ， ?Ｒ） ? ?A*（Ｐ，Ｑ，Ｒ）75§4等价式《定理》：若二个命题公式互为等价，则它们的对 偶式也互为等价，亦即若Ａ?Ｂ，则A*?B*成 立。证明：已知：Ａ、Ｂ为任一命题公式，且Ａ?Ｂ，要证明A*?B* 设：P1、P2．．．Pn 是出现在Ａ和Ｂ中的原子 命题变元，76§4等价式由Ａ?Ｂ， 即Ａ（P1，P2．．．Pn） ? Ｂ（P1，P2．．．Pn） ∴ ?Ａ（P1，P2．．．Pn）??Ｂ（P1，P2．．．Pn）由摩根推广定理∴Ａ*（?P1，?P2．．．?Pn）?Ｂ*（?P1，?P2．．．?Pn）77§4等价式∴Ａ*（?P1，?P2．．．?Pn）? Ｂ*（?P1，?P2．．．?Pn）为永真式 ＊ 前面讲过永真式的代换实例仍为永真式，所以 用 ?Pi代换A*和B*中的Pi （1≤i≤n) 则得： Ａ*（ ? ?P1， ? ?P2．．． ? ?Pn）? Ｂ*（ ? ?P1， ? ?P2．．． ? ?Pn） 即为：Ａ*（P1，P2．．．Pn）? Ｂ*（P1，P2．．．Pn）78§4等价式例：证明： （１）?（ＰΛＱ）→（?Ｐ∨（?Ｐ∨ Ｑ）） ?（?Ｐ∨Ｑ） （２）（Ｐ∨Ｑ） Λ （?ＰΛ（?ＰΛＱ）） ?（?ＰΛＱ） 证明：（１）左边 ? ??（ＰΛＱ） ∨ （?Ｐ∨（?Ｐ∨ Ｑ）） ? （ＰΛＱ） ∨ （?Ｐ∨ Ｑ） ? （Ｐ∨ ?Ｐ∨ Ｑ） Λ （Ｑ∨ ?Ｐ∨ Ｑ） ? （?Ｐ∨ Ｑ）79§4等价式（２）左边 ? （Ｐ∨Ｑ） Λ （?ＰΛＱ） ? （ＰΛ?ＰΛＱ） ∨ （ＱΛ?ＰΛＱ） ? （?ＰΛＱ） 结论：（１）和（２）是互为对偶的。80§5永真蕴含式《定义》：命题公式Ａ 称为永真蕴含命题公式Ｂ，当且仅当Ａ→Ｂ是一 个永真式， 记作：Ａ?Ｂ 说明：“Ａ? Ｂ”读作“Ａ永真蕴含Ｂ”，“Ａ蕴含Ｂ”，“Ａ能推 得Ｂ” “? ”是关系符，Ａ? Ｂ不为命题公式。 例：证明：Ｐ? Ｐ∨Ｑ； ＰΛＱ? P （１）列出真值表 证明：Ｐ→（Ｐ∨Ｑ）和（ＰΛＱ）→Ｐ为永真式81§5永真蕴含式P Q Ｐ→（Ｐ∨Ｑ） （ＰΛＱ）→ＰF F F T F F T F T T T F T T T T T T T TF F F TT F T F T T T T（２）可用等价公式证： Ｐ→（Ｐ∨Ｑ） ? ?Ｐ∨（Ｐ∨Ｑ）? T （ＰΛＱ）→Ｐ? ?（ＰΛＱ）∨Ｐ ? ?Ｐ∨ ?Ｑ∨Ｐ? T82§5永真蕴含式《定理》：设Ａ、Ｂ是二个命题公式 Ａ?Ｂ的充分必要条件是 Ａ?Ｂ且Ｂ? Ａ。 证明： 若Ａ?Ｂ，则Ａ?Ｂ为一永真式 由定律： （Ａ?Ｂ）?（Ａ→Ｂ）Λ（Ｂ→Ａ） ∴（Ａ→Ｂ）且（Ｂ→Ａ）也为一永真式 即： Ａ? Ｂ且Ｂ?Ａ成立 反之 Ａ? Ｂ且Ｂ? Ａ 则Ａ?Ｂ也成立 此定理把“?”和“? ”之间建立了相应的关系。83§5永真蕴含式下面给出常用的永真蕴含式I1 Ｐ?Ｐ∨Ｑ （Ｑ?Ｐ∨Ｑ） I2 ＰΛＱ? Ｐ （ＰΛＱ? Ｑ） I3 ＰΛ（Ｐ→Ｑ） ?Ｑ I4 （Ｐ→Ｑ）Λ?Ｑ? ?Ｐ I5 ?ＰΛ（Ｐ∨Ｑ） ? Ｑ I6 （Ｐ→Ｑ）Λ（Ｑ→Ｒ） ? （Ｐ→Ｒ） I7 （Ｐ→Ｑ）Λ（Ｒ→Ｓ） ? （ＰΛＲ→ＱΛＳ） I8 （Ｐ?Ｑ）Λ（Ｑ?Ｒ） ? （Ｐ?Ｒ） I9 ?P ?Ｐ→Ｑ84§5永真蕴含式I10 I11 I12 I13 Ｑ? Ｐ→Ｑ ?（Ｐ→Ｑ） ? Ｐ ?（Ｐ→Ｑ） ? ?Ｑ （Ｐ∨Ｑ）Λ（Ｐ→Ｒ）Λ（Ｑ→Ｒ） ? Ｒ证明上述永真蕴含式的方法有三种： （１）把“? ”关系符改为“→”联结词，证明它为永真式。 (a)真值表法 (b)命题演算法85§5永真蕴含式（２）＊找出使单条件命题前件为“Ｔ”的所有真值 指派，试看能否导致后件均为“Ｔ”，若为“Ｔ”， 则永真蕴含关系成立。P F F T T Q F T F T P→Q T T F T86§5永真蕴含式例：ＰΛ（Ｐ→Ｑ） ? Ｑ 前件为“Ｔ”的所有指派为Ｐ、（Ｐ→Ｑ）均为“Ｔ”， Ｐ→Ｑ为“Ｔ”，∵Ｐ为“Ｔ”，∴Ｑ也应为“Ｔ”， ∴ＰΛ（Ｐ→Ｑ） ? Ｑ成立 （３）＊找出使单条件命题的后件均为“Ｆ”的所有 真值指派，试看前件的所有真值是否为“Ｆ”，若 是，则蕴含成立。87§5永真蕴含式例：?ＱΛ（Ｐ→Ｑ） ? ?Ｐ 后件为“Ｆ”的所有条件是：Ｐ为“Ｔ”， 代入前件得 （）若Ｑ为Ｔ，则?ＱΛ（Ｐ→Ｑ）为“Ｆ”； （）若Ｑ为Ｆ，则?ＱΛ（Ｐ→Ｑ）为“Ｆ”； ∴?ＱΛ（Ｐ→Ｑ） ? ?Ｐ成立 若后件简单则可选用(3)；若前件简单则可选用(2)。 二种方法是互为独立的，只需使用一种证明就行。88§5永真蕴含式讨论一下永真式 可得出三个结论： （１）若一个命题公式等价于一个永真式，则该 公式一定为永真式。 （２）若一个永真的命题公式永真蕴含一个命题 公式，则此命题公式一定也为永真式。 （３）若一个永假的命题公式永真蕴含一个命题 公式，则该公式可能是永真式、永假式或可满 足的。89§5永真蕴含式《定理》：给定命题公式Ａ、Ｂ、Ｃ， 若Ａ?Ｂ，且Ｂ?Ｃ，则Ａ?Ｃ。 证明：∵Ａ?Ｂ，且Ｂ?Ｃ， ∴（Ａ→Ｂ）Λ（Ｂ→Ｃ）为永真式， 由I6：（Ａ→Ｂ）Λ（Ｂ→Ｃ） ? （Ａ→Ｃ）， ∴（Ａ→Ｃ）也为永真式；即，Ａ?Ｃ成立90§5永真蕴含式《推论》：若Ａ?B1 、B1 ? B2．．．．．．Bm ?Ｂ，则Ａ?Ｂ。Ｃ，则Ａ?（ＢΛＣ） 证明：∵Ａ?Ｂ Λ Ａ?Ｃ， ∴（Ａ→Ｂ）Λ（Ａ→Ｃ）为永真式， 由条件，若Ａ一定为“Ｔ”，则Ｂ、Ｃ均为“Ｔ”， ∴Ａ→（ＢΛＣ）也为“Ｔ”， 结论：Ａ?（ＢΛＣ）为“Ｔ”。《定理》：给定一个命题公式Ａ、Ｂ、Ｃ，若Ａ?Ｂ,Ａ?91§5永真蕴含式上述也可用等价公式证明它： （Ａ→Ｂ）Λ（Ａ→Ｃ） ?（?Ａ∨Ｂ）Λ（ ?Ａ∨Ｃ） ? ?Ａ∨（ＢΛＣ） ?Ａ→（ＢΛＣ）也为永真式 ∴Ａ?（ＢΛＣ）成立《定义》：设H1,H2….Hm,Ｑ均为命题公式，若（H1 ΛH2Λ…Hm ） ?Ｑ，则称： H1,H2….Hm,共同蕴含Ｑ，并记作： H1,H2….Hm ?Ｑ。92§5永真蕴含式《定理》：若 （H1 ΛH2Λ…Hm ）,P ?Ｑ， 则（H1 ΛH2Λ…Hm ） ?（Ｐ→Ｑ）。 证明： （H1 ΛH2Λ…ΛHm ΛP）→Ｑ ??（H1 ΛH2Λ…ΛHm ΛP）∨Q ?（ ? H1 ∨ ? H2 ∨ … ∨ ? Hm ） ∨ （ ? P ∨Q ） ??（H1 ΛH2Λ…ΛHm ） ∨ （ P→ Q ） H1 Λ H2 Λ …. Λ Hm→（Ｐ→Ｑ）也为永真式 ∴ （ H1 Λ,H2 Λ …. Λ Hm ）?（Ｐ→Ｑ） 成立93§6命题联结词总结１．其他命题联结词： （１）不可兼或（异或，异） (a)符号：“?”（），Ｐ?Ｑ，读作“Ｐ异或Ｑ” (b)定义：（由真值表） (c)异或的性质： Ｐ?Ｑ ?（?ＰΛＱ）∨（ ?ＱΛＰ） ?（Ｐ∨Ｑ）Λ（ ?Ｐ∨ ?Ｑ） Ｐ?Ｑ? ? （Ｐ?Ｑ） Ｐ?Ｑ?Ｑ?Ｐ （可交换的） （Ｐ?Ｑ） ? Ｒ? Ｐ? （Ｑ? Ｒ）（可结合的）P Q P?QF F F F T T T F T T T F94§6命题联结词总结ＰΛ（Ｑ?Ｒ）?（ＰΛＱ） ? （ＰΛＲ） （Λ对? 可分配的） Ｐ? Ｐ?Ｆ Ｐ? ?Ｐ?Ｔ Ｆ? Ｐ?Ｐ Ｔ? Ｐ? ?Ｐ 若Ｐ? Ｑ?Ｒ，则有：Ｐ? Ｒ?Ｑ?Ｒ? Ｐ Ｒ? Ｑ?Ｐ?Ｑ? Ｒ Ｑ? Ｐ?Ｒ，Ｐ? Ｑ? Ｒ?Ｆ95§6命题联结词总结（２）“与非”联结词： (a)符号“↑”，（Ｐ↑Ｑ）读作：“Ｐ与Ｑ的否定”或“Ｐ与非Ｑ” (b)定义：（由真值表） （Ｐ↑Ｑ）??（Ｐ∧Ｑ）PQP ↑Q T T T FF F T TF T F T96§6命题联结词总结(c)性质： （Ｐ↑Ｑ）?（Ｑ↑Ｐ） （Ｐ↑Ｐ）??Ｐ （Ｐ↑Ｑ）↑（Ｐ↑Ｑ）?（Ｐ∧Ｑ） （Ｐ↑Ｐ）↑（Ｑ↑Ｑ）?（Ｐ∨Ｑ） Ｐ↑（Ｑ↑Ｒ）??Ｐ∨（Ｑ∧Ｒ） 不可结合的 （Ｐ↑Ｑ）↑Ｒ?（Ｐ∧Ｑ）∨?Ｒ 不可结合的 Ｐ↑Ｔ? ?Ｐ，Ｐ↑Ｆ?Ｔ97§6命题联结词总结（３）“或非”联结词： (a)符号：“↓” （Ｐ↓Ｑ）读作：“Ｐ或Ｑ的否定”或 “Ｐ或非Ｑ” (b)定义（由真值表给出）： （Ｐ↓Ｑ） ? ?（Ｐ∨Ｑ）P F F T TQ F T F TＰ↓Ｑ T F F F98§6命题联结词总结(c)性质： Ｐ↓Ｑ?Ｑ↓Ｐ（可交换的） Ｐ↓Ｐ??Ｐ （Ｐ↓Ｑ）↓（Ｐ↓Ｑ）?Ｐ∨Ｑ （Ｐ↓Ｐ）↓（Ｑ↓Ｑ）?Ｐ∧Ｑ Ｐ↓（Ｑ↓Ｒ）??Ｐ∧（Ｑ∨Ｒ） 不可结合的 （Ｐ↓Ｑ）↓Ｒ?（Ｐ∨Ｑ）∧ ?Ｒ 不可结合的 Ｐ↓Ｆ??Ｐ； Ｐ↓Ｔ?Ｆ (d)由（２）和（３）中的性质可见，↑和↓是互为对偶 的。99§6命题联结词总结（4）“ 蕴含否定”联结词： c (a)符号： “→ ” (b)定义 （由真值表给出）： Pc Q ??(P→Q) →P T T F FQ T F T Fc P → Q FT F F100§6命题联结词总结（１）不同真值表的命题公式： 按命题公式的生成规则，用联结词可组成无限个 命题公式。下面讨论这些命题公式有多少种不 同的真值表： (a)若命题变元只有一个Ｐ，则用联结词组成的命 题公式由四种不同的真值表，即为：P F T 0 F F 1 F T 2 T F 3 T T101§6命题联结词总结所有依赖于Ｐ的命题公式均等价于这四个中的一个 (b)若有二个命题变元Ｐ、Ｑ，则命题公式的不同 2 2 真值表有：2 =24=16种。推广到一般：若有ｎ个变元的命题公式，则可构 n 2 成不同的真值表为2 （个）。102§6命题联结词总结（２）二元运算中的全部联结词总结： ?、∧、∨、→、? 是五个基本联结词。 到此为止，一个符号系统已定义完毕，它们是： 命题变元 :Ａ、Ｂ…Ｘ、Ｙ、Ｚ 。 值 :Ｆ、Ｔ 运算符 : ?、∧、∨、→、?、C 、↑、↓、? → 括号 :（） 关系符 :? 、?103§6命题联结词总结３．全功能联结词集合：《定义》：一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出 来，则称此联结词集合为全功能联结词集合。《定义》：设有一联结词集合Ａ，若（１）用Ａ中的联结词的等价式能表达任何的 一个命题公式；104§6命题联结词总结（２）删除Ａ中的任一联结词，从而形成一个新的 联结词集合Ａ’，至少有一个命题公式Ｂ不能用Ａ’ 中的联结词的等价式来表示，则称A为最小的全 功能联结词集合。 我们可以证明：{?，∨}；{?，∧}；{?，→}；{↑}； {↓}均为全功能联结词集合，且均是最小的全功 能联结词集合。 例：用上述最小全功能联结词集合中的联结词单一 表达下述命题公式：105§6命题联结词总结（Ｐ→Ｑ）? ?Ｐ∨Ｑ { ?，∨} ? ??（?Ｐ∨Ｑ） ??（Ｐ∧ ?Ｑ） { ?，∧} ???（Ｐ→Ｑ） { ?，→} ??(Ｐ Ｑ) { ?， } ?? ? （ ?Ｐ∨Ｑ） c c → ?（（Ｐ↓Ｐ） ↓Ｑ）↓（（Ｐ↓ Ｐ）↓Ｑ） → {↓} ?? ? （ ?Ｐ∨Ｑ） ?? （Ｐ∧ ?Ｑ） ?Ｐ↑（Ｑ↑Ｑ） {↑}106§7范式和判定如何判定命题公式为永真式、永假式和可满足的 呢或二个命题公式等价，归纳有三种方法： （1）真值表法：对于变元的所有真值指 派，看对 应命题公式的真值。 （2）命题演算方法：化简命题公式至最简式，看 是否存在和 （Ｐ∨?Ｐ）、（Ｐ∧?Ｐ）等 价，若不则为可满足的。 （3）范式方法：本节就介绍此法。107§7范式和判定什么叫范式 把命题公式化归为一种标准的形式，称此标准形 式为范式。 什么叫判定 以有限次步骤来决定命题公式是否为永真式、永 假式，还是可满足的，或者判定二个命题公式 是否等价等这一类的问题，统称为判定问题。 讨论范式和主范式的目的就是为了进行判定。108§7范式和判定１．析取范式和合取范式： 设命题变元为：Ｐ、Ｑ、Ｒ，则：（Ｐ∨Ｑ∨ Ｒ）的析取式称为“和”；（Ｐ∧Ｑ∧Ｒ）的合取 式称为“积”。 《定义》：命题公式的变元和变元的否定之积称 为基本积，而变元和变元的否定之和称为基本 和。109§7范式和判定例：设Ｐ、Ｑ为二个命题变元，则：Ｐ∨Ｐ，Ｑ∨ Ｑ，?Ｐ∨Ｑ， ?Ｑ∨ ?Ｐ，Ｐ∨Ｑ，Ｐ∨ ?Ｑ称 为基本和；Ｐ∧Ｐ，Ｑ∧Ｑ， ?Ｐ∧Ｑ， ?Ｑ∧ ? Ｐ，Ｐ∧Ｑ，Ｐ∧ ?Ｑ称为基本积。 若“基本和”或“基本积”中的子公式”，称为此基本积 （和）的因子。 例：?Ｑ∧Ｐ∧ ?Ｐ的因子有： ?Ｑ、Ｐ、 ?Ｐ、 ?Ｑ∧Ｐ、Ｐ∧ ?Ｐ……110§7范式和判定《定理》：一个基本积必定是永假式， 它的充分必要条件是，它至少包含一对因子， 其中一个是另一个的否定。 证明： （）充分条件： Ｐ、?Ｐ为基本积中一对因子 ?该基本积一定为永假式。 ∵（（Ｐ∧?Ｐ）∧（…））? （Ｆ∧（…））?Ｆ （）必要条件：基本积为永假式?基本积中包 含Ｐ、?Ｐ这对因子。111§7范式和判定反证法：假设基本积中不包含Ｐ、?Ｐ这样的因 子，且为永假式。若给基本积中的命题变元指 派“Ｔ”，而命题变元的否定指派为“Ｆ”， ∵ 在基本积中不包含Ｐ、?Ｐ这对因子， ∴ 基本积得到的真值为“Ｔ”，这和假设相矛盾； ∴基本积中必然包含Ｐ、?Ｐ这对因子才能使基本 积为“Ｆ”。112§7范式和判定《定理》：一个“基本和”必定为永真式， 其充要条件（当且仅当）是，它至少包含一对因 子，其中一个是另一个的否定。 《定义》：与给定命题公式等价的一个公式，如果 是由基本积之和组成，则称它为命题公式的析取 范式。并记为：P?P1 ∨ P2 ∨… ∨ Pn （n∈I+）。其中P1，P2．．．Pn均为基本积。 方法可按下列三步（或四步）进行：113§7范式 和判定（１）利用等价公式：化去“→”、“?”联结词，把命题公式变 为与其等价的用{?，∧，∨}表达的公式。 例: Ｐ→Ｑ??Ｐ∨Ｑ， Ｐ?Ｑ?（Ｐ∧Ｑ）∨（?Ｐ∧?Ｑ） ?（?Ｐ∨Ｑ）∧（Ｐ∨?Ｑ） （２）将“?”深入到原子命题变元之前，并使变元之前最多只 有一个“?”词。 例：?（?Ｐ∨?Ｑ）?? ?Ｐ∧ ? ?Ｑ ?Ｐ∧Ｑ114§7范式和判定（３）利用“∧”对“∨”的分配，将公式化成为析取范 式。 （４）除去永假项得最简析取范式。 例：求?（Ｐ∨Ｑ）?（Ｐ∧Ｑ）的析取范式： 解：原式 ?(?（Ｐ∨Ｑ）∨ （Ｐ∧Ｑ）) ∧ (?（Ｐ∧Ｑ）∨ ?（Ｐ∨Ｑ）)115§7范式和判定?(? （Ｐ∨Ｑ）∧ （Ｐ∧Ｑ）) ∨ (? ? （Ｐ∨Ｑ）∧ ? （Ｐ∧Ｑ）) -----（1）化去?词 ?（?Ｐ∧ ?Ｑ∧Ｐ∧Ｑ）∨（（Ｐ∨Ｑ）∧（ ?Ｐ∨ ? Ｑ）） -----（2）将“?”深入到变元前面，并最多保留一个? ?（ ?Ｐ∧ ?Ｑ∧Ｐ∧Ｑ）∨（（Ｐ∧ ?Ｐ）∨（Ｐ∧ ? Ｑ）∨（ ?Ｐ∧Ｑ）∨（Ｑ∧ ?Ｑ））-----（3）“∧”对或“∨”的分配，化成为析取范式?（Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ）-----（4）最简析取范式116§7范式 和判定讨论定义： （１）从上例看出，一个命题公式的析取范式不是唯一 的，但同一命题公式的析取范式一定是等价的。 （２）若一个命题公式的析取范式中每一个基本积均为永 假式，则该公式也一定为永假式。 即，P?P1∨P2∨…∨Pn （P1，P2．．．Pn均为基本积） 则，当P1?P2 ? … ? Pn ?F时， Ｐ一定为永假式。 (可用来判定是否为永假式)117§7范式和判定例：（析取范式）Ｐ? ?Ｐ?（Ｐ∧ ?Ｐ）∨（ ?Ｐ∧Ｐ） ?Ｆ 永假式《定义》：与给定命题公式等价的一个公式，如果它是由基本和之积所组成，则称它是给定 命题公式的合取范式。 并表示成： Q ? Q1∧ Q2∧ …∧ Qn，(n∈I+),其中 Q!,Q2,…Qn均为基本和。118§7范式和判定求一个命题公式的合取范式的方法和求析取范式的 方法类同： 第（１）、（２）步相同； 第（３）利用“∨”对“∧”的分配就行； 第（４）去掉永真的析取项。119§7范式和判定例：求Ｑ∨?（Ｐ→Ｑ）∨?（Ｐ∨Ｑ）的合取范式 原式 ? Ｑ∨?（?Ｐ∨Ｑ）∨?（Ｐ∨Ｑ） ――化去“→”词 ?Ｑ∨（Ｐ∧ ?Ｑ）∨（ ?Ｐ∧ ?Ｑ） ――“?”深入到变元前，并最多保留一个 ?（（Ｑ∨Ｐ）∧（Ｑ∨ ?Ｑ））∨（ ?Ｐ∧ ?Ｑ） ――“∨”对“∧”的分配 ?（Ｑ∨Ｐ∨ ?Ｐ）∧（Ｑ∨ ?Ｑ∨ ?Ｐ）∧（Ｑ∨Ｐ∨ ?Ｑ）∧（Ｑ∨ ?Ｑ∨ ?Ｑ） ?Ｔ（最简合取范式）120§7范式和判定讨论定义： （１）给定一命题公式的合取范式不是唯一的，但 同一命题公式的合取范式一定是等价的。 （２）若一个命题公式的合取范式中的各基本和的 真值为“Ｔ”，则该命题公式一定是永真式。 (可用来判定是否为永真式) 例：（Ｐ ?Ｐ）?（?Ｐ∨Ｐ）∧（Ｐ∨?Ｐ）?Ｔ121§7范式和判定２．主析取范式。 《定义》：在ｎ个变元的基本积中，若每个变元 及其否定并不同时存在，且二者之一出现一次 且仅出现一次，则称此基本积为极小项。 例：对二个命题变元讲，极小项有22=4个，即：Ｐ∧Ｑ、?Ｐ∧Ｑ、Ｐ∧ ?Ｑ、 ?Ｐ∧ ?Ｑ对一个命题变元讲，极小项有21=2个， 即：Ｐ、?Ｐ122§7范式和判定对三个命题变元讲，极小项有23=8个， 即：Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧?Ｒ、Ｐ∧?Ｑ∧Ｒ、Ｐ∧?Ｑ∧?Ｒ、?Ｐ∧Ｑ∧Ｒ、?Ｐ∧Ｑ∧?Ｒ、 ?Ｐ∧?Ｑ∧Ｒ、?Ｐ∧?Ｑ∧?Ｒ 推广到一般：ｎ个命题变元构成的不同极小项有2n个 （n∈I+）。使得每个极小项为真的赋值仅有一个。123§7范式和判定《定义》：对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的主析取 范式。《定理》：在真值表中，一个公式的真值为Ｔ的指派所对应的极小项的析取，即为此公式的主析 取范式。124§7范式和判定例：求出Ｐ→Ｑ、Ｐ∨?Ｑ、 ?（Ｐ∧Ｑ）、Ｐ∧?Ｑ的主析取范式Ｐ Ｑ Ｐ∨?Ｑ ?（Ｐ∧Ｑ） Ｐ∧?Ｑ Ｐ→ＱF F T F T F T F T T T TT T T FF F T FT T F T125§7范式和判定则可直接写出各命题公式的主析取范式：Ｐ→Ｑ?（?Ｐ∧ ?Ｑ）∨（ ?Ｐ∧Ｑ）∨（Ｐ∧Ｑ） Ｐ∨ ?Ｑ?（ ?Ｐ∧ ?Ｑ）∨（Ｐ∧ ?Ｑ）∨（Ｐ∧Ｑ） ?（Ｐ∧Ｑ）? （?Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ）∨（Ｐ∧?Ｑ） Ｐ∧?Ｑ?（Ｐ∧?Ｑ）讨论此定理： （1）只要命题公式不是永假式，则一定可以根据该命题 公式的真值表直接写出其主析取范式，其方法是找出该 公式为“Ｔ”的行，对应写出极小项的析取式，且一定是 唯一的。126§7范式和判定（2）若命题公式是含有n个变元的永真式，则它 的主析取范式一定含有2n个极小项。 （3）若二个命题公式对应的主析取范式相同，则 此二个命题公式一定是等价的。 （4）命题公式的主析取范式中极小项的个数一定等 于对应真值表中真值为“Ｔ”的个数。127§7范式和判定下面介绍不用真值表，直接求命题公式主析取范式 的方法，分四步： （１）将命题公式化归为与其等价的析取范式； （２）除去永假项，合并基本积中相同项（例：Ｐ ∧Ｐ∧Ｑ?Ｐ∧Ｑ），变为最简析取范式。 （３）利用添变元的方法，将所有基本积变为极小 项。128§7范式和判定例：二个变元Ｐ、Ｑ，利用“∧”对或“∨”的分配添项Ｐ?Ｐ∧（Ｑ∨?Ｑ） ?（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ） Ｑ?Ｑ∧（Ｐ∨?Ｐ） ?（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ）（４）合并相同的极小项变为一项。 例：求（Ｐ∧（Ｐ→Ｑ））∨Ｑ的主析取范式 解：原式?（Ｐ∧?Ｐ）∨（Ｐ∧Ｑ）∨Ｑ ----（1）化为析取范式129§7范式和判定? （Ｐ∧Ｑ）∨Ｑ ----（2）消去永假项，变为最简析取范式 ?（Ｐ∧Ｑ）∨（Ｑ∧（Ｐ∨?Ｐ）） ?（Ｐ∧Ｑ）∨（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ） ----（3）添项 ?（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ） ----（4）合并相同最小项130§7范式和判定例：证明Ｐ∨（?Ｐ∧Ｑ）?Ｐ∨Ｑ 证明方法是写出二个命题公式的主析范式，看其是否相同： （Ｑ∨?Ｑ）∧Ｐ∨（?Ｐ∧Ｑ） ?（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ） 而Ｐ∨Ｑ ? （Ｐ∧（Ｑ∨?Ｑ））∨（Ｑ∧（Ｐ∨?Ｐ）） ?（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（Ｐ∧Ｑ）∨（?Ｐ∧ Ｑ） ?（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ） 主析范式相同，∴有Ｐ∨（?Ｐ∧Ｑ） ?Ｐ∨Ｑ131§7范式和判定３．主合取范式《定义》：在ｎ个变元的基本和中，若每个变元与其否定，并不同时存在，且二者之一出现 一次且仅出现一次，则称这种基本和为极大 项。 例：有二个变元Ｐ,Ｑ的极大项有22=4个，（Ｐ ∨Ｑ）、（Ｐ∨?Ｑ）、（?Ｐ∨Ｑ）、（?Ｐ ∨?Ｑ）有ｎ个变元，则有2n个极大项 （n∈I+）。132§7范式和判定《定理》：在真值表中，一个公式的真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。在真值表中真值为“Ｆ”的个数等于主合取范式中 极大项的个数。 例：求出（Ｐ→Ｑ）、（Ｐ∨Ｑ）、?（Ｐ∧Ｑ）、 （Ｐ∧Ｑ）的主合取范式133§7范式和判定Ｐ F F T T Ｑ F T F T Ｐ∨Ｑ F T T T ?（Ｐ∧Ｑ） T T T F Ｐ∧Ｑ F F F T Ｐ→Ｑ T T F T直接写出其主合取范式： （Ｐ→Ｑ） ?（?Ｐ∨Ｑ）（极大项） ?（ ?Ｐ∧ ?Ｑ）∨（ ?Ｐ∧Ｑ）∨（Ｐ∧Ｑ）134§7范式和判定（Ｐ∨Ｑ） ? （Ｐ∨Ｑ） ? （ ?Ｐ∧Ｑ）∨（Ｐ∧ ?Ｑ）∨（Ｐ∧Ｑ） ?（Ｐ∧Ｑ） ?（ ?Ｐ∨ ?Ｑ） ?（ ?Ｐ∧ ?Ｑ）∨（ ?Ｐ∧Ｑ）∨（Ｐ∧ ? Ｑ）（Ｐ∧Ｑ） ? （Ｐ∨Ｑ）∧（Ｐ∨ ?Ｑ）∧（ ?Ｐ∨Ｑ）135§7范式和判定讨论（１）与命题公式等价的主合范式中极大项的个 数等于其真值表中真值为“Ｆ”的个数。由真值表 找极大项的方法为：将表中值为“Ｆ”的对应真值 指派中，把变元写成否定，把变元的否定写成 变元。 （２）只要命题公式不是永真式，则一定可以写 出对应与其等价的唯一的主合取范式。136§7范式和判定（３）若命题公式为含有ｎ个变元的永假式，则主合取范式 包含了2n个极大项的合取式。 （４）可用主合取范式判定二个命题公式是否等价。 （５）已知一个命题公式的主析取范式，则一定可以直接写 出与其等价的主合取范式来。反之也行。 例：Ｐ∨ ?Ｑ ?（ ?Ｐ∧ ?Ｑ）∨（Ｐ∧?Ｑ）∨（Ｐ∧Ｑ） ……主析范式 ?? （ ?Ｐ∧Ｑ）?Ｐ∨ ?Ｑ……主合取范式137§7范式和判定（６）对应于有ｎ个变元的命题公式，则一定有： 主析范式极小项数＋主合范式极大项数＝ 2n 下面介绍不用真值表求一命题公式主合取范式的方 法： （1）化为与命题公式等价的合取范式； （2）除去真值为“T”的析取项和除去析取项中相同 变元且只保留一个，变为最简合取式； （3）添项，使析取项均变为极大项；138§7范式和判定例如：Ｐ、Ｑ为二个变元， 即：Ｐ?Ｐ∨（Ｑ∧?Ｑ） ? （Ｐ∨Ｑ）∧（Ｐ∨ ?Ｑ） （4）合并相同的极大项，保留一项。 例：求Ｐ∧（Ｐ→Ｑ）∨Ｑ的主合取范式 解：原式 ?Ｐ∧（?Ｐ∨Ｑ）∨Ｑ ?（Ｐ∧Ｑ）∨Ｑ ?（Ｐ∨Ｑ） ∧Ｑ ? （Ｐ∨Ｑ）∧（ ?Ｐ∨Ｑ）139§7范式和判定４．主范式排序（列）的唯一性 （１）极小项极其编码 为了确保主范式的唯一性，二个安排： （a）各命题变元的位置安排一固定次序； （b）对极小项、极大项安排一个次序。 对于有ｎ个变元的命题公式，则最多可有2n个极小 项，用m0 ∧m1… ∧m2n-1来表示。 下面列出三个变元，且Ｐ、Ｑ、Ｒ的位置已排定，则140§7范式和判定m(i)十 十 十 十 十 十 十 十 十十进制数 二进制数 极小项表示0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 ?P ∧ ? Q ∧ ? R ? P ∧ ? Q ∧R ? P ∧Q ∧ ? R P ∧ ? Q ? ∧R P∧?Q∧?R P ∧ ? Q ∧R P ∧Q ∧ ? R P ∧Q ∧R141m(0)m(1) m(2) m(3) m(4) m(5) m(6)m(7)§7范式和判定例：设一命题公式有五个变元，P0,P1,P2,P3,P4（次 序已定），则必可写出25=32个极小项， 下列出m(11) 和m(18) 的极小项表示： 十 十 即， m(11) ＝ m(01011)十 二＝（? P0 ∧P1 ∧ ? P2 ∧P3 ∧P4 ） m(18) ＝ m(10010) 十 二 ＝（ P0 ∧ ? P1 ∧ ? P2 ∧P3 ∧ ? P4 ）142§7范式和判定通过上例归纳出一求极小项m(i) 的方法： (a)把(i) 变换成等价的(J0,J1…Jn-1)二十 十(b)由二进制写出其对应的极小项： 例：求（Ｐ∧Ｑ）∨（?Ｐ∧Ｒ）的编码表达式： （设Ｐ、Ｑ、Ｒ次序已定） 解：原式?（ ?Ｐ∧ ?Ｑ∧Ｒ）∨（ ?Ｐ∧Ｑ∧ Ｒ）∨（Ｐ∧Ｑ∧Ｒ）∨（Ｐ∧Ｑ∧ ?Ｒ）143§7范式和判定? m(001) ∨ m(010) ∨ m(100) ∨ m(101)二 二 二 二?m(1)十∨m(3)十∨m(7)十∨m(6)十? ∑m1,m3,m7,m6?∑1,3,6,7（２）极大项及其编码用M0,M1,…M2n-1表示ｎ个变元的命题公式的极 大项。 求极大项的方法：144§7范式和判定(a)把(i) 变换成等价的(J0,J1…Jn-1)二 十 (b)由二进制数写出其对应的极大项： 例：求（Ｐ∧Ｑ）∨（?Ｐ∧Ｒ）的极大项编码表 示（设Ｐ、Ｑ、Ｒ次序已定）145§7范式和判定解：原式? （Ｐ∨Ｑ∨Ｒ）∧（Ｐ∨ ?Ｑ∨Ｒ）∧ （ ?Ｐ∨ Ｑ∨Ｒ）∧（ ?Ｐ∨Ｑ∨ ?Ｒ） ?M(000) ∧ M(010) ∧ M(100) ∧ (110)二 二 二 二?M (0) ∧ M (2) ∧ M (4) ∧ M (5) 十 十 十 十 ?∏ M0,M2,M4,M5 ? ∏0,2,4,5146§7范式和判定极大项和极小项编码约定刚好相反， 从上例中，（Ｐ∧Ｑ）∨（ ?Ｐ∧Ｒ） ?∑1,3,6,7 ? ∏0,2,4,5 例：写出（Ｐ∨ ?Ｑ）的主析和主合编码表示147§7范式和判定P Q P ∨?QF F T TF T F TT F T TP ∨?Q?∏1 ?∑0,2,3 主析范式为：（ ?Ｐ∧ ?Ｑ）∨（Ｐ∧ ?Ｑ）∨（Ｐ∧Ｑ） 主合范式为： P ∨?Q 且 P ∨?Q?（ ?Ｐ∧ ?Ｑ）∨（Ｐ∧ ?Ｑ）∨（Ｐ∧Ｑ）148§7范式和判定５．主范式的个数 在介绍联结词总结时讲到： 1 2 一个原子命题变元有四个不同的真值表（2 个）； 2 2 二个原子命题变元有16个不同的真值表（2 个）； n 2 以此类推，若有ｎ个变元的命题公式，则可构成2 个不同的真值表。 ∴得到结论： n 2 对于含有ｎ个变元的命题公式，必定可写出2 个主 范式， 若排除永真式或永假式，则实际可写出 n （ 22 －１）个主析（或主合）范式。149§8推理理论按公认的推论规则，从前提集合中推导出一个结论 来，这样的推导过程称为演绎，或者叫形式证明。 在任何论证中，若认定前提是真的，且从前提集合推 导出结论的论证是遵守了逻辑规则的，则我们称此 结论是合法的。 根据逻辑规则推导出来的任何结论称为有效结论。 推论规则就是指确定论证的有效性的判据，常是用命 题形式表示这些规则，而不涉及实际命题和它的真 值。150§8 推理理论本节介绍的证明方法，归纳分成三类： （一）真值表技术； （二）推论规则； （三）间接证明法。 真值表技术的主要依据是“→”的真值表定义。 若Ｐ?Ｑ当且仅当 （Ｐ→Ｑ）为永真式。 P QＰ→ＱF F T TF T F TT T F T151§8推理理论真值表技术： 《定义》：给定二个命题公式Ａ和Ｂ，当且仅当Ａ→ Ｂ是一个永真式，才可以说Ｂ是从Ａ推导出来的， 或称Ｂ是前提Ａ的有效结论。 《定义》：设H1，H2,…Hm,Ｃ都是命题公式，当且仅 当H1 ∧ H2 ∧ … ∧ Hm ?Ｃ，才可以说Ｃ是前提集 合｛ H1，H2,…Hm ｝的有效结论。152§8推理理论从给定真值表常用的判断方法有二种：（１）检查真值表中H1，H2,…Hm全部为“Ｔ”的所有行，看 结论Ｃ是否也均为“Ｔ”，若Ｃ均为“Ｔ”，则结论有效。 否则结论无效。 （２）看结论Ｃ为“Ｆ”的所有行，检查每行前提H1， H2,…Hm中是否至少有一个为Ｆ，若有“Ｆ”，则结论有 效；若有均为“Ｔ”的行，则结论无效。 例：试证明下列结论是否有效： 画出真值表：153§8推理理论P Q Ｐ→Ｑ ?Ｐ ?Q ? （Ｐ∧Ｑ） Ｐ?ＱF F T TF T F TT T F TT T F FT F T FT T T FT F F T由真值表可见： （１）Ｐ，Ｐ→Ｑ?Ｑ （２）Ｐ→Ｑ，?Ｐ?Ｑ （３）Ｐ→Ｑ， ? （Ｐ∧Ｑ） ? ?Ｐ （４） ?Ｐ，Ｐ?Ｑ? ? （Ｐ∧Ｑ）有效 无效 有效 有效154§8推理理论（５）Ｐ→Ｑ，Ｑ?Ｐ 无效例：H1：如果大连是一个大城市，则大寨是一个 乡村； Ｐ→Ｑ H2：大寨是一个乡村； Ｑ Ｃ：大连是一个大城市； Ｐ 则：Ｐ→Ｑ，Ｑ?Ｐ 或者称：Ｐ不能从前提集合中推导出来。155§8推理理论２．推理（论）规则： 从这节开始，我们只讨论命题论证的有效性，而不去讨 论命题的真假值； ∴在推论规则中不需要有真值表，也不需要对命题进行 真值指派。 推理规则的依据是常用的永真蕴含式和等价公式。I1 Ｐ?Ｐ∨Ｑ； I2 Ｐ∧Ｑ?Ｐ； I3 Ｐ，Ｐ→Ｑ?ＱＱ?Ｐ∨Ｑ Ｐ∧Ｑ?Ｑ156§8推理理论I4 （Ｐ→Ｑ）， ?Ｑ? ?Ｐ I5 ?Ｐ，（Ｐ∨Ｑ） ?Ｑ I6 （Ｐ→Ｑ），（Ｑ→Ｒ） ? （Ｐ→Ｒ） I7 （Ｐ→Ｑ） ? （（Ｑ→Ｒ）→（Ｐ→Ｒ）） I8 （Ｐ→Ｑ），（Ｒ→Ｓ） ? （Ｐ∧Ｒ→Ｑ∧ Ｓ） I9 （Ｐ?Ｑ），（Ｑ?Ｒ） ? （Ｐ?Ｒ） I10 ?Ｐ?Ｐ→Ｑ157§8推理理论下面介绍二个规则： P规则：在推导的任何步骤上都可以引入前提 （条件） T规则：在推导过程中，如果前面有一个或多个 公式永真蕴含S，则可以把S引入推导过程之 中。 例1：证明：P→Q,Q → R,P?R 推理过程：158§8推理理论步骤 推理过程 (1) P→Q (2) P (3) Q (4) Q→R (5) R 也可以这样推理： (1) P→Q (2) Q →R (3) P→R 规则 P P T P T P P T 根据I(1)(2) I(3)(4)I(1)(2)159§8推理理论(4) P P (5) R T I(3)(4) 例2 证明： (P∨Q),(P →R),(Q →S)?S∨R (1) (P∨Q) P (2) ? P →Q T(1) E16 (3) Q →S P (4) ? P →S T(2)(3) I6 (5) ? S →P T(4) E18160§8推理理论(6) (7) (8) P →R ? S →R S∨R P T(6) T(7) I6 E16下面引进条件证明规则CP： 如果能从Q和给定的前提集合P中推导出R来， 则就能从前提集合中推导出（Q → R）来。 即: (P∧Q?R)则：P ? (Q→R)161§8推理理论例1： P→(Q →S), ?R∨P,Q ? R→S 证: (1) R 附加前提 (2) ?R∨P P (3) R→P T(2) E (4) P T(1)(3) I (5) P→(Q →S) P (6) Q →S T(4)(5) I162§8推理理论(7) Q (8) S (9) R→S 例2: (1) (2) (3) (4) (5) P T(6)(7) CPIP→Q ? P→(P ∧Q) P 附加前提 P→Q P Q T(1)(2) I P ∧Q T(1)(3) P→(P ∧Q) CP163§8推理理论3．间接证明法：（反证法、归谬法） 《定义》给出命题公式H1,H2…Hm， H1∧H2 ∧ … ∧ Hm具有真值为“T”，则命题公式 集合{H1,H2…Hm}称为是一致的。否则称 {H1,H2…Hm}是非一致的。164§8推理理论《定理》设{H1,H2…Hm}是一致的，同时设C是一个命题公式，如果前提集合{H1,H2…Hm,?C} 是非一致的，则一定有H1,H2…Hm?C成立。 证明：由条件H1∧H2 ∧ … ∧ Hm ∧ ?C ?F ∴ H1∧H2 ∧ … ∧ Hm ∧ ?C必定为永假式。而H1∧H2 ∧ … ∧ Hm是一致的，即为永真式，从而只有?C 为永假式，则C 一定为永真式， 故H1∧H2 ∧ … ∧ Hm?C成立。165§8推理理论例：证明 ? P ∧ ? Q? ? (P∧Q) 证: (1) (2) (3) ?(? (P∧Q)) P∧Q P 假设前提 T(1) T(2) P T(4) T(3)(5)(4) ? P ∧ ? Q (5) ? P (6) P∧ ? P (7) F166§8推理理论例2:证明: R→?Q, R∨S , S→?Q, P→Q ? ?P (1) ? (?P) 假设前提 (2) P T(1) (3) P→Q P (4) Q T(2)(3) (5) S→?Q P (6) Q→?S T(5) (7) ?S T(4)(6) (8) R∨S P (9) R T(7)(8)167§8推理理论(10) R→?Q P (11) ?Q T(9)(10) (12)Q ∧ ?Q T(4)(11) 讨论： 由上例可见，间接证明法在结论较为简单的条件 下，使用是比较方便的，实际上间接证明法也 可以用CP规则代替它。168§8推理理论间接证明法：特殊条件下的CP规则 ∵H1∧H2 ∧ … ∧ Hm ∧ ?C ?F 由CP规则： H1∧H2 ∧ … ∧ Hm ? ?C →F ?C∨F ?C ∴ H1,H2…Hm?C成立169§8推理理论例：一位计算机工作者协助公安人员审查一起谋杀案，经调 查，他认为下列情况均是真的。 （1）会计张某或邻居王某谋害了厂长。 （2）如果会计张某谋害了厂长，则谋害不可能发生在 半夜。 （3）如果邻居王某的证词不正确，则在半夜时房里灯 光未灭。 （4）如果邻居王某的证词是正确的，则谋害发生在半 夜。 （5）在半夜房子里的灯光灭了，且会计张某曾贪污 过。170§8推理理论解：设 P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋害发生在半夜 O：邻居王某的证词是正确的 R：半夜时房子的灯光灭了 A：会计张某曾贪污过列出条件公式：171§8推理理论(1) P∨Q (4) Q→N (2) P→?N (5) R∧A (3) ?O→ ? R 推导过程为： (1) R∧A P (6) N T (2) R T (7) P→?N P (3) ?O→ ?R P (8) ?P T (4) O T (9) P∨Q P (5) O→ R P (10) Q T 结论：邻居王某谋害了厂长；172第一章小结学习第一章要注意以下几点： （1）弄清命题与陈述句的关系。 （2）弄清由6种基本联结词联结的复合命题的逻辑关系及其 真值。特别是要弄清蕴含式”P→Q“的逻辑关系及其真值。 （3）记住常用的蕴含式和等价式，这是学好命题逻辑的关 键问题。 （4）会准确地求出给定公式的主析取范式和主合取范式。 掌握主析取范式与真值表、成真赋值、主合取范式的关 系。 （5）会用多种方法判断公式的类型及判断两个公式是否等 价。173第一章小结（6）会用等价变换法将一个联结词集中的公式等价地化为 另一个联结词全功能集中的公式。 （7）掌握推理和判断推理是否正确的方法。174例题选讲例1.符号化下列命题： （1）辱骂和恐吓决不是战斗； （2）除非天气好，否则我是不会去公园的； （3）如果晚上做完作业且没有其它的事，他就会去看电视 或听音乐。 解：（1）设P：辱骂不是战斗。 Q：恐吓不是战斗。 P∨Q （2）设P：今天天气好。 Q：我去公园。 Q→P175例题选讲（3）设P：他晚上做完了作业。 Q：他晚上没有其它事情。 R：他看电视。 S：他听音乐。 （P∧Q）→（R?S） 例2.证明P → （Q → R）?（P → Q） → （P → R） 给出本题的各种证明： （1）列真值表：设 M? P → （Q → R） K ? （P → Q） → （P → R） S ?P → （Q → R） → （P → Q） → （P → R）176例题选讲P Q R Q →R M P →QP →R T F T F T T T TK T F T T T T T TS T T T T T T T T177T T T T T F T F T T F F F T T F T F F F T F F FT F T T T F T TT F T T T T T TT T F F T T T T例题选讲a)直接证法： P → （Q → R）的真值为T，其对应指派下 （P → Q） → （P → R）的真值均为T。 b)反证法：（P → Q） → （P → R）的真值为F，其对应指 派下P → （Q → R）的真值为F。 c)条件永真式： （P → （Q → R）） →（ （P → Q） → （P → R）） 的真值都为T，及为永真式。 （2）逻辑推证 a)直接证法：设P → （Q → R）为T，则 ① P为T， Q → R为T，有三种情况： P为T，Q为T，R为T，则（P → Q） → （P → R）为T。178例题选讲P为T，Q为F，R为T，则（P → Q） → （P → R）为T。 P为T，Q为F，R为F，则（P → Q） → （P → R）为T。 ②P为F， Q → R为F，则： P为F，Q为T，R为F，所以P → Q为T， P → R为T，得 （P → Q） → （P → R）为T。 ③P为F， Q → R为T，则： P为F，Q为T，R为T，则（P → Q） → （P → R）为T。 P为F，Q为F，R为F，则（P → Q） → （P → R）为T。 P为F，Q为F，R为T，则（P → Q） → （P → R）为T。 综上各点：当P → （Q → R）为T时，必有（P → Q） → （P → R）为T。179例题选讲b)间接证法： 设（P → Q） → （P → R）为F，则 必有P → Q为T， P → R为F，故得P为T，Q为T，R为F。 所以P → （Q → R）为F。 （3）等价变换 S? (P → (Q → R))→((P → Q) → (P → R)) ?(?P∨( ?Q ∨R)) →(( ?P ∨ Q) →(?P ∨ R)) ? ? (?P∨?Q ∨R)∨ (?( ?P ∨ Q) ∨ (?P ∨ R)) ?(P∧Q ∧ ?R) ∨((P ∧ ?Q) ∨(?P ∨ R)) ? (P∧Q ∧ ?R) ∨((?P ∨ R ∨ P) ∧(?Q ∨ ?P ∨ R)) ? (P∧Q ∧ ?R) ∨(?P ∨ ?Q ∨ R) ? (P∧Q ∧ ?R) ∨ ?(P∧Q ∧ ?R)?T180例题选讲例3.证明 ｛?，?｝不是最小联结词组。 证明：设变元P，Q，用联结词?，?作用于P，Q得到： P，Q，?P，?Q，P?Q，P?P，Q?Q，Q?P。但 (P?Q)?(Q?P)，(P?P) ? (Q?Q)，故实际有： P，Q， ?P，?Q，P?Q，P?P(T) (A) 用?作用于(A)类,得到扩大的公式类(包括原公式类): P，Q， ?P，?Q，P?Q， ?(P?Q)，T，F (B) 用?作用于(A)类得到： P?Q， P? ?P(F)， P? ?Q? ?(P?Q)， P? (P?Q) ? Q ， P? (P?P) ?P, Q? ?P ? ?(P?Q)， Q? ?Q(F)，Q ? (P?Q) ? P, Q?T ?Q，181例题选讲?P? ?Q? (P?Q)， ?P? (P?Q) ? ?Q， ?P?T ??P， ?Q? (P?Q) ? ?P， ?Q?T ? ?Q， (P?Q) ? (P?P) ? P?Q。 因此(A)类使用?运算后，仍在(B)类中。 同样，对(B)类使用?， ?运算后，结果仍在(B)中。 由上证明：用?， ?两个联结词，反复作用在两个变元的公 式中，结果只能产生(B)类中的公式，总共仅八个不同公 式，而两个变元所形成的公式共有222=16个彼此不等价的 公式，因此｛?，?｝不是功能完备的，更不可能是最小 联结词组。182例题选讲例4. 求(A→B∧C) ∧(?A?(?B∧?C))的主析取范式与主合取 范式。 解：(1)列表法： 设 S ? (A→B∧C) ∧(?A?(?B∧?C))， R? A→B∧C， M? ?A?(?B∧?C)， 根据真值表中S真值为T的指派，所对应的小项析取即为S的 主析取范式，S真值为F的指派，所对应的大项合取即为 主合取范式。 S的真值表如下：183例题选讲A B C B∧C R ?A ?B∧?CM T T T F F F F TS T F F F F F F T184T T T T T T F F T F T F T F F F F T T T F T F F F F T F F F F FT F F F T T T TF F F F T T T TF F F T F F F T例题选讲S ? (A∧B ∧ C)∨(?A ∧?B ∧?C) －－ 主析取范式 S ?(?A ∨ ?B ∨ C) ∧(?A ∨ B ∨ ?C) ∧(?A ∨ B ∨ C) ∧(A ∨ ?B ∨ ?C) ∧(A ∨ ?B ∨ C) ∧(A ∨ B ∨ ?C) －－主合取范式 (2)公式推导法： S ? (A→B∧C) ∧(?A?(?B∧?C)) ? (?A ∨ (B∧C)) ∧(?A →(?B∧?C)) ∧((?B∧?C) →?A) ? (?A ∨ (B∧C)) ∧(A ∨(?B∧?C)) ∧((B∨C) ∨?A) ? ((?A ∧?B∧?C) ∨ (A ∧B∧C)) ∧(B∨C ∨?A) ? (?A ∧?B∧?C) ∨ (A ∧B∧C) ?m000 ∨m111 ?∑0,7185例题选讲当求出主析取范式的编码表达式后可直接利用编码关系，解 出主合取范式。即： S ? (A→B∧C) ∧(?A?(?B∧?C)) ? (?A ∧?B∧?C) ∨ (A ∧B∧C) ?m000 ∨m111 ?∑0,7 ?∏1,2,3,4,5,6 ?M001 ∧M010 ∧M011 ∧M100 ∧M100 ∧M101 ∧M110 ? (?A ∨ ?B ∨ C) ∧(?A ∨ B ∨ ?C) ∧(?A ∨ B ∨ C) ∧(A ∨ ?B ∨ ?C) ∧(A ∨ ?B ∨ C) ∧(A ∨ B ∨ ?C)186例题选讲例5.用推理规则论证下述问题： 或者是天晴，或者是下雨。如果是天晴，我去看电影。 如果我去看电影，我就不看书。所以，如果我在看书，则 天在下雨。 解：设 S：今天天晴。 R：今天下雨。 E：我去看电影。 B：我去看书。 本题符号化为： S?R，S→E，E→?B?B→R 因为 S?R??(S?R) 故本题为?(S?R)，S→E，E→?B?B→R187例题选讲①直接证法： (1) ?(S?R) (2) S? ? R (3) (S→?R)∧(?R→S) (4) ?R→S (5)S→E (6) ?R→E (7)E→?B (8) ?R→?B (9)B→R P T(1),E T(2),E T(3),I P T(4)(5),I P T(6)(7),I T(8),E188例题选讲②间接证法： a) (1) ?(S?R) (2) S? ? R (3) (S→?R)∧(?R→S) (4) ?R→S (5) ?(B→R) (6)B∧?R (7)B (8)?R (9)S P T(1) T(2) T(3) P(附加前提) T(5) T(6) T(6) T(4)(8)189例题选讲(10) S→E (11)E (12)E→?B (13) ?B (14)B∧?B b) (1)B (2)E→?B (3)?E (4) S→E P(附加前提) P T(1)(2) P190P T(4)(10) P T(11)(12) 矛盾(7)(13)例题选讲(5) ?S (6) ?(S?R) (7) S? ? R (8) (S→?R)∧(?R→S) (9) ?R→S (10) ?S→R (11)R (12) B→R T(3)(4) P T(6) T(7) T(8) T(9) T(5)(10) CP191第二章 谓词逻辑n n n n n n n§1 谓词的概念与表示法 §2 命题函数与量词 §3 谓词公式与翻译 §4 变元的约束 §5 谓词演算的等价式与蕴含式 §6 前束范式 §7 谓词演算的推理理论§1 谓词的概念与表示法在研究命题逻辑中， 原子命题是命题演算中最基本的单位，不再对原子命题进行 分解， 这样会产生二大缺点： （1）不能研究命题的结构，成分和内部逻辑的特征； （2）也不可能表达二个原子命题所具有的共同特征，甚 至在命题逻辑中无法处理一些简单又常见的推理过程。 例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则 推导出来。 “所有的人总是要死的。 A “苏格拉底是人。 B “所以苏格拉底是要死的。” C§1 谓词的概念与表示法1.谓词： 《定义》：用以刻划客体的性质或关系的即是谓词。 我们可把陈述句分解为二部分： 主语（名词，代词）和谓语（动词）。 例：张华是学生，李明是学生。则可把它表示成： H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用 下列符号表示上述二个命题：H(j)，H(m)。 H作为“谓词”（或者谓词字母）用大写英文字母表示， j,m为主语，称为“客体”或称“个体”。§1 谓词的概念与表示法（1）谓词填式：谓词字母后填以客体所得的式子。 例：H(a, b) （2）若谓词字母联系着一个客体，则称作一元谓词；若谓 词字母联系着二个客体，则称作二元谓词；若谓词字母联 系着n个客体，则称作n元谓词。 （3）客体的次序必须是有规定的。 例：河南省北接河北省。 n L b 写成二元谓词为：L(n,b)，但不能写成L(b,n) 。§2 命题函数与量词1. 命题函数客体在谓词表达式中可以是任意的名词。 例：C―“总是要死的。” j：张三；t：老虎；e：桌子。 则C(j), C(t), C(e)均表达了命题。 在上面的例子中，C：表示“总是要死的”；x：表示变元（客 体变元），则C(x)表示“x总是要死的”，则称C(x)为命题函 数。 《定义》由一个谓词字母和一个非空的客体变元的集合所组 成的表达式，称为简单命题函数。§2 命题函数与量词讨论定义： （a）当简单命题函数仅有一个客体变元时，称为一元简 单命题函数； （b）若用任何客体去取代客体变元之后，则命题函数就 变为命题； （c）命题函数中客体变元的取值范围称为个体域（论述 域）。 例：P(x)表示x是质数。这是一个命题函数。 其值取决于个体域。 可以将命题函数→命题，有两种方法：§2 命题函数与量词a)将x取定一个值。如：P(4)，P(5) b)将谓词量化。如：?xP(x)，?xP(x) 个体域的给定形式有二种： ①具体给定。 如：｛j, e, t｝ ②全总个体域?任意域：所有的个体从该域中取得。§2 命题函数与量词2.量词（1）全称量词 “?”为全称量词符号，读作“对于所有的”，“对任一个”，“对 一切”。 例：“这里所有的都是苹果” 可写成： ?xA(x)或(?x)A(x) 几种形式的读法： ? ?xP(x)： “对所有的x，x是…”； ? ?x?P(x) ： “对所有x，x不是…”； ? ??xP(x) ： “并不是对所有的x，x是…”； ? ??x?P(x) ： “并不是所有的x，x不是…”。§2 命题函数与量词例：将“对于所有的x和任何的y，如果x高于y，那么y不高于 x”写成命题表达形式。 解： ?x ?y(G(x,y)→ ? G(y,x)) G(x,y)：x高于y （2）存在量词 “?”为存在量词符号，读作“存在一个”，“对于一些”，“对于 某些”，“至少存在一个”，“这里存在着这样的”等等。 “?”表达式的读法： ? ? x A(x) ：存在一个x,使x是…； ? ? x?A(x) ：存在一个x, 使x不是…； ? ?? x A(x) ：不存在一个x, 使x是…； ? ?? x?A(x) ：不存在一个x, 使x不是…。§2 命题函数与量词例：（a）存在一个人； （b）某个人很聪明； （c）某些实数是有理数 将（a）,（b）,（c）写成命题。 解：规定：M(x)：x是人；C(x)：x是很聪明； R1(x)：x是实数(特性谓词) R2(x)：x是有理数。 则 （a） ? x M(x) ； （b） ? x (M(x) ∧C(x))； （c） ? x (R1(x) ∧ R2(x)) 。 （3）量化命题的真值：决定于给定的个体域 给定个体域：{a1…an}以{a1…an}中的每一个代入 ?xP(x)?P(a1)∧… ∧ P(an) ?xQ(x)?Q(a1)∨… ∨ Q(an)§3谓词公式与翻译1.谓词公式 原子谓词公式：不出现命题联结词和量词的谓词命名式称 为原子谓词公式，并用P(x1…xn)来表示。（P称为n元谓 词， x1…xn称为客体变元），当n=0时称为零元谓词公 式。 《定义》（谓词公式的归纳法定义） ⑴原子谓词公式是谓词公式； ⑵若A是谓词公式，则?A也是谓词公式； ⑶若A, B都是谓词公式，则(A∧B),(A∨B),(A→B),(A?B)都 是