离散数学教程课件

离散数学

第一部分数理逻辑

数理逻辑又名符号逻辑，是一门用数学方法研究推理过程的科学。逻辑学主要是研究各种论证。它可以是有意义的一般论证，也可以是科学理论中的数学证明或结论。建立逻辑学的主要目的在于探索出一套完整的规则，按照这些规则，就可以确定任何特定论证是否有效。这些规则，通常称为推理规则。同其它科学理论一样，也可以把推理理论公式化(由于自然语言易产生二义性,用它来表示严格的推理就不合适了)。由于在逻辑学中使用了符号，故数理逻辑也称为符号逻辑。

命题逻辑是数理逻辑的基本组成部分.本章重点：命题、命题的符号化、命题联结词及其真值、命题公式及其赋值本章难点：命题公式及其赋值

第一章命题逻辑1.1命题及命题联结词

一、命题及其表示法能够判断真假的陈述句称作命题。

1命题的概念真值：作为命题的陈述句所表达的判断结果真值只能取两个：真或假。因为只有两种真值，所以这种逻辑有时称为二值逻辑。真值为真的命题称为真命题；真值为假的命题为假命题。判断句子是否为命题的标准：(1)陈述句(2)有唯一的真值说明：命题必须是陈述性语句，而不能是疑问句、命令句、感叹句等；2.命题语句或者为真或者为假，二者必取其一，即命题的真值是唯一的

例1判断下列句子是不是命题:(1)4是素数。(2)是无理数。(3)(4)火星上有水。(5)2005年元旦是晴天(6)(7)请不要吸烟！

