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

12024/7/14离散数学Discrete Mathematics CHAPTER 1 The Foundations:Logic,Sets,and Functions&学习内容学习内容1.1 Logic 1.1 Logic 逻辑逻辑逻辑逻辑1.2 1.2 Propositional EquivalencesPropositional Equivalences 命题等价命题等价命题等价命题等价1.3 Predicates and Quantifiers 1.3 Predicates and Quantifiers 谓词和量词谓词和量词谓词和量词谓词和量词 1.4 Sets 1.4 Sets 集合集合集合集合1.5 Set Operations 1.5 Set Operations 集合运算集合运算集合运算集合运算1.6 Functions 1.6 Functions 函数函数函数函数1.7 1.7 Sequence and SummationsSequence and Summations 序列与求和序列与求和序列与求和序列与求和1.81.8 The Growth of Functions The Growth of Functions 函数增长函数增长函数增长函数增长&谓词与量与量词问题的提出与解决问题的提出与解决客体、谓词与量词客体、谓词与量词谓词公式谓词公式命题的符号化命题的符号化等价式与蕴含式等价式与蕴含式&问题的提出的提出 在命题逻辑中,一个原子命题只用一个字母表示请看下面的例子。例1 令：小张是大学生。：小李是大学生。从符号、中不能归纳出他们都是大学生的共性。若要从所使用的符号那里得到更多的信息，比如归纳出他们的共性，则需要引进新的表示方法。&问题的解决的解决 令S(x)表示x是大学生，a:小张，b:小李。则：S(a):小张是大学生；S(b):小李是大学生。从符号S(a)、S(b)可看出“都是大学生”的共性。符号符号 S(x)S(x)就是所谓的谓词就是所谓的谓词简单命题函数简单命题函数。&含含变量的量的语句句&含含变量的量的语句句 Example (1)x is greater than y.P(x,y)(2)x is between y and z.B(x,y,z)Note:Propositional function has not a definite truth value.命题函数没有明确的真值命题函数没有明确的真值 Once a value has been assigned to the variable x,P(x)becomes a proposition and has a truth value.当变量当变量x被赋予一个值时，被赋予一个值时，P(x)变为一个有真假值的命题变为一个有真假值的命题 The truth value of P(x)can be determined when x is assigned a value.(The variable x is bound.)当当x被指派一个被指派一个值时，P(x)的真的真值就能确定了就能确定了Example Let P(x)denote the statement x 0.What are the truth values of P(-3),P(0)and P(3)?Example Let Q(x,y)denote the statement“x y”.Q(4,3)means“4 3”which is false,Q(2,7)means“2 0.(1)Is P(y)P(0)a proposition?(2)Is P(3)P(0)a proposition?&谓词与量与量词问题的提出与解决问题的提出与解决客体、谓词与量词客体、谓词与量词谓词公式谓词公式命题的符号化命题的符号化等价式与蕴含式等价式与蕴含式&客体、客体、谓词与量与量词客体与客体变元客体与客体变元谓词与命题函数谓词与命题函数谓词的量化及量词谓词的量化及量词&客体与客体客体与客体变元元 定义定义：能够独立存在的事物，称为客体，也称为个体。它可以是具体的，也可以是抽象的。通常用小写英文字母a、b、c、.表示。例如，小张、小李、8、a、沈阳、社会主义等等都是客体。&客体与客体客体与客体变元元 定义定义：用小写英文字母x、y、z.表示任何客体，则称这些字母为客体变元。注意：客体变元本身不是客体。&客体、客体、谓词与量与量词客体与客体变元客体与客体变元谓词与命题函数谓词与命题函数谓词的量化及量词谓词的量化及量词&谓 词 定义：定义：谓词用来描述个体的性质或个体间的关系，用大写字母后加括号表示，括号内为客体变元。如果括号内有n个客体变元，称该谓词为n元谓词。用 P(x1,x2,xn)表示n元谓词。&谓 词 例例例例 如：如：如：如：S(x):表示x是大学生。一元谓词 G(x,y)：表示 xy。二元谓词 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)：xy，论域是:实数。定义：定义：由所有客体构成的论域，称之为全总个体域。它是个“最大”的论域。约定约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。&论域域(个体域个体域)&客体、客体、谓词与量与量词客体与客体变元客体与客体变元谓词与命题函数谓词与命题函数谓词的量化及量词谓词的量化及量词 There are two ways to create a proposition from a propositional function:可以通过两种方式从命题函数中产生命题可以通过两种方式从命题函数中产生命题 1.assigning a value to every variable 对每个变量赋予值对每个变量赋予值 2.quantifying it 对它进行定量对它进行定量（由量词产生命题）（由量词产生命题）&由量由量词产生命生命题&量量 词&量量词的种的种类&存在量存在量词 x P(x)-There exists an element x in the universe of discourse such that P(x)is true.（在论域中存在一个（在论域中存在一个x使使P(x)的真值为真）的真值为真）For some x P(x);（对某个（对某个x,P(x)）There is an x such that P(x);（有一个（有一个x使得使得P(x)）There is at least one x such that P(x);（至少有一个（至少有一个x使得使得P(x)）I can find an x such that P(x).（我可以找出一个（我可以找出一个x使得使得P(x)）-existential quantifier（存在量词）（存在量词）&存在量存在量词Assume that the universe of discourse is .x P(x)=?Solution:uIn general,the universe of discourse is .（当当域中的所有元素可以列成域中的所有元素可以列成 时，存在量化时，存在量化 与析取与析取 是等价的）是等价的）Example Express the following statement as a existential quantification.Some real numbers are rational numbers.（一些（一些实数是有理数）数是有理数）Solution:Let Q(y):y is a rational numbers(1)Assuming that the universe of discourse is the set of all real numbers.（论域为实数集合）（论域为实数集合）(2)Assuming that the universe of discourse is the set of all numbers.Let R(y):y is a real number（论域为全体数论域为全体数）&全称量全称量词 x P(x)-P(x)is true for all values of x in the universe of discourse.（对论域中任意一个域中任意一个x而言，而言，P(x)的真的真值都都为真。真。）For all x P(x)For every x P(x)-Universal quantifier（全称量词）（全称量词）Solution:Assume that the universe of discourse is .x P(x)=?In general,the universe of discourse is .（当当域域中中的的所所有有元元素素可可以以列列成成 时时，量量化化语语句句 与与合取合取 是等价的）是等价的）Example Express the following statement as a universal quantification.All lions are fierce.Solution:Let Q(x)denote the statement“x is fierce”.(1)Assuming that the universe of discourse is the set of all lions.(2)Assuming that the universe of discourse is the set of all creatures.Let P(x)denote the statement“x is a lion”.&两种量两种量词的区的区别与与联系系StatementWhen true?When false?x P(x)P(x)is true for every x.There is an x for which P(x)is false.x P(x)There is an x for which P(x)is true.P(x)is false for every x.由上可知，成立下面两式：由上可知，成立下面两式：Negations of QuantifiersNegations of Quantifiers量词的否定量词的否定量词的否定量词的否定 Distributing a negation operator across a uantifier changes a universal to an existential and vice versa.&量量词的否定的否定&量量词的否定的否定NegationEquivalent StatementWhen is Negation True?When False?x P(x)x P(x)P(x)is false for every xThere is an x for which P(x)is truex P(x)x P(x)There is an x for which P(x)is falseP(x)is true for every x&量量词的指的指导变元元&例例 题&谓词与量与量词问题的提出与解决问题的提出与解决客体、谓词与量词客体、谓词与量词谓词公式谓词公式命题的符号化命题的符号化等价式与蕴含式等价式与蕴含式&谓词公式公式谓词演算公式谓词演算公式量词的辖域量词的辖域约束变元与自由变元约束变元与自由变元约束变元的改名约束变元的改名&原子原子谓词公式公式 n元谓词P(x1,x2,.,xn)又称为原子谓词公式。例如 P、Q(x)、A(x,f(x)、B(x,y,a)都是原子谓词公式。&谓词演算公式演算公式定义定义定义定义 谓词演算的合式公式递归定义如下：1.原子谓词公式是合式公式。2.如果A是合式公式，则A也是合式公式。3.如果A、B是合式公式，则(AB)、(AB)、(AB)、(AB)都是合式公式。4.如果A是合式公式，x是中的任何客体变元，则x和x也是合式公式。5.只有有限次应用规则(1)至(4)得到的才是合式公式。&谓词演算公式演算公式&谓词公式公式谓词演算公式谓词演算公式量词的辖域量词的辖域约束变元与自由变元约束变元与自由变元约束变元的改名约束变元的改名&量量词的的辖域域 定义定义 在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。例如 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是自由变元。Binding VariablesBinding Variables 在一个谓词公式中，变量的出现是绑定的，当且仅当在一个谓词公式中，变量的出现是绑定的，当且仅当有量词作用于它或者给它赋值时；变量的出现说是自由有量词作用于它或者给它赋值时；变量的出现说是自由的，当且仅当它的出现不是绑定的。的，当且仅当它的出现不是绑定的。Bound variable（绑定变量）（绑定变量）:Quantified or assigned a specific value Free variable（自由变量）（自由变量）:Neither quantified nor assigned a specific valueBinding Variables Example:x P(x)：x是是绑定绑定变量变量 x Q(x,y)：x是是绑定绑定变量变量y是自由变量是自由变量Scope of quantifiers（量词的作用域）（量词的作用域）:Part of a logical expression to which a quantifier is applied Example:x(P(x)Q(x)x R(x)1.3 Predicates and Quantifiers&约束束变元与自由元与自由变元元 例如，下面公式：x(F(x,y)yP(y)Q(z)(x,y)中的x在x的辖域内，受x约束，y不受x约束。P(y)中的y在y的辖域内，受y约束。Q(z)中的z不受量词约束。&约束束变元与自由元与自由变元元说明 (1)(1)对约束变元用什么符号表示无关紧要。对约束变元用什么符号表示无关紧要。就是说就是说 xA(x)xA(x)与与 yA(yyA(y)是一样的。是一样的。(2)(2)一个谓词公式如果无自由变元，它就表示一个谓词公式如果无自由变元，它就表示一个命题。一个命题。例如：例如：A(x)A(x)表示表示x x是个大学生。是个大学生。xA(x)xA(x)或者或者 xA(x)xA(x)就是个命题了，因为它们分别表示命题就是个命题了，因为它们分别表示命题“有些人是大学生有些人是大学生”和和“所有人都是大学生所有人都是大学生”。&约束束变元与自由元与自由变元元 (3)(3)一个一个n n元谓词元谓词P(xP(x1 1,x,x2 2,x xn n)，若在前边添，若在前边添加加k k个量词，使其中的个量词，使其中的 k k个客体变元变成约束变元，个客体变元变成约束变元，则此则此 n n元谓词就变成了元谓词就变成了n-kn-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)&谓词与量与量词问题的提出与解决问题的提出与解决客体、谓词与量词客体、谓词与量词谓词公式谓词公式命题的符号化命题的符号化等价式与蕴含式等价式与蕴含式Translating from English into Logical ExpressionTranslating from English into Logical ExpressionGoal:To produce a logical expression that is simple and can be easily used in subsequent reasoning.Steps:Clearly identify the appropriate quantifier(s)确定恰当的量词确定恰当的量词 Introduce variable(s)and predicate(s)引入变量和谓词引入变量和谓词 Translate using quantifiers,predicates,and logical operators 用量词，谓词，和逻辑操作来转化用量词，谓词，和逻辑操作来转化Example C(x):x is a CS student,E(x):x is an CM studentS(x):x is a smart student,U=all students in our class1)Everyone is a CS student.x C(x)2)Nobody is an CM student.x E(x)or x E(x)3)All CS students are smart students.x(C(x)S(x)4)Some CS students are smart students.x(C(x)S(x)&命命题的符号化的符号化5)No CS student is an CM student.If x is a CS student,then that student is not an CM student.x(C(x)E(x)There does not exist a CS student who is also an CM student.x C(x)E(x)6)If any CM student is a smart student then he is also a CS student.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)。&特性特性谓词的添加方法的添加方法特性谓词的添加方法如下：特性谓词的添加方法如下：如果前边是全称量词，特性谓词后如果前边是全称量词，特性谓词后边是蕴含联结词边是蕴含联结词“”；如果前边是存在量词，特性谓词后如果前边是存在量词，特性谓词后边是合取联结词边是合取联结词“”。&特性特性谓词的添加依据的添加依据添加依据：分析各概念之间的关系例例1 1IN I包含Nx(N(x)I(x)SA吸烟大学生例例2 2吸烟大学生是S与A的交集 x(S(x)A(x)&命命题符号化例符号化例题&命命题符号化例符号化例题&命命题符号化例符号化例题&命命题符号化小符号化小结&命命题符号化小符号化小结&谓词与量与量词问题的提出与解决问题的提出与解决客体、谓词与量词客体、谓词与量词谓词公式谓词公式命题的符号化命题的符号化等价式与蕴含式等价式与蕴含式&等价式和等价式和蕴含式含式基本概念基本概念重要公式重要公式&基本概念基本概念 定义：定义：定义：定义：将谓词公式中的命题变元，用确定的命题代替；对公式中的客体变元用论域中的客体代替，这个过程就称之为对谓词公式作指派，或者称之为对谓词公式赋值。&基本概念基本概念 例如：例如：公式 PN(x)，N(x)：x是自然数，论域为实数集合R。令P：21，x=4 时，此公式变成PN(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作任何赋值，都使得AB为永真式，则称在论域E上公式A永真蕴含B。如果不论对什么论域E，都使得公式AB为永真式，则称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)A(x)B(x)A(x)B(x)P PPQPQ x(A(x)B(x)x(A(x)B(x)x(x(A(x)B(x)A(x)B(x)PQPQP PQ Q(xA(x)xA(x)xB(x)xB(x)xA(x)xA(x)xB(xxB(x)摩根定律摩根定律&重要公式重要公式&重要公式重要公式&重要公式重要公式可以看出：“不是所有人都是优等生。”与“有些人不是优等生。”等价。“没有人是优等生。”与“所有人都不是优等生。”是等价的。&重要公式重要公式 例：例：令(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的辖域内。即有如下公式：&重要公式重要公式 如果是个不含客体变元x的谓词公式，且不在x和x的辖域内，可以将放入x和x的辖域内。即有如下公式：&重要公式重要公式证明：证明：证明：证明：设论域为设论域为a1,a2,.,an，xA(x)B(A(a1)A(a2).A(an)B(A(a1)B)(A(a2)B).(A(an)B)x(x)B xA(x)B xA(x)x(B A(x)x(BA(x)xA(x)BxA(x)Bx A(x)B x(A(x)B)x(A(x)B)使用公式使用公式7.、8.要注意，量词的辖域扩充后，量要注意，量词的辖域扩充后，量词发生了变化。词发生了变化。&重要公式重要公式1.x(A(x)B(x)xA(x)xB(x)2.x(A(x)B(x)xA(x)xB(x)3.x(A(x)B(x)xA(x)xB(x)4.xA(x)xB(x)x(A(x)B(x)证明：略证明：略&重要公式重要公式1.x(A(x)B(x)xA(x)xB(x)2.xA(x)xB(x)x(A(x)B(x)证明证明证明证明1 1 1 1：x xA(x)A(x)x xB(x)x xA(x)A(x)x xB(x)x x A(x)A(x)x xB(x)x(x(A(x)A(x)B(x)x(A(x)x(A(x)B(x)证明证明证明证明2 2 2 2：xA(x)xA(x)x xB(xB(x)xA(x)xA(x)x xB(x)x x A(x)A(x)x xB(x)x(x(A(x)A(x)B(x)x(x(A(x)A(x)B(x)&重要公式重要公式1.x yA(x,y)y xA(x,y)2.x yA(x,y)y xA(x,y)3.y xA(x,y)x yA(x,y)4.x yA(x,y)x yA(x,y)&重要公式重要公式5.y xA(x,y)x yA(x,y)6.x yA(x,y)y xA(x,y)7.y xA(x,y)x yA(x,y)8.x yA(x,y)y xA(x,y)注意：下面式子不成立注意：下面式子不成立 x yA(x,y)y xA(x,y)&重要公式重要公式为了便于记忆，用图形表示上面八个公式 x x yA(x,yyA(x,y)y y xA(x,y)xA(x,y)x x yA(x,yyA(x,y)y y xA(x,y)xA(x,y)x x yA(x,yyA(x,y)y y xA(x,y)xA(x,y)y y xA(x,y)xA(x,y)x x yA(x,yyA(x,y)本节内容到此结束本节内容到此结束