离散数学命题逻辑.ppt

第一章 命 题 逻 辑,命题与联结词,逻辑,研究人类思维的科学。公元前四世纪亚里斯多德工具论奠定了逻辑学的理论基础。中国最早的一部逻辑专著墨经也创造了一个比较完整的逻辑体系。,形式逻辑,辨证逻辑,数理逻辑,数理逻辑,数理逻辑是一门用数学方法来研究推理规律的科学。 所谓数学方法主要是指引进一套符号体系的方法，所以数理逻辑也称做符号逻辑。,（创始人：十七世纪，德国数学家莱布尼兹）,形式符号体系,由于自然语言存在模棱两可、含糊的特性，所以有必要引入形式化语言。形式化语言在数理逻辑中称为目标语言。 例如：今天晚上八点中央一台播放连续剧或纪录片。 我吃苹果或雪梨。 定义目标语言：具有单一、明确的含义的语言。（基本元素是命题） 定义形式符号体系：由目标语言和一些规定的公式与符号构成的体系,为何学习数理逻辑,程序 = 算法 + 数据结构 算法 = 逻辑 + 控制,数理逻辑的主要内容,数理逻辑内容丰富，但其主要包括“两个演算” 加“四论”，即： 逻辑演算。包括命题演算和谓词演算 证明论。主要研究数学理论系统的相容性（即不矛盾、协调性）的证明。 递归论（能行性理论）。自从电子计算机发明后，迫切需要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论，它为能行可计算的函数找出各种理论上精确化的严密类比物。 模型论。主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系。 公理集合论。主要研究在消除已知集合论悖论的情况下，用公理方法把有关集合的理论充分发展下去。,命题逻辑研究的内容,命题逻辑也称为命题演算 研究以命题为基本单位构成的前提和结论之间的可推导关系. (1) 什么是命题？ (2) 如何表示命题？ (3) 如何由一些前提推导出一些结论?,命题与联结词,命题 联结词,命题的概念,具有判断内容（非真即假）的陈述句称为命题。 能够确定或分辨其真假的陈述句。 命题有一个值，称为真值，真值只有“真”和“假”两种，分别用“T”（或“1”）和“F”（或“0”）表示。 命题中的判断正确，其真值为真，称为真命题，命题中的判断错误，真值为假，称为假命题。,命题示例1,中华人民共和国的首都是北京。 我们在学习离散数学的数理逻辑部分。 所有素数都是奇数。 雪是黑色的。,命题示例2,某些感叹句、祈使句、疑问句等没有真假之分，所以不是命题。 明天开会吗？ 多美妙啊！ 请进来。 全体立正。,判断语句是否为命题要注意的问题：,目前无法确定真值，但从本质而言，真值存在的语句是命题。 例： (1) 别的星球上有生物。 (2) 2046年世界杯在中国举行。 真值因时因地而异的判断性陈述句是命题。 例：(1) 现在是上午。 (2) 今天下雨。 含有未确定内容的代词，不能判断真假的语句不是命题。 例： (1) 1+101=110。 当1和101是二进制数，语句为真，为十进制数，语句为假。 (2) x+y10。 悖论不是命题。 例：我正在说慌。,命题的分类,根据命题的构成形式，可以将命题分为： 定义原子命题：不包含任何联结词的命题。 定义复合命题：由原子命题和联结词组成的命题。连接词一般译为：“或者”、“并且”、“不”、“如果则”、“仅当”、“当且仅当”等。 例如：“明天下雪”、“9是素数”都是原子命题， “2不是素数”是复合命题 “明天下雪或明天下雨”是复合命题。 “中国获得2008奥运的主办权并且加入了WTO”是复合命题。 “如果A和B是对顶角，则角A等于角B”是复合命题。,命题的表示,定义命题标识符：表示命题的符号，通常是大写英文字母。 定义命题符号化：将表示命题的符号放在该命题的前面。 例：P：北京是中国的首都。 Q：北京承办2008年奥运。,命题的表示（续）,定义命题常量：表示确定命题的命题标识符。 定义命题变元：可表示任意一个（原子或复合）命题的命题标识符，就称为命题变元。当命题变元表示原子命题时，该变元称为原子变元。 当命题变元P用一个特定命题去取代时， 才能确定P的真值，这时也称对P进行指派。 例： 若P是命题变元， P：北京是中国的首都。（指派P为命题北京是中国的首都）,命题小结,判断一句话是否是命题的步骤： 1）看它是否是陈述句，如果是疑问句、感叹句和祈使句则不是命题； 2）看它是否是悖论，悖论不是命题，如“我正在说谎”； 3）看它真值是否唯一，如果不唯一，则不是命题。,命题与联结词,命题 联结词,命题联结词,1. 否定： 2. 合取： 3. 析取： 4. 排斥析取： 5. 条件（蕴含）： 6. 双条件：,否定,设P为命题，P的否定也是一个命题，记作 P 当P为T时， P为F 当P为F时， P为T P与P的关系如右表 例：设P：上海是个大城市。 则P：上海不是一个大城市。 或：上海是个不大的城市。,合取,设P、Q是命题，P和Q的合取也是个命题，记作PQ 当且仅当P、Q同时为T时，PQ为T 其他情况下，PQ的真值都是F 读作“P并且（与）Q”,合取示例,(1) P: 我富有。 Q: 我快乐。 PQ：我富有并且快乐。 (2) P: 我们去食堂吃饭。 Q: 教室里有三块黑板。 PQ: 我们去食堂吃饭并且教室里有三块黑板。 注：复合命题中的原子命题之间无需有一般逻辑意义上的关联，如(2)。,析取,设P、Q是命题，则P和Q的析取也是个命题，记作PQ。 当且仅当P、Q同时为F时，PQ为F 其他情况下， PQ的真值都是T 读作“P或Q” （与自然语言中的“或”不完全相同，是兼并或）,析取例子,例：(1) P：猴子吃香蕉。 Q：猴子吃橘子。 猴子吃香蕉或者吃橘子 ？ PQ (2) P：他明天早上吃蛋糕。 Q：他明天早上喝牛奶。 PQ？ 他明天早上吃蛋糕或者喝牛奶 。 (3) P: 我明天早上9点在家看书。 Q: 我明天早上9点出去打球。 我明天早上9点在家看书或出去打球 PQ？,排斥析取,设P、Q是命题，P和Q的排斥析取也是个命题，记作 PQ 当且仅当P和Q的真值不相同时， PQ为T， 其他情况下,PQ的真值都是F 读作“P或Q” （排斥或）,排斥析取示例,指出下列命题中的“或”是析取还是排斥析取 今晚我去看演出或在家里看电视现场转播。 他是一百米冠军或跳高冠军。 派小王或小赵出差去上海。 派小王或小赵中的一个出差去上海。 2、3为析取，1、 4为排斥析取,条件/蕴含,设P、Q是命题，P对于Q的条件命题记为PQ，或称为P蕴含Q 。 当且仅当P的真值为T，Q的真值为F时，PQ的真值为F， 其他情况， PQ的真值为T。 读作“如果（若）P，则Q”、“Q是P的必要条件” 、“仅当Q为真时，P为真” 称P为前件，Q为后件。,条件示例,P：天不下雨 Q：我去看电影 如果天不下雨，那么我去看电影： PQ 。 P：我不到学校去。 Q：我生病。 PQ：如果我不到学校去，那么我生病。 P：我去踢足球。 Q：我有时间。 仅当我有时间，我去踢足球。,PQ,双条件,P、Q是命题，P和Q的双条件命题记作：P Q 当P和Q的真值相同时，P Q的真值为T， 否则PQ的真值为F 翻译为：“P当且仅当Q” 或者“若P则Q，否则，则Q”,双条件示例,P：整数a能被2整除 Q：a是偶数。 当且仅当整数a能被2整除，a才是偶数：P Q 。 P：天不下雨 Q：我去看足球 P Q：如果天不下雨，我就去看足球，否则，我就不去看足球。 P：224 Q：雪是白的 224当且仅当雪是白的： P Q 注：复合命题中的原子命题之间无需有一般逻辑意义上的关联。如此例中P和Q并无因果关系，P Q仍是命题，其真值根据联结词定义以及P和Q的真值来确定。,综合示例,设P表示命题“天下雪”。 Q表示命题“我去看电影”。 R表示命题“我有时间”。 试以符号形式表示下列命题：,P PQ Q R (QR) P,天不下雪。 如果天不下雪，那么我去看电影。 我去看电影，仅当我有时间。 如果我去看电影且我有时间，那么天不下雪。,联结词小结,1. 复合命题的真值只取决于构成它们的原子命题的真值和命题联结符的定义，而与它们的内容、含义无关，与联结词所连接的两个原子命题之间是否有关系无关。 2. ，和具有可交换性，而，没有。,联结词小结,1.“只要(若、当)A成立，则B成立” ：AB 2.“仅当A成立时,B成立”和“只有A成立时，B成立”： BA 3. “A成立,否则B成立”：AB。 4. 遇到“或”，就需要考察两件事情可否同时发生，若不能同时，则是，否则用“”。,联结词运算顺序,优先级从高到底排列： 、/、 、 ,命题（合式）公式,定义命题合式公式： (1) 单个命题变元本身是一个命题合式公式。 (2) 如果A是合式公式，则A是命题合式公式。 (3) 如果 A和B是合式公式，则AB,AB、AB、AB、AB都是命题合式公式。 (4) 当且仅当能够有限次应用(1)、(2)、(3)所得到的包含命题变元，联结词和括号的符号串是命题合式公式。,命题（合式）公式举例,设P、Q、R、S、T都是命题变元，判断下列字符串哪些是合式公式： (1) (P Q) (2)(PQ) (Q R ) (S T) (3) (PQ) (Q) (4) (PQ)，