离散数学课件-第1章-3

12023/7/24离散数学DiscreteMathematics

汪荣贵教授合肥工业大学软件学院专用课件2010.3CHAPTER1

TheFoundations:Logic,Sets,andFunctions学习内容1.1Logic逻辑1.2PropositionalEquivalences

命题等价1.3PredicatesandQuantifiers谓词和量词

1.4Sets集合1.5SetOperations集合运算1.6Functions函数1.7

SequenceandSummations

序列与求和1.8

TheGrowthofFunctions函数增长谓词与量词问题的提出与解决客体、谓词与量词谓词公式命题的符号化等价式与蕴含式问题的提出在命题逻辑中,一个原子命题只用一个字母表示请看下面的例子。例1

令Ｐ：小张是大学生。Ｑ：小李是大学生。从符号Ｐ、Ｑ中不能归纳出他们都是大学生的共性。若要从所使用的符号那里得到更多的信息，比如归纳出他们的共性，则需要引进新的表示方法。问题的解决

令S(x)表示x是大学生，a:小张，b:小李。则：

S(a):小张是大学生；

S(b):小李是大学生。从符号S(a)、S(b)可看出“都是大学生”的共性。符号S(x)就是所谓的谓词——简单命题函数。含变量的语句含变量的语句，如：“x＞3”，“x=y+3”和“x+y=z”常见于数学断言与计算机程序，当变量值未知的时候，这些语句既不为真，也不为假。

如何从这些语句中产生命题？含变量的语句

语句“x＞3”由两个部分组成：第一部分是变量x，即语句的主语，第二部分为语句的谓词“大于3”，表示主语的一个性质。

可以用P(x)表示语句“x＞3”。其中P表示谓词“大于3”，x为变量。一旦给变量x赋值，P(x)就成为命题。〖Example〗

(1)xisgreaterthany.

P(x,y)(2)xisbetweenyandz.

B(x,y,z)Note:Propositionalfunctionhasnotadefinitetruthvalue.命题函数没有明确的真值

Onceavaluehasbeenassignedtothevariablex,P(x)becomesapropositionandhasatruthvalue.当变量x被赋予一个值时，P(x)

变为一个有真假值的命题

ThetruthvalueofP(x)canbedeterminedwhenxisassignedavalue.(Thevariablexisbound.)当x被指派一个值时，P(x)的真值就能确定了〖Example〗

LetP(x)denotethestatement"x>0."WhatarethetruthvaluesofP(-3),P(0)andP(3)?

〖Example〗

LetQ(x,y)denotethestatement“x<y”.Q(4,3)means“4<3”whichisfalse,Q(2,7)means“2<7”whichistrue.

〖Example〗LetP(x)denotethestatement"x>0."

Is

P(y)

P(0)

a

proposition?IsP(3)

P(0)aproposition?

谓词与量词问题的提出与解决客体、谓词与量词谓词公式命题的符号化等价式与蕴含式客体、谓词与量词客体与客体变元谓词与命题函数谓词的量化及量词客体与客体变元

定义：能够独立存在的事物，称为客体，也称为个体。它可以是具体的，也可以是抽象的。通常用小写英文字母a、b、c、...表示。例如，小张、小李、8、a、沈阳、社会主义等等都是客体。

客体与客体变元

定义：用小写英文字母x、y、z...表示任何客体，则称这些字母为客体变元。注意：客体变元本身不是客体。客体、谓词与量词客体与客体变元谓词与命题函数谓词的量化及量词谓词

定义：谓词用来描述个体的性质或个体间的关系，用大写字母后加括号表示，括号内为客体变元。如果括号内有n个客体变元，称该谓词为n元谓词。用P(x1,x2,…,xn)表示n元谓词。

谓词例如：

S(x):表示x是大学生。一元谓词

G(x,y)：表示x>y。二元谓词

B(x,y,z)：表示x在y与z之间。三元谓词

注意：S(x)、G(x,y)，B(x,y,z)表示的不是命题，而是命题函数。命题函数用P(x1,x2,…,xn)表示n元谓词。n元谓词也称简单命题函数，将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。简单命题函数与复合命题函数统称为命题函数。

命题函数

例如给定简单命题函数：

A(x)：x身体好，B(x)：x学习好，

C(x)：x工作好.则：复合命题函数

A(x)→(B(x)∧C(x))

