离散数学(第2版)840

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)、(A

B)是命题合式公式。

(ⅲ)(极小性)只有有限次地应用条款(ⅰ)和(ⅱ)生成的表达式才是命题合式公式。图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)，记做A

B，读做“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

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

complete)。证明不是全功能联结词集合。

设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：无义证明法。如果能够证明P恒为假，则有P→Q恒为真，即P

Q。

方法2：平凡证明法。如果能够证明Q恒为真，则有P→Q恒为真，即P

Q。

方法3：直接证明法。直接证明法就是从一组前提出发，利用公认的推理规则(表1.3.3所列的等价公式、表1.3.7所列蕴含公式、P规则、T规则)，逻辑演绎得到有效结论。具体地说，采用直接证明法证明H1，H2，…，Hn

C的过程如下：

构造一个公式序列A1，A2,…,Am，使之满足:

(1)Am=C。

(2)对于每一个Ai(i=1,2,…,m)，或者Ai=Hj,(1≤j≤n)，即由P规则得到,或者存在Ai1，Ai2,…,Aik(1≤i1＜i2＜…＜ik≤i－1)，Ai1∧Ai2∧…∧Aik

Ai(表1.3.7中的蕴含公式)，或者Ai1∧Ai2∧…∧Aik

Ai(表1.3.3中的等价公式)，即由T规则得到。

定义1.7.2

设P1，P2，…，Pn是命题公式H1，H2，…，Hm中的所有命题变元，如果存在P1，P2，…，Pn的一种赋值，使得H1∧H2∧…∧Hm的真值为T，则称命题公式集合｛H1，H2，…,Hm｝是一致的或相容的，否则称为不一致的或不相容的。

因为当｛H1，H2，…,Hm｝不相容时，H1∧H2∧…∧Hm的真值恒为F，所以这个定义的另一种等价说法是：设H1，H2，…,Hm是公式，若存在公式

R，使得H1,H2,…,Hn

R∧R，则称命题公式集合｛H1，H2,…,Hm｝是不一致的或不相容的，否则称为一致的或相容的。

定理1.7.1

H1，H2，…,Hm，C是公式，如果存在公式R，使得H1，H2，…,Hm，CR∧

R，则有H1，H2，…,Hm

C。2.1谓词和量词

2.2谓词公式

2.3谓词演算的永真公式

2.4谓词逻辑的推理理论第2章谓词逻辑2.1.1谓词

定义2.1.1

刻画单个个体的特性或者多个个体间关系的模式称为谓词(predicate)。

通常，一元谓词用于刻画个体的特性，由一个表示个体特性的大写字母(称为特性谓词符、一元谓词符、一元关系符)和一个个体常元或变元组成的表达式表示，如P(a)、Q(x)等。2.1谓词和量词二元谓词用于刻画两个个体之间的关系，由一个表示两个个体关系的大写字母(称为二元谓词符、二元关系符)和两个个体常元或变元组成的表达式表示，如Q(a,b)、Q(x，y)、R(a,x)等。

……

n元谓词用于刻画n个个体之间的关系，由一个表示n个个体关系的大写字母(称为n元谓词符、n元关系符)和n个个体常元或变元组成的表达式表示，如R(a1,a2,…,an)、R(x1,x2,…,xn)等。

根据以上约定，谓词就可以简单地描述为是由一个谓词符和若干具有有固定次序的个体常元或变元组成的表达式。带有n(n≥0)个个体的谓词称为n

元谓词。

例如，“x是偶数”可以用谓词P(x)表示，P(2)、P(3)分别表示“2是偶数”、“3是偶数”。“x小于y”可以用谓词Q(x，y)表示，Q(5，7)、Q(6，5)分别表示“5小于7”、“6小于5”。“x在y和z之间”可以用谓词R(x,y,z)表示，R(a,b,c)表示“a在b和c之间”。

设有谓词P(x1,x2…,xn)，D1，D2，…，Dn是个体域集合，其中x1∈D1，x2∈D2，…，xn∈Dn。n元谓词P(x1,x2,…,xn)是从D1×D2×…×Dn到集合{T，F}上的一个n元函数，因此，也把P(x1,x2…,xn)称做n

