《离散数学》课件-第1章

1.1命题和联结词

1.2命题公式

1.3逻辑等价与蕴含

1.4联结词的完备集

1.5对偶式

1.6范式

1.7命题逻辑的推理理论第1章命题逻辑1.1.1命题

命题逻辑主要研究前提(premises)和结论(conclusion)之间的逻辑关系。例如，由前提“如果我平时不努力学习离散数学，那么我的期末成绩就会不及格”和“期末成绩出来，我的离散数学及格了”可以推出“我平时努力学习了”的结论。这里前提和结论都是断言(陈述句)，具有确定的真假值，它们是推理的基本单位，在数理逻辑中称为命题(proposition)。本节首先给出命题的定义并引入命题的逻辑运算。1.1命题和联结词

定义1.1.1

一个具有真或假但不能两者都是的断言称为命题。

如果一个命题所表达的判断为真，则称其真值(truthvalue)为“真”，用大写字母T或数字1表示；如果一个命题所表达的判断为假，则称其真值为“假”，用大写字母F或数字0表示。为简便起见，本书在构建真值表时一般用0表示“假”，用1表示“真”。

由命题的定义可知，命题必须满足以下两个条件：

(1)命题是表达判断的陈述句。疑问句、祈使句和感叹句等都不是命题。

(2)命题有确定的真假值，它的真值或者为真，或者为假，两者必居其一。1.1.2联结词

在代数中，用“＋”、“×”等运算符连接数字得到代数表达式，例如“3＋2”等。同样，在数理逻辑中，也存在运算符，称为逻辑联结词(logicconnective)，简称联结词。五个常用联结词的定义如下所述。

1.否定联结词

否定联结词也称为“非”运算，它对单个命题进行操作，是一个一元运算符。

定义1.1.2

设P是命题，P的否定(negation)是一个复合命题，记做P

，称为“非P”。符号用于表示否定联结词。P为真，当且仅当P为假。

下面引入真值表(truthtable)来描述复合命题的真值。真值表的左边列出参与运算的命题真值的所有可能组合，复合命题的真值结果列在最右边一列。因此，否定联结词的定义如表1.1.1所示。表1.1.1

2.合取联结词

定义1.1.3

如果P和Q是命题，那么“P并且Q”是一个复合命题，记做P∧Q，称为P和Q

的合取(conjunction)。符号∧用于表示合取联结词。P∧Q

为T，当且仅当P、Q

均为T。

“∧”是一个二元运算符。合取联结词∧的定义如表1.1.2所示。表1.1.2

3.析取联结词

定义1.1.4

如果P和Q是命题，那么“P或Q”是一个复合命题，记做P∨Q，称为P和Q

的析取(disjunction)。符号∨用于表示析取联结词。P∨Q

为T，当且仅当P、Q

至少有一个为T。

“∨”是一个二元运算。析取联结词∨的定义如表1.1.3所示。表1.1.3

4.条件联结词

定义1.1.5

如果P和Q是命题，那么“如果P，那么Q”是一个复合命题，记做P→Q

，称为P和Q

的条件命题(conditionalproposition)。符号→用于表示条件联结词。当且仅当P

为T且Q

为F时，P→Q

为F。这里，称P

为假设(hypothesis)或前件(antecedent)，称Q

为结论(conclusion)或后件(consequent)。

“→”是一个二元运算。条件联结词→的定义如表1.1.4所示。表1.1.4

5.双条件联结词

定义1.1.6

如果P和Q是命题，那么“P当且仅当Q”是一个复合命题，记做

P

Q，称为P和Q的双条件命题(biconditionalproposition)。符号用于表示双条件联结词。P

Q为T，当且仅当P和Q

的真值相同。

“”是一个二元运算。双条件联结词的定义如表1.1.5所示。表1.1.51.2.1命题公式及其符号化

定义1.2.1

用于代表取值为真(T、1)或假(F、0)之一的变量，称为命题变元，通常用大写字母或带下标或上标的大写字母表示，如P、Q、R、P1、P2等。将T和F称为命题常元。

通常把由命题常元、命题变元、联结词以及括弧组成的式子称为表达式，但是只有按照特定组合规则所形成的表达式才有实际意义。1.2命题公式

定义1.2.2

命题合式公式(简称命题公式)：

(ⅰ)(基础)单个命题常元或命题变元是命题合式公式。

(ⅱ)(归纳)如果A和B是命题公式，则A、(A∧B)、(A∨B)、(A→B)、(AB)是命题合式公式。

(ⅲ)(极小性)只有有限次地应用条款(ⅰ)和(ⅱ)生成的表达式才是命题合式公式。图1.2.1