表示如果x身体不好，则x的学习与工作都不会好定义：在命题函数中命题变元的取值范围，称之为论域，也称之为个体域。例如：S(x):x是大学生，论域是:人类。

G(x,y)：x>y，论域是:实数。定义：由所有客体构成的论域，称之为全总个体域。它是个“最大”的论域。约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。论域(个体域)客体、谓词与量词客体与客体变元谓词与命题函数谓词的量化及量词Therearetwowaystocreateapropositionfromapropositionalfunction:可以通过两种方式从命题函数中产生命题

1.assigningavaluetoeveryvariable对每个变量赋予值

2.quantifyingit对它进行定量（由量词产生命题）由量词产生命题量词例如：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。定义：命题中表示对客体数量化的词，称之为量词。量词的种类

(1)存在量词：

记作，表示“有些”、“一些”、“某些”、“至少一个”等。

(2)全称量词：

记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。存在量词Existentialquantification存在量化

x

P(x)----Thereexistsanelementxintheuniverseofdiscourse

suchthatP(x)istrue.（在论域中存在一个x使P(x)

的真值为真）

Forsomex

P(x);（对某个x,P(x)

）

ThereisanxsuchthatP(x);（有一个x使得P(x)

）

ThereisatleastonexsuchthatP(x);（至少有一个x使得P(x)

）

IcanfindanxsuchthatP(x).（我可以找出一个x使得P(x)

）

----existentialquantifier

（存在量词）存在量词ExistentialquantifierAssumethattheuniverseofdiscourseis.

x

P(x)=?

Solution:Ingeneral,theuniverseofdiscourseis.（当域中的所有元素可以列成{}时，存在量化

与析取是等价的）〖Example〗Expressthefollowingstatementasaexistentialquantification.Somerealnumbersarerationalnumbers.

（一些实数是有理数）Solution:Let

Q(y):yisarationalnumbersAssumingthattheuniverseofdiscourseisthesetofallrealnumbers.（论域为实数集合）(2)Assumingthattheuniverseofdiscourseisthesetofallnumbers.LetR(y):yisarealnumber（论域为全体数）

全称量词Universalquantification全称量化

x

P(x)----

P(x)istrueforallvaluesofxintheuniverseofdiscourse.（对论域中任意一个x而言，P(x)

的真值都为真。）

Forallx

P(x)Foreveryx

P(x)

----Universalquantifier

（全称量词）Solution:Assumethattheuniverseofdiscourseis.

x

P(x)=?

Ingeneral,theuniverseofdiscourseis.（当域中的所有元素可以列成{}时，量化语句与合取是等价的）〖Example〗Expressthefollowingstatementasauniversalquantification.Alllionsarefierce.

Solution:LetQ(x)denotethestatement“xisfierce”.

Assumingthattheuniverseofdiscourseisthesetofalllions.

(2)Assumingthattheuniverseofdiscourseisthesetofallcreatures.LetP(x)denotethestatement“xisalion”.两种量词的区别与联系StatementWhentrue?Whenfalse?xP(x)P(x)istrueforeveryx.ThereisanxforwhichP(x)isfalse.xP(x)ThereisanxforwhichP(x)istrue.P(x)isfalseforeveryx.由上可知，成立下面两式：NegationsofQuantifiers量词的否定

Distributinganegationoperatoracrossauantifierchangesauniversaltoanexistentialandviceversa.量词的否定量词的否定NegationEquivalentStatementWhenisNegationTrue?WhenFalse?x

P(x)x

P(x)P(x)isfalseforeveryxThereisanxforwhichP(x)istruex

P(x)xP(x)ThereisanxforwhichP(x)isfalseP(x)istrueforeveryx量词的指导变元定义：量词后边要有一个客体变元，指明对哪个体变元量化，称此客体变元是量词后的指导变元。

例如：

x(读作“任意x”)，x(读作“存在x”)，其中的x就是量词后的指导变元。例题例题１.所有的自然数都是整数。设N(x)：x是自然数。I(x)：x是整数。此命题可以写成x(N(x)→I(x))例题２.有些自然数是偶数。设E(x)：x是偶数。此命题可以写成x(N(x)∧E(x))例题3.每个人都有一个生母。设P(x):x是个人。M(x,y):y是x的生母。此命题可以写成x(P(x)→y(P(y)∧M(x,y)))谓词与量词问题的提出与解决客体、谓词与量词谓词公式命题的符号化等价式与蕴含式谓词公式谓词演算公式量词的辖域约束变元与自由变元约束变元的改名原子谓词公式n元谓词P(x1,x2,...,xn)又称为原子谓词公式。例如P、Q(x)、A(x,f(x))、B(x,y,a)都是原子谓词公式。谓词演算公式定义

