《1_ch1.1 预备知识-2011.9》由会员分享，可在线阅读，更多相关《1_ch1.1 预备知识-2011.9（72页珍藏版）》请在金锄头文库上搜索。
1、2017年6月5日星期一,1,第1讲 预备知识,命题逻辑基础 命题公式：联结词、真值表、永真式、符号化 等值演算：等值式、等值演算 形式化证明：命题逻辑推理数理逻辑基础 个体、谓词与量词 命题符号化 一阶谓词逻辑公式及分类 一阶谓词逻辑等值式与基本等值式 前束范式 重要的推理定律,2017年6月5日星期一,2,命题公式联结词,命题：能表达判断，并且具有确定真值的陈述句。简单命题： p, q, r, p1, q1, r1,联结词 ： 合取联结词：“与” 析取联结词：“或” 否定联结词： 蕴涵联结词：“充分条件” 等价联结词：“充分必要条件”逻辑真值： 0，1, (F，T 或 假，真),2017年
2、6月5日星期一,3,联结词否定,P为真当且仅当P为假.例 p：上海是一个大城市。 p：上海不是一个大城市。 上海是一个不大的城市。,2017年6月5日星期一,4,pq为真当且仅当p与q同时为真.例 (1) 王晓既用功又聪明. (2) 王晓一边吃苹果一边看电视,联结词合取,2017年6月5日星期一,5,联结词析取,pq为假当且仅当p与q都为假.,2017年6月5日星期一,6,联结词蕴含联结词,pq为假当且仅当p为真而q为假. 称p为前件,q为后件.例 如果 3+3=5, 那么雪是白的. p: 3+3=5, q: 雪是白的. pq,2017年6月5日星期一,7,联结词等价式,pq为真当且仅当p与q
3、的真值相同.,例 求下列复合命题的真值 .(1) 两个等腰三角形全等，当且仅当它们的三组对应边相等。(2) 如果两个圆的面积相等，则它们的半径相等，反之亦然.,2017年6月5日星期一,8,命题公式,命题公式的形成规则: 1. 单个命题变元（或常元）是命题公式。 2. 如果A是命题公式, 那么A也是命题公式。 3. 如果A、B是命题公式, 那么 (AB), (AB), (AB)和(A B)是命题公式。 4. 当且仅当经过有限次地使用1、2、3所组成的符号串才是命题公式。注：p, q, r, 既可以表示命题(命题常元),也可以表示命题变元.,2017年6月5日星期一,9,真值表(truth-ta
4、ble),赋值(assignment)：给变元指定0、1值.n个变元,共有2n 种不同的赋值,有22n种不等值公式.,2017年6月5日星期一,10,命题公式的真值表,例 求 (pq)r 和 pqr 的真值表。,2017年6月5日星期一,11,公式的类型,永真式: 在各种赋值下取值均为真(重言式)永假式: 在各种赋值下取值均为假(矛盾式)可满足式：非永假式,2017年6月5日星期一,12,*命题符号化举例合取,例1 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓虽然聪明，但不用功. 解: 令 p: 王晓用功，q: 王晓聪明 (1) pq (2) pq. (3) 王丽一边吃苹果，一
5、边看电视. r:王丽吃苹果，s:王丽看电视 r s.,2017年6月5日星期一,13,*命题符号化举例合取(续),(4) 张辉与王丽都是优秀学生.r: 张辉是优秀学生，s:王丽是优秀学生, r s(5) 张辉与王丽是同学. s : 张辉与王丽是同学.分清简单命题与复合命题。 (5) 中“与”联结主语成分，因而(5) 是简单命题.,2017年6月5日星期一,14,*命题符号化举例析取,“或”的两种表示方法：根据题意，若“p或q”为真， p和q可以单个为真, 也可以同时为真，则为“可兼或”. 符号化为pq.根据题意，若“p或q”为真， p和q可以单个为真, 但不能同时为真，则为“排斥或”. 符号化
6、为 (pq) (pq),2017年6月5日星期一,15,*命题符号化举例析取(续),例2 将下列命题符号化 (1)他昨天做了二十或三十道习题。 解: (1)是原子命题, 用 m 表示. (2) 2或4是素数. 解: 令 p: 2是素数, q: 4是素数, 则 (2) p q, 其真值为 t. (3) 王晓红生于1975年或1976年. 解: 令 y: 王晓红生于1975年,u: 王晓红生于1976年. y, u不能同时为真, 可以同时为假, 可符号化为 (yu) (yu). 由于实际中y, u不能同时为真,所以也可符号化为 yu.,2017年6月5日星期一,16,*命题符号化举例析取(续),(
7、4) 小元只能拿一个苹果或一个梨.解: 令 v : 小元拿一个苹果, w: 小元拿一个梨， 这里的“或”受到“只能”的限制, 应为排斥或, (vw) (vw) (3)与(4)中的排斥或不同, (3)中y, u不能同时为真, 而(4)中的v 和w可能同时发生, 所以不能符号化为vw。,2017年6月5日星期一,17,*命题符号化举例蕴涵,自然科学中, “pq”表达 p 为 1, q 也为 1 的推理关系. p 为0时，数理逻辑规定 pq 永为1，称为“善意的推定”。 pq 的逻辑关系：q为p的必要条件, p是q的充分条件. “如果p，则q” 的不同表述方式 “若 p，就 q” “只要 p，就q”
8、 “ p 仅当 q” “只有 q 才 p ” “除非 q, 才 p” 或 “除非 q, 否则非p”. 常出现的错误：不分充分与必要条件.,2017年6月5日星期一,18,*命题符号化举例蕴涵(续),例3 将下列命题符号化. (1) 如果我借到这本书, 今夜就读完它. p: 我借到这本书, q: 我今夜读完这本书. pq (2) 如果 3+3=5, 那么雪是白的. p: 3+3=5, q: 雪是白的. pq (3) 如果 3+3=5, 那么雪是黑的. p: 3+3=5, q: 雪是白的. pq,2017年6月5日星期一,19,*命题符号化举例蕴涵(续),例4 设 p: 天冷，q: 小王穿羽绒服.
9、 符号化下列命题. (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,pq,pq,qp,pq,qp,qp,pq,qp,2017年6月5日星期一,20,逻辑等值式(identities),等值： AB读作：A等值于B含义：A与B在各种赋值下取值均相等。AB 当且仅当AB是永真式 例如： (pq)r pqr,2017年6月5日星期一,21,常用逻辑等
10、值式(关于与),幂等律(idempotent laws)AAAAAA 交换律(commutative laws)ABBAABBA,2017年6月5日星期一,22,常用逻辑等值式(关于与),结合律 (associative laws)(AB)CA(BC)(AB)CA(BC)分配律 (distributive laws)A(BC) (AB )(AC )A(BC) (AB )(AC )吸收律(absorption laws)A(AB) AA(AB) A,2017年6月5日星期一,23,常用逻辑等值式(关于),双重否定律(double negation law)AA德摩根律(DeMorgans law
11、s)(AB) AB(AB) AB,2017年6月5日星期一,24,常用逻辑等值式(关于0,1),排中律(excluded middle)AA1矛盾律(contradiction)AA0零律(dominance laws)A11A00同一律(identity laws)A0A A1A,2017年6月5日星期一,25,常用逻辑等值式(关于),蕴涵等值式 (conditional as disjunction)AB AB假言易位 (contrapositive law)ABBA归谬论(AB )( AB ) A,2017年6月5日星期一,26,常用逻辑等值式(关于),等价等值式 (biconditio
12、nal as implication)AB (AB)(BA)等价否定等值式AB AB,2017年6月5日星期一,27,等值式模式,A，B，C 代表任意的公式上述等值式称为等值式模式 每个等值式模式都给出了无穷多个同类型的具体的等值式。举例：ABAB 取A=p，B=q时，得到 pqpq 取A=pqr，B=pq时，得到(pqr)(pq) (pqr)(pq),2017年6月5日星期一,28,对偶原理,对偶原理:一个逻辑等值式,如果只含有, , ,0,1,同时把与互换、0 与1互换，得到的还是等值式.例 A(BC) (AB )(AC )与 A(BC) (AB )(AC ) AA1与AA0 A11与A0
13、0 A0A与A1A,2017年6月5日星期一,29,等值演算,置换规则: (A)是含有公式 A 的公式, 用公式 B 置换(A)中的A得到(B). 若AB, 则(A)(B)等价演算: 由已知的等值式,应用置换规则推出新等值式的过程.等价演算的基础： (1) 基本等价式 (2) 置换规则,2017年6月5日星期一,30,等值演算（举例）,例：(pq)r pqr解：(pq)r (pq)r （蕴涵等值式） (pq)r （德 摩根律） pqr （结合律）,2017年6月5日星期一,31,*等值演算（举例,续）,例 证明 (PQ) (PQ) P.证明： (PQ) (PQ) P (Q Q) 分配律 P 1排中律 P 同一律,
