第1章---数理逻辑-new.ppt

离散数学;离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学根底等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的根底。;第一章数理逻辑;1.1命题;例1下述都是命题:;

(a)今天下雪;;

(b)3+3=6;;

(c)2是偶数而3是奇数;;

(d)陈涉起义那天,杭州下雨;;

(e)较大的偶数都可表为两个质数之和。;

以上命题,(a)的真值取决于今天的天气,(b)和(c)是真,(d)已无法查明它的真值,但它是或真或假的,将它归属于命题。(e)目前尚未确定其真假,但它是有真值的,应归属于命题。;例2下述都不是命题:;

(a)x+y＞4。 (c)真好啊!;

(b)x=3。 (d)你去哪里?;

(a)和(b)是断言,但不是命题,因为它的真值取决于x和y的值。(c)和(d)都不是断言,所以不是命题。;例3一个人说:“我正在说谎”。

他是在说谎还是在说真话呢?如果他讲真话,那么他所说的是真,也就是他在说谎。我们得出结论如果他讲真话,那么他是在说谎。另一方面,如果他是说谎,那么他说的是假;因为他成认他是说谎,所以他实际上是在说真话,我们得出结论如果他是说谎,那么他是讲真话。

从以上分析,我们得出他必须既非说谎也不是讲真话。这样,断言“我正在说谎”事实上不能指定它的真假,所以不是命题。这种断言叫悖论。;在萨维尔村，理发师挂出一块招牌：“我只给村里所有那些不给自己理发的人理发。”有人问他：“你给不给自己理发？”理发师顿时无言以对。

这是一个矛盾推理：如果理发师不给自己理发，他就属于招牌上的那一类人。有言在先，他应该给自己理发。

反之，如果这个理发师给他自己理发，根???招牌所言，他只给村中不给自己理发的人理发，他不能给自己理发。

因此，无论这个理发师怎么答复，都不能排除内在的矛盾。这个悖论是罗素在一九○二年提出来的，所以又叫“罗素悖论”。;假设一个命题已不能分解成更简单的命题,那么这个命题叫原子命题或本原命题。例1中(a),(b),(d),(e)都是本原命题,但(c)不是,因为它可写成“2是偶数”和“3是奇数”两个命题。

命题和本原命题常用大写字母P,Q,R:表示。如用P表示“4是质数”,那么记为;

P:4是质数。;1.1.2命题联结词

命题和原子命题常可通过一些联结词构成新命题,这种新命题叫复合命题。例如;

P:明天下雪,Q:明天下雨

是两个命题,利用联结词“不”,“并且”,“或”等可分别构成新命题:;

“明天不下雪”;;

“明天下雪并且明天下雨”;;

“明天下雪或者明天下雨”等。;即;

“非P”;;

“P并且Q”;

“P或Q”等。

在代数式x+3中,x,3叫运算对象,+叫运算符,x+3表示运算结果。在命题演算中,也用同样术语。联结词就是命题演算中的运算符,叫逻辑运算符或叫逻辑联结词。常用的有以下5个。

∧∨→;1.否认词;这张表叫真值表,定义运算符的真值表,指明如何用运算对象的真值,来决定一个应用运算符的命题的真值。真值表的左边列出运算对象的真值的所有可能组合,结果命题的真值列在最右边的一列。为了便于阅读,我们通常用符号T(true)或1代表真,符号F(false)或0代表假。一般在公式中采用T和F,在真值表中采用1和0。这样,以上真值表可写成;例4

(a)P:4是质数。

P:4不是质数。或4是质数,不是这样。

(b)Q:这些都是男同学。

Q:这些不都是男同