谓词演算的合式公式递归定义如下：

1.原子谓词公式是合式公式。

2.如果A是合式公式，则A也是合式公式。3.如果A、B是合式公式，则(A∧B)、(A∨B)、(A→B)、(AB)都是合式公式。4.如果A是合式公式，x是Ａ中的任何客体变元，则xＡ和xＡ也是合式公式。

5.只有有限次应用规则(1)至(4)得到的才是合式公式。谓词演算公式如：

P、(P→Q)、(Q(x)∧P)、

x(A(x)→B(x))、xC(x)是谓词公式；而

xyP(x)、P(x)∧Q(x)x不是谓词公式谓词公式谓词演算公式量词的辖域约束变元与自由变元约束变元的改名量词的辖域

定义

在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。

例如

x((P(x)∧Q(x))→yR(x,y))中x的辖域是((P(x)∧Q(x))→yR(x,y)),y的辖域为R(x,y)。量词的辖域如果量词后边只是一个原子谓词公式时，其辖域为此原子谓词公式。如果量词后边是括号，其辖域为括号所表示的区域。紧挨着出现的多个量词，它们的辖域相同。谓词公式谓词演算公式量词的辖域约束变元与自由变元约束变元的改名约束变元与自由变元定义：如果客体变元x在x或者x的辖域内，则称x在此辖域内约束出现，并称x在此辖域内是约束变元。否则x为自由出现，并称x是自由变元。BindingVariables

在一个谓词公式中，变量的出现是绑定的，当且仅当有量词作用于它或者给它赋值时；变量的出现说是自由的，当且仅当它的出现不是绑定的。Boundvariable（绑定变量）:QuantifiedorassignedaspecificvalueFreevariable（自由变量）:NeitherquantifiednorassignedaspecificvalueBindingVariablesExample:

xP(x)：x是绑定变量

xQ(x,y)：x是绑定变量y是自由变量Scopeofquantifiers（量词的作用域）:PartofalogicalexpressiontowhichaquantifierisappliedExample:x(P(x)Q(x))xR(x)1.3PredicatesandQuantifiers约束变元与自由变元

例如，下面公式：x(F(x,y)→yP(y))∧Q(z)Ｆ(x,y)中的x在x的辖域内，受x约束，y不受x约束。

P(y)中的y在y的辖域内，受y约束。

Q(z)中的z不受量词约束。

约束变元与自由变元说明

(1)对约束变元用什么符号表示无关紧要。就是说xA(x)与yA(y)是一样的。(2)一个谓词公式如果无自由变元，它就表示一个命题。例如：A(x)表示x是个大学生。xA(x)或者xA(x)就是个命题了，因为它们分别表示命题“有些人是大学生”和“所有人都是大学生”。约束变元与自由变元

(3)一个n元谓词P(x1,x2,…,xn)，若在前边添加k个量词，使其中的k个客体变元变成约束变元，则此n元谓词就变成了n-k元谓词。

例如P(x,y,z)表示x+y=z，论域是整数集。

xyP(x,y,z)表示“？”（思考）如果令z=1，则xyP(x,y,1)就变成了命题可见给z指定整数a后，xyP(x,y,a)就变成了一个命题。所以谓词公式xyP(x,y,z)就相当于只含有客体变元z的一元谓词了。谓词公式谓词演算公式量词的辖域约束变元与自由变元约束变元的改名约束变元的改名在谓词公式中，如果某客体变元既以约束变元形式出现，又以自由变元形式出现。为避免混淆，可对此客体变元改名。如x(F(x,y)→yP(y))∧Q(z)约束变元的改名规则：(1)对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此客体变元出现的各处同时换名。(2)改名后用的客体变元名称，不能与该量词的辖域内的其它变元名称相同。约束变元的改名例如：x(P(x)→Q(x,y))∨(R(x)∧A(x))中的x以两种形式出现。可以对x改名成

z(P(z)→Q(z,y))∨(R(x)∧A(x))对自由变元也可以换名，此换名叫代入。

换名原则适用于代入。上例也可以对自由变元x作代入，改成：

