《离散数学》命题逻辑

《《离散数学》命题逻辑》由会员分享，可在线阅读，更多相关《《离散数学》命题逻辑（121页珍藏版）》请在金锄头文库上搜索。

1、第1章 命题逻辑命题逻辑逻辑是研究推理的科学。数理逻辑是用数学方法研究推理的形式结构和推 理规律的数学学科。由于它使用一套符号来表达各种 推理的逻辑关系，因此数理逻辑又称为符号逻辑。从广义上讲，数理逻辑包括集合论、模型论、递 归论、证明论和命题演算、谓词演算，但本书只研究 两个演算：命题演算和谓词演算两个演算。数理逻辑研究的中心问题是推理，而推理的前提 与结论都是表达判断的陈述句，因而表达判断的陈述 句构成了推理的基本单位。数理逻辑称之为命题。第第1 1章章命命 题题 逻逻 辑辑一、命题定义1.1 能判断真假的陈述句叫做命题。 该定义有两层含义：(1)命题是陈述句。其他的语句，如疑问句 、祈使

2、句、感叹句均不是命题；(2)这个陈述句对事物的判断是否符合客观 事实是可以给出结论的：不是真（符合客观事 实）就是假（不符合客观事实），不能不真也 不假，也不能既真又假，所以又称二值逻辑。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词二、命题的真值命题所表示的判断结果称为命题的真值 。 真值只取两个值：真（判断与事实相 符）或假（判断与事实不符）。通常用1（或字 母T）表示真，用0（或字母F）表示假。 真命题：真值为真的命题。 假命题：真值为假的命题。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词例6.1.1 判断下列语句是否为命题，并指出其真 值。 （1）

3、北京是中国的首都。 （2）5可以被2整除。 （3）2+2=5。 （4）请勿吸烟。 祈使句 （5）乌鸦是黑色的吗？ 疑问句 （6）这个小男孩多勇敢啊！ 感叹句 （7）地球外的星球上存在生物。 （8）我正在说谎。 悖论注意：注意：一个语句本身是否能分辨真假与我们是否知道 它的真假是两回事。也就是说，对于一个句子，有时我 们可能无法判定它的真假，但它本身却是有真假的，那 么这个语句是命题，否则就不是命题。悖论不是命题。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词判断一个句子是否为命题1、是否为陈述句 2、真值是否唯一-X+y5-1+101=110-真值是否唯一与我们是否知道它的真

4、 值是两回事三、命题的分类原子命题（Automic Proposition）：不能 再分解为更简单的陈述句的命题；也称简单命 题。 复合命题（Compound Proposition）：由 若干简单命题用联结词联结成的命题。例如：“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明 天天晴我就去打球或者游泳”都是复合命题。 1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词四、命题的表示引进数学符号来表示命题。常用大写英文字母A,B,P,Q或带下标的 字母P1,P2,P3 , ,或数字(1),2, ,等表示命题， 称之为命题标识符。例如：P：罗纳尔多是球星。Q：5是负数。P3

5、：明天天气晴。(2)：太阳从西方升起。皆为符号化的命题，其真值依次为1、0、1 或0、0。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词v 命题标识符有命题常量、命题变元和原子变 元之分。命题常元：真值确定的命题标识符。命题变元：真值不确定，仅表示任意命题 的位置标志。原子变元：当命题变元表示原子 命题时，该变元称为原子变元v 如果命题符号P代表命题常元则意味它是某 个具体命题的符号化，如果P代表命题变元则意 味着它可指代任何具体命题。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词一、否定联结词“”（或“”）否定联结词是一元联结词。相当于日常 用语中的“非”

6、，“不”，“无”，“没有”等。设P为一命题， P的否定是一个新的复合 命题, 称为P的否定式，记作 “P”，读作“非P”。P为真当且仅当P为假。P P0 11 01.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词例6.1.2. P: 天津是一个城市.Q: 3是偶数. 于是: P: 天津不是一个城市.Q: 3不是偶数. 例6.1.3. P:苏州处处清洁.Q:这些都是男同学.P:苏州不处处清洁 (注意,不是处处不 清洁).Q:这些不都是男同学.1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词二、合取联结词“”合取词是二元联结词。相当于自然语言中 的“与” 、“并且”

7、、“而且” 、“也”等。设P,Q为二命题，复合命题“P与Q”记作 PQ。 PQ为真当且仅当P和Q同时为真。P Q P Q0 0 00 1 01 0 01 1 11.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词例6.1.4. 将下列命题符号化.(1) 李平既聪明又用功.(2) 李平虽然聪明, 但不用功.(3) 李平不但聪明,而且用功.(4) 李平不是不聪明,而是不用功. 解: 设 P:李平聪明. Q:李平用功. 则 (1) PQ (2) PQ (3) PQ (4) (P)Q 注意：不要见到“与”或“和”就使用联结词 ！例如: (1)李敏和李华是姐妹。(2)李敏和张华是朋友。1.1

8、1.1命命 题题 符符 号号 化化 及及 联联 结结 词词1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词例6.1.5. 试生成下列命题的合取.(1) P: 我们在6-503. Q: 今天是星期二.(2) S：李平在吃饭. R：张明在吃饭. 解: (1) PQ :我们在6-503且今天是星期二.(2) SR:李平与张明在吃饭. 三、析取联结词“”析取词是二元联结词。相当 于自然语言中的“或”、“要么要么 ”等。设P,Q为二命题，复合命题 “P或Q”，记作PQ 。 PQ为真当 且仅当 P与Q中至少有一个为真。P Q PQ0 0 00 1 11 0 11 1 1在现代汉语中， “或