元命题函数,如图2.1.1所示。图2.1.1有时关系符直接采用特殊的习惯符号，如=、≠、<、>、≤、≥、、等，其表达方式也可采用中缀表示法，如x≤y、x≠y等。

谓词也可以用前面介绍的联结词进行组合，这里联结词的意义与命题逻辑完全相同。例如，S(x)表示“x是学习委员”，W(x)表示“x是离散数学课代表”，则S(x)∧W(x)表示“x既是学习委员又是离散数学课代表”。

从谓词的定义可以看出，谓词P(x1,x2…,xn)仅是一个函数，因此它没有真假值。若将谓词符P指定一个确定的n元关系，每个个体变元均代入相应个体域中确定的个体常元，则得到一个具有确定真假值的命题。2.1.2量词

使用2.1.1节所讲的谓词还不能很好地表达日常生活中的所有命题，如“所有的人都要呼吸”、“有些有理数是自然数”等。为了刻画这类表示全称判断或特称判断的命题，需要引入量词(quantifier)。

1.全称量词

x表示“对于所有的x”、“对于任一x”或“对于每一个x”，这里符号称为全称量词(universalquantifier)，x是量词的作用变元(指导变元)。

2.存在量词

x表示“存在某个x”或“至少有一个x”，这里符号称为存在量词(existentialquantifier)，x是量词的作用变元(指导变元)。

在谓词P(x)或Q(x,y)等前面加上全称量词或者存在量词，称个体变元x被全称量化或存在量化。对于一个谓词，如果为谓词符指定具体含义，为每个个体变元指定论域，则谓词中的所有变元都被量词量化，则该命题成为一个具有真假值的命题。如果论域是全总个体域，则(a)“所有的人都是要死的”实际上等价于“对于一切x，如果x是人，那么x是要死的”，各概念间的关系如图2.1.3所示，应该表示为x(H(x)→

D(x))，而不能表示为x(H(x)∧D(x)),(b)“有些人不怕死”实际上等价于“存在一些x，x是人，并且x不怕死”，各概念间的关系如图2.1.3所示，应该表示为x(H(x)∧F(x))，而不能表示为x(H(x)→F(x))。图2.1.2图2.1.3以上例子中的H(x)是特性谓词，用以刻画论述个体是“人”这一特性。特性谓词的作用是限定论域为一个满足该谓词的所有个体构成的一个特定的论域。例如，例4中特性谓词H(x)的作用如图2.1.4所示。图2.1.4把特性谓词加入到公式时，有以下两条规则：

规则1：对于全称量词，特性谓词作为条件式的前件加入；

规则2：对于存在量词，特性谓词作为合取式的合取项加入。

定义2.2.1

谓词逻辑的合式公式(简称谓词公式)可由下述步骤生成：

(ⅰ)原子公式是谓词公式。

(ⅱ)如果A和B是谓词公式，则A、(A∧B)、(A∨B)、(A→B)、(A

B)是谓词公式。

(ⅲ)如果A是谓词公式，并且A中有未被量化的个体变元x，则xA(x)和xA(x)是谓词公式。2.2谓词公式

(ⅳ)只有有限次应用步骤(ⅰ)、(ⅱ)和(ⅲ)所得到的公式才是谓词公式。

由上述定义可知，任何一个命题公式都是谓词公式。书写谓词公式时，规定与命题逻辑相同，可以将最外层的括号略去，但紧跟量词后面的括号不能略去。

需要注意条款(ⅲ)的适用条件，例如，由xP(x,y)可以生成y

xP(x,y)，但是不能生成x

yP(x,y)。

定义2.2.2

若B是谓词公式A的一个连续段且B也是谓词公式，则称B是A的一个子公式。

在例1中，F(x)、B(y)、G(y,x)、(B(y)∧G(y,x))、

y(B(y)∧G(y,x))、(F(x)→

y(B(y)∧G(y,x)))、x(F(x)→

y(B(y)∧G(y,x)))等均为x(F(x)→

y(B(y)∧G(y,x)))的子公式。

下面举例说明如何用谓词公式表示自然语言表达的命题。约束变元的换名规则如下：

(1)对某个约束变元换名时，需对量词的作用变元以及该量词辖域内所有受该量词约束的约束变元一起换名。