定义1.2.3

若B是命题公式A的一个连续段且B也是命题公式，则称B是A

的一个子公式。

例如，

等均为的子公式。

在命题公式中，为了减少括号的使用，可以作以下约定：

(1)联结词运算的优先次序：的运算优先级最高，∧、∨的运算优先级次之，→、的运算优先级最低，不改变运算先后次序的括号可省去。

(2)相同的联结词，按从左至右顺序计算时，括号可省去。

(3)最外层的括号可省去。

定义1.2.4

把一个用自然语言叙述的命题写成与之内涵相同的命题公式的形式，称为命题的符号化。

1.2.2命题公式的赋值

命题公式的真值取决于其所含命题变元的真值，为了讨论命题公式，有必要引入赋值(assign)的概念。

定义1.2.5

设p1,p2,…,pn是命题公式A中出现的所有命题变元，如果给p1,p2,…,pn指定一组真值，则称为对命题公式A

赋值(指派或解释)。

不难验证，对于含有n

个命题变元的公式，由于每个命题变元可以有0(F)、1(T)两个不同赋值，因此有2n

个不同赋值。对含有n个命题变元的命题公式，为方便地观察命题公式在不同赋值下的真值，可以采用真值表的方式将命题公式在所有可能赋值下的真值列出来。对于真值表,可以作如下约定：

(1)将公式中出现的n

个命题变元按字典升序或降序排列。

(2)对2n

个不同赋值，按其对应的n

位二进制数从小到大或从大到小顺序排列。

(3)若公式较复杂，可从里层向外层先列出各子公式的真值，最后列出所求公式的真值。公式的真值表如表1.2.1所示。表1.2.1公式的真值表如表1.2.2所示。表1.2.2

公式的真值表如表1.2.3所示。表1.2.3

定义1.2.6

给定一个命题公式，如果在任何赋值下，它的真值都为T，则称该命题公式为重言式(tautology)或者永真式。

定义1.2.7

给定一个命题公式，如果在任何赋值下，它的真值都为F，则称该命题公式为矛盾式(contradiction)或者永假式。

定义1.2.8

给定一个命题公式，如果既不是永真式，也不是永假式，则称该命题公式为偶然式(contingency)。

对于某一个命题公式A

，如果至少存在一种赋值，使得它的真值为T，则A

是可满足式(satisfiable)。事实上,重言式和偶然式都是可满足式。如果一个命题公式不是可满足式，那么它是矛盾式。构造公式的真值表，如表1.2.4所示。表1.2.41.3.1等价

定义1.3.1

给定两个命题公式A和B，设P1,P2,…,Pn为所有出现在A和B中的命题变元，但Pi(i=1,2,…,n)不一定在A和B中同时出现，若对于P1,P2,…,Pn的任一赋值，A和B的真值都相同，则称A和B逻辑等价(logicallyequivalent)，记做AB，读做“A等价于B”。

要注意符号和的区别:是联结词，而表示两个命题公式之间的关系。1.3逻辑等价与蕴含由表1.3.1可见，P→Q和P∨Q在每一种赋值情况下，都具有相同的真值，所以二者是等价的。表1.3.1构造真值表，如表1.3.2所示。表1.3.2表1.3.3列出了一些常见的命题等价公式，这些结论都可以通过构造真值表进行验证。表1.3.3验证德·摩根定律(DeMorgan’slaws)构造真值表,如表1.3.4所示。表1.3.4

定理1.3.1(代入规则)

设

A、B是命题公式，其中A是重言式，P是A中的命题变元，如果将A中每一处出现的P均用B代入，则所得命题公式A′仍然是一个重言式。

定理1.3.2

设

A、B是命题公式，则A和B逻辑等价，当且仅当A

B是一个重言式。

定理1.3.3(替换规则)

设A、X、Y是命题公式，X是A的子公式，且有X

Y。如果将A中的X用Y来替换(不必每一处都替换)，则所得到的公式B与A等价，即B

A。

定理1.3.4(传递规则)

设A、B、C是命题公式，若

A

B且B

C，则有A

C。1.3.2蕴含

定义1.3.2

设A、B是命题公式，如果A→B是一个重言式，则称A

蕴含(implicate)B，记做

A

B。

由表1.3.5可见，(P→Q)→P是重言式，所以(P→Q)P。表1.3.5由表1.3.6可见，P∧(P→Q)→Q是重言式，所以P∧(P→Q)

Q

。表1.3.6表1.3.7列出了一些常见的蕴含公式，这些结论都可以通过构造真值表进行验证。表1.3.7

