数理逻辑1.1 (2)

1、离散数学,李秀春,特点,离散数学研究的对象一般为有限或可数个元素是以研究离散量的结构和相互间的关系为主要目标的抽象、定义多、定理多、数学符号多是计算机专业的基础核心课程与数据结构，操作系统，编译系统，算法分析，逻辑设计，系统结构及机器证明等课程紧密联系,主要内容,数理逻辑、集合、二元关系、函数、代数、图论第5章、第7章不讲带*不讲共56课时,第一章数理逻辑2014.2,逻辑学的组成,辩证逻辑是以辩证法认识论的世界观为基础的逻辑学。形式逻辑是对思维的形式结构和规律进行研究。思维的形式结构包括了概念、判断、推理之间的结构和联系。,数理逻辑是用数学方法研究形式逻辑的一门科学，它是在传统逻辑（自然语言

2、）的基础上从17世纪70年代开始发展起来的，它采用数学符号化的方法，也称为现代逻辑或符号逻辑。数理逻辑着重于研究从前提到结论的推理过程是否正确，而不是前提或结论本身是否正确。从广义上讲，数理逻辑包括公理集合论、模型论、递归论、证明论和逻辑演算。但现在提到数理逻辑，一般只指逻辑演算（命题逻辑和谓词逻辑）。,数理逻辑,1.1命题,主要内容命题及其符号化常用联结词及其符号化命题变元与命题公式,1.1.1命题及其符号化,概念命题：能够判断真假（具有真假意义的）的陈述句。命题的真值：命题的判断结果。真值只取两个值：真、假。真命题：真值为真的命题。假命题：真值为假的命题。判断命题的两个步骤1、是否为陈述句

3、；2、是否有确定的、唯一的真值。,说明,句子可以分为疑问句、祈使句、感叹句与陈述句等，其中只有陈述句能分辨真假，其他类型的句子无所谓真假。陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。断言是一陈述句。,例1下述都是命题:(a)今天下雪;(b)3+3=6;(c)2是偶数而3是奇数;(d)陈涉起义那天,杭州下雨;(e)较大的偶数都可表为两个质数之和。以上命题,(a)的真值取决于今天的天气,(b)和(c)是真,(d)已无法查明它的真值,但它是或真或假的,将它归属于命题。(e)目前尚未确定其真假,但它是有真值的,应归属于命题。,例2下述都不是命题:(a)x+y4。(c

4、)真好啊!(b)x=3。(d)你去哪里?(a)和(b)是断言,但不是命题,因为它的真值取决于x和y的值。(c)和(d)都不是断言,所以不是命题。,命题的分类原子命题：由不能再分解为更简单的陈述句的陈述句构成。复合命题：由简单命题通过联结词联结而成的陈述句。命题及其真值的抽象化命题和本原命题常用大写字母P,Q,R表示，用“1”、“0”分别表示命题真值的真、假。如用P表示“4是质数”,则记为P:4是质数。,1.1.2逻辑联结词及其符号化,在代数式x+3中,x,3叫运算对象,+叫运算符,x+3表示运算结果。在命题演算中,也用同样术语。联结词就是命题演算中的运算符,叫逻辑运算符或叫逻辑联结词。常用的有

5、以下5个。,1.否定词,设P表示命题,那么“P不真”是另一命题,表示为P,叫做P的否定,读做“非P”。并规定P为真当且仅当P为假。,用来描述应用联结词的命题的真值结果左边列出参与运算的命题真值的所有可能组合右边列出所得命题的真值结果用符号T(true)或1代表真,符号F(false)或0代表假一般在公式中采用T和F,在真值表中采用1和0,真值表,2.合取词;,如果P和Q是命题,那么“P并且Q”也是一命题,记为PQ,称为P和Q的合取,读做“P与Q”或“P并且Q”。并规定PQ为真当且仅当P和Q均为真。,注：,在自然语言中的表示“并且”意思的联结词是多种多样的。如“既又”、“不但而且”、“虽然但是”

6、、“一面一面”等。不要见到“与”或“和”就使用联结词。,例5,1.张辉与王丽都是三好学生。2.张辉与王丽是同学。1.是复合命题；2.是原子命题P:张辉是三好学生。Q:王丽是三好学生。T:张辉与王丽是同学。,3.析取词如果P和Q是命题,则“P或Q”也是一命题,记作PQ,称为P和Q的析取,读做“P或Q”。从真值表可知PQ为真,当且仅当P或Q至少有一为真。,例6(a)P:今晚我写字,Q:今晚我看书。PQ:今晚我写字或看书(b)P:今年是闰年;Q:今年她生孩子。PQ:今年是闰年或者今年她生孩子。,4.蕴涵词(常简写作含),如果P和Q是命题,那么“P蕴含Q”也是命题,记为PQ,称为蕴含式,读做“P蕴含Q

7、”或“如果P,那么Q”。运算对象P叫做前提,假设或前件,而Q叫做结论或后件。命题PQ是假,当且仅当P是真而Q是假。,为什么规定前件为假时，不论后件真假与否，蕴含式都为真呢？其实我们平时也采用这种思维方式，譬如，说“如果太阳从西边出来，我就不姓张。”其实不管“我”是否姓张，这句话都是对的，因为太阳根本就不会从西边出来。,注意：,蕴涵运算PQ表示的逻辑关系是：Q是P的必要条件，P是Q的充分条件。自然语言中可用PQ蕴涵式表述命题格式有：“只要P，就Q”、“因为P，所以Q”、“P仅当Q”、“只有Q才P”、“除非Q才P”、“除非Q，否则非P”等。与自然语言的不同：数理逻辑蕴涵式的前件与后件可以没有任何内

8、在联系！在数学中，如果P,则Q表达的仅仅是P为真，Q也为真的推理关系。,例7(a)P:天不下雨,Q:草木枯黄。PQ:如果天不下雨,那么草木枯黄。(b)R:G是正方形,S:G的四边相等。RS:如果G是正方形,那么G的四边相等。(c)W:桔子是紫色的,V:大地是不平的。WV:如果桔子是紫色的,那么大地是不平的。,5.等值词如果P和Q是命题,那么“P等值于Q”也是命题,记为PQ,称为等值式,读做“P等值于Q”。把蕴含式和等值式的真值表加以比较,易知如果PQ是真,那么PQ和QP俱真;反之如果PQ和QP俱真,那么PQ是真。由于这些理由,PQ也读做“P是Q的充要条件”或“P当且仅当Q”。,联结词之意义由其真值表唯一确定,而不由命题的含义确定。今后我们关心的各命题的真值关系，而不是命题的内容。运算符结合力的强弱顺序为、,结论,相同的运算符,按从左至右次序计算时,括号可省去。最外层的圆括号可以省去。,1.1.3命题变元和命题公式简单命题/命题常元：确指的或具体的命题。命题变元：不确指的或抽象的命题。以“真”,“假”为其变域的变元,称为