(8）这朵花真美丽啊！(9）我正在说假话.假命题真命题命题命题由真推出假，又由假推出真的陈述句称为悖论，凡悖论都不是命题。2命题与真值的符号化

本书中命题用大写英文字母表示：用1和0分别表示“真”和“假”,于是命题的真值取值为1或0.3原子命题与复合命题

不能分解成更简单的语句的命题称为原子命题。

原子命题中的“原子”取原子的“不可再分”之意,它是最基本的命题,相当于自然语言的简单陈述句。例２下面的命题由哪些原子命题组成:(1)只要明天天气好,我就去春游。(2)如果10是一个大于１的整数,则10的大于１的最小因数一定是素数。

解(1)有两个原子命题P和Q,其中

P:明天天气好。

Q:我去春游。(2)有两个原子命题R和S,其中

R:10是一个大于１的整数。

S:10的大于１的最小因数是素数。

多个原子命题由联结词和圆括号联结起来构成的命题称为复

合命题。复合命题的真假值只与原子命题的真假值有关。

二、联结词定义1.1若P是一个命题,则由否定词┐和命题P组成的复合命题┐P称为P的否定式,读作“非P”。┐P的真值定义为

命题┐P和P的关系可以用下表表示。称为┐P的真值表。1否定联结词﹁┐P为真当且仅当P为假

P﹁P0110定义1.２若P,Q是两个命题,则由合取词∧和命题P,Q

组成的复合命题P∧Q称为P,Q的合取式,读作“P且Q”。

P∧Q的真值定义为

P∧Q为真当且仅当P,Q都为真因此,P,Q同时为假或一真一假时,P∧Q都为假。

2合取联结词∧复合命题P∧Q的真值表：

PQP∧Q000010100111例３设有命题P,Q为

P:吴颖用功。Q:吴颖聪明。

则P,Q的合取式P∧Q

为

P∧Q

:吴颖既用功又聪明。或P∧Q

:吴颖不仅用功而且聪明。

合取词∧是自然语言中的连接词“并且”、“和”、“及”、“与”“既又”、“不但…，而且…”、“虽然…，但是…”、“一面…，一面…”等的逻辑抽象。

定义1.3若P,Q是两个命题,则由析取词∨和命题P,Q组成的复合命题

P∨Q称为P,Q的析取式,读作“P或Q”。

P∨Q的真值定义为

P∨Q为真当且仅当P,Q

至少有一个为真

因此只有P,Q同时为假时,P∨Q才为假。3析取联结词∨复合命题P∨Q

的真值表：

PQP∨Q000011101111例1.3将下列命题符号化。

(1)张晓静爱唱歌或爱听音乐。

(2)张晓静是江西人或安徽人。

(3)张晓静只能挑选202或203房间。解在解题时，先将原子命题符号化。

(1)P：张晓静爱唱歌。

Q：张晓静爱听音乐。自然语言的或有二义性,用它联结的命题有时是相容的,有时是排斥的,对应称为相容或与排斥或显然(1)中“或”为相容或，即P与Q可以同时为真，符号化为P∨Q.

(2)R：张晓静是江西人。

S：张晓静是安徽人。

易知，(2)中“或”应为排斥或，但不可能同时为真，可符号化为R∨S.

(3)T：张晓静挑选202房间。

U：张晓静挑选203房间。

由题意可知，(3)中“或”应为排斥或。T，U的联合取值情况有四种：同真，同假，一真一假(两种情况)。如果也符号化为T∨U，张晓静就可能同时得到两个房间，这违背题意。因而不能符号化为T∨U.如何达到只能挑一个房间的要求呢？可以使用多个联结词，符号化为(T∧┐U)∨(┐T∧U)定义1.4若P,Q是两个命题,则由蕴涵词→和命题P,Q组成的复合命题P→Q

称为P,Q的蕴涵式,读作“如果P,则Q”。4蕴涵联结词→

P→Q

为假当且仅当P为真而Q为假

因此,P为假时,不管Q

为真还是为假,P→Q

都为真;而P,Q同时为真时,P→Q

也为真。

复合命题P→Q

的真值表：

PQP→Q

001011100111P→Q

的真值定义为1．在自然语言里，特别是在数学中，Q是P的必要条件有许多不同的叙述方式。例如，“只要P，就Q”，“因为P，所以Q”，“P仅当Q”，“只有Q才P”，“除非Q才P”，“除非Q，否则非P”等等。以上各种叙述方式表面看来有所不同，但都表达的是Q是P的必要条件，因而所用联结词均应符号化为→，上述各种叙述方式都应符号化为P→Q.注意：在使用联结词→时，要特别注意以下几点：

例5设有命题P,Q为

P:∠1和∠2是对顶角。Q:∠1＝∠2则蕴涵式P→Q为

P→Q:若∠1和∠2是对顶角,则∠1＝∠2。这时我们也说“P是Q的充分条件”,或“Q是P的必要条件”。

3．在数学或其它自然科学中，“如果P，则Q”往往表达的是前件P为真，后件Q也为真的推理关系。但在数理逻辑中，作为一种规定，当P为假时，无论Q是真是假，P→Q均为真。也就是说，只有P为真Q为假这一种情况使得复合命题P→Q为假。

2．在自然语言中，“如果P，则Q”中的前件P与后件Q往往具有某种内在联系。而在数理逻辑中，P与Q可以无任何内在联系。

解:令P:3+3=6,P的真值为1;Q:雪是白色的,Q的真值为1;R:a能被4整除;S:a能被2整除.则(1)-(4)分别符号化为(5)-(9)符号化为(10)符号化为复合命题P

Q的真值表：

定义1.5若P,Q是两个命题,则由等值词和命题P,Q

组成的复合命题P

Q

称为P,Q的等价式,读作“P当且仅当Q”。P

Q为真当且仅当P,Q同真值因此,P,Q一真一假时,P

Q为假。

PQPQ001010100111P

Q的真值定义为

5等值联结词等值词

是自然语言中的连接词“当且仅当”等的逻辑抽象。

以上定义了五种最基本、最常用、也是最重要的联结词┐，∧，∨，→，，将它们组成一个集合{┐，∧，∨，→，}，称为一个联结词集。其中┐为一元联结词，其余的都是二元联结词。

联结词可以嵌套使用，在嵌套使用时，规定如下优先顺序：()，┐，∧，∨，→，，对于同一优先级的联结词，先出现者先运算。

解P，Q，R的真值分别为1，1，0。容易算出(1)、(2)、(3)的真值分别为1，1，0。

可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。命题翻译时应注意下列事项：（1）确定所给句子是否为命题。（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命题联结词。

命题的翻译(命题符号化)本例可表示为：（PQ）∧（P（R∨S））。

例7：假如上午不下雨，我去看电影，否则就在家里读书或看报。

解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。例8设P:明天下雨，

Q:明天下雪，

R:我去学校。试把下列命题符号化:(1)如果明天不是雨夹雪,我就去学校。(2)如果明天既不下雨又不下雪,我就去学校。(3)明天下雨或者下雪,我就不去学校。

解(1)┐(P∧Q)→R(2)(┐P∧┐Q)→R(3)(P∨Q)→┐R例9设有命题P,Q,R为

P:雪是黑的。

Q:小李是共青团员。

R:小王是大学生。请写出命题┐P,P∧Q,P∨Q和(P∧Q)→R的含义。

解┐P:雪不是黑的。

P∧Q:雪是黑的且小李是共青团员。

P∨Q:雪是黑的或者小李是共青团员。

P∧Q)→R:如果雪是黑的且小李是共青团员,那么小王是大学生。