第 3 编 数 理 逻 辑第 6 章 命 题 逻 辑16.1 6.1 命题的概念与表示命题的概念与表示命题命题 日常语言不确切，具有二义性需引入目标语言、公式符号目标语言：表达判断的一些语言的汇集判断：肯定、否定的思维形式命题：能表达判断，具有确定真值的陈述句2真值：命题的判断结果称为真值只有“真”和“假”两种，记为“T”和“F”，或“1”和“0”没有判断无所谓是非的句子感叹句、疑问句、祈使句不是命题原子命题：不能分为更简单的陈述句复合命题：由联结词、标点符号和原子命题复合构成的命题用大写字母A,B,.,P,Q,.或Ai,12等表示命题例 P:今天下雨12:今天刮风命题标识符：表示命题的符号3例：语句是否命题真值中国人民是伟大的中国人民是伟大的雪是黑的雪是黑的1+1=10别的星球上有生物别的星球上有生物全体立正！全体立正！明天是否开会？明天是否开会？天气多好啊！天气多好啊！我正在说谎我正在说谎我学英语，或者我学日语我学英语，或者我学日语如果天气好，那么我去散步如果天气好，那么我去散步10?(悖论)?4 命题常量：一个命题标识符表示确定的命题命题变量：一个命题标识符仅表示任意命题的位置标志(无真值)。
原子变元：命题变元表示原子命题56.2 命题联结词命题联结词 复合命题原子命题+联结词1)否定否定定义定义 设P为命题，P的否定是一个新的命题，记为P若P为T，则P为F；若P为F，则P为TPP1001例：P：上海是大城市P：上海不是大城市或上海是不大的城市一元联结词62)合取合取(并且并且)定义定义 两个命题P、Q的合取是一个复合命题，记作PQ当且仅当P、Q同为T时，PQ为T；在其它情况下，PQ的真值为FPQPQ000010100111例:P:今天下雨.Q:明天下雨.PQ:今天下雨且明天下雨今天明天都下雨这两天都下雨二元联结词7 与自然语言不同P：我们去看电影Q：房间里有十张桌子PQ：我们去看电影且房间里有十张桌子仍是新命题可将若干个命题联结一起P：高中毕业Q：上分数线R：被某大学录取PQR：大学生83)析取析取(或者或者)定义定义 两个命题P、Q的析取是一个复合命题，记作PQ当且仅当P、Q同为F时，PQ为F；在其它情况下，PQ的真值为TPQPQ000011101111例:P:今天下雨.Q:今天刮风.PQ:今天下雨或者刮风二元联结词9 日常语言中的“或者”可分“可兼或”与“不可兼或”两种：例例1：今天晚上我在家看电视或去剧院看戏。
不可兼或)例例2：他可能是100米或400米赛跑的冠军可兼或)析取是可兼或例例3：P:他中了大奖Q:他中了小奖PQ:他中了大奖或者中了小奖也可能两奖都中)104)不可兼析取不可兼析取 (排斥析取排斥析取)定义定义 设设P、Q是两个命题，复合命题P Q称为P、Q的不可兼析取P Q的真值为T当且仅当P与Q的真值不相同；否则，P Q的真值为FPQP Q000011101110例:P:他坐船去大连Q:他乘车去大连P Q:他坐船或乘车去大连二元联结词P Q (PQ)(PQ)115)蕴含蕴含(条件条件)定义定义 两个命题P、Q的蕴含是一个复合命题，记作PQ当且仅当P的真值为T，Q的真值为F时，PQ的真值为F；在其它情况下，PQ的真值为TPQPQ001011100111例1:“如果某动物为哺乳动物，则它必胎生”将命题符号化设P:某动物为哺乳动物Q:某动物胎生命题符号化：PQ且命题为真：PQ 1二元联结词12例例2:“如果我得到这本小说，那么我今天就读完它”将命题符号化，并求命题的真值解解 设P:我得到这本小说.Q:我今天就读完它.命题符号化：PQ且命题的真值有以下四种实际情况：(1)我得到这本小说，我今天读完它。
T)(2)我得到这本小说，我今天没有读完F)(3)我没有得到这本小说，我今天读完它T)(4)我没有得到这本小说，我今天没有读完T)13例例3:“如果雪是黑的，那么太阳从西方出”将命题符号化，并求命题的真值解解 设P:雪是黑的Q:太阳从西方出命题符号化：PQ且命题的真值：PQ 1.例例4:“如果雪是黑的，那么太阳从东方出”将命题符号化，并求命题的真值解解 设P:雪是黑的Q:太阳从东方出命题符号化：PQ且命题的真值：PQ 1.14 PQ中P称为前件，Q称为后件自然语言中，若前提为假，无论结论为真或假，往往无法判断PQPQ001011100111 在条件命题中，当前提为假时，结论都为真 称“善意的推定”PQ“如果P那么Q”“只要P则Q”“从P推出Q”“P仅当Q”“只有Q才P”“P蕴含Q”156)等价等价(双条件双条件)定义定义 给定两个命题P和Q，复合命题PQ称为双条件命题当P、Q的真值相同时，PQ的真值为T；在其它情况下，PQ的真值为FPQPQ001010100111例1:“两个三角形全等当且仅当对应边相等”设P:两个三角形全等Q:三角形对应边相等命题符号化：PQ且命题为真：PQ 1二元联结词。
16例例2:“燕子飞回南方，春天来了”将命题符号化，并求命题的真值解解:设P:燕子飞回南方Q:春天来了命题符号化：PQ且命题的真值：PQ 1.例例3:“2+2=4 当且仅当雪是白的”将命题符号化，并求命题的真值解解 设P:2+2=4Q:雪是白的命题符号化：PQ且命题的真值：PQ 1.17 复合命题：设 A1,A2,An是命题,用五种逻辑联结词将这n个命题联结起来，得到一个新命题，称为复合命题18练习练习1.设命题P，Q的真值为1，命题R，S的真值为0，试确定下面命题的真值：(PQR)(PQ)(RS);解：(PQR)(PQ)(RS)(110)(11)(00)(10)(10)00 01 1 196.3 命题公式的翻译与解释命题公式的翻译与解释 用大写英文字母代表一个抽象命题,而不代表一个具体命题,这个抽象命题称为命题符号.原子：命题符号称为原子.定义 合式公式是如下定义的一个符号串(1)原子是合式公式；(2)若G,H是合式公式，则如下符号串(G),(GH),(GH),(GH),(GH),(G H)是合式公式；(3)所有公式都是有限次使用(1)(2)得到的符号串20 命题公式：由命题变项、联结词、括号按一定规则组成的合式公式为命题公式。
例：如下符号串 (P (Q R)(Q (S)R)就是公式五种逻辑联结词的优先级按如下次序递减 ,故上例可写成:P(QR)Q(SR)对公式中的每个原子赋值后，公式就有一个真值对原子一组赋值称公式的一个解释21定义定义 设G是公式，A1,A2,An 是出现在G中的所有原子,指定 A1,A2,.An 一组真值,则这组真值称为G的一组赋值(解释、指派）,记作I例：G PQR.G的真值记为 TI(G)1.一般地G是具有n个不同原子的公式,则G有2n 个不同的赋值对一个公式G,将它在所有赋值下所取的真值列成一个表,称为G的真值表6.4 真值表与等价公式真值表与等价公式22PQR000001010011100101110111例例:求G P (Q R)的真值表PQRRQ RP(Q R)000110001000010110011010100111101000110111111011成真赋值成假赋值PQRRQ R0001100100010110110110011101001101111101PQRR0001001001010110100110101101111023 有时赋值 0,0,0 写成 P,Q,R,0,0,1 写成 P,Q,R,0,1,0 写成 P,Q,R,1,1,1 写成 P,Q,R,24定义定义：如果公式G,H在任一组赋值 I 下真值相同，则称公式G,H等值，记作 G H。
不是联结词，它表示两个公式的关系逻辑等价25P Q1101可见在所有赋值 I 下真值相同，PQ PQ.例例：用真值表证明公式 PQ 和 PQ等值.证：由真值表：PQ00011011P1100PQ110126例例：证明 P Q (PQ)(PQ)P Q P Q P QPQPQ(PQ)(PQ)0 01100000 11010111 00111011 1000000证证：由真值表可见在所有赋值 I 下真值相同，P Q (PQ)(PQ)27 共学了六个联结词：,全功能联结词组：任一命题公式都可用组中的联结词表示，这样的联结词组称全功能联结词组如,.由于PQ (PQ)(QP),也是全功能联结词组由于P Q (PQ)(PQ),也是全功能联结词组由于PQ PQ,也是全功能联结词组28 并非所有联结词都是必要的，公式中有些联结词可由其它联结词代替最小联结词组：任一命题公式可由这些联结词表示，但不能再少一个因为 PQ (PQ)如 ,因为 PQ (PQ)29常用的逻辑等价式 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 A (同一律)A 0 0，A 1 1 (零律)A A 1，A A 0 (否定律)(A B)A B,(A B)A B(德摩根律)30 A A (双重否定律)A B B A (假言易位)A B A B (等价否定式)(A B)(A B)A (归谬律)A B (A B)(A B)(异或等值式)31以上公式的证明有两种方法：(1)真值表；(2)利用公式。
例例：证明吸收律A (A B)A证证一：ABA B A (A B)0000010010011111A (A B)A32证证二：A (A B)(A 1)(A B)A (1 B)A 1 A A (A B)A33代换规则 在等值式中某命题变项用新的命题公式取代，得到新的等值式如由 A A A 可产生 (P Q)(P Q)(P Q)等等等值演算：从某公式A推导出新公式B，且使 A B由基本等值式可以产生无数个不同等值式34 重言式、永真式：G在所有的赋值下都是真的矛盾式、永假式：G在所有的赋值下都是假的可满足式：除矛盾式以外的公式仅可满足式：除重言式和矛盾式以外的公式6.5 重言式与蕴含式重言式与蕴含式35例：G P PQ 1PQ P G0011011110011101 G 是重言式PQ P PQK00110011101000011011 K P(PQ)K是可满足式仅可满足式)H P PQ 0 H 是矛盾式PQ P H001001101000110036重言蕴含式的三种等价定义重言蕴含式的三种等价定义定义定义1：设G,H是两个公式，如果对任意赋值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:PGPG000011101111由定义1得证.证2:若P 1,则PG 1G 1由定义2得证.证3:P(PG)P(PG)PPG 1G 1由定义3得证.37(1)证明两个公式等值，化简公式；(2)判别公式的类型；(3)解决实际问题。
等值式的推演能够解三类问题：38例例1 证明(1)(PQ)(PQ)P (2)P(QR)(PQ)R 证证:(1)(PQ)(PQ)P()P1 P(PQ)(PQ)P(2)P(QR)P(QR)PQR (PQ)R (PQ)R P(QR)(PQ)R 39例例2 化简(AB)(BA)C.解解：BA BA AB ABAB)(BA)C(AB)(AB)C 1C(由等价的。