《命题逻辑i命题公式与等值演算概要》由会员分享，可在线阅读，更多相关《命题逻辑i命题公式与等值演算概要（41页珍藏版）》请在金锄头文库上搜索。
1、1,第1章 命题逻辑,1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 范式 1.5 联结词完备集 1.6 推理理论,2,1.1 命题符号化及联结词,命题与真值 原子命题 复合命题 命题常元 命题变元 联结词,3,命题与真值,命题: 判断结果惟一的陈述句 命题的真值: 判断的结果，非真即假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题,4,例 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？ (5)
2、这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,5,命题的分类,简单命题(原子命题)： 简单陈述句构成的命题 复合命题： 由简单命题与联结词按一定规则复合 而成的命题,6,简单命题符号化,用小写英文字母 p, q, r, ,pi,qi,ri (i1）表示 简单命题 真值的符号化：用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1,7,复合命题及其符号化：联结词,1.否定式复合命题与否定联结词“” 定义 设P为任意命题，复
3、合命题 “非P”(或“p的否定”)称 为P的否定式，记作P。其中符号表示“非”，称作否定联结词。P 为真当且仅当P为假（根据联结词的涵义） 2.合取式复合命题与合取联结词“” 定义 设P,Q为任意两个命题,复合命题“P且Q”(或“P与Q”)称为P与Q的合取式，记作PQ。其中符号表示“且”，称作合取联结词。 PQ为真当且仅当P与Q均为真。 注意：合取式描述方式的灵活性与多样性 分清简单命题与复合命题,8,例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解 令 p：王
4、晓用功，q：王晓聪明，则 (1) pq (2) pq (3) q p.,9,例 (续),令 r : 张辉是三好学生，s :王丽是三好学生 (4) rs. (5) 令 t : 张辉与王丽是同学，t 是简单命题 .,说明: (1)(4)说明描述合取式的灵活性与多样性. (5) 中“与”联结的是两个名词（而不是两个命题），整个句子是一个简单命题.,10,联结词与复合命题(续),定义 设 P,Q为任意两个命题，复合命题“P或Q”称作P与Q 的析取式，记作PQ。其中符合，表示“相容或”，称作析取联结词。PQ为假当且仅当p与q均为假.,例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数.
5、(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) 为排斥或. 令 t :小元元拿一个苹果，u:小元元拿一个梨， 则 (4) 符号化为 (tu) (tu). 令v :王晓红生于1995年,w:王晓红生于1996年,则 (5) 可符号化为 (vw)(vw)。注：在不强调只能生于一个年份时，也可符号
6、化为 vw .,12,联结词与复合命题(续),定义 设 P,Q为任意两个命题，复合命题 “若P,则Q” 称作P与Q的蕴涵式，记作PQ，并称P是蕴涵式的前件或前提，q为蕴涵式的后件或结论. 符号表示“若，则”（形式推论关系），称作蕴涵联结词。 根据形式推论的涵义，PQ为假当且仅当 P为真且 Q为假。,4.蕴涵式与蕴涵联结词“”,13,PQ 的逻辑关系： P 为 Q 的充分条件 ，Q 为 P 的必要条件 “若 P，则 Q ” 的不同表述法很多： 若 P，就 Q 只要 P，就 Q P 仅当 Q 只有 Q 才 P 除非 Q, 才 P 或 除非 Q, 否则非 P. 当 P 为假时，PQ 为真 常出现的错
7、误：不分充分与必要条件,联结词与复合命题(续),14,例 设 p:天冷，q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,注意： pq 与 qp 等值（真值相同）,pq,pq,pq,pq,qp,qp,qp,qp,15,联结词与复合命题(续),定义 设P，Q为任意两个命题，复合命题 “P当且仅当Q”称作P与Q的
8、等价式，记作PQ. 称作等价联结词.PQ为真当且仅当P与Q真值相同. 说明: (1) PQ 的逻辑关系: 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 连续.,1,1,0,0,0,例,17,联结词与复合命题(续),以上给出了5个联结词：, , , , ，
9、组成 一个联结词集合, , , , ， 联结词的优先顺序为：, , , , ; 如果出 现的联结词同级，又无括号时，则按从左到右 的顺序运算; 若遇有括号时，应该先进行括号 中的运算. 注意: 本书中使用的 括号全为圆括号.,18,1.2 命题公式及分类,命题变元与合式公式 公式的赋值 真值表 命题的分类 重言式 矛盾式 可满足式 真值函数,19,命题变元与合式公式,命题常元：具体的简单命题，真值确定 命题变元：可表示任意简单命题，真值不确定 定义 合式公式 (命题公式 , 公式) 递归定义如下： (1) 单个命题常元或变元 p,q,r,pi ,qi ,ri ,0,1 是合式公式 (2) 若A
10、是合式公式，则 (A)也是合式公式 (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式 (4) 只有有限次地应用(1)(3)形成的符号串才是合式公式 说明: 外层括号可以省去,20,合式公式的层次,定义 (1) 若公式A是单个命题常/变元, 则称A为0层公式. (2) 称A是n+1(n0)层公式是指下面情况之一： (a) A=B, B是n层公式； (b) A=BC, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c) A=BC, 其中B,C的层次及n同(b)； (d) A=BC, 其中B,C的层次及n同(b)； (e) A=BC, 其中B
11、,C的层次及n同(b).,21,合式公式的层次 (续),例如 公式 p 0层 p 1层 pq 2层 (pq)r 3层 (pq) r)(rs) 4层,22,公式的赋值,定义 给公式A中的命题变元 p1, p2, , pn指定 一组真值，称为对A的一个赋值或解释 成真赋值: 使公式为真的赋值 成假赋值: 使公式为假的赋值 说明： 赋值=12n之间不加标点符号，i=0或1. A中仅出现 p1, p2, , pn，给A赋值12n是 指 p1=1, p2=2, , pn=n A中仅出现 p, q, r, , 给A赋值123是指 p=1,q=2 , r=3 含n个变元的公式有2n个赋值.,23,真值表,真
12、值表: 公式A在所有赋值下的取值情况列成的表 例 给出公式的真值表 A= (qp) qp 的真值表,24,例 B = (pq) q 的真值表,实例,25,例 C= (pq) r 的真值表,26,公式的类型,定义 设A为一个命题公式 (1) 若A无成假赋值，则称A为重言式(也称永真式) (2) 若A无成真赋值，则称A为矛盾式(也称永假式) (3) 若A不是矛盾式，则称A为可满足式 注意：重言式是可满足式，但反之不真. 上例中A为重言式，B为矛盾式，C为可满足式 A= (qp)qp，B =(pq)q，C= (pq)r,27,真值函數,问题：含n个命题变元的所有公式共产生多少个互 不相同的真值表？
13、定义 称定义域为000, 001, , 111，值域 为0,1的函数是n元真值函数，定义域中的元素是 长为n的0,1串，若将所有这些串的集合记为0,1n，则F:0,1n0,1 表示一个n元真值函数F. 共有 个n元真值函数. 2元真值域函数的例子：F:0,120,1， 且F(00)=F(01)=F(11)=0，F(01)=1。,28,命题公式与真值函数,对于任何一个含n个命题变元的命题公式A，都存在 惟一的一个n元真值函数F， F就是A的真值表. 两个等值的公式，其真值函数相同. 下表给出所有2元真值函数对应的真值表, 每一个含 2个命题变元的公式的真值表都可以在下表中找到. 例如：pq, p
14、q, (pq)(pq)q) 等都对应 表中的,29,2元真值函数对应的真值表,30,1.3 命题逻辑等值演算,等值式 基本等值式 等值演算 置换规则,31,等值式,定义 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式 说明：A或B中可能有哑元(非A和B的共同变元)出现. 例如，在 (pq) (pq) (rr)中，r为左边 公式的哑元. 用真值表来验证两个公式是否等值， 并取两个者命题变元的并集，则可避免由哑元带来的 不一致(例：写出pq在p,q,r三个变元下的真值表， 并与(pq) (rr)的真值表比较)。练习：请验证 p(qr) (pq) r p(qr) (pq) r,3
15、2,基本等值式,双重否定律 : AA 幂等律： AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)(AC) A(BC) (AB)(AC),33,基本等值式(续),德摩根律: (AB)AB (AB)AB 吸收律: A(AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA0,34,基本等值式(续),蕴涵等值式: ABAB 等价等值式: AB(AB)(BA) 假言易位: ABBA 等价否定等值式: ABAB 归谬论: (AB)(AB) A 注意: A,B,C代表任意的命题公式 牢记这些等值