x(P(x)→Q(x,y))∨(R(z)∧A(z))谓词与量词问题的提出与解决客体、谓词与量词谓词公式命题的符号化等价式与蕴含式TranslatingfromEnglishintoLogicalExpressionGoal:Toproducealogicalexpressionthatissimpleandcanbeeasilyusedinsubsequentreasoning.Steps:Clearlyidentifytheappropriatequantifier(s)

确定恰当的量词

Introducevariable(s)andpredicate(s)

引入变量和谓词

Translateusingquantifiers,predicates,andlogicaloperators

用量词，谓词，和逻辑操作来转化〖Example〗C(x):xisaCSstudent,E(x):xisanCMstudentS(x):xisasmartstudent,U={allstudentsinourclass}EveryoneisaCSstudent.xC(x)NobodyisanCMstudent.x

E(x)or

xE(x)AllCSstudentsaresmartstudents.x(C(x)S(x))SomeCSstudentsaresmartstudents.x(C(x)S(x))命题的符号化NoCSstudentisanCMstudent.IfxisaCSstudent,thenthatstudentisnotanCMstudent.x(C(x)

E(x))TheredoesnotexistaCSstudentwhoisalsoanCMstudent.

x[C(x)E(x)]IfanyCMstudentisasmartstudentthenheisalsoaCSstudent.x((E(x)S(x))C(x))命题的符号化命题的符号化

在谓词演算中，命题的符号表达式与论域有关系

当论域扩大时，需要添加谓词用来表示客体特性称此谓词为特性谓词。命题的符号化例如：

1.每个自然数都是整数。(1)如果论域是自然数集合N，令I(x)：x是整数，则命题表达式为xI(x)；(2)如果论域扩大为全总个体域，上述表达式xI(x)表示“所有客体都是整数”，显然是假命题。因此需要添加谓词N(x)：x是自然数，用于表明x的特性，这时命题的符号表达式为x(N(x)→I(x))。命题的符号化

2.有些大学生吸烟。(1)如果论域是大学生集合S，令A(x)：x吸烟，则命题的表达式为xA(x)；(2)如果论域为全总个体域，xA(x)表示“有些客体吸烟”，就不是此命题了。故需添加谓词S(x)：x是大学生，以表明x的特性，命题表达式为x(S(x)∧A(x))。特性谓词的添加方法特性谓词的添加方法如下：如果前边是全称量词，特性谓词后边是蕴含联结词“→”；如果前边是存在量词，特性谓词后边是合取联结词“∧”。特性谓词的添加依据添加依据：分析各概念之间的关系例1IN

I包含Nx(N(x)→I(x))SA吸烟大学生例2吸烟大学生是S与A的交集

x(S(x)∧A(x))命题符号化例题例1所有大学生都喜欢一些歌星。令S(x)：x是大学生，X(x)：x是歌星，

L(x,y)：x喜欢y。则命题的表达式为x(S(x)→y(X(y)∧L(x,y)))例2没有不犯错误的人。令P(x)：x是人，F(x)：x犯错误，此命题的表达式为

x(P(x)∧F(x))或者x(P(x)→F(x))命题符号化例题例3不是所有的自然数都是偶数。令N(x)：x是自然数，E(x)：x是偶数，则命题表达式为:x(N(x)→E(x))或者x(N(x)∧E(x))命题符号化例题例4如果一个人只是说谎话，那么他所说的每句话没有一句是可以相信的。令A(x)：x是人，B(x,y)：y是x说的话，

C(x):x是谎话，D(x)：x是可以相信的。命题的表达式为:x(A(x)→(y(B(x,y)→C(y))→z(B(x,z)∧D(z)))

或者x(A(x)→y((B(x,y)∧C(y))→D(y)))命题符号化小结1.命题的符号表达式形式与论域有关系。

论域扩大需要用特性谓词对客体进行说明.注意如何添加特性谓词。2.如果量词前有否定符号，如“没有...”“不是所有的...”等，可以按照字面直译。如“x…”“x...”命题符号化小结

3.命题的符号表达式中所有客体变元必须都是约束变元，才表示命题。有时给定命题中有些量词没有明确给出，要仔细分析并写出这些隐含量词。

例如：

a)金子闪光，但闪光的不一定都是金子。G(x),F(x)x(G(x)→F(x))∧x(F(x)→G(x))

b)没有大学生不懂外语。S(x),K(x,y),F(x)x(S(x)∧y(F(y)→K(x,y)))谓词与量词问题的提出与解决客体、谓词与量词谓词公式命题的符号化等价式与蕴含式等价式和蕴含式基本概念重要公式基本概念

