离散数学课件 第1章 命题逻辑

离散数学

Discrete

Mathematics第1章命题逻辑1.1命题及联结词1.2命题公式及真值表1.3命题公式的等值式及蕴含式1.4联结词的全功能集1.5命题公式的范式1.6推理理论1.7命题逻辑的应用2

1.1命题及联结词第1章数理逻辑

命题的定义命题的表示命题变元联结词3离散数学命题的定义4定义1.1

能判断真假的陈述句叫做命题。离散数学

例如：别的星球上有人类存在。虽然目前我们还没有确切的依据来判断真假，但这句话描述的是一个事实，要么真，要么假。

命题的定义包含两层含义：首先，从语法上命题必须是陈述句，因此疑问句、祈使句、感叹句等都不是命题；其次，一个陈述句能否判断真假，与是否知道它的真假是两码事。5离散数学命题的定义凡是与事实相符合的命题称为真命题，否则称为假命题。一个命题总有一个“值”（或真或假），称为命题的真值，或简称为命题的值。一般用T或1表示真，用F或0表示假。6离散数学命题的定义命题有两种类型：第一类型是不能分解为更简单的陈述句，称为简单命题或原子命题。第二类型是由原子命题用联结词联结而成的命题，称为复合命题。7离散数学命题的定义例题1.1判断下列句子是否为命题，如果是命题，试给出其真值。（1）北京是中国的首都。（2）地球是圆柱形的。（3）11+1=100。（4）这些花朵真漂亮呀！（5）请勿在此停车！（6）请问去火车站怎么走？（7）我正在说谎。（8）（9）如果天气好，那么我去散步。