定理1.3.5

设A和B是任意两个命题公式，A

B当且仅当A

B且B

A。

下面列出蕴含关系的几个常用性质：

性质1

设A、B和C是命题公式，如果A

B并且A是重言式，则B

也是重言式。

性质2

如果A

B并且B

C，则A

C，即蕴含关系是传递的。

性质3

如果A

B并且A

C，则A

B∧C。

性质4

如果A

C并且B

C，则A∨B

C。

1.1节定义了5种联结词，那么是否使用这5种联结词就能够表达所有命题呢？本节讨论其他联结词和联结词的完备性理论。

对于一个一元运算符，只作用于一个命题变元，则其可能的运算结果就只有4种情况，如表1.4.1所示。1.4联结词的完备集表1.4.1对于二元运算，有两个命题变元参与运算，共4种赋值，则有16种可能的运算结果，如表1.4.2所示。表1.4.2其余几个运算可以定义如下新的联结词：关于以上4个新定义的联结词，有如下性质：

定义1.4.1

给定一个联结词集合，如果所有的命题公式都能用其中的联结词等价表示出来，则称该联结词集合为全功能联结词集合，或称该联结词集合是功能完备的(functionallycomplete)。证明不是全功能联结词集合。

设f(P,Q)表示仅用命题变元P和Q以及联结词构成的任意命题公式，现证明对P、Q的任意4种指派，f(P,Q)的取值封闭在表1.4.3所列的8种结果之中。表1.4.3

定义1.4.2

一个联结词集合是全功能的，并且去掉其中任意一个联结词后均不是全功能的，则称其为极小全功能联结词集合。

定义1.5.1

设有命题公式A，其中仅含有联结词、∨和∧，如果将A中的∨换成∧，∧换成∨，常元F和T

也互相替换，所得公式记做A*，则称A*为A的对偶(dual)公式。

显然，A也是A*的对偶公式，即对偶是相互的，即(A*)*=A。1.5对偶式

定理1.5.1

设A和A*是对偶公式，其中仅含有联结词、∨和∧，P1,P2,…,Pn是出现在A和A*中的所有命题变元，于是有

(证明过程用到的归纳法将在本书3.4节中详细给出。)

定理1.5.2

设A和B是命题公式，P1，P2，…，Pn是出现在A和B中的命题变元，则有：

(1)如果A

B，则A*B*。

(2)如果A

B，则B*A*。1.6.1析取范式和合取范式

定义1.6.1

仅由若干命题变元和若干命题变元之否定通过联结词∨构成的命题公式称为析取式。

1.6范式

定义1.6.2

仅由若干命题变元和若干命题变元之否定通过联结词∧组成的命题公式称为合取式。

定义1.6.3

一个命题公式称为析取范式(disjunctivenormalform)，当且仅当它具有如下形式：

A1∨A2∨…∨An(n≥1)

定义1.6.4

一个命题公式称为合取范式(conjunctivenormalform)，当且仅当它具有如下形式：

A1∧A2∧…∧An(n≥1)对于任何一个命题公式，都可以求得它的合取范式或者析取范式，步骤如下：

(1)将公式中的联结词都归约成、∨和∧。

(2)利用德·摩根定律将否定联结词直接移到各命题变元之前。

(3)利用分配律、结合律将公式归约成合取范式或者析取范式。1.6.2主析取范式

定义1.6.5

一个含n个命题变元的合取式，如果其中每个变元与其否定不同时存在，但两者之一必须出现且仅出现一次，则称该合取式为极小项(minterm)。

n个命题变元P1，P2，…，Pn可构成2n个不同的极小项，具有如下形式：

现以两个变元P、Q为例，编码如下：

依次类推，含n个命题变元P1,P2,…,Pn的极小项的编码为

表1.6.1列出了两个变元P和Q及其极小项的真值表。由表1.6.1可以看出，没有两个极小项是等价的，且每个极小项都恰对应P和Q的一组赋值使其为真。表1.6.1

n个命题变元P1,P2,…,Pn构成的极小项具有如下性质：

(1)每一个极小项当其赋值与编码相同时，其真值为T，在其余2n－1种赋值下其真值均为F。

(2)任意两个不同极小项的合取式永假，即

(3)所有极小项的析取式永真，记为

定义1.6.6

设P1,P2,…,Pn是命题公式A中包含的所有命题变元，若由P1,P2,…,Pn的若干极小项析取所构成的析取范式与A等价，则称该析取范式为A的主析取范式(principledisjunctivenormalform)。

