离散数学命题逻辑

1、 命题与联结词离散数学逻辑逻辑 研究人类思维的科学。公元前四世纪亚里斯多德工具论奠定了逻辑学的理论基础。中国最早的一部逻辑专著墨经也创造了一个比较完整的逻辑体系。离散数学数理逻辑数理逻辑是一门用数学方法来研究推理规律数理逻辑是一门用数学方法来研究推理规律的科学。的科学。所谓数学方法主要是指引进一套符号体系的所谓数学方法主要是指引进一套符号体系的方法，所以数理逻辑也称做符号逻辑。方法，所以数理逻辑也称做符号逻辑。（创始人：十七世纪，德国数学家莱布尼兹）离散数学形式符号体系形式符号体系 由于自然语言存在模棱两可、含糊的特性，所以有必要引入由于自然语言存在模棱两可、含糊的特性，所以有必要引入形式化语

2、言。形式化语言在数理逻辑中称为目标语言。形式化语言。形式化语言在数理逻辑中称为目标语言。 例如：今天晚上八点中央一台播放连续剧或纪录片。例如：今天晚上八点中央一台播放连续剧或纪录片。 我吃苹果或雪梨。我吃苹果或雪梨。 定义定义目标语言：具有单一、明确的含义的语言。（基本元素目标语言：具有单一、明确的含义的语言。（基本元素是命题）是命题） 定义定义形式符号体系：由目标语言和一些规定的公式与符号构形式符号体系：由目标语言和一些规定的公式与符号构成的体系成的体系离散数学为何学习数理逻辑为何学习数理逻辑 程序程序 = 算法算法 + 数据结构数据结构 算法算法 = 逻辑逻辑 + 控制控制 离散数学数理逻

3、辑的主要内容数理逻辑的主要内容 数理逻辑内容丰富，但其主要包括数理逻辑内容丰富，但其主要包括“两个演算两个演算” 加加“四论四论”，即：，即： 逻辑演算。包括命题演算和谓词演算逻辑演算。包括命题演算和谓词演算 证明论。主要研究数学理论系统的相容性（即不矛盾、证明论。主要研究数学理论系统的相容性（即不矛盾、协调性）的证明。协调性）的证明。 递归论（能行性理论）。自从电子计算机发明后，迫切递归论（能行性理论）。自从电子计算机发明后，迫切需要在理论上弄清计算机能计算哪些函数。递归论研究需要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论，它为能行可计算的函数找出各种理能行可计算的理论，它

4、为能行可计算的函数找出各种理论上精确化的严密类比物。论上精确化的严密类比物。 模型论。主要是对各种数学理论系统建立模型，并研究模型论。主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系。各模型之间的关系以及模型与系统之间的关系。 公理集合论。主要研究在消除已知集合论悖论的情况下，公理集合论。主要研究在消除已知集合论悖论的情况下，用公理方法把有关集合的理论充分发展下去。用公理方法把有关集合的理论充分发展下去。现代数理逻辑离散数学命题逻辑研究的内容命题逻辑研究的内容 命题逻辑也称为命题演算命题逻辑也称为命题演算 研究以命题为基本单位构成的前提和结论之间的可推导关系研究

5、以命题为基本单位构成的前提和结论之间的可推导关系. (1) 什么是命题？什么是命题？ (2) 如何表示命题？如何表示命题？ (3) 如何由一些前提推导出一些结论如何由一些前提推导出一些结论?离散数学命题与联结词命题与联结词 命题命题 联结词联结词离散数学命题的概念命题的概念具有判断内容（非真即假）的陈述句称为命题。具有判断内容（非真即假）的陈述句称为命题。 能够确定或分辨其真假的陈述句。能够确定或分辨其真假的陈述句。命题有一个值，称为真值，真值只有命题有一个值，称为真值，真值只有“真真”和和“假假”两种，分别用两种，分别用“T”（或（或“1”）和）和“F”（或（或“0”）表）表示。示。命题中的

