离散数学chapter1.ppt

,高等学校工科电子类规划教材,主讲：李立平,离散数学,西安电子科技大学出版社,第一章 数理逻辑 前言,研究人的思维形式和规律的科学称为逻辑学，由于研究的对象和方法各有侧重而又分为形式逻辑、辨证逻辑和数理逻辑。 数理逻辑是利用数学方法研究推理的科学。数理逻辑又叫符号逻辑，因为它的主要工具是符号体系。数理逻辑的核心是把逻辑推理符号化，即变成象数学演算一样完全形式化的逻辑演算。 本章主要介绍命题演算(1.1-1.5)和谓词演算(1.6-1.8)。,第一章 数理逻辑,1 命题 2 重言式 3 范式 4 联结词扩充与归约 5 推理规则证明方法 6 谓词与量词 7 谓词演算永真公式 8 谓词演算推理规则,命题的概念,所谓命题，是具有真假意义的陈述句，也就是能够确定或分辨其真假的陈述句，且真与假必居其一。简言之，命题是非真即假的陈述句。 命题是真就说其真值为真，命题是假就说其真值为假。,关于命题的注记,某些命题可能无法查明其真值。如例1(d), (e). 命题真假会因时因地而异。例如： a) 人一只手有五指 b) 现在是上午 那些自称谓的陈述句可能产生自相矛盾的结论，故不在我们讨论之列。例如：某人说: 我正在说谎(见P.1例3)悖论 请注意: 数理逻辑的任务不在于研究某个具体命题的真假问题，而在于它可以赋予真或假的可能性，特别是研究各命题规定其真值后它们之间的联系。,原子命题,复合命题与命题联结词,不能再细分的命题称为原子命题。例如，“明天下雪”、“明天下雨”都是原子命题。 原子命题常可通过一些命题联结词构成新命题，这种命题称为复合命题。例如，“明天下雪或明天下雨”是复合命题。 命题联结词又称为逻辑运算符，常用的有五种，它们是：否定词、合取词、析取词、蕴涵词和等价词。,1 否定词 ,设P表示命题，则P不真 是另一命题，记为 P，读为 非P 否定词可用右表定义，此表称为 P的真值表,2 合取词 ,若 P,Q 表示命题，则 P并且Q 也是命题，记为 PQ ,读为 P合取Q. PQ 的真值表如右表所示。 由真值表可知 PQ 真,当且仅当 P,Q 俱真.,3 析取词 ,若 P,Q 表示命题，则 P或者Q 也是命题，记为 PQ,读为 P析取Q. PQ 的真值表如右表所示。 由真值表可知 PQ 真,当且仅当P,Q 至少有一个真,4 蕴涵词 ,若 P,Q 表示命题，则 P蕴涵Q 也是命题，记为 PQ,读为 P蕴涵Q. PQ 的真值表如右表所示。 由真值表可知PQ为假,当且仅当P为假而Q为真.,关于 PQ 真值表的说明,在日常生活中当P=0时，PQ 没有实际意义。故人们只考虑 P=1 的情形。但在PQ 真值表中规定：当 P=0 时，不管Q如何 PQ 的真值都为1. 有没有道理呢？ 例如，张三对李四说：我去图书馆一定帮你借那本书。可以将这句话表为命题 PQ(P表示:张三去图书馆,Q表示:张三借那本书)。后来张三因有事未去图书馆，即 P=0，此时按规定 PQ 为真。我们应理解为张三讲了真话，即他要是去图书馆我们相信他一定会为李四借书。这种理解也称为善意推定。,逆反命题与原命题的真值表完全一样,设PQ为原命题, 则QP、 P Q 、QP分别称为PQ的逆命题、反命题、逆反命题。 逆反命题与原命题的真值表完全一样. 也就是它们本质上相同.（课堂练习）,5 等值词 ,若 P,Q 表示命题，则P等值于Q 也是命题,记为 PQ, 读为 P等值于Q. PQ 的真值表如右表所示. 由真值表可知 PQ 为真,当且仅当P与Q有相同的真值.,命题联结词应用实例：,设 P:天不下雨, Q:草木枯黄, 则 P:天下雨; PQ:天不下雨并且草木枯黄; PQ:天不下雨或草木枯黄; PQ:如果天不下雨,那么草木枯黄; PQ:天不下雨当且仅当天草木枯黄.,五个逻辑运算符强弱顺序,运算符结合力的强弱顺序约定为： , 没有括号时按上述先后顺序执行. 相同运算符按从左至右顺序执行括号可省去. 最外层的括号总可以省去. 例如 PPQSQR 与 (P)(P)(Q(S)(Q)R) 运算顺序完全一样,前者不加一个括号. 请大家特别注意先后的习惯.,命题符号化自然语言翻译为逻辑式 (见P4 例1.1-8),符号化应注意以下几点： 确定句中连接词是否能对应于并且对应于哪一个命题连接词. 确定句子是否为命题.不是就不必翻译. 正确表示原子命题和选择命题连接词. 要按逻辑关系翻译而不能凭字面翻译.例如 令：P:林芬做作业 Q:林芳做作业. 则林芬和林芳同在做作业可译为PQ; 但林芬和林芳是姐妹不能译为PQ，因为这是一个原子命题.,命题符号化其他例子,除非你努力，否则你将失败 可以符号化为：PQ, 其中 P:你努力，Q:你将失败. 只有睡好觉才能恢复疲劳可以符号化为：QP, 其中 P:睡好觉，Q:恢复疲劳,命题变元和命题公式,以真、假为变域的变元称为命题变元；T 和 F 称为命题常元. 单个命题变元和命题常元称为原子公式；由下列递归规则生成的公式称为命题公式: (1)单个原子公式是命题公式. (2)若A和B是命题公式，则 A,AB,AB,AB,AB 是命题公式. (3)只有有限步应用(1)和(2)生成的公式(称为合式公式)才是命题公式. （见P6 例1.1-9）,n元命题公式A=(P1,Pn)可视为具有布尔变元的布尔函数,P1,Pn 真值的一种组合(P1,Pn), Pi 取值0或1,称为一种指派. A(P1,Pn)的真值称为命题A在指派(P1,Pn)下的值. 例1 若 A(P1,P2) = P1(P1P2),则 A(0,1) 0(01) 0; A(1,0) 1(10) 1. 例2 若 A(P,Q,R) = (PQR)Q，则 A(1,1,0) (110)1 1.,m(n)元命题公式A=(P1,Pm)也可视为n元命题公式A=(P1,Pn). 例如PQ,与(PQ)R的真值表可在同一张表上列出.,逻辑等价命题: 具有相同真值的命题 证明: PQ与PQP Q是逻辑等价命题。 证 用真值表,因后两列的真假值完全一致, 所以它们是逻辑等价命题。,若AB是重言式, 则记为 AB, 称为逻辑恒等式, 读为 A恒等于B. 易见: AB,当且仅当A,B真值表相同, 故逻辑恒等式常用真值表来证明.,最重要的逻辑恒等式已列入表1.2-1中. 建议大家记住并使用它们的称谓, 例如: 双否定律, 等幂律, 交换律, 结合律, 分配律, 摩根律, 吸收律, 蕴涵表达式, 等值表达式, 零律(E16,E17), 同一律(E18,E19), 排中律, 矛盾律, 输出律, 归谬律, 逆反律, 等等.,用真值表证明逻辑恒等式 E8,再用真值表证明逻辑恒等式 E14, E24, E15,再用真值表证明逻辑恒等式 E22,AB是永真式,则记为AB,称为永 真蕴涵式, 读为A永真蕴涵B。易见: AB,当且仅当A为真时B必为真. 逻辑蕴涵式也常用真值表来证明.,最重要的逻辑蕴涵式已列入表1.2-2中. 建议大家也记住并使用它们通常的称谓: 例如I1,I2,I6 分别叫做加法式, 简化式, 假言推理, 拒取式, 析取三段, 前提三段. I6, I9 也叫做(蕴涵,等值)传递律.,逻辑恒等符与永真蕴涵符的两个性质,（1）若 AB ，BC, 则AC； 若 AB ，B C, 则 A C （2）若 AB ，A C, 则 A B C,用真值表证明永真蕴涵式 I7 (只要证明：前件真后件必真即可）,再用真值表证明蕴涵式 I9,用其它方法证明逻辑蕴涵式时,可以只证明下列两条之一: (1) 假定前件是真, 若能推出后件是真, 则此蕴涵式是真(因按善意推定原则, P为假时PQ常为真)； (2) 假定后件是假, 若能推出前件是假, 则此蕴涵式是真(因按逆反律: PQ QP).,分析指派证明方法举例,1试证：对任何命题P恒有 PT,其中T为永真命题 解：若P为真，则因T为真得 P T为真，因此有 PT 2试证：P P(PQ) 解：若P为真，则无论Q取何真值都有P(PQ)为 真，所以 PP(PQ). 反之，若P为假，则 PQ为假，从而P(PQ)为 假，所以 P(PQ)P,代入规则重言式中某命题变元出现的每一处均代以同一命题公式后所得命题公式仍为重言式(因为重言式之值不依赖于变元的值),例 在 PQ QP 中以 AB 代P得 (AB)Q Q(AB). 或以C代P,同时以AB代Q得 C(AB) (AB)C,注:非重言式作代入运算可能出错,例 B: PQ 为偶然式.若用永真命题T代B中之Q所得命题为 A: PT. 上面已证A是重言式, 从而得出偶然式经代入运算后得出重言式的不协调现象.,子公式 A 是合式公式 C 中的一部分且 A 为合式公式, 则 A 称为 C 的子公式,例1 (PR)Q 和 WB 都是合式公式 (PR)Q U(WB) 的子公式.,替换规则 - 若A 是 C 的子公式, 且 A B . 令 D为将C中的 A 用B 代替后得到 的公式, 则 C D .,证明: 因 A B , 即对它们的命题变元的任何指派 A 与 B 的真值都相同, 故 B 替换 A 后公式 D 与 C对其命题变元做相应任何指派, 它们的真值亦相同. 因此 C D 成立.,用替换规则证明的例子,证明: (Q (P(PQ) (Q P). 解: 我们有 (Q P) (Q P) 和 (P(PQ) P (吸收律) 于是由替换规则可得 (Q (P(PQ) (Q P).,代入、替换规则的一个应用,基本逻辑恒等式表1.2-1和基本永真 蕴涵式表1.2-2中字符 P, Q, R 可以是 命题变元也可以是命题公式；T, F 可以 是真、假命题,也可以是重言式、永假式.,例2(a)证明: (PQ)Q PQ,证:(P Q)Q Q(P Q) 交换律 (QP)(Q Q) 分配律 (QP)T 排中律和替换规则 QP 同一律 PQ 交换律,对偶原理,定义1.2-1 设有公式A，其中仅有联结词、 、 ，在A中将、T、F分别换以、 、 F 、 T 得公式A*，则称A*为A的对偶公式。 对偶是相互的。 P (Q R)与P (Q R)互为对偶,注: 含 , 的命题公式求对偶公式时需先用E14 和 E15 以 ,代替, 后再进行,例如: 对 A=R (P(P Q) A R (P(PQ)(QP) R (P( PQ)( QP) R(P( PQ)( QP) 则 A* R (P ( P Q) ( Q P),定理 1.2-1 设 A=(P1,Pn). 则 A*(P1,Pn) A(P1,Pn), 或 A*(P1,Pn) A(P1,Pn).,例如: A(P,Q,R)= P(QR)，则 A(P,Q,R) (P)(QR) 摩根律 A*(P,Q,R) P(QR) A* (P,Q,R) (P)(QR) A(P,Q,R),定理 1.2-3 设 A, B 为含命题变元P1,Pn 及 , ,的合式. 若 AB, 则 B*A* (1) 反之, 若 B*A* , 则 AB (2) 即 AB, 当且仅当 B*A*,只需证(1). 若 A(P1,Pn)B(P1,Pn)永真,则 B(P1,Pn) A(P1,Pn)永真(逆反律),由定理1.2-1及代入定理得 B*(P1,Pn)A*(P1,Pn) 永真. 最后由代入定理(以Pi代Pi )即得 B* A*.,对偶原理(定理1.2-2) 设 A, B 为仅含命题变元P1,Pn 及 ,的合式. 若 A B, 则 B* A*, 反之亦真.,由于 A* A, B* B, 只需证前者即可. 若 A B, 即 A B 永真, 则 AB 和 BA 都永真, 由定理1.2-3 得 A* B* 和 B* A*都永真, 由此得证 A* B*.,析取范式与合取范式,基本积: X1X2Xn 基本和: X1X2Xn 其中, n0, 且每个 Xi 是命题变元或命题变元的否定. 当 n=1 时, 只有一项: X1,它既是基本积也是基本和. 换句话说,命题变元或命题变元的否定既是基本积也是基本和.,注意下列定理也是互相对偶的：,定理 1.3-1 基本积为矛盾式,当且仅当它含有一个命题变元及其否定. 定理 1.3-2 基本和为重言式,当且仅当它含有一个命题变元及其否定.,定理 1.3-2 基本和A为重言式,当且仅当它含有一个命题变元及其否定.,证: 充分性: 若A含有P与 P,则 A =(P P)B TB T 必要性:若A=X1X2Xn T.我们要证一定存在命题变元 P,使 P, P X1,X2,Xn. 不然的话, A只含有P, P之一. 对A中不带否定符的每个命题变元指派F,带否定符的指派T,则在此指派下A的真值为F,便与为重言式矛盾.,析取范式 : A A1A2An 其中, n0, A1, A2 , , An 为基本积. 例: P(PQ)(QR) 合取范式 : A A1 A2 An 其中, n0, A1, A2 , , An 为基本和. 例: ( PQR)( Q R),定理 对于任何命题公式A都存在与其逻辑等价的析取范式和合取范式,证: 使用下列算法一定能够找到与A等价的析取范式和合取范式: 用命题定律消去A中除 ,外的其它联结词; 用 ( P)=P 和摩根律将A中的 都消去或移到命题变元之前; 用结合律、分配律将公式化成析、合取范式,例 求 A = (PQ)P 的析,合取范式:,解 A ( PQ)P (蕴涵表达式) (P Q)P (摩根律) 最后一式为析取范式. 为求合取范式, 再用分配律和等幂律得 A (PP)( Q)P) P( QP) 上述两式都是A的合取范式. 再用吸收律得 A P 这是A的最简合(析)取范式.,例1(b) 求 (PQ)(PQ) 的最简析取范式:,解 ( PQ)(PQ) ( PQ)(PQ) ( PQ)(PQ) (P6 例10) (P Q(PQ) (PQ)(PQ) 摩根律 F(PQ)(PQ)交换,矛盾律 (QP)(PQ) 同一,分配律,例2(a) 求最简范式 A = Q(P Q)( P Q),解 A Q(P Q)( P Q) 结合律 Q(P P) Q) 分配律 Q(T Q) 排中律 T 同一,排中律 结论：A是重言式.,范式不唯一性,由上例可见，无论析取范式或合取范式都不是唯一的。这带来许多不便，故有进一步改进范式的必要。从而提出主析取范式、主合取范式的概念。 主析取范式、主合取范式的显著优点是其唯一性一定成立。,极小项的记法与编号,设n=3, 令3个命题变元为 P1,P2,P3，称 X1X2X3为极小项 当且仅当 Xi Pi, Pi. 将极小项X1X2X3 与3位二进制串abc按下列规则对应: a=1(0) 当且仅当 X1=P1(P1) b=1(0) 当且仅当 X2=P2(P2) c=1(0) 当且仅当 X3=P3(P3) 再把 abc 的(十进制)数值记为r,则可用 mr记该极小项,换句话说,我们用abc和r表示8个极小项及其顺序.,任何非永假(真)命题A都有主析(合)取范式,求主析(合)范式的两种常用方法: 公式化归法 真值表法,主析(合)取范式公式化归法步骤:, 把给定命题公式化成析(合)取范式. 删除析(合)取范式中所有为永假(真)的基本积(和). 用等幂律将重复出现的变元化简为一次出现. 用同一律补进析(合)取范式中未出现的所有变元.,用公式化归法求A=(PQ)P 的主析取范式,解 A (PQ)Q (PQ)(QQ) 分配律 (PQ)(TQ ) 等幂,同一律 (PQ)(PP)Q) 排中律 (PQ)(PQ)(PQ)分配律 (PQ)(PQ) 等幂律 m1 m3 (1,3),用真值表法求A=(PQ)Q 的主析取范式 由下表得答案: A ( PQ)(PQ),用公式化归法求A=(PQ)Q 的主合取范式,解 A (PQ)Q (PQ)(PP)Q) (PQ)(PQ)(PQ) (PQ)(PQ) M0 M2 (0,2),用真值表法求A=(PQ)Q 的主合取范式 由下表得答案: A ( PQ)(PQ),用A的真值表同时可求A的主析、合取范式 例如对A=(PQ)Q,其真值表列有两个1分别对应的PQ二进制串为:01,11,由此得主析取范式为: ( PQ)(PQ); A的真值表列有两个0分别对应的PQ二进制串为:00,10,由此得主合取范式为: (PQ)( PQ),任何非永假(真)命题公式A的主析(合)取范式都是唯一的,证(反证法) 设A有两个不同的主析取范式:A1和A2, 则 A1A2. 由于A1和A2不同,故有极小项m只出现在它们的一个当中.不妨令m在A1而不在A2中. 取A1和A2的所有小项除m为成真外全为成假指派，于是对应这个指派, A1为真而A2为假, 便与A1A2矛盾。,极小项、大项性质的证明 (5)由摩根律直接推出，例如当n=3时， m1 = (PQR)PQR = M1 因(2),(4),(6)是(1),(3),(5) 的对偶式，故只需证明(1),(3),(5) (1)的证明 若ij, 则 mi mj 分别含有 P,P,从而 mimj (PP)W,W为基本积得证 mimj F. (3)的证明 因(3)的左边包含所有极小项,故由分配律它逻辑等价于 (P1P1) (PnPn) T,如果把互相逻辑等价的命题公式看作一类,则n个变元的命题公式恰有4n个等价类.由于主析(合)取范式的等价唯一性,4n也是主析(合)取范式的个数,证: 每个等价类都有相同的真值表，而真值表是2n维(0,1)-向量，其总数为2的2n次方个.,n个变元时,极大(小)项有2n个;主析(合)取范式有22n = 4n个. 4n是2n元集的所有子集的个数.,例如: n=2时,4个极小项为 PQ, PQ, PQ, PQ 主析取范式共有16个,如教本所示.,二元运算有16种可能定义:f1-f16,它们可分成8组，每组两个元:一个运算及其非运算. 例如: f1 F 与 f16 T 为一组; 又 f2 (PQ) 与 f14 PQ; f12 (PQ) 与 f5 PQ; f9 (PQ) 与 f8 PQ; f3 (PQ) 与 f13 PQ; f4 (QP) 与 f14 QP 配对.,扩充联结词及其真值表,与非: PQ (PQ) 或非: PQ (PQ) (PQ)* (与对偶) 异或: PQ (PQ) (PQ)(PQ),F都是全功能的,证: 我们已证,是全功能的.,的全功能性分别由公式: PPP,(PP)(QQ)PQ; PPP,(PQ)(PQ)PQ 推出.,F的全功能性则由公式: PQPQ,PPFPF 推出., 都不是全功能的,证: 若,为全功的则PQ必可只用,等价地表示出来.但P,Q,P,Q,PQ 的真值表列作为4维(0,1)-向量都恰有两个1,而PQ的真值表有3个1和一个0,所以, PQ 显然不能只用,等价地表示出来.这个矛盾证明所需结论. 同理可证:, 不是全功能的.,在逻辑学中把从所谓前提的一些命题出发,依据公认的推理规则,推导出所谓结论的一个命题的过程称为有效推理或形式证明, 所得结论叫做有效结论.,1.5 推理规则和证明方法,例如, 由前提: 若x是偶数, 则x2是偶数并且x是偶数 推导出结论: x2是偶数 的形式证明可以表示为: (PQ)P Q, 其中, P: x是偶数, Q: x2是偶数. 注: 还有别的表示方法,如教本所示,但今后 我们常用这里介绍的表示法.,在形式证明中的重要注意事项,在形式证明中重要的是推理的有效性而不在于结论是否真实; 所谓推理有效是指它的结论是它的前提的合乎逻辑的结果, 也即是说, 若前提为真则所得结论必然为真, 这里并不要求前提或结论一定为真或一定为假.,结论C为前提H1,H2,Hn的有效结论,当且仅当H1H2Hn C, 即H1H2Hn C 为重言式(T),例1 由假言推理(I3): (PQ)P Q, 所以, Q为P,PQ的有效结论. 例4 由拒取式(I4): (PQ)Q P, 所以, P为PQ,Q的有效结论. 注: C为B的有效结论, 即BC 的主要含义是:B为真时C必为真.,由此可见,可用真值表判明C 是否为H1,H2,Hn 的有效结论,也可用公式归约把H1H2Hn C等价地化为永真命题T来证明C 是否为H1,H2,Hn 的有效结论. 因此,表1.2-1,表1.2-2,代入规则,替换规则,对偶原理等已知结论都可作为本节的形式推理规则来应用.,习题1.5 #2(a) 用真值表证明 PQ (PPQ),例2的推理不正确. 因为(PQ)QP不是重言式. 例如,在指派:P为假且Q为真的指派下, PQ为真,从而 (PQ)Q为真, 但P为假最后给出 (PQ)QP为假的矛盾.,例3的推理不正确. 因为(PQ)P Q不是重言式. 例如,在指派:P为假且Q为真的指派下, (PQ )P为真,从而给出 (PQ)P Q为假. 注：这是两个常犯的错误，切记莫犯.,用公式化归法证构造性两难推理: (PQ)(RS)(PR) QS,证: (PQ)(RS)(PR) QS (PQ)(RS)(PR)QS (PQ)(RS)(PR)QS (PQ)Q(RS)S(PR) PQRS (PR) (PR)(PR)QS TQS T,注意: 可以用真值表证明有效结论,但在命题变元较多时用真值表法是相当不方便的.,例如,若用真值表法证构造性两难推理: (PQ)(RS)(PR) QS 将要求构造一个有16行的真值表,这会是相当不方便的.,用公式化归法证破坏性两难推理: (PQ)(RS)(QS) PR,证: (PQ)(RS)(QS) PR (PQ)(RS)(QS )PR (PQ)P(RS)R(QS) (QP)(SR)(QS) PR(QS)(QS) PRT T,演绎法证明中的公认推理规则, P规则(前提引入): 在推导过程中前提可视需要随时引入使用. T规则(前提引入): 在推导过程中前面已导出的有效结论Q都可作为后继的前提随时引入使用.(依据是 前提三段论I6: (PQ)(QR)PR) CP规则(条件证明引入): 为了证明有效结论QR,只需将Q加入前提中再去推出R即可. (依据是 输出律 E22: P(QR) PQR),形式推理的表上作业,形式推理的具体操作可在包含3列的一张表上进行. 第一列是序号列, 将各次操作按先后排序; 第二列是断言列或命题公式列, 内容可以是前提, 中间结论或最终结论; 第三列是注释列或根据列,表明所引用的推理规则及与之有关的行的编号. 第三列是形式推理的特点与优点.,形式推理举例 证例5(b): (CD)(CR)(DS) RS,步骤 断言 根据 . 1 CD P 2 CD T,1,蕴含表达 3 DS P 4 CS T,2,3,前提三段 5 CR P 6 RC T, 5, 逆反律 7 RS T,4,6,前提三段 8 RS T,7,蕴含表达,#6(c) 问题归结为证: (PQ)R)(SP)Q SR, 其中P,Q,R,S分别表示李来学院,王生病,王去看李,李去南京.,步骤 断言 根据 . 1 S CP 附加前提 2 SP P 3 P T,1,2,假言推理 4 Q P 5 PQ T,3,4,合取式 6 (P Q)R P 7 R T,5,6,假言推理 8 SR CP,1,7,反证法基础(归谬定理): 若 H1Hn有成真指派, 且 H1HnCRR, 则 H1HnC.,证: H1HnC RR (F) 表明H1HnC 为永假(矛盾式),即对任何使 H1Hn 为真的指派必使C 为假,即C为真. H1Hn C.,证明(PQ)(RS)(PR) QS,步骤 断言 根据 . 1 PR P 2 (QS) P 反证法 3 QS T,2,摩根律 4 Q T,3,简化律 5 S T,3,简化律 6 PQ P 7 P T,4,6,拒取式 8 RS P 9 R T,5,8,拒取式 10 PR T,7,9,合取式 11 (PR) T,10,摩根律 12 (PR)(PR) T,1,11,合取式矛盾,习题1.5 #13 说明 从假的前提出发能证明任意命题,只须由下表证明 PPQ 步骤 断言 根据 . 1 PP P 2 P T, 1, 简化式 3 PQ T, 2, 加法式 4 PQ T, 3, 蕴含表达式 注: 已证对任意命题公式P成立PT, 由逆反律这逻辑等价于FP, 以Q记任意命题P即得 FQ.,概念与定义: 个体,谓词,谓词命名式, n 元谓词.,在原子命题(陈述句)中所描述的对象称为个体(常用小写字母表示); 用以描述个体性质或个体间关系的部分称为谓词(常用大写字母表示); 一个原子命题用一个谓词P和n 个有序的个体变元 a1 , ,an 表示成 P(a1,an),并称为谓词命名式; P 称为n 元谓词.,谓词命名式进一步解释,例1 x 是素数中x 是个体,谓词是是素数 ,记为 P,则此谓词表达式可写为 P(x). 特别, P(5)是命题:5是素数. 此例中x 表示不确定的个体,称为个体变元, 5 是个体常元. 注意P(x)把谓词命名式进一步抽象化;并且P(x)的真值随x 而变,它对某些x 可能为真,对某些x 可能为假.所以,P(x)是命题函数,而不是(命题演算部分中要求的非真即假的)命题.,谓词命名式的中缀记法,例如 原子命题:x-y=z,意指 x减去y等于z,其中有3个个体变元:x,y,z,若记此谓词为 P,则可把它表示为 P(x,y,z).对于由数学公式定义的原子命题,更方便的谓词记法是直接用数学式代替谓词命名式,并称为谓词的中缀记法. 注意:n 元谓词公式中个体的顺序是重要的,顺序变了谓词公式的含义也变了. 例如, 对上例有 P(x,y,z) x-y=z y-x=z P(y,x,z),谓词概念是命题概念的扩充与深化,考虑谓词: P(x,y,z)x y=z.若定义 P1(y,z)P(3,y,z)3y=z; P2(z) P(3,2,z)3-2=z; P3P(3,2,1)3-2=1, 则P(x,y,z),P1(y,z),P2(z)分别是3元,2元,1元谓词,它们都不是命题演算中的命题,而P3 是0元谓词,是命题演算中的命题. 由此可见:谓词概念是命题概念的扩充与深化.,Fray引入全称量词和存在量词使得用逻辑符号表示命题概念的能力大为加强,x,表示并读作:对一切x; xP(x),表示并读作:对一切x,P(x)是真(称x被全称量化); x,表示并读作:存在一个x; x P(x),表示并读作:存在一个x,P(x)是真 (称x被存在量化). 例 当论述域为实数集R时, x(xx+1)表示对一切实数x,xx+1为真. 例 当论述域为实数集R时,y(y=3)表示存在一个实数y,y=3 为真.,习题1.6 #3 令S(x,y,z)x-y=z; M(x,y,z)xy=z,(c)用谓词表示:任何整数减去0,其结果是原整数. 解:答案为: xS(x,0,x). (d)用谓词表示:对所有x,对所有y,xy=y. 解:答案为: xyM(x,y,y).,!xP(x)表示:存在唯一的x使P(x)为真.可将!xP(x)表为只用,=构成的式子.,注意: 如果!xP(x)为真,则xP(x)为真; 对任意两个非空集合S,R,如果S中任一元都等于R中任一元,则S=R,并且是一元集. 答案为: !xP(x)等价于() xP(x)xy(P(x)P(y)(x=y).,谓词F(x)(命题函数)变命题的两种途径,令命题变元x取定一个a值,所得F(a)是命题. 将谓词量化,如xF(x),xF(x)都是命题(可取非真即假的真值). 例如, F(x) x 是素数 不是命题,因其真值随x而变,但xF(x)是命题,因它有唯一的真值:假; xF(x)也是命题,因它有唯一的真值:真.,习题1.6 #11 (e),(k),令论述域:I; E(x,y): x=y; G(x,y):xy, 则 (e) 除非y0 x2=y不存在解 可符号化为 xy(G(y,0)E(y,0) E(x2,y) 或 xy(E(x2,y)G(y,0)E(y,0). (f) 存在一个x,对每一对y和z,使xy=xz可符号化为 xyzE(xy,xz).,量化后所得命题的真值与论述域有关,即随个体域不同而可能不同,例1 y(y=3)当论述域为正整数集N时为真; 而当论述域为负整数集-N时为假. 例2 x(x0)当论述域为N时为真;而当论述域为R时为假.,全总个体域与特性谓词的概念与例子,令D(x)表示x是要死的; F(x)表示x是不怕死的.当论述域为全人类时,人总是要死的 译为xD(x),有些人不怕死 译为xF(x).而当论述域为全总个体域时, 它们分别译为 x(M(x)D(x), x(M(x)F(x),其中,M(x)表示x是人. 苏格拉底论证(教本P.33)可符号化为: (x(M(x)D(x) M(s)D(s),其中s表示特定的一个人:苏格拉底.(习题#10),特性谓词加入断言规则: 全称谓词作蕴涵式前件加入; 存在谓词作合取项加入.,例如,令P(x)表示x为素数,则有(1.5习题#15 (k),(l): 任何两个素数之和是一个素数可符号化为: xy(P(x)P(y)P(x+y); 存在两个素数其和是素数 可符号化为: xy(P(x)P(y)P(x+y).,谓词逻辑的翻译或符号化概念与步骤,把一个文字叙述的命题用谓词公式表示出来的过程称为谓词逻辑翻译或符号化,其一般步骤如下: 正确理解给定命题,必要时可适当加以改叙使其中的原子命题的关系更明显. 把每个原子命题分解成个体，谓词和量词,在全总个体域中讨论时要给出特性谓词. 找出适当量词,注意后跟蕴涵式,后跟合取式.,谓词逻辑符号化之例(习题1.6 #13),(d)令T(x):x是火车;C(x):x是卡车;Q(x,y):x比y快,则某些卡车慢于所有火车,但至少有一火车快于每辆卡车可符号化为 y(C(y)x(T(x)Q(x,y) u(T(u)v(C(v)Q(u,v). (f)令论述域为全人类; B(x):x步行;M(x):x骑马; C(x):x乘车; K(x):x口渴; Q(x):x喝泉水. 则所有步行的,骑马的或乘车的人，凡是口渴的都喝泉水可符号化为 x(B(x)M(x)C(x)(K(x)Q(x).,用函数观点理解谓词逻辑的翻译,下列两例中论述域都是全人类. 例1 翻译张强是李冰的外公.(1.6习题#14) 解: 答案为: x(F(z,x)M(x,l),其中, F(x,y):x是y的父亲; M(x,y):x是y的母亲; z张强; l李冰. 例2 翻译张强的父亲是教授. 解:答案为: P(f(z),其中,P(x):x是教授; f(x):x的父亲(f(x)为个体); z张强.,论述域为有限集时量化断言与命题的关系,不失一般性设论述域为1,2, ,n. 则有下列逻辑等价关系: xP(x)P(1) P(n); xP(x) P(1) P(n).,谓词演算的合式公式(谓词公式),不出现命题联结词和量词的谓词命名式称为谓词演算的原子公式. 由下列递归规则生成的公式称为谓词公式: (1)单个原子公式是谓词公式. (2)若A和B是谓词公式，则 A,AB,AB,AB,AB,xA,xA是谓词公式. (3)只有有限步应用(1)和(2)生成的公式才是谓词公式.,辖域,自由变元与约束变元,确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式,具体地讲: 若量词后有括号,则括号内的子公式就是该量词的辖域; 若量词后无括号,则与量词邻接的子公式为该量词的辖域. 判定公式中的个体变元是约束变元还是自由变元,关键在于看它是约束出现还是自由出现.,辖域,自由变元与约束变元举例, 在 xP(x)Q(x) 中,x的辖域是P(x); 在 y(C(y)x(T(x)uQ(x,u) 中,u的辖域是Q(x,u); x的辖域是T(x)uQ(x,u); y的辖域是 C(y)x(T(x)uQ(x,u).,基本定义,谓词公式A在任意论述域上对A中谓词变元指派以任一有定义的确定的谓词;对A中的个体变元指派以任一确定的个体后 A永真, 则称A永真; A永假, 则称A永假; 否则, 称A可满足. 两个谓词公式A,B在其公共论述域上的任意上述两种指派下所得命题都有相同真值时(即AB为永真式),称A和B等价,记为 A B.,谓词公式的逻辑等价举例,设P,Q为任意谓词变元;x为全总个体域上的个体变元,则谓词公式 A=P(x)Q(x) 与B=(P(x)Q(x)逻辑等价. 证 将P,Q分别指派以任意确定的一元谓词U,V,同时将x,y分别指派以任意确定的个体a,b之后,由A,B分别得到命题公式U(a)V(b)和(U(a)V(b). 但由摩根律上述命题公式的真值表相同,所以 AB. 仿此,可从表1.2-1的每个命题演算的逻辑等价式或表1.2-2的每个永真蕴涵式得到相应的谓词公式的等价式.,谓词永真蕴涵式AB的含义是谓词公式AB为永真式,例: 设A=P(x)Q(y),B=P(x),论其中, P,Q为任意谓词变元;x,y为全总个体域上的个体变元,则AB. 证 考虑AB P(x)Q(y)P(x).将P,Q指派以任意确定的一元谓词U,V,同时将x,y指派以任意确定的个体a,b之后得到命题公式U(a)V(b)U(a). 由简化律(I2)知上述命题公式为重言式, 所以 AB.,量词的否定与摩根律-与的对偶性,当个体域为有限集x1,xn时, (xP(x) xP(x) 可表为 (P(x1)P(xn)P(x1)P(xn); (xP(x)xP(x) 可表为 (P(x1)P(xn)P(x1) P(xn). 这些正是熟知的摩根律. 从中我们也发现与具有对偶性. 而当个体域不为有限集时, 量词否定可视为摩根律的推广.,谓词演算中的对偶原理,在仅含 , ,的谓词公式A中,将其中的与,T与F, 与 对换所得公式称为A的对偶式,记为A. 对偶原理:对任意谓词公式A,B都有 AB 当且仅当 AB; AB 当且仅当 BA.,量词辖域扩张收缩基本公式的对偶性,4个量词辖域扩张收缩四个基本公式中 xA(x)P x(A(x)P)与 xA(x)P x(A(x)P) 互相对偶; xA(x)P x(A(x)P)与 xA(x)P x(A(x)P) 互相对偶, 其中, P为不含自由变元 x 的任意谓词. 证式:当P为真时,左右两边都为真;否则, P为假,此时左右两边都等价于xA(x), 证迄.,量词的分配形式永真公式的对偶性,4个量词分配形式永真公式中前两个公式的对偶性易见. 今证后两个公式 x(A(x)B(x) xA(x)xB(x), xA(x)xB(x) x(A(x)xB(x) 的对偶性.事实上,由对偶原理知: 等价于 (xA(x)xB(x) (x(A(x)B(x). 后一式正是. 证式:当左边成立时,即存在一个x使A(x)B(x) 是真,所以, xA(x)xB(x)是真.,多个量词永真式的例子,P43(vii)中的公式: yxP(x,y)xyP(x,y) 显然成立;但其逆命题: xyP(x,y)yxP(x,y) 的却不成立(即不是等价式). 这一点可由下列反例推出: 令 P(x,y) x+y=0,论述域是有理数集合,则xyP(x,y)是真,但yxP(x,y)是假.,表1.7-1中公式的对偶性,由对偶原理可推出下列各对公式互为对偶: Q1与 Q2; Q3与 Q4; Q5的对偶是x P(x)x P(x),即是它自己; Q6与 Q9; Q7与 Q8; Q10与 Q11; Q12与 Q13; 注意: Q14与 Q15 不互为对偶.,某些常用含量词永真公式的证明,Q18 x(A(x)B(x) xA(x) xB(x). 证 x(A(x)B(x) x( A(x)B(x) 蕴涵表达式 x A(x)xB(x) 量词分配 xA(x)xB(x) 量词否定 xA(x) xB(x) 蕴涵表达式,某些常用含量词永真公式的证明,Q15 xA(x)B x(A(x)B) (B不含x) 证 xA(x)B (xA(x)B 蕴涵表达式 x A(x)B 量词否定 x(A(x)B) 量词辖域扩张 x(A(x)B) 蕴涵表达式,某些常用含量词永真公式的证明,Q16 AxB(x) x(AB(x) (A不含x) 证 AxB(x) AxB(x) 蕴涵表达式 x( AB(x) 量词