(2)换名后的变元符号应是量词辖域内未出现的符号，最好是整个公式中未出现的符号。2.3.1谓词公式的赋值

谓词公式中通常包括谓词符、个体变元、个体常元、命题变元和联结词。2.3谓词演算的永真公式

定义2.3.1

对于一个谓词公式，若给它指定一个个体域E，再给所有谓词符均指派出确定的关系(具体的特性或关系)，给所有命题变元指派出确定命题(或者指定T或F)，并为所有自由变元分别指派E上确定的个体，则称为对谓词公式的一个赋值(指派或结识)。

谓词公式经过赋值之后就变成了具有确定真值的命题。

定义2.3.2

设A是谓词公式，如果对于特定论域E上的任何赋值，A的真值都为真，则称谓词公式A在E上永真；如果对于特定论域E上的任何赋值，A的真值都为假，则称谓词公式A在E上永假；若特定论域E上存在一种赋值，使得A的真值都为真，则称谓词公式A在E上可满足。

定义2.3.3

设A是谓词公式，如果对于任何赋值，A的真值都为真，则称谓词公式A是永真式；如果对于任何赋值，A的真值都为假，则称谓词公式A是永假式；若存在一种赋值，使得A的真值为真，则称谓词公式A是可满足式。

由定义可知，对于任意谓词公式A，若A是永真式，则A在特定论域E上永真；若A是永假式，则A在特定论域E上永假；若A在特定论域E上可满足，则A是可满足式。

构造谓词公式P(x)∧

xP(x)的真值表，见表2.3.1。表2.3.1

定义2.3.4

给定任意两个谓词公式A和B，若对于任何赋值，A和B的真值均相同，则称谓词公式A和B等价，记为A

B。

定义2.3.5

给定任意两个谓词公式A和B，若A→B是永真式，则称A蕴含B，记为A

B。

类似于命题逻辑，对于谓词公式A、B、C，有如下结论：

(1)A

B当且仅当A

B是重言式；

(2)A

B当且仅当A

B且B

A；

(3)A

B且B

C，则A

C；

(4)A

B且B

C，则A

C。2.3.2谓词演算的基本永真式

1.命题逻辑的等价式和蕴含式在谓词逻辑中的推广应用

对于命题逻辑中的任一等价公式(蕴含式)，对其应用代入规则，即用谓词逻辑的任意公式代入命题逻辑等价公式(蕴含式)的某个命题变元，所得结果是谓词逻辑的一个等价公式(蕴含式)。

2.量词的否定律

(1)

(2)

证明

(1)设论域为D，t是任一赋值。如果t使得

xP(x)为真，则t使得xP(x)为假，即存在个体a∈D，使得P(a)为假，从而有P(a)为真，故有x

P(x)为真。如果t使得xP(x)为假，则t使得xP(x)为真，即对于任一个体a∈D，均有P(a)为真，从而有P(a)为假，故有

x

P(x)为假。综上所述，xP(x)

x

P(x)成立。这里再给出等价公式xP(x)

x

P(x)在一个有限论域上的证明。设有限论域D={a1,a2,…,an}，则有

同理可证(2)。

证毕

3.量词辖域的扩张与收缩律

证明(5)

证毕

其他留作练习。

4.量词的分配律

证明

(1)设t是谓词公式x(P(x)∧Q(x))的任一赋值,其论域为D。

如果t使得x(P(x)∧Q(x))为真，则对于任一个体a∈D，使得P(a)∧Q(a)为真，即P(a)和Q(a)的真值均为真,从而有xP(x)和xQ(x)均为真，即xP(x)∧

xQ(x)为真。

如果t使得x(P(x)∧Q(x))为假，则存在个体a∈D，使得P(a)∧Q(a)为假，即P(a)或Q(a)的真值为假,从而有xP(x)或xQ(x)为假，即xP(x)∧

xQ(x)为假。

综上所述，x(P(x)∧Q(x))

xP(x)∧

xQ(x)成立。

(5)任给一个赋值t，设其个体域为D。