6、判断正确，其真值为真，称为真命题，命命题中的判断正确，其真值为真，称为真命题，命题中的判断错误，真值为假，称为假命题。题中的判断错误，真值为假，称为假命题。离散数学命题示例命题示例1 中华人民共和国的首都是北京。中华人民共和国的首都是北京。 我们在学习我们在学习离散数学离散数学的数理逻辑部分。的数理逻辑部分。 所有素数都是奇数。所有素数都是奇数。 雪是黑色的。雪是黑色的。离散数学命题示例命题示例2 某些感叹句、祈使句、疑问句等没有真假之分，所以不是某些感叹句、祈使句、疑问句等没有真假之分，所以不是命题。命题。 明天开会吗？明天开会吗？ 多美妙啊！多美妙啊！ 请进来。请进来。 全体立正。全体立正

7、。离散数学判断语句是否为命题要注意的问题：判断语句是否为命题要注意的问题： 目前无法确定真值，但从本质而言，真值存在的语句是命题。目前无法确定真值，但从本质而言，真值存在的语句是命题。例：例： (1) 别的星球上有生物。别的星球上有生物。 (2) 2046年世界杯在中国举行。年世界杯在中国举行。 真值因时因地而异的判断性陈述句是命题。真值因时因地而异的判断性陈述句是命题。例：例：(1) 现在是上午。现在是上午。 (2) 今天下雨。今天下雨。 含有未确定内容的代词，不能判断真假的语句不是命题。含有未确定内容的代词，不能判断真假的语句不是命题。例：例： (1) 1+101=110。当当1和和101

8、是二进制数，语句为真，为十进制数，语句为假。是二进制数，语句为真，为十进制数，语句为假。 (2) x+y10。 悖论不是命题。悖论不是命题。 例：我正在说慌。例：我正在说慌。离散数学 命题的分类命题的分类根据命题的构成形式，可以将命题分为：根据命题的构成形式，可以将命题分为：定义定义原子命题原子命题：不包含任何联结词的：不包含任何联结词的命题命题。定义定义复合命题：复合命题：由由原子命题原子命题和联结词组成的命题和联结词组成的命题。连接词一。连接词一般译为：般译为：“或者或者”、“并且并且”、“不不”、“如果如果则则”、“仅仅当当”、“当且仅当当且仅当”等。等。 例如：例如：“明天下雪明天下雪

9、”、“9是素数是素数”都是原子命题，都是原子命题， “2不是素数不是素数”是复合命题是复合命题 “明天下雪或明天下雨明天下雪或明天下雨”是复合命题。是复合命题。 “中国获得中国获得2008奥运的主办权并且加入了奥运的主办权并且加入了WTO”是复合命题。是复合命题。 “如果如果A和和B是对顶角，则角是对顶角，则角A等于角等于角B”是复合命题。是复合命题。离散数学 命题的表示命题的表示 定义定义命题标识符：表示命题的符号，通常是大写英文字母。命题标识符：表示命题的符号，通常是大写英文字母。 定义定义命题符号化：将表示命题的符号放在该命题的前面。命题符号化：将表示命题的符号放在该命题的前面。 例：例

10、：P P：北京是中国的首都。北京是中国的首都。 Q Q：北京承办：北京承办20082008年奥运。年奥运。 离散数学命题的表示（续）命题的表示（续） 定义定义 命题常量：表示命题常量：表示确定命题确定命题的命题标识符。的命题标识符。 定义定义 命题变元：可表示任意一个（原子或复合）命题的命题变元：可表示任意一个（原子或复合）命题的命命题标识符题标识符，就称为命题变元。当，就称为命题变元。当命题变元命题变元表示表示原子命题原子命题时，时，该变元称为原子变元。该变元称为原子变元。 当命题变元当命题变元P P用一个特定命题去取代时，用一个特定命题去取代时， 才能确定才能确定P P的真值，的真值，这时

11、也称对这时也称对P P进行指派。进行指派。 例：例： 若若P P是是命题变元，命题变元， P P：北京是中国的首都。（指派北京是中国的首都。（指派P P为命题北京是中国的为命题北京是中国的首都）首都）离散数学命题命题小结小结 判断一句话是否是命题的步骤：判断一句话是否是命题的步骤： 1 1）看它是否是）看它是否是陈述句陈述句，如果是疑问句、感叹句和祈使句则不，如果是疑问句、感叹句和祈使句则不是是命题命题； 2 2）看它是否是）看它是否是悖论悖论，悖论不是命题，如，悖论不是命题，如“我正在说谎我正在说谎”； 3 3）看它真值是否唯一，如果不唯一，则不是）看它真值是否唯一，如果不唯一，则不是命题命