9、”有“可兼或可兼或”和“排斥或排斥或 ”之分。这里只是“可兼或可兼或”。 例6.1.6 （1）小王爱打球或爱跑步。（可兼或）可兼或）设P：小王爱打球。 Q：小王爱跑步。则上述命题可符号化为：P Q1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词（2）林芳学过英语或法语。（可兼或）可兼或） 设P：林芳学过英语。 Q：林芳学过法语。则上述命题可符号化为： P Q （3）派小王或小李中的一人去开会。（排斥排斥 或或） 设P：派小王去开会。Q：派小李去开会。则上述命题可符号化为：(PQ) (PQ)四、蕴含联结词“”蕴含词是

10、二元联结词。相当于自然语言 中的“若则”、“如果就”、“只有才” 。设P,Q为二命题,复合命题“若P则Q” 记作 PQ。并称P为前件，Q为后件。PQ为假当且仅当P为真且Q为假。P QP Q0 0 10 1 11 0 01 1 11.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词例6.1.7 将下列命题符号化。 1）天不下雨，则草木枯黄。P：天下雨。 Q：草木枯黄。 则原命题可表示为： PQ。 2）如果小明学日语，小华学英语，则小芳 学德语。P：小明学日语. Q：小华学英语. R：小芳 学德语. 则原命题可表示为：(PQ)R 3）只要不下雨，我就骑自行车上班。P：天下雨。Q：我骑自

11、行车上班。则原命题可表示为： PQ。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词4）只有不下雨，我才骑自行车上班。P：天下雨。Q：我骑自行车上班。则原命题可表示为： Q P 。注意: (1)与自然语言的不同：前件与后件可以没有任何内在联系！(2) 在数学中，“若P则Q”往往表示前件P为真，则后件Q为真的推理关系. 但数理逻辑中，当前件P为假时， PQ的真值为真。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词“如果 p，则 q ” 的不同表述法很多：若 p，就 q只要 p，就 qp 仅当 q只有 q 才 p除非 q, 才 p 除非 q, 否则非 p，1.11

12、.1命命 题题 符符 号号 化化 及及 联联 结结 词词例：设 p:天冷，q:小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服.(2) 因为天冷，所以小王穿羽绒服.(3) 若小王不穿羽绒服，则天不冷.(4) 只有天冷，小王才穿羽绒服.(5) 除非天冷，小王才穿羽绒服.(6) 除非小王穿羽绒服，否则天不冷.(7) 如果天不冷，则小王不穿羽绒服.(8) 小王穿羽绒服仅当天冷的时候.注意： pq 与 pq 等值（真值相同） pq pq pqpqqp qpqp qp1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词五、等价联结词“ ” 等价联结词是二元联结 词。相当于自然

13、语言中的“等价” 、“当且仅当”、“充要条件”等， 真值表如右图。设P,Q为二命题，复合命 题“P当且仅 当Q” 记作PQ。PQ为真当且仅当P，Q 真值相同。P Q PQ0 0 10 1 01 0 01 1 11.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词注：（1）P仅当Q 可译为PQP当Q 可译为QPP当且仅当Q 译为PQ（2）命题PQ所表达的逻辑关系是, P与Q互 为充分必要条件,相当于(PQ)(QP). 双条件联结词连接的两个命题之间可以没有 因果关系。例6.1.8 分析下列命题的真值.(1) 2+2=4 当且仅当3是奇数 . (PQ)P： 2+2=4. Q：3是奇数

14、. (2) 2+2=4 当且仅当3不是奇数 . (PQ)(3) 2+24 当且仅当3是奇数 . (PQ)(4) 2+24 当且仅当3不是奇数 . (PQ)1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词5种联结词类似5种运算符，称之为逻辑运 算符，有运算的优先级顺序：-联结词的优先顺序为：, , , , ;- 如果出现的联结词同级，又无括号时， 则按从左到右的顺序运算; -若遇有括号时，应该先进行括号中的运 算。1.11.1命命 题题 符符 号号 化化 及及 联联 结结 词词一、概念 定义1.3 命题公式按下列规则生成：（1）单个命题常项或变项p,q,r,.,0,1是命题 的公

15、式；（2）如果是命题公式，则也是命题公式；（3）如果和是命题公式，则， ，均是命题公式；（4）只有有限次地利用（1）（3）形成的符号 串才是命题公式。 例如：(PQ)，P(PQ)等都是命题公式，而CPQ， RP等不是命题公式。1.21.2命命 题题 公公 式式 及及 分分 类类注: (1)命题公式也称为合式公式，由命题常项、命题变 项、联结词和括弧组成。(2)如果把公式中的命题变元代以原子命题或复合命 题，则该公式便是一个复合命题。因此，对复合命题的 研究可化为对命题公式的研究。命题公式一般不是命题,仅当公式中的命题变元用 确定的命题代入时，才得到一个命题。其真值依赖于代 换变元的那些命题的真值。日常生活中的推理问题是用自然语言描述的，因 此要进行推理演算必须先把自然语言符号化（或形式化 ）成逻辑语言，即命题公式。然后再根据逻辑演算规律 进行推理演算。1.21.2命命 题题 公公 式式 及及 分分 类类二、命题符号化 (1) 分析出各简单