对于一个给定的命题公式，可以用构造真值表的方法求得它的主析取范式。

定理1.6.1

在一个命题公式A的真值表中，使A的真值为T的所有赋值所对应的极小项构成的析取范式即为A的主析取范式。用构造真值表的方法求命题公式P∧(Q→R)的主析取范式。构造其真值表如表1.6.2所示。表1.6.2

P∧(Q→R)的主析取范式为

除了用真值表求一个命题公式的主析取范式外，还可以用常用等价公式进行等价推演的方法，得到它的主析取范式。这是因为任何一个命题公式都可以求得它的析取范式，而析取范式可转化为主析取范式，步骤如下：

(1)将原命题公式转化为析取范式。

(2)将每个合取式等价变换为若干极小项的析取(对每个合取式填补没有出现的变元，如缺P和P，则合取

P∨P，再应用分配律展开)。

(3)重复的极小项只保留一个。1.6.3主合取范式

与主析取范式相对应的还有主合取范式。下面介绍主合取范式的相关概念以及求一个命题公式的主合取范式的方法。

定义1.6.7

一个含n个命题变元的析取式，如果其中每个变元与其否定不同时存在，但两者必须出现且仅出现一次，则这样的析取式称为极大项(maxterm)。

n个命题变元P1，P2，…，Pn可构成2n个不同的极大项，具有如下形式：

现以两个变元P、Q为例进行编码。

依次类推，含n个命题变元P1,P2,…,Pn的极大项的编码为

表1.6.3列出了两个变元P和Q及其极大项的真值表。由表1.6.3可以看出，没有两表1.6.3读者可以验证，这个结论可以推广到三个和三个以上变元的情况。

n个命题变元P1,P2,…,Pn构成的极大项具有如下性质：

(1)每一个极大项当其真值赋值与编码相同时，其真值为F，在其余2n－1种指派下其真值均为T。

(2)任意两个不同极大项的析取式永真。

(3)所有极大项的合取式永假，记为

定义1.6.8

设P1,P2,…,Pn是命题公式A中包含的所有命题变元，若由P1,P2,…,Pn的若干极大项合取所构成的合取范式与A等价，则称其为A的主合取范式(principleconjunctivenormalform)。

对于一个给定的命题公式，也可以用真值表求得它的主合取范式。

定理1.6.2

在一个命题公式A的真值表中，使A的真值为F的所有赋值所对应的极大项构成的合取范式即为A的主合取范式。用构造真值表的方法求命题公式P∧(Q→R)的主合取范式。构造其真值表如表1.6.4所示。表1.6.4除了用真值表求一个命题公式的主合取范式外，也可以用基本等价公式进行等价推演的方法得到它的主合取范式。这是因为任何一个命题公式都可以求得它的合取范式，而合取范式可转化为主合取范式，步骤如下：

(1)将原命题公式转化为合取范式。

(2)将每个析取式等价变换为若干极大项的合取(对每个析取式填补没有出现的变元，如缺P和P，则析取P∧

P，再应用分配律展开)。

(3)重复的极大项只保留一个。

定理1.6.3

已知由n个不同命题变元构成的命题公式A的主析取范式为，其主合取范式为

，则有

证明由于命题公式A的主析取范式为，主合取范式为，则有

且。由此可得：

则有

因为

故有

又因为

定义1.7.1

设H1,H2,…,Hn,C是命题公式，若H1∧H2∧…∧Hn

C，则称C是一组前提H1,H2,…,Hn的有效结论(validconclusion)，或者称C可由前提H1,H2,…,Hn逻辑推出。从前提H1,H2,…,Hn推出结论的过程，称为推理(reasoning)、论证(argument)或证明(proof)。1.7命题逻辑的推理理论如果H1∧H2∧…∧Hn

C，说明H1,H2,…,Hn可以逻辑推出C，即推理是正确的。但推理正确不保证结论C一定正确，结论的真假取决于前提H1∧H2∧…∧Hn的真假，前提为真时，结论C为真,前提为假时，结论C可能为真，也可能为假。

为了方便起见，通常也可将H1∧H2∧…∧Hn

C写做H1,H2,…,Hn

C。

表1.3.3和表1.3.7所列的等价公式和蕴含公式都可以作为推理规则使用。另外，在推理过程中还有两条常用的重要推理规则：

(1)P规则：在推导过程中，前提可以在任何步骤引入。

(2)T规则：在推导过程中，如果由已经推出的一个或多个公式蕴含S，则公式S可以引入到推导过程中。判别结论是否有效有各种不同的方法。下面介绍几种常用的证明方法。

方法1：无义证明法。如果能够证明