假设在t下，x(P(x)→

xQ(x)的真值为F，则xP(x)为T，xQ(x)为F。由xQ(x)为F，得到存在a∈D，使得Q(a)为F，又因为xP(x)为T，有P(a)为T,从而推出P(a)→Q(a)为F，即x(P(x)→Q(x))为F。由否定后件法得到，x(P(x)→

Q(x))

xP(x)→

xQ(x)。

(8)

xP(x)→

xQ(x)

xP(x)∨

xQ(x)

x

P(x)∨

xQ(x)

x(

P(x)∨Q(x))

x(P(x)→Q(x))

5.多重量词律

对于多个量词的情况，量词出现的先后次序不能随意调换。为了便于说明，这里只讨论两个量词的情况，其他量词的使用方法与此类似。

若设P(x,y)表示x和y是同乡，x的论域为一班学生，y的论域为二班学生,则x

yP(x,y)表示“一班每个学生和二班每个学生都是同乡”，y

xP(x,y)表示“二班每个学生和一班每个学生都是同乡”，二者都表示“一班和二班所有的学生都是同乡”，含义相同,所以x

yP(x,y)

y

xP(x,y)。

x

yP(x,y)表示“一班的某些学生和二班的某些学生是同乡”，例如，一班的小明和二班的小强是同乡，也可以说“二班的某些学生和一班的某些学生是同乡”，即y

xP(x,y)，所以x

yP(x,y)

y

xP(x,y)。

x

yP(x,y)表示“对于一班任意学生，二班至少有一个学生和他是同乡”，y

xP(x,y)则表示“二班存在某个学生，和一班所有学生是同乡”。显然，二者的含义是不同的，如果后者为真，则前者也为真，即y

xP(x,y)

x

yP(x,y),但是如果前者为真，后者不一定为真，即x

yP(x,y)

y

xP(x,y)，所以二者不等价。对于二元谓词前置量词，可以有以下8个等价公式和蕴含公式。其关系如图2.3.1所示。

(1)

x

yP(x,y)

y

xP(x,y)。

(2)

x

yP(x,y)

y

xP(x,y)。

(3)

y

xP(x,y)

x

yP(x,y)。

(4)

x

yP(x,y)

y

xP(x,y)。

(5)

y

xP(x,y)

x

yP(x,y)。

(6)

x

yP(x,y)

y

xP(x,y)。

(7)

y

xP(x,y)

x

yP(x,y)。

(8)

x

yP(x,y)

y

xP(x,y)。

图2.3.1谓词逻辑中常用的等价公式和蕴含公式如表2.3.2所示，此表是表1.3.3和表1.3.7的扩充。表2.3.2类似于命题逻辑关于推理的基本概念，在谓词逻辑中，设H1,H2,…,Hn,C是谓词公式，若H1∧H2∧…∧Hn

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

2.4谓词逻辑的推理理论谓词逻辑的推理方法可以看做是命题逻辑推理方法的扩充。命题逻辑的推理规则，如P规则、T规则和CP规则，以及证明方法在谓词逻辑中同样适用。但是在谓词逻辑中，某些前提和结论可能是带量词约束的，在推理过程中有时需要消去或引入量词。下面介绍消去和引入量词的四种常用推理规则。

(1)存在指定规则(existentialspecification)，简记为ES。

(2)全称指定规则(universalspecification)，简记为US。

如果xP(x)为真，那么x的论域的每个确定个体a必然满足P(a)的真值为真，故全称指定规则也可以指定到确定的个体常元,即

(3)存在推广规则(existentialgeneralization)，简记为EG。

(4)全称推广规则(universalgeneralization)，简记为UG。

3.1集合的概念与表示

3.2集合的基本运算

*3.3容斥原理

3.4归纳证明

3.5集合的笛卡儿积

3.6二元关系

3.7集合上的二元关系及其特性

3.8关系的闭包运算

3.9等价关系

3.10序关系第3章集合与关系集合是一个原概念，很难严格定义，只能对它给予直观描述。所谓集合，就是若干(有穷或者无穷多)个具有某种共同性质的事物的全体。组成集合的单个事物称为该集合的元素(element)，或称为成员(member)。3.1集合的概念与表示

1.列举法

列举法是将集合中的元素在一对大括号“{}”中一一列举出来。例如，A={a，b，c}表示集合A由a、b、c三个元素组成。又如，D={0，1，2,…，99}表示集合D由前100个自然数组成。当集合中的元素较多且有一定规律时，为了避免书写麻烦,可以先列出集合中的一些元素，用省略号表示其他元素，如果是有限集合还要在最后列举出末尾元素。

需要注意的是，如果没有特别说明，集合中的元素不能重复列举且元素间无次序之分。

2.描述法

描述法使用自然语言或谓词描述集合中元素的共同特征。例如，A={x|x是中国的省份}，B={y|y=a或y=b}。当用谓词描述集合中元素的共同特征时，集合的表示形式为S={x|P(x)}，其中P(x)是一元谓词，对于变元x的论域D中的任一个体a，如果P(a)为真，那么a∈S，否则a∈S。

3.归纳定义法

外延性公理两个集合A、B相等，记为A=B，当且仅当它们有相同的元素。用与其等价的谓词公式可表示为

A=B

x(x∈A

x∈B)

若两个集合A和B不相等，通常记为A≠B。除相等关系外，包含也是集合间常见的一种关系。

定义3.1.1

设A、B是任意的两个集合，若集合A的每个元素都是集合B的元素，则称A为B的子集(subset)或称B包含A，记为A

B或B

A，用逻辑公式表示为

A

B

x(x∈A→x∈B)

如果集合A不是集合B的子集，通常记为A

B。

⊆⊇⊆⊆

定义3.1.2

如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集(propersubset)，记为A

B，用逻辑公式表示为

A

B

x(x∈A→x∈B)∧

y(y∈B∧y∈A)

(A

B)∧(A≠B)

通常在研究和讨论问题时，所涉及的事物或者对象总限定在一定范围内，为了方便起见，有必要引入两种特殊的集合：全集和空集。⊂

⊂

⊆

定义3.1.3

在一定范围内所有事物组成的集合称为该范围内的全集(universalset)，记为U，用逻辑公式表示为

U={x|P(x)∨

P(x)}

其中，P(x)是任意的谓词。

全集由所讨论的事物范围确定。如在讨论实数时，全体实数组成全集U=R，此时所提到的任一集合A必须是U的子集，而不能是{a，b，c}、{老虎，灯泡}等。又如，在初等数论中，全体整数组成全集U=Z。

定义3.1.4

不含任何元素的集合称为空集(emptyset)，记为，用逻辑公式表示为

={x|P(x)∧

P(x)}

其中，P(x)是任意的谓词。根据空集的定义，显然有|

|=0。

定理3.1.1

空集是任一集合的子集且是任何非空集合的真子集。

证明任取集合A，由于对任意的元素x，x∈恒为假，则有x(x∈

→x∈A)为真，故有A成立。

若A不为空集，则存在元素

a∈A且a∈，故有A。证毕∅∅∅∅⊆∅∅∅∅⊂

定理3.1.2

设A、B、C是集合，若A

B且B

C，则A

C。

证明任取x∈A

，因为A

B，所以x∈B。又因为B

C，所以有x∈C。故有A

C。

证毕

定理3.1.3

集合A和集合B相等的充分必要条件是A和B互为子集。

证明⊆⊆⊆⊆⊆⊆

推论对于任意集合A，均有A

A。

定理3.1.4

空集是唯一的。

证明设有两个空集和′，根据定理3.1.1，有′且′，再根据定理3.1.3，故′=。

证毕

⊆∅∅∅∅⊆∅∅∅文氏图(Venndiagram)是一种可以直观地表示集合之间关系的图形化工具，它是英国数学家约翰·韦恩(JohnVenn)于1881年首先发明的。在文氏图中，用矩形表示全集U，在表示全集的矩形内部用圆、椭圆或其他几何图形表示集合，在表示集合的图形内部用点来表示集合中的元素。例如，图3.1.1表示了全集U的一个子集A和两个元素x和y，其中x画在集合A的椭圆内部，这表示元素x属于集合A，而y画在集合A的椭圆外部，这表示元素y属于U而不属于集合A。图3.1.1文氏图示意又如，图3.1.2所示的文氏图显示了集合A与集合B的四种不同关系。其中，图(a)表示集合A和B相等，图(b)表示集合B是A的真子集，图(c)表示集合A和B不等且交集不为空集，图(d)表示A和B的交集为空集。图3.1.2

定义3.1.5

给定集合A，以A的所有子集为元素组成的集合称为集合A的幂集(powerset)，记为ρ(A)。

1.集合的交

定义3.2.1

对于任意两个集合A和B，由所有属于集合A且属于集合B的元素组成的集合称为A和B的交集(intersection)，记为A∩B。

A∩B={x|x∈A∧x∈B}

集合交运算的文氏图表示如图3.2.1所示。3.2集合的基本运算图3.2.1

2.集合的并

定义3.2.2

对于任意两个集合A和B，由所有属于集合A或属于集合B的元素组成的集合称为A和B的并集(union)，记为A∪B。

A∪B={x|x∈A∨x∈B}

集合并运算的文氏图表示如图3.2.2所示。图3.2.2

3.集合的补

定义3.2.3

对于任意两个集合A和B，由所有属于集合A而不属于集合B的元素组成的集合称为集合B在A中的相对补集(complementofBwithrespecttoA)，记为A－B。

A－B={x|x∈A∧x∈B}

A－B也称为集合A与B的差。集合差运算的文氏图表示如图3.2.3所示。图3.2.3

定义3.2.4

如果U是包含集合A的全集，则属于U而不属于A的元素组成的集合称为集合A的补(complementofA)，记为。

=U－A={x|x∈U∧x∈A}

集合A的补集是集合A相对于全集U的补，也称A的绝对补。集合绝对补运算的文氏图表示如图3.2.4所示。图3.2.4

4.集合的对称差

定义3.2.5

对于任意两个集合A和B，由属于集合A而不属于集合B以及属于集合B而不属于集合A的所有元素组成的集合称为集合A与B的对称差(symmetricdifference)，记为A

B。

A

B=(A－B)∪(B－A)={x|(x∈A∧x∈B)∨(x∈B∧x∈A)}

集合对称差运算的文氏图表示如图3.2.5所示。图3.2.5

5.集合的环积

定义3.2.6

对于任意两个集合A和B，由属于集合A且属于集合B，以及既不属于集合A又不属于集合B的所有元素组成的集合，称为集合A与B的环积，记为A

B。

A

B=

=

={x|(x∈A∧x∈B)∨(x∈A∧x∈B)}

集合的环积运算的文氏图表示如图3.2.6所示。图3.2.6以上定义的集合运算满足若干性质，表3.2.1给出了其中11条基本性质。表3.2.1

定理3.2.1

设A和B是全集U的任意子集，若A

B，则

(a)

;

(b)B－A=B∩

;

(c)(B－A)∪A=B。

证明

因为A

B，就有(B∪A)=B，所以(B－A)∪A=B。⊆

⊆

⊆

集合的运算可用于解决有限集合的计数问题。根据集合运算的定义，显然有以下各式成立。

(a)|A1∪A2|≤|A1|+|A2|。

(b)|A1∩A2|≤min(|A1|，|A2|)。

(c)|A1－A2|≥|A1|－|A2|。

(d)|A1

A2|=|A1|+|A2|－2|A1∩A2|。*3.3容斥原理

加法原理：如果A1，A2，…，An是n个两两互不相交的集合，那么这n个集合的并集的元素个数为这n个集合中的元素个数之和。

|A1∪A2∪…∪An|=|A1|+|A2|+…+|An|

定理3.3.1

设A1和A2是有限集合，其元素个数分别为|A1|和|A2|，则|A1∪A2|=|A1|+|A2|－|A1∩A2|。

证明(1)若A1∩A2=，即|A1∩A2|=0，则根据加法原理有

|A1∪A2|=|A1|+|A2|

这时显然公式成立。∅

(2)若A1∩A2≠，根据

(A1－A2)∪(A1∩A2)=A1

且

(A1－A2)∩(A1∩A2)=

可得

|A1|=|A1－A2|+|A1∩A2|

同理有

|A2|=|A2－A1|+|A1∩A2|

∅∅而A1∪A2可以表示A1－A2、A2－A1和A1∩A2这三个两两互不相交的集合的并集，所以有

|A1∪A2|=|A1－A2|+|A2－A1|+|A1∩A2|

=|A1|+|A2|－|A1∩A2|

证毕

定理3.3.1

也可以通过图3.3.1验证。图3.3.1例2以1开始或者以00结束的8位不同的二进制符号串有多少个？

以上计算公式可以用图3.3.2验证。图3.3.2

定理3.3.2(容斥原理)设A1，A2，…，An是有限集合，那么有

|A1∪A2∪…∪An|=

|Ai|－|Ai∩Aj|

+

|Ai∩Aj∩Ak|－…+(－1)n+1|A1∩A2∩…∩An|

证明用数学归纳法。

(1)当n=2时，结论成立，即

|A1∪A2|=|A1|+|A2|－|A1∩A2|

(2)假设当n=k－1(k≥3)时结论成立。

(3)现证明当n=k时结论也成立。

证毕3.4.1集合的归纳定义

有些集合很难用3.1节中所介绍的列举法和描述法进行定义，如命题合式公式集合、C语言程序集合等。为此，这里再介绍另一种

定义集合的方法——归纳定义(inductivedefinition)。

一个集合S的归纳定义由三部分组成：

(1)基础条款：指出某些事物属于S，其功能是给集合S指定初始元素，使得定义的集合S非空。3.4归纳证明

(2)归纳条款：指出由集合S中的已有元素构造新元素的方法。归纳条款的形式总是断言：如果事物x，y，…是集合S中的元素，那么用某些方法组合它们所得的新元素也在集合S中。它的功能是给出从已知元素构造其他元素的规则。

(3)极小性条款：断言一个事物除非能有限次应用基础条款和归纳条款构成，否则它不在集合S中。

集合归纳定义的极小性条款还有其他一些常见的形式，例如，“集合S是满足基础条款和归纳条款的最小集合”，“若T是S的子集，T又满足基础条款和归纳条款，那么T=S”。这些极小性条款虽然形式不同，但都指明了所定义的集合是满足基础条款和归纳条款的最小集合，即所谓的极小性。3.4.2自然数集合

自然数集合N被广泛运用，但是要给出一个严格的定义是比较困难的。这里介绍美国数学家约翰·冯·诺依曼(JohnVonNeumann)的定义方法，他巧妙地采用空集和后继集合的概念找到了自然数集合的一个构造。

设A是任意集合，A的后继集合记为A′，定义A′=

A∪{A}。自然数集合N可进行以下归纳定义：

(1)(基础)

∈N；∅

(2)(归纳)如果A∈N，那么A′∈N；

(3)(极小性)如果S

N且满足条款(1)和(2)，那么S=N。自然数集合可以直观地表示为以为起点，另一端无限延伸的一条链，其结构如图3.4.1所示。习惯上，将自然数集合的最小元素用0标记，0的后继集合{

}用1标记，1的后继集合{，{

}}用2标记，以此类推，从而产生了人们所熟悉的自然数集合N={0,1,2,3，…}。进一步，可以在N上定义各种运算。例如，对于加法运算，任取n∈N，n+1=n′。

⊆∅∅∅∅∅图3.4.13.4.3归纳法

对于形如(

x)P(x)的命题，如果其论域是归纳定义的集合，则用归纳法往往是较为有效的证明方法。

归纳法证明的一般步骤如下：

(1)基础步骤。对于基础条款中指定的每个初始元素t，证明命题P(t)为真。

(2)归纳步骤。证明如果事物x，y，…有P性质，那么用归纳条款指定的方法组合它们所得的新元素也具有P性质。3.4.4数学归纳法

数学归纳法(mathematicalinduction)被广泛地用来证明形如xP(x)的命题，其中x的论域常常是自然数集、正整数集等，例如，用来证明算法的复杂度，计算机程序的正确性，关于图和树等离散结构满足的等式或不等式。数学归纳法的有效性源于自然数集的归纳定义。

下面分别介绍数学归纳法第一原理和数学归纳法第二原理。

数学归纳法第一原理其实是自然数集合N上的一个推理规则，其形式如下：

为了证明n(P(n)→P(n+1))，根据谓词逻辑中的全称推广规则，只需任取n证明P(n)→P(n+1)成立即可，当然n必须是任意选取的。

用数学归纳法第一原理进行证明的