12、题。离散数学命题与联结词命题与联结词 命题命题 联结词联结词离散数学命题联结词命题联结词1. 否定：否定： 2. 合取：合取： 3. 析取：析取： 4. 排斥析取：排斥析取： 5. 条件（蕴含）：条件（蕴含）： 6. 双条件：双条件：离散数学否定否定 设设P为命题，为命题，P的否定也是一个命题，记作的否定也是一个命题，记作 P 当当P为为T时，时， P为为F 当当P为为F时，时， P为为T P与与P的关系如右表的关系如右表 例：设例：设P：上海是个大城市。：上海是个大城市。 则则P：上海不是一个大城市。：上海不是一个大城市。 或：上海是个不大的城市。或：上海是个不大的城市。PPFTTF离散数学

13、合取合取 设设P、Q是命题，是命题，P和和Q的合取也是个命题，记作的合取也是个命题，记作PQ 当且仅当当且仅当P、Q同时为同时为T时，时，PQ为为T 其他情况下，其他情况下，PQ的真值都是的真值都是F 读作读作“P并且（与）并且（与）Q”PQPQFFFFTFTFFTTT离散数学合取示例合取示例(1) P: 我富有。我富有。 Q: 我快乐。我快乐。 PQ：我富有并且快乐。：我富有并且快乐。(2) P: 我们去食堂吃饭。我们去食堂吃饭。 Q: 教室里有三块黑板。教室里有三块黑板。 PQ: 我们去食堂吃饭并且教室里有三块黑板。我们去食堂吃饭并且教室里有三块黑板。 注：复合命题中的原子命题之间无需有一

14、般逻辑意义上的关注：复合命题中的原子命题之间无需有一般逻辑意义上的关联，如联，如(2)。离散数学 析取析取 设设P、Q是命题，则是命题，则P和和Q的析取也是个命题，记作的析取也是个命题，记作PQ。 当且仅当当且仅当P、Q同时为同时为F时，时，PQ为为F 其他情况下，其他情况下， PQ的真值都是的真值都是T 读作读作“P或或Q” （与自然语言中的（与自然语言中的“或或”不完全相同，是不完全相同，是兼并或）兼并或） PQPQFFFFTTTFTTTT离散数学析取例子析取例子 例：例：(1) P：猴子吃香蕉。：猴子吃香蕉。 Q：猴子吃橘子。：猴子吃橘子。 猴子吃香蕉或者吃橘子猴子吃香蕉或者吃橘子 ？

15、PQ (2) P：他明天早上吃蛋糕。：他明天早上吃蛋糕。 Q：他明天早上喝牛奶。：他明天早上喝牛奶。 PQ？ 他明天早上吃蛋糕或者喝牛奶他明天早上吃蛋糕或者喝牛奶 。 (3) P: 我明天早上我明天早上9点在家看书。点在家看书。 Q: 我明天早上我明天早上9点出去打球。点出去打球。 我明天早上我明天早上9点在家看书或出去打球点在家看书或出去打球 PQ？ 离散数学 排斥析取排斥析取 设设P、Q是命题，是命题，P和和Q的排斥析取也是个命题，记作的排斥析取也是个命题，记作 PQ 当且仅当当且仅当P和和Q的真值不相同时，的真值不相同时， PQ为为T， 其他情况下其他情况下,PQ的真值都是的真值都是F

16、读作读作“P或或Q” （排斥或）（排斥或）PQPQFFFFTTTFTTTFPQPQFFFFTTTFTTTT离散数学排斥析取示例排斥析取示例 指出下列命题中的指出下列命题中的“或或”是析取还是排斥析取是析取还是排斥析取今晚我去看演出或在家里看电视现场转播。今晚我去看演出或在家里看电视现场转播。他是一百米冠军或跳高冠军。他是一百米冠军或跳高冠军。派小王或小赵出差去上海。派小王或小赵出差去上海。派小王或小赵中的一个出差去上海。派小王或小赵中的一个出差去上海。1. 2、3为析取，为析取，1、 4为排斥析取为排斥析取PQPQFFFFTTTFTTTFPQPQFFFFTTTFTTTT离散数学条件条件/蕴含蕴