定义：

将谓词公式中的命题变元，用确定的命题代替；对公式中的客体变元用论域中的客体代替，这个过程就称之为对谓词公式作指派，或者称之为对谓词公式赋值。谓词公式赋值基本概念

例如：公式P→N(x)，N(x)：x是自然数，论域为实数集合R。令P：2>1，x=4时，此公式变成P→N(4)，它的真值就是“真”。谓词公式赋值基本概念

定义：给定谓词公式A，E是其论域，如果不论对公式A作任何赋值，A的真值均为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式，则称A为永真式。谓词公式的永真式基本概念

例如：

I(x)：x是整数，论域E为自然数集合，公式I(x)在E上就是永真式。而公式I(x)∨I(x)就是与论域无关的永真式。谓词公式的永真式基本概念

定义：给定谓词公式A、B，E是它们的论域，如果不论对公式A、B作任何赋值，都使得A与B的真值相同(或者说AB是永真式)，则称公式A与B在论域E上等价。如果不论对什么论域E，都使得公式A与B等价，则称A与B等价，记作AB。谓词公式的等价基本概念

例如：

I(x)：表示x是整数，N(x)：表示x是自然数，假设论域E是自然数集合，公式I(x)与N(x)在E上等价。而公式N(x)→I(x)与N(x)∨I(x)就是与论域无关的等价的公式，即N(x)→I(x)N(x)∨I(x)。谓词公式的等价基本概念

定义：给定谓词公式A、B，E是它们的论域，如果不论对公式A、B作任何赋值，都使得A→B为永真式，则称在论域E上公式A永真蕴含B。如果不论对什么论域E，都使得公式A→B为永真式，则称A永真蕴含B，记作AB。谓词公式的永真蕴含基本概念

例如：

G(x)：表示x大于5，N(x)：表示x是自然数，论域E={-1,-2,6,7,8,9,....}，则：在E上公式G(x)→N(x)是永真式。而公式(G(x)∧N(x))→N(x)就是与论域无关的永真式，所以(G(x)∧N(x))N(x)。谓词公式的永真蕴含等价式和蕴含式基本概念重要公式重要公式推广命题公式可以得到谓词公式的一些永真式在命题演算的永真式中，将其中的同一个命题变元，用同一个谓词公式代替，所得到的公式也是永真式。重要公式推广命题公式可以得到谓词公式的一些永真式例如：A(x)A(x)∨B(x)PP∨Qx(A(x)→B(x))x(A(x)∨B(x))P→QP∨Q(xA(x)∧xB(x))xA(x)∨xB(x)摩根定律重要公式带量词的公式在论域内的展开式例如：令A(x)：x是整数，B(x)：x是奇数，论域是{1,2,3,4,5}，则有

xA(x)A(1)∧A(2)∧A(3)∧A(4)∧A(5)xB(x)B(1)∨B(2)∨B(3)∨B(4)∨B(5)重要公式带量词的公式在论域内的展开式结论：设论域为{a1,a2,....,an}，则1.xA(x)A(a1)∧A(a2)∧......∧A(an)2.xB(x)B(a1)∨B(a2)∨......∨B(an)重要公式量词否定公式可以看出：

“不是所有人都是优等生。”与“有些人不是优等生。”等价。“没有人是优等生。”与“所有人都不是优等生。”是等价的。重要公式量词否定公式例：令Ａ(x)表示x是优等生，论域是某班学生集。则：

xA(x)表示：不是所有人都是优等生。

xA(x)表示：有些人不是优等生。

xA(x)表示：没有人是优等生。

xA(x)表示：所有人都不是优等生。重要公式量词否定公式结论：

1.xA(x)xA(x)2.xA(x)xA(x)证明：设论域为{a1,a2,....,an}，则

xA(x)(A(a1)∧A(a2)∧...∧A(an))A(a1)∨A(a2)∨...∨A(an)xA(x)类似可以证明公式2。重要公式量词否定公式结论从公式1和2，可以总结出如下规律：将量词前的“”移到量词的后边，或将量词后的“”移到量词的前边时，量词也随着改变，即“”与“”互相替换。所以，称这两公式为量词转换公式。重要公式量词辖域的扩充公式

如果Ｂ是个不含客体变元x的谓词公式，且不在x和x的辖域内，可以将Ｂ放入x和x的辖域内。即有如下公式：1.