1、1第第1章章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类1.3 等值演算等值演算1.4 范式范式1.5 联结词完备集联结词完备集1.6 推理理论推理理论21.1 命题符号化及联结词命题符号化及联结词 命题与真值命题与真值 原子命题原子命题 复合命题复合命题 命题常元命题常元 命题变元命题变元 联结词联结词 3命题与真值命题与真值 命题命题:判断结果惟一的陈述句判断结果惟一的陈述句命题的真值命题的真值:判断的结果判断的结果，非，非真即假真即假真命题真命题:真值为真的命题真值为真的命题假命题假命题:真值为假的命题真值为假的命题注意注意:感叹句
2、、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是陈述句中的悖论以及判断结果不惟一确定的也不是命题命题 4 例例 下列句子中那些是命题？下列句子中那些是命题？(1)是无理数是无理数.(2)2+5 8.(3)x+5 3.(4)你有铅笔吗？你有铅笔吗？(5)这只兔子跑得真快呀！这只兔子跑得真快呀！(6)请不要讲话！请不要讲话！(7)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题25命题的分类命题的分类 简单命题简单命题(原子命题原子命题)：简单陈述
3、句构成的命题简单陈述句构成的命题 复合命题复合命题：由简单命题与联结词按一定规则复合由简单命题与联结词按一定规则复合 而成的命题而成的命题 6简单命题符号化简单命题符号化 2用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i1）表示）表示简单命题简单命题真值的符号化：用真值的符号化：用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为 0 q：2+5=7，则，则 q 的真值为的真值为 1 7复合命题及其符号化：联结词复合命题及其符号化：联结词1.否定式复合命题与否定联结词否定式复合命题与否定联结词“”定义定义 设设P为任
4、意命题，复合命题为任意命题，复合命题 “非非P”(或或“p的否定的否定”)称称 为为P的的否定式否定式，记作，记作 P。其中符号。其中符号 表示表示“非非”，称作称作否定联否定联结词结词。P 为真当且仅当为真当且仅当P为假（根据联结词的涵义）为假（根据联结词的涵义）2.合取式复合命题与合取联结词合取式复合命题与合取联结词“”定义定义 设设P,Q为任意两个命题为任意两个命题,复合命题复合命题“P且且Q”(或或“P与与Q”)称为称为P与与Q的的合取式合取式，记作，记作PQ。其中符号。其中符号表示表示“且且”，称作称作合取联结词合取联结词。PQ为真当且仅当为真当且仅当P与与Q均为真。均为真。注意：合
5、取式描述方式的灵活性与多样性注意：合取式描述方式的灵活性与多样性 分清简单命题与复合命题分清简单命题与复合命题 8 例例 将下列命题符号化将下列命题符号化.(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与王丽是同学张辉与王丽是同学.解解 令令 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1)pq (2)pq (3)q p.9 例例(续续)令令 r:张辉是三好学生，张辉是三好学生，s:王丽是三好学生王丽是三好学生 (4)rs.
6、(5)令令 t:张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题.说明说明:(1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性.(5)中中“与与”联结的是两个名词（而不是两个联结的是两个名词（而不是两个命题），整个句子是一个简单命题命题），整个句子是一个简单命题.10联结词与复合命题联结词与复合命题(续续)定义定义 设设 P,QP,Q为任意两个命题，复合命题为任意两个命题，复合命题“P P或或Q Q”称作称作P P与与Q Q 的的析取式析取式，记作，记作P PQ Q。其中符合。其中符合，表示表示“相容或相容或”，称作，称作析取联结词。析取联结词。P PQ Q为
7、假当为假当且仅当且仅当p p与与q q均为假均为假.例例 将下列命题符号化将下列命题符号化 (1)2或或4是素数是素数.(2)2或或3是素数是素数.(3)4或或6是素数是素数.(4)小小元元只能拿一个苹果或一个梨元元只能拿一个苹果或一个梨.(5)王晓红生于王晓红生于1995年或年或1996年年.3.析取式与析取联结词析取式与析取联结词“”11解解 令令 p:2是素数是素数,q:3是素数是素数,r:4是素数是素数,s:6是素数是素数,则则 (1),(2),(3)均为均为相容或相容或.分别符号化为分别符号化为:pr,pq,rs,它们的真值分别为它们的真值分别为 1,1,0.(4),(5)为为排斥或
8、排斥或.令令 t:小小元元拿一个苹果，元元拿一个苹果，u:小小元元拿一个梨，元元拿一个梨，则则 (4)符号化为符号化为 (t u)(tu).令令v:王晓红生于王晓红生于1995年年,w:王晓红生于王晓红生于1996年年,则则 (5)可符号化为可符号化为 (v w)(vw)。注：在。注：在不强调只能生于一个年份时，也不强调只能生于一个年份时，也可符号化为可符号化为 vw.12联结词与复合命题联结词与复合命题(续续)定义定义 设设 P,QP,Q为任意两个命题，复合命题为任意两个命题，复合命题 “若若P,P,则则Q Q”称作称作P P与与Q Q的的蕴涵式蕴涵式，记作，记作P PQ Q，并称，并称P
9、P是是蕴涵式的蕴涵式的前件或前提前件或前提，q q为蕴涵式的为蕴涵式的后件或结论后件或结论.符号符号表示表示“若，则若，则”（形式推论关系），（形式推论关系），称作称作蕴涵联结词蕴涵联结词。根据形式推论的涵义，根据形式推论的涵义，P PQ Q为假为假当且仅当当且仅当 P P为真且为真且 Q Q为假。为假。4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”13PQ 的逻辑关系：的逻辑关系：P 为为 Q 的充分条件的充分条件，Q 为为 P 的必要条件的必要条件“若若 P，则，则 Q”的不同表述法很多：的不同表述法很多：若若 P，就，就 Q 只要只要 P，就，就 Q P 仅当仅当 Q 只有只有 Q 才才
10、P 除非除非 Q,才才 P 或或 除非除非 Q,否则非否则非 P.当当 P 为假时，为假时，PQ 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件联结词与复合命题联结词与复合命题(续续)14 例例 设设 p p:天冷，天冷，q q:小王穿羽绒服，小王穿羽绒服，将下列命题符号化将下列命题符号化 (1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽
11、绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意：pq 与与 qp 等值（真值相同）等值（真值相同）pqpqpqpqqp qpqpqp15联结词与复合命题联结词与复合命题(续续)定义定义 设设P，Q为任意两个命题，复合命题为任意两个命题，复合命题“P当且当且仅当仅当Q”称作称作P与与Q的的等价式等价式，记作，记作PQ.称作称作等价联结词等价联结词.PQ为真当且仅当为真当且仅当P与与Q真值相同真值相同.说明说明:(1)PQ 的逻辑关系的逻辑关
12、系:P与与Q互为充分必要条件互为充分必要条件 (2)PQ为真当且仅当为真当且仅当P与与Q同真或同假同真或同假5.等价式与等价联结词等价式与等价联结词“”16例例 求下列复合命题的真值求下列复合命题的真值 (1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.(5)函数函数 f(x)在在x0 可导的充要条件是它在可导的充要条件是它在 x0连续连续.11000例例17联结词与复合命题联结词与复合命题(续续)以上给出了以上给出
13、了5个联结词：个联结词：,，组成，组成一个联结词集合一个联结词集合,，联结词的优先顺序为：联结词的优先顺序为：,;如果出如果出现的联结词同级，又无括号时，则按从左到右现的联结词同级，又无括号时，则按从左到右的顺序运算的顺序运算;若遇有括号时，应该先进行括号若遇有括号时，应该先进行括号中的运算中的运算.注意注意:本书中使用的本书中使用的 括号全为圆括号括号全为圆括号.181.2 命题公式及分类命题公式及分类命题变元与合式公式命题变元与合式公式公式的赋值公式的赋值真值表真值表命题的分类命题的分类 重言式重言式 矛盾式矛盾式 可满足式可满足式 真值函数真值函数19命题变元与合式公式命题变元与合式公式
14、 命题常元命题常元：具体的简单命题，真值确定：具体的简单命题，真值确定命题变元命题变元：可表示任意简单命题，真值不确定：可表示任意简单命题，真值不确定定义定义 合式公式合式公式(命题公式命题公式,公式公式)递归定义如下：递归定义如下：(1)单个命题常元或变元单个命题常元或变元 p,q,r,pi,qi,ri,0,1 是是合式公式合式公式(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式(3)若若A,B是合式公式，则是合式公式，则(A B),(A B),(AB),(AB)也是合式公式也是合式公式(4)只有有限次地应用只有有限次地应用(1)(3)形成的符号串才是形成的符号串才是合
15、式公式合式公式说明说明:外层括号可以省去外层括号可以省去 20合式公式的层次合式公式的层次 定义定义(1)若公式若公式A是单个命题常是单个命题常/变元变元,则称则称A为为0层公式层公式.(2)称称A是是n+1(n0)层公式是指下面情况之一：层公式是指下面情况之一：(a)A=B,B是是n层公式；层公式；(b)A=B C,其中其中B,C分别为分别为i层和层和j层公式，且层公式，且 n=max(i,j)；(c)A=B C,其中其中B,C的层次及的层次及n同同(b)；(d)A=BC,其中其中B,C的层次及的层次及n同同(b)；(e)A=BC,其中其中B,C的层次及的层次及n同同(b).21合式公式的层
16、次合式公式的层次(续续)例如例如 公式公式 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 (p q)r)(r s)4层层22公式的赋值公式的赋值 定义定义 给公式给公式A中的命题变元中的命题变元 p1,p2,pn指定指定一组真值，称为对一组真值，称为对A的一个的一个赋值赋值或或解释解释成真赋值成真赋值:使公式为真的赋值使公式为真的赋值成假赋值成假赋值:使公式为假的赋值使公式为假的赋值说明说明：赋值赋值=1 2 n之间不加标点符号，之间不加标点符号，i=0或或1.A中仅出现中仅出现 p1,p2,pn，给，给A赋值赋值 1 2 n是是指指 p1=1,p2=2,pn=n A中仅出现中仅出
17、现 p,q,r,给给A赋值赋值 1 2 3是指是指p=1,q=2,r=3 含含n个变元的公式有个变元的公式有2n个赋值个赋值.23真值表真值表 真值表真值表:公式公式A在所有赋值下的取值情况列成的表在所有赋值下的取值情况列成的表 例例 给出公式的真值表给出公式的真值表 A=(qp)qp 的的真值表真值表 p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 111124例例 B=(p q)q 的的真值表真值表 p q p p q (p q)(p q)q0 00 11 01 1 1100110100100000实例实例25例例 C=(p q)r 的的真值表真值表
18、p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 1110101026公式的类型公式的类型 定义定义 设设A为一个命题公式为一个命题公式 (1)若若A无成假赋值，则称无成假赋值，则称A为为重言式重言式(也称也称永真式永真式)(2)若若A无成真赋值，则称无成真赋值，则称A为为矛盾式矛盾式(也称也称永假式永假式)(3)若若A不是矛盾式，则称不是矛盾式，则称A为为可满足式可满足式注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真.上例中上例中A为重言式，为重言式，B为矛盾
19、式，为矛盾式，C为可满足式为可满足式 A=(qp)qp，B=(p q)q，C=(p q)r27真值函數真值函數 n22问题：含问题：含n个命题变元的所有公式共产生多少个互个命题变元的所有公式共产生多少个互不相同的真值表？不相同的真值表？定义定义 称定义域为称定义域为000,001,111，值域，值域为为0,1的函数是的函数是n元真值函数元真值函数，定义域中的元素是，定义域中的元素是长为长为n的的0,1串串，若将所有这些串的集合记为，若将所有这些串的集合记为0,1n，则则F:0,1n0,1 表示表示一个一个n元真值函数元真值函数F.共有共有 个个n元真值函数元真值函数.2 2元真值域函数的例子：
20、元真值域函数的例子：F:0,120,1，且且F(00)=F(01)=F(11)=0，F(01)=1。28命题公式与真值函数命题公式与真值函数)2(13F对于任何一个含对于任何一个含n个命题变元的命题公式个命题变元的命题公式A，都存在，都存在惟一的一个惟一的一个n元真值函数元真值函数F，F就是就是A的真值表的真值表.两个等值的公式，其真值函数相同两个等值的公式，其真值函数相同.下表给出所有下表给出所有2元真值函数对应的真值表元真值函数对应的真值表,每一个含每一个含2 2个命题变元的公式的真值表都可以在下表中找到个命题变元的公式的真值表都可以在下表中找到.例如：例如：pq,p q,(p q)(pq
21、)q)等等都对应都对应表中的表中的292元真值函数对应的真值表元真值函数对应的真值表p q0 00 10 11 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFFp q0 00 10 11 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF301.3 命题逻辑等值演算
22、命题逻辑等值演算 等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则31等值式等值式 定义定义 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称，并称AB是是等值式等值式说明：说明：A或或B中可能有哑元中可能有哑元(非非A和和B的共同变元的共同变元)出现出现.例如，在例如，在(pq)(p q)(r r)中，中，r为左边为左边公式的哑元公式的哑元.用真值表来验证两个公式是否等值，用真值表来验证两个公式是否等值，并取两个者命题变元的并集，则可避免由哑元带来的并取两个者命题变元的并集，则可避免由哑元带来的不一致不一致(例：写出例：写出pq在在p,q,
23、r三个变元下的真值表，三个变元下的真值表，并与并与(p q)(r r)的真值表比较的真值表比较)。练习：请验证。练习：请验证 p(qr)(pq)r p(qr)(p q)r32基本等值式基本等值式 双重否定律双重否定律:AA幂等律幂等律：A AA,A AA交换律交换律:A BB A,A BB A结合律结合律:(A B)CA(B C)(A B)CA(B C)分配律分配律:A(B C)(A B)(A C)A(B C)(A B)(A C)33基本等值式基本等值式(续续)德德摩根律摩根律:(A B)AB (A B)AB吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11,A 00 同一律同一律
24、:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA034基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:ABA B等价等值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础35等值演算与置换规则等值演算与置换规则 等值演算等值演算:由已知的等值式推出新的等值式的过程由已知的等值式推出新的等值式的过程置换规则置换规则：若：若AB,则则(B)(A)把公式把公式(A)当中当中A的某个出现替换成与之
25、等值的的某个出现替换成与之等值的B，得到的得到的(B)与原来的与原来的(A)等值。等值。等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2)基本的等值式基本的等值式 (3)置换规则置换规则 36应用举例应用举例证明两个公式等值证明两个公式等值 例例1 证明证明 p(qr)(p q)r证证 p(qr)p(q r)（蕴涵等值式，置换规则）（蕴涵等值式，置换规则）(pq)r （结合律）（结合律）(p q)r （德（德 摩根律，置换规则）摩根律，置换规则）(p q)r （蕴涵等值式）（蕴涵等值式）说明说明:也可以从右边开始演算（请做一遍）也可以
26、从右边开始演算（请做一遍）37应用举例应用举例证明两个公式不等值证明两个公式不等值例例2 证明证明:p(qr)(pq)r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一 真值表法（自己证）真值表法（自己证）方法二方法二 观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的的成真赋值，是右边的成假赋值的成真赋值，是右边的成假赋值.方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.3
27、8应用举例应用举例判断公式类型判断公式类型 例例3 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式，置换规则）（蕴涵等值式，置换规则）q(pq)（德（德 摩根律，置换规则）摩根律，置换规则）p(qq)（交换律，结合律）（交换律，结合律）p 0 （矛盾律，置换规则）（矛盾律，置换规则）0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.39例例3(续续)(2)(pq)(qp)解解 (pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最后一步可知，该
28、式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？40例例3(续续)(3)(p q)(pq)r 解解 (p q)(pq)r (p(qq)r （分配律，置换规则）（分配律，置换规则）p 1 r （排中律）（排中律）p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的可这不是矛盾式，也不是重言式，而是非重言式的可满足式满足式.如如101是它的成真赋值是它的成真赋值,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一,应尽量使演算短些应尽量使演算短些第4次作业题 1.判别下列公式的类型，并写出它们的真值表(1)(p q)(q r)(p r)(2)(p q)p(3)(p q)(q q)r)2.（选做）A、B、C、D四人参加百米赛跑。观众甲、乙、丙预测比赛名次如下。比赛结束后发现三个人每人预测对了一半，问实际名次如何（假设无并列）？甲：C第一，B第二 乙：C第二，D第三 丙：A第二，D第四提示：可设pi,qi,ri,si分别表示A第i名，B第i名，这里i=1,2,3,4.该题实际是给出若干命题的合取，求一个成真赋值使所有命题为真。可以用等值演算法逐步化简，直至得到单一而且形式简单的命题，能看出其成真赋值。