17、含 设设P、Q是命题，是命题，P对于对于Q的条件命题记为的条件命题记为PQ，或称为，或称为P蕴含蕴含Q 。 当且仅当当且仅当P的真值为的真值为T，Q的真值为的真值为F时，时，PQ的真值为的真值为F， 其他情况，其他情况， PQ的真值为的真值为T。 读作读作“如果（若）如果（若）P，则，则Q”、“Q是是P的必要条件的必要条件” 、“仅当仅当Q为真时，为真时，P为真为真” 称称P为前件，为前件，Q为后件。为后件。PQPQFFTFTTTFFTTT离散数学条件示例条件示例 P：天不下雨：天不下雨 Q：我去看电影：我去看电影 如果天不下雨，那么我去看电影：如果天不下雨，那么我去看电影： PQ 。 P：我

18、不到学校去。：我不到学校去。 Q：我生病。：我生病。 PQ：如果我不到学校去，那么我生病。：如果我不到学校去，那么我生病。 P：我去踢足球。：我去踢足球。 Q：我有时间。：我有时间。 仅当我有时间，我去踢足球。仅当我有时间，我去踢足球。PQ?FFTFTTTFFTTT离散数学双条件双条件 P、Q是命题，是命题，P和和Q的双条件命题记作：的双条件命题记作：P Q 当当P和和Q的真值相同时，的真值相同时，P Q的真值为的真值为T， 否则否则PQ的真值为的真值为F 翻译为：翻译为：“P当且仅当当且仅当Q” 或者或者“若若P则则Q，否则，则，否则，则 Q”PQP QFFTFTFTFFTTT离散数学双条件

19、示例双条件示例 P：整数：整数a能被能被2整除整除 Q：a是偶数。是偶数。 当且仅当整数当且仅当整数a能被能被2整除，整除，a才是偶数：才是偶数：P Q 。 P：天不下雨：天不下雨 Q：我去看足球：我去看足球 P Q：如果天不下雨，我就去看足球，否则，我就不去看足球。：如果天不下雨，我就去看足球，否则，我就不去看足球。 P：224 Q：雪是白的：雪是白的 224当且仅当雪是白的：当且仅当雪是白的： P Q 注：复合命题中的原子命题之间无需有一般逻辑意义上的关联。如此例中注：复合命题中的原子命题之间无需有一般逻辑意义上的关联。如此例中P和和Q并无并无因果关系，因果关系，P Q仍是命题，其真值根据

20、联结词定义以及仍是命题，其真值根据联结词定义以及P和和Q的真值来确定。的真值来确定。离散数学综合示例综合示例设设P表示命题表示命题“天下雪天下雪”。Q表示命题表示命题“我去看电影我去看电影”。R表示命题表示命题“我有时间我有时间”。试以符号形式表示下列命题：试以符号形式表示下列命题：PPQQ R(QR) P天不下雪。天不下雪。如果天不下雪，那么我去看电如果天不下雪，那么我去看电影。影。我去看电影，仅当我有时间。我去看电影，仅当我有时间。如果我去看电影且我有时间，如果我去看电影且我有时间，那么天不下雪。那么天不下雪。离散数学联结词联结词小结小结 1. 1. 复合命题复合命题的真值只取决于构成它们

21、的的真值只取决于构成它们的原子命题原子命题的真值和命的真值和命题联结符的定义，而与它们的内容、含义无关，与联结词所题联结符的定义，而与它们的内容、含义无关，与联结词所连接的两个连接的两个原子命题原子命题之间是否有关系无关。之间是否有关系无关。 2. 2. ， 和和具有可交换性，而具有可交换性，而 ，没有。没有。离散数学联结词联结词小结小结 1.“1.“只要只要( (若、当若、当)A)A成立，则成立，则B B成立成立” ：A AB B 2.“2.“仅当仅当A A成立时成立时,B,B成立成立”和和“只有只有A A成立时，成立时，B B成立成立”： B BA A 3. 3. “A A成立成立, ,否则否则B B成立成立”：