(10）我学习英语或俄语。8离散数学命题的定义

在上述例子中，（1）、（2）、（3）、（9）、（10）是命题，其中（9）、（10）是复合命题。（3）在二进制中为真，在10进制中为假，故需根据上下文才能确定真值。（4）、（5）、（6）都不是陈述句，因此不是命题。（7）是悖论，假设这句话为真，从语义上来说，我应该说的是谎话，逻辑真值与语义正相反，反之亦然，互相矛盾，所以不能判断真假。（8）在不确定x,y取值时，无法确定真值，因此它不是命题。、9离散数学命题的表示在数理逻辑中，常用大写字母或用小写字母在本书中，通常用小写字母表示简单命题，称为命题符号化。

表示命题。

：今天下雨了。

：雪是黑色的。

例如10离散数学

一个命题标识符如果表示具体的、确定内容的命题就称为命题常元（或命题常量）。如果命题标识符表示任意的、没有赋予具体内容的抽象命题，就称为命题变元（或命题变量）。命题变元

因为命题变元可以表示任何命题，所以它不能确定真值，只有用具体命题代入后，它才可以确定其真值，故命题变元不是命题。11离散数学

联结词

在数理逻辑中，复合命题是由原子命题和逻辑联结词组合而成，联结词是复合命题中的重要组成部分。在数理逻辑中，常用的联结词中常用的联结词有5个，它们分别为：┐,∧,∨,→,

。12离散数学

联结词：否定词

1.否定（negation）词:

定义1.2设p表示一个命题，利用“

”和p组成的复合命题称为命题

p的否命题，记作

p，读作非p。称符号“

”为否定联结词。若p为真，

p

为假；若

p

为假，

p

为真。13离散数学

命题p与其否定

p

的真值关系如表1.1所示。表1.1

p

的真值表

联结词：否定词

14离散数学

联结词：否定词

15离散数学

联结词：合取词∧2.合取（conjunction）词:∧16离散数学

联结词：合取词∧17离散数学

联结词：合取词∧18离散数学

联结词：合取词∧19离散数学

联结词：析取词∨3.

析取（

disjunction）词：∨20离散数学

联结词：析取词∨21离散数学

联结词：析取词∨还有一些汉语中的“或”，不是命题联结词。例题1.7

他看起来有二十或三十岁。这个例子中的“或”，表示年龄的近似值，不是联结词。22离散数学

联结词：条件词

4.

条件（conditional）词：

23离散数学

联结词：条件词

为避免与后文定义“蕴含式”的定义混淆，一般条件命题中不使用“蕴涵”一词。24离散数学

联结词：条件词

例题1.8

符号化下列命题。（1）如果周末是晴天，那么我们去爬山。

（2）只要天不下雨，我就骑车去上班。（3）仅当下雨，我才坐公交车去上班。25离散数学

联结词：条件词

26离散数学

联结词：等价联结词

5.等价（equivalence）联结词：

27离散数学

联结词：等价联结词

28离散数学

联结词：等价联结词

例题1.9

符号化下列命题，并确定其真值。（1）两个三角形全等，当且仅当它们的三组对应边相等。（2）雪是黑的当且仅当太阳从西方落下。29离散数学

联结词：等价联结词

例题1.9

符号化下列命题，并确定其真值。（1）两个三角形全等，当且仅当它们的三组对应边相等。（2）雪是黑的当且仅当太阳从西方落下。30离散数学

联结词优先次序的规定：

（1）逻辑联结词的优先级由强到弱依次是：

┐,∧,∨,→,

。其中∧与∨同级。（2）括号中的运算最优先。（3）同级联结词，按从左往右的次序运算。31离散数学

练习题：列出下列命题公式的真值表。联结词

1.2命题公式及真值表第1章数理逻辑

命题公式的定义命题公式的赋值真值表命题的分类重言式矛盾式可满足式

32离散数学33离散数学

命题公式的定义

命题演算的合式公式，又称命题公式，简称为公式，是由命题变元、联结词和圆括号组成的符号串。34离散数学

命题公式的定义

等都是命题公式。35离散数学

命题公式的定义

36离散数学

命题公式的赋值

37离散数学

真值表

38离散数学

真值表

39离散数学

真值表

40离散数学

真值表

41离散数学

命题的分类

1.3命题公式的等值式及蕴含式第1章数理逻辑

等值式常用等值式置换规则等值演算蕴含式常用蕴含式

42离散数学43离散数学

等值式

44离散数学

等值式45离散数学

等值式46离散数学

常用等值式1

A

A双重否定律2A

A

A,A

A

A等幂律3(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)结合律4A

B

B

AA

B

B

A交换律5A

(B

C)

(A

B)

(A

C)A

(B

C)

(A

B)

(A

C)分配律6A

(A

B)

AA

(A

B)

A吸收律7

(A

B)

A

B

(A

B)

A

B德·摩根率8A

0

A,

A

1

A同一律9A

1

1,A

0

0零律10A

A

1，A

A

0否定律11A

B

A

B蕴涵等值式12A

B

(A

B)

(B

A)等价等值式13A

B

B

A假言易位47离散数学

置换规则故48离散数学

等值演算49离散数学

等值演算50离散数学

等值演算51离散数学

蕴含式52离散数学

蕴含式53离散数学

蕴含式注意：蕴涵式与蕴含式的区别。蕴涵式：

A→B蕴含式：当且仅当A→B是一个重言式时，我们称“A蕴含B”。54离散数学

蕴含式55离散数学

常用蕴含式56离散数学

蕴含式57离散数学

蕴含式的几个常用性质：设A、B、C为命题公式(1)若A

B且A是重言式，则B也是重言式。（2若A

B，B

C，则A

C，即蕴含关系

是传递的。（3）若A

B且A

C，那么A

(B∧C)。（4）若A

B且C

B，则A∨C

B。蕴含式

1.4联结词的全功能集第1章数理逻辑

其他联结词

排斥或、与非、或非全功能集对偶式58离散数学59离散数学

其他联结词60离散数学

其他联结词61离散数学

其他联结词62离散数学

其他联结词63离散数学

其他联结词64离散数学

其他联结词65离散数学

其他联结词66离散数学

全功能集67离散数学

全功能集68离散数学

全功能集69离散数学

全功能集70离散数学

对偶式

在等值演算中，考查给出的常用的逻辑等值式（如表1.11），基本是成对出现的，这些成对出现的等值公式存在着对偶关系。71离散数学

对偶式72离散数学

对偶式73离散数学

对偶式证明：由德·摩根定律即同理74离散数学

对偶式75离散数学

对偶式76离散数学

对偶式

1.5命题公式的范式第1章数理逻辑

析取范式与合取范式简单析取式、简单合取式、范式主析取范式与主合取范式

极小项、极大项、主范式主范式的应用77离散数学78离散数学

析取范式与合取范式

定义1.18仅由有限个命题变元或其否定所组成的析取式称为简单析取式；仅由有限个命题变元或其否所组成的合取式称为简单合取式。79离散数学

析取范式与合取范式

定义1.19由有限个简单合取式的析取所构成的命题公式称为析取范式；由有限个简单析取式的合取所构成的命题公式称为合取范式。80离散数学析取范式与合取范式析取范式:由有限个简单合取式组成的析取式。

A1

A2

Ar,其中A1,A2,,Ar是简单合取式。合取范式:由有限个简单析取式组成的合取式。

A1

A2

Ar,其中A1,A2,,Ar是简单析取式。都是析取范式。例如：都是合取范式。而：81离散数学

析取范式与合取范式82离散数学

析取范式与合取范式83离散数学

析取范式与合取范式

84离散数学

析取范式与合取范式

可见，一个命题公式的析取范式和合取范式并不是唯一的。为了将命题公式的范式唯一化，下面介绍主范式的相关知识。85离散数学

主析取范式与主合取范式86离散数学

主析取范式与主合取范式87离散数学

主析取范式与主合取范式88离散数学

主析取范式与主合取范式89离散数学

主析取范式与主合取范式极小项的编码及成真赋值如表1.17。90离散数学

主析取范式与主合取范式

定义1.21

对于给定的命题公式，若它的一个等值公式仅由极小项的析取所组成，则称该等值公式为原式的主析取范式。

定理1.7在真值表中，一个命题公式的真值为真的赋值所对应的极小项的析取，即为此公式的主析取范式。91离散数学

主析取范式与主合取范式92离散数学

主析取范式与主合取范式93离散数学

主析取范式与主合取范式

94离散数学

主析取范式与主合取范式95离散数学

主析取范式与主合取范式96离散数学

主析取范式与主合取范式极大项的编码如表1.19所示。97离散数学

主析取范式与主合取范式

定义1.23对于给定的命题公式，若它的一个等值公式仅由极大项的合取所组成，则称该等值公式为原式的主合取范式。

定理1.8

在真值表中，一个公式的真值为假的赋值所对应的大项的合取，称为该公式的主合取范式。98离散数学

主析取范式与主合取范式99离散数学

主析取范式与主合取范式100离散数学

主析取范式与主合取范式下面用等值演算进行求解

101离散数学

主范式的应用（1）求公式的成真赋值和成假赋值例如

则其成真赋值为001,011,101,110,111；其余的赋值000,010,100都是成假赋值.102离散数学

主范式的应用（2）判断公式的类型103离散数学

例题1.25用主析取范式判断下列公式的类型。主范式的应用

104离散数学

主范式的应用该式为矛盾式。105离散数学

主范式的应用

106离散数学

主范式的应用

107离散数学

该式主析取范式中有5个极小项，故不是重言式，是可满足式。主范式的应用108离散数学

主范式的应用

若两个命题公式的主析取范式或主合取范式完全相同，则这两个命题公式等值。（3）判断两个命题公式是否等值例题1.26用主范式判断下述两个公式是否等值：

109离散数学

主范式的应用

110离散数学

主范式的应用111离散数学

主范式的应用（4）其他应用问如何选派？112离散数学

主范式的应用则可将选派方案表示为如下命题公式：113离散数学

主范式的应用求该公式的主析取范式：

1.6命题逻辑的推理理论第1章数理逻辑

推理的基本概念

有效结论、相容、不相容推理的判别方法

真值表法、直接证法反证法、CP规则114离散数学115离散数学推理的基本概念116离散数学

推理的基本概念117离散数学

推理的判别方法

（1）真值表法118离散数学

解：列出真值表如表1.21所示。推理的判别方法119离散数学

解：列出相关真值表如表1.22所示推理的判别方法120离散数学

推理的判别方法121离散数学

推理的判别方法（2）直接证法

直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等值式和蕴含式，推演得到有效的结论。常用的推理规则有：

前提引入规则：推导过程中可随时引入前提集合中的任意一个前提。

逻辑结果引入规则：推导过程中可随时引入公式S，公式S是由其前的一个或多个公式推导出来的逻辑结果。

122离散数学

推理的判别方法例题1.30用推理规则证明123离散数学

推理的判别方法

例题1.31符号化下列命题，并用推理规则导出结论。

假如我的考试通过，那么我很快乐；如果我快乐，那么阳光很好；现在是凌晨一点且天气暖和。该生考试是否通过？124离散数学

推理的判别方法故结论是该生考试没有通过。125离散数学

推理的判别方法（3）故谬法（反证法）126离散数学

推理的判别方法（4）附加前提证明法（CP)规则127离散数学

推理的判别方法128离散数学

推理的判别方法

1.7命题逻辑的应用第1章数理逻辑

优化数字电路设计在加法器电路设计中的应用推理的判别方法129离散数学130离散数学优化数字电路设计131离散数学

优化数字电路设计图1.1基本逻辑运算132离散数学

优化数字电路设计

例题1.34试利用命题公式的基本等值关系化简图1.2所示的逻辑图。图1.2原始逻辑图解：