《第编数理逻辑.ppt》由会员分享，可在线阅读，更多相关《第编数理逻辑.ppt（84页珍藏版）》请在三一文库上搜索。
1、1,第 3 编 数 理 逻 辑,第 6 章 命 题 逻 辑,2,6.1 命题的概念与表示,命题 日常语言不确切，具有二义性需引入目标语言、公式符号。 目标语言：表达判断的一些语言的汇集。 判断：肯定、否定的思维形式。 命题：能表达判断，具有确定真值的陈述句。,3,真值：命题的判断结果称为真值。只有“真”和“假”两种，记为“T”和“F”，或“1”和“0”。,没有判断无所谓是非的句子感叹句、疑问句、祈使句不是命题。 原子命题：不能分为更简单的陈述句。 复合命题：由联结词、标点符号和原子命题复合构成的命题。 用大写字母A,B,.,P,Q,.或Ai,12等表示命题。例 P: 今天下雨。12: 今天刮风
2、。 命题标识符：表示命题的符号。,4,例：,1,0,?,(悖论),?,5,命题常量：一个命题标识符表示确定的命题。,命题变量：一个命题标识符仅表示任意命题的位置标志(无真值)。 原子变元：命题变元表示原子命题。,6,6. 2 命题联结词,复合命题原子命题+联结词 否定 定义 设P为命题，P的否定是一个新的命题，记为P。若P为T，则P为F；若P为F，则P为T。,例：P：上海是大城市。 P：上海不是大城市。 或上海是不大的城市。 一元联结词。,7,合取(并且),定义 两个命题P、Q的合取是一个复合命题，记作PQ。当且仅当P、Q同为T时，PQ为T ；在其它情况下，PQ的真值为F。,例: P: 今天下
3、雨. Q: 明天下雨. PQ: 今天下雨且明天下雨。 今天明天都下雨。 这两天都下雨。 二元联结词。,8,与自然语言不同。,P：我们去看电影。Q：房间里有十张桌子。 PQ：我们去看电影且房间里有十张桌子。 仍是新命题。 可将若干个命题联结一起。 P：高中毕业。 Q：上分数线。 R：被某大学录取。 PQR：大学生。,9,析取(或者),定义 两个命题P、Q的析取是一个复合命题，记作PQ。当且仅当P、Q同为F时，PQ为F ；在其它情况下，PQ的真值为T。,例: P: 今天下雨. Q: 今天刮风. PQ: 今天下雨或者刮风。 二元联结词。,10,日常语言中的“或者”可分“可兼或”与“不可兼或”两种：,
4、例1：今天晚上我在家看电视或去剧院看戏。 (不可兼或) 例2：他可能是100米或400米赛跑的冠军。 (可兼或) 析取是可兼或。 例3：P: 他中了大奖。Q: 他中了小奖。 PQ: 他中了大奖或者中了小奖。 (也可能两奖都中),11,不可兼析取 (排斥析取),定义 设P、Q是两个命题，复合命题P Q称为P、Q的不可兼析取。P Q的真值为T当且仅当P与Q的真值不相同；否则，P Q的真值为F。,例: P: 他坐船去大连。 Q: 他乘车去大连。 P Q: 他坐船或乘车去大连。 二元联结词。 P Q (PQ)(PQ),12,蕴含(条件),定义 两个命题P、Q的蕴含是一个复合命题，记作PQ。当且仅当P的
5、真值为T，Q的真值为F时，PQ的真值为F ；在其它情况下，PQ的真值为T。,例1: “如果某动物为哺乳动物，则它必胎生”。将命题符号化。 设P: 某动物为哺乳动物。 Q: 某动物胎生。 命题符号化：PQ。 且命题为真：PQ 1。 二元联结词。,13,例2: “如果我得到这本小说，那么我今天就读完它”。将命题符号化，并求命题的真值。,解 设P: 我得到这本小说. Q: 我今天就读完它. 命题符号化：PQ。 且命题的真值有以下四种实际情况： (1) 我得到这本小说，我今天读完它。(T) (2) 我得到这本小说，我今天没有读完。(F) (3) 我没有得到这本小说，我今天读完它。(T) (4) 我没有
6、得到这本小说，我今天没有读完。(T),14,例3: “如果雪是黑的，那么太阳从西方出”。将命题符号化，并求命题的真值。,解 设P: 雪是黑的。Q: 太阳从西方出。 命题符号化：PQ。 且命题的真值：PQ 1. ,例4: “如果雪是黑的，那么太阳从东方出”。将命题符号化，并求命题的真值。,解 设P: 雪是黑的。Q: 太阳从东方出。 命题符号化：PQ。 且命题的真值：PQ 1. ,15,PQ中P称为前件，Q称为后件。,自然语言中，若前提为假，无论结论为真或假，往往无法判断。,在条件命题中，当前提为假时，结论都为真 称“善意的推定”。,PQ“如果P那么Q” “只要P则Q” “从P推出Q” “P仅当Q
7、” “只有Q才P” “P蕴含Q”,16,等价(双条件),定义 给定两个命题P和Q，复合命题PQ称为双条件命题。当P、Q的真值相同时，PQ的真值为T ；在其它情况下，PQ的真值为F。,例1: “两个三角形全等当且仅当对应边相等”。 设P: 两个三角形全等。 Q: 三角形对应边相等。 命题符号化：PQ。 且命题为真：PQ 1。 二元联结词。,17,例2: “燕子飞回南方，春天来了”。将命题符号化，并求命题的真值。,解: 设P: 燕子飞回南方。Q: 春天来了。 命题符号化：PQ。 且命题的真值：PQ 1. ,例3: “2+2 = 4 当且仅当雪是白的”。将命题符号化，并求命题的真值。,解 设P: 2
8、+2 = 4。Q: 雪是白的。 命题符号化：PQ。 且命题的真值：PQ 1. ,18,复合命题：设 A1,A2,An是命题,用五种逻辑联结词将这n个命题联结起来，得到一个新命题，称为复合命题。,19,练习1. 设命题P，Q的真值为1，命题R，S的真值为0，试确定下面命题的真值： (PQR)(PQ)(RS);,解： (PQR)(PQ)(RS) (110)(11)(00) (10)(10) 00 01 1 ,20,6.3 命题公式的翻译与解释,用大写英文字母代表一个抽象命题, 而不代表一个具体命题, 这个抽象命题称为命题符号. 原子：命题符号称为原子.,定义 合式公式是如下定义的一个符号串 (1)
9、 原子是合式公式； (2) 若G, H是合式公式，则如下符号串(G), (GH), (GH), (GH), (GH), (G H)是合式公式； (3) 所有公式都是有限次使用(1)(2)得到的符号串。,21,命题公式：由命题变项、联结词、括号按一定规则组成的合式公式为命题公式。,例：如下符号串 (P (Q R) (Q (S) R) 就是公式。,五种逻辑联结词的优先级按如下次序递减 , , , , 故上例可写成: P(QR)Q(SR) 对公式中的每个原子赋值后，公式就有一个真值。对原子一组赋值称公式的一个解释。,22,定义 设G是公式，A1, A2, An 是出现在G中的所有原子, 指定 A1,
10、A2,An 一组真值, 则这组真值称为G的一组赋值(解释、指派）, 记作I。,例：G PQR. G的真值记为 TI (G)1.,一般地G是具有n个不同原子的公式, 则G有2n 个不同的赋值。 对一个公式G, 将它在所有赋值下所取的真值列成一个表, 称为G的真值表。,6.4 真值表与等价公式,23,例: 求G P (Q R) 的真值表。,成真赋值,成假赋值,24,有时赋值 0, 0, 0 写成 P, Q, R, 0, 0, 1 写成 P, Q, R, 0, 1, 0 写成 P, Q, R, 1, 1, 1 写成 P, Q, R,25,定义：如果公式G,H在任一组赋值 I 下真值相同，则称公式G,
11、H等值，记作 G H。 “ ”不是联结词，它表示两个公式的关系。,逻辑等价,26,可见在所有赋值 I 下真值相同， PQ PQ . ,例：用真值表证明公式 PQ 和 PQ等值.,证：由真值表：,27,例：证明 P Q (PQ)(PQ)。,证：由真值表,可见在所有赋值 I 下真值相同， P Q (PQ)(PQ)。 ,28,共学了六个联结词：,全功能联结词组：任一命题公式都可用组中的联结词表示，这样的联结词组称全功能联结词组。如,. 由于PQ (PQ)(QP) ,也是全功能联结词组。 由于P Q (PQ)(PQ) ,也是全功能联结词组。 由于PQ PQ ,也是全功能联结词组。,29,并非所有联结词
12、都是必要的，公式中有些联结词可由其它联结词代替。,最小联结词组：任一命题公式可由这些联结词表示，但不能再少一个。 如 ,。 因为 PQ (PQ) 如 ,。 因为 PQ (PQ),30,常用的逻辑等价式, A B (A B) (B A) (等价式) A B A B (蕴含式) A A A， A A A (幂等律) A B B A， A B B A (交换律) A (B C) (A B) C A (B C) (A B) C (结合律) A (A B) A，A (A B) A (吸收律) A (B C) (A B) (A C) A (B C) (A B) (A C) (分配律) A 0 A， A 1
13、 A (同一律) A 0 0， A 1 1 (零律) A A 1， A A 0 (否定律) (A B) A B, (A B) A B (德摩根律),31, A A (双重否定律), A B B A (假言易位) A B A B (等价否定式) (A B)(A B) A (归谬律) A B (A B) (A B) (异或等值式),32,以上公式的证明有两种方法：(1)真值表；(2)利用公式。,例：证明吸收律A (A B) A。 证一：,A (A B) A。,33,证二：A (A B) (A 1) (A B), A (1 B) A 1 A A (A B) A。 ,34,代换规则 在等值式中某命题变
14、项用新的命题公式取代，得到新的等值式。 如由 A A A 可产生 (P Q) (P Q) (P Q) 等等。 等值演算：从某公式A推导出新公式B，且使 A B。 由基本等值式可以产生无数个不同等值式。,35,重言式、永真式：G在所有的赋值下都是真的。 矛盾式、永假式：G在所有的赋值下都是假的。 可满足式：除矛盾式以外的公式。 仅可满足式：除重言式和矛盾式以外的公式。,6.5 重言式与蕴含式,36,例： G P PQ 1, G 是重言式。, K P(PQ) K是可满足式。(仅可满足式), H P PQ 0 H 是矛盾式。,37,重言蕴含式的三种等价定义,定义1：设G,H是两个公式，如果对任意赋值
15、I，都有TI(G) TI(H)，则称G重言蕴含H，记作G H. 定义2：设G,H是两个公式，对任意赋值I，如果G为真，必有H为真，则称G重言蕴含H，记作G H. 定义3：设G,H是两个公式，如果(GH)是恒真公式，则称G重言蕴含H，记作G H.,例1: 证P PG. 证1:,由定义1得证.,证2: 若P 1, 则PG 1G 1由定义2得证.,证3: P(PG) P(PG) PPG 1G 1 由定义3得证.,38,(1) 证明两个公式等值，化简公式； (2) 判别公式的类型； (3) 解决实际问题。,等值式的推演能够解三类问题：,39,例1 证明 (1) (PQ)(PQ) P (2) P(QR)
16、 (PQ)R,证: (1) (PQ)(PQ) P(QQ) P1 P (PQ)(PQ) P (2) P(QR) P(QR) PQR (PQ)R (PQ)R P(QR) (PQ)R ,40,例2 化简 (AB)(BA)C.,解： BA BA AB AB。 (AB) (BA)C (AB) (AB)C 1C (由等价的定义：当P、Q的真值相 同时，PQ的真值为 1 ) C. ,41,例3 判别下列公式的类型: (1) Q(PQ)P).,解：Q(PQ)P) Q(PQ)P) PQ(PQ) 1. 公式Q(PQ)P)为重言式。,42,(2) (PP)(QQ)R).,解：(PP)(QQ)R) 1(0R) 10
17、0. 公式(PP)(QQ)R)为矛盾式。 (3) (PQ)P. 解：(PQ)P (PQ)P P 当P1, 公式 0；当P0, 公式 1。 公式(PQ)P是可满足式。 ,43,对偶式,对偶式:在一个不含联结词和的公式里, 将换成, 换成, 1 换成0, 0换成1, 得一新公式, 称为原公式的对偶式. 将一个等值式的等号两端换成其对偶式, 得到一新等值式, 称为原等值式的对偶式. 对偶性质: 如果一个等值式是成立的, 其对偶等值式也成立.,6.6 范式,44,公式的形式千变万化：G G (G H) G G G 1等等，是否有标准形式？,定义：有限个命题变项或其否定构成的析取式称为简单析取式。有限个
18、命题变项或其否定构成的合取式称为简单合取式。 如：PQ ； ABC.,定义：有限个简单合取式构成的析取式称为析取范式。有限个简单析取式构成的合取式称为合取范式。 如：P(PQ )(PQR )； Q(PQ )(PQR ).,45,析取范式的对偶式称为合取范式；合取范式的对偶式称为析取范式。,如： (PQ )(PQR )； 对偶式为 (PQ )(PQR ).,PQR 既是析取范式，又是合取范式。 PQR 既是析取范式，又是合取范式。 P 既是析取范式，又是合取范式。,46,定理 (范式存在定理)：对于任意公式，都存在等值于它的析取范式和合取范式。,证：对任意公式G，通过如下算法可得出等值于G的范式
19、： (1) 将,化为 , , ； (2) 将 移到原子前； (3) 反复使用分配律,即可得到等值于G的范式。,例1: 将G (P(QR) S 化为析取范式和合取范式. 解：G (P(QR)S (P(QR)S (P(Q R)S P(QR) S (PS )(QR) (PSQ)(PSR) ,析取范式,合取范式,47,例2：将P(QR)化为析取范式和合取范式。,解：P(QR) (合取范式) (PQ) (PR) (析取范式) ,析取范式和合取范式不唯一。 如：P P 1 P(QQ) (PQ)(PQ). P P 0 P(QQ) (PQ)(PQ). (第二式由对偶关系得到),主析取范式和主合取范式唯一。,4
20、8,定义：n个命题变项P1,P2,Pn , 每个变项与它的否定不同时出现，但是两者必须出现一个, 且排列顺序与 P1,P2,Pn的顺序一致, 这样的简单合取式称为关于P1,P2,Pn 的一个极小项或布尔合取。,含n个命题变项的公式G共有2n个极小项，且与公式G的2n个赋值对应。,49,例：公式G中包含P,Q,R三个命题变项：,50,定义：对于含有n个命题变项的命题公式，如果有一个仅由极小项的析取构成的等值式, 则该等值式称为原命题公式的主析取范式。,定理：任何命题公式都存在与之等值的主析取范式，并且是唯一的。,求主析取范式的方法 : 1. 真值表法 在一个命题公式的真值表中，真值为1的赋值所对
21、应的极小项的析取，即为此命题公式的主析取范式。,51,例3 用真值表法求 PQ, PQ, (PQ) 的主析取范式。,解：,PQ (PQ)(PQ)(PQ) m0m1m3 (0, 1, 3) P Q (PQ) m3 (3) (P Q) (PQ)(PQ)(PQ) m0m1m2 (0, 1, 2),52,2. 等值演算法：,(1) 求命题公式的析取范式； (2) “消去”命题公式中所有矛盾式的析取项(如 P P)，合并相同项； (3) 若析取范式的某个合取项缺少命题变项Pj或Pj，则添加(Pj Pj)，再用分配律展开； (4) 将极小项按由小到大的次序排列，用表示之。,53,例：求公式G (RP) (
22、Q (P R) 的主析取范式。,解：G (RP) (Q (P R) (RP) (Q ( P R) (R P) (Q P) (Q R) (R P)(Q Q) (QP)(R R) (Q R)(P P) (RPQ)(RPQ)(QPR) (QPR)(QRP)(QRP) (PQR)(PQR)(PQR) (PQR)(PQR)(PQR),54, (PQR)(PQR)(PQR) (PQR), m3 m1 m7 m6 m1 m3 m6 m7 (1, 3, 6, 7). ,对任意公式G, 存在唯一一个与G等值的主析取范式。 恒假公式的主析取范式用 0 表示。,55,主合取范式,定义：n个命题变项P1,P2,Pn
23、, 每个变项与它的否定不同时出现，但是两者必须出现一个, 且排列顺序与 P1,P2,Pn的顺序一致, 这样的简单析取式称为关于P1,P2,Pn 的一个极大项或布尔析取。 极小项的对偶称为极大项。 含n个原子的公式G共有2n个极大项，且与公式G的2n个赋值对应。,56,例：公式G中包含P,Q,R三个命题变项：,57,定义：对于含有n个命题变项的命题公式，如果有一个仅由极大项的合取构成的等值式, 则该等值式称为原命题公式的主合取范式。,定理：任何命题公式都存在与之等值的主合取范式，并且是唯一的。,58,例5 用真值表法求 (R(PQ)(P(Q R) 的主合取范式。,解：,59, M1M4M6M7
24、(1, 4, 6, 7),(R(PQ)(P(Q R) (PQR)(PQR)(PQR) (PQR),60,等值演算法：,(1) 求命题公式的合取范式； (2) “消去”命题公式中所有永真的合取项(如 P P)，合并相同项； (3) 若合取范式的某个析取项缺少命题变项Pj或Pj，则添加(Pj Pj)，再用分配律展开； (4) 将极大项按由小到大的次序排列，用表示之。,61,主合取范式的求法与主析取范式的求法类似。,例：求公式G (PQ) P 的主合取范式。 解：G (PQ) P (PQ) P (PQ) P (P P) (Q P) P (Q P) P(Q Q) (Q P) (PQ) (P Q) (P
25、 Q) (PQ) (P Q) M0 M1 (0, 1). ,62,主析取范式、主合取范式和真值表之间的关系：,知道三者之一能直接求出另外两个。,63,例: G (RP) (Q (P R), 求G的主析取范式，主合取范式和真值表。,解：前已求出G的主析取范式 G (PQR) (PQR) (PQR)(PQR) m1 m3 m6 m7 (1, 3, 6, 7) (0, 2, 4, 5) M0M2M4M5 (PQR)(PQR) (PQR)(PQR) (主合取范式)(真值表).,64,同一赋值对应的极小项和极大项不相同。如公式G中包含P,Q二个原子。,主析取范式 极小项 成真赋值 主合取范式 极大项 成
26、假赋值,65,主范式的用途：,(1) 判断(证明)两个公式等值； (2) 判断公式的类型：,解题可考虑三种方法：等值公式；主范式；真值表。,(3) 解决实际问题； (4) 求公式的成真赋值和成假赋值。,含2n个极小项(1) 永真式,含0个极小项(0) 永假式,至少含1个极小项 可满足,66,6.7 命题逻辑的推理理论,推理：从给定的前提推出一个结论。也称为 演绎、形式证明、蕴含。 定义：设A1,A2,.,Am,C为命题公式，如果 (A1,A2,.,Am)C 为重言式，则称C为前提A1,A2,.,Am的有效结论，或称由A1,A2,.,Am逻辑地推出C. 记作 A1A2.Am C 上式为重言蕴含式
27、。,67,判断推理的五种方法： 真值表法 等值演算法 主析取范式法 直接证法 间接证法,1. 真值表法 如果A1A2.Am=1, C也为1，则有 A1A2.Am C,68,例1：C是否是前提A1和A2的有效结论。 (1) A1: PQ A2: P C: Q (2) A1: PQ A2: P C: Q (3) A1: PQ A2: Q C: P,解：构造真值表 (1) 当A1和A2都为1时，C为1，PQ , P Q . (2) 当A1和A2都为1时，C有值为0， Q不是PQ和P 的有效结论 . (2) 当A1和A2都为1时，C有值为0， P不是PQ和Q 的有效结论 .,69,2 等值演算法,例2
28、: 证例1中各题,(1) A1: PQ A2: P C: Q,解：(1) (PQ)P)Q (PQ)P)Q (PQ)P)Q (PQ)PQ (PPQ)(QPQ) 11 1 所以 PQ , P Q .,70,(2) (PQ)P)Q,(2) A1: PQ A2: P C: Q, (PQ)P)Q (PQ)P)Q PQ 不是重言式，所以Q 不是 PQ 和 P 的有效结论。,71,3 主析取范式法,例3: 证例1中各题,(1) A1: PQ A2: P C: Q,解：(1) (PQ)P)Q (PQ)P)Q (PQ)P)Q (PQ)PQ (PQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ)(PQ)(P
29、Q) m0m1m2m3 (0, 1, 2, 3) 所以 PQ , P Q .,72,(2) (PQ)P)Q,(2) A1: PQ A2: P C: Q, (PQ)P)Q (PQ)P)Q PQ M0 (0) (1, 2, 3) 不是重言式，所以Q 不是 PQ 和 P 的有效结论。,73,4 直接证法(形式演绎),A1，A2，.，An B (从前提推演出结论) 形式演绎规则: 规则P: 在推导的过程中引入已知前提公式; 规则T: 在演绎过程中可以利用前面演绎出来的中间结果推出新的命题公式。 演绎过程中需要用到等值式和重言蕴含式。,74,重言蕴含式(14个),I1 A B A I2 A B B (化
30、简) I3 A A B I4 B A B (附加) I5 A (A B) I6 B (A B) I7 (A B) A I8 (A B) B I9 A, B A B (合取引入) I10 A, A B B (析取三段论) I11 A, A B B (假言推论) I12 B, A B A (拒取式) I13 A B, B C A C (假言三段论) I14 A B, A C, B C C (构造性二难),I5和I7、I6和I8互为逆否命题。,75,例4: 证明CD, (CD)H, H(AB), (AB)(RS) RS.,证: (1) CD P (2) (CD)H P (3) H T (1)(2)
31、(4) H(AB) P (5) AB T (3)(4) (6) (AB)(RS) P (7) RS T (5)(6) CD, (CD)H, H(AB), (AB)(RS) RS. ,76,例5: 证明AB, AC, DE, DC, E B,证: (1) E P (2) DE P (3) D T (1)(2) (4) DC P (5) C T (3)(4) (6) AC P (7) A T (5)(6) (8) AB P (9) B T (7)(8) AB, AC, DE, DC, E B ,77,例6: 证明 P Q, PR, QS SR.,证: (1) P Q P (2) PQ T (1)
32、(3) QS P (4) PS T (2)(3) (5) SP T (4) (6) PR P (7) SR T (5)(6) (8) SR T (7) P Q, PR, QS SR ,78,例6: 证明 P Q, PR, QS SR.,证二: (1) Q S P (2) S Q T (1) (3) P Q P (4) Q P T (3) (5) S P T (2)(4) (6) P R P (7) S R T (5)(6) (8) SR T (7) P Q, PR, QS SR ,79,5 间接证法,有时要证明的结论以蕴含式的形式出现： A1，A2，.，An B C 由于 A1A2.An (B
33、 C) (A1A2.An B) C 这说明可把B作为附加前提加入到前提中，这种方法称为附加前提证法，简称CP规则。 规则CP: 如果需要演绎出的公式具有B C 的形式,则可以将B 做为附加前提使用, 而力图演绎出C即可。,80,例7: 证明 P (Q S), R P, Q R S.,证: (1) R P (附加) (2) R P P (3) P T (1)(2) (4) P(QS) P (5) QS T (3)(4) (6) Q P (7) S T (5)(6) (8) RS CP (1)(7) P (Q S), R P, Q R S. ,81,例7: 证明 P (Q S), R P, Q R
34、 S.,证二: (1) Q P (2) P(QS) P (3) P Q S T (2) (4) P S T (1)(3) (5) P S T (4) (6) R P P (7) R P T (6) (8) R S T (5)(7) P (Q S), R P, Q R S. ,82,例6: 证明 P Q, PR, QS SR.,证三: 等价于证 P Q, PR, QS SR. (1) S P (附加) (2) Q S P (3) S Q T (2) (4) Q T (1)(3) (5) P Q P (6) P T (4)(5) (7) P R P (8) R T (6)(7) (9) SR CP
35、 (1)(8) P Q, PR, QS SR ,83,反证法(归谬法) 例8: 证明 RQ, RS, SQ, PQ P.,证:反证法 (1) P P (附加) (2) PQ P (3) Q T (1)(2) (4) RQ P (5) R T (3)(4) (6) RS P (7) S T (5)(6) (8) SQ P (9) Q T (7)(8) (3)(9)矛盾 (P Q), Q R, R P. ,84,例9: 证明 (P Q), Q R, R P.,证: 反证法。 (1) P P (附加) (2) (P Q) P (3) P Q T (2) (4) Q T (1)(3) (5) Q R P (6) R T (4)(5) (7) R P (6)与(7)矛盾， (P Q), Q R, R P. ,