离散数学课件-第1章-3(修改).ppt

1,2019/1/20,离散数学 Discrete Mathematics,汪荣贵 教授 合肥工业大学软件学院专用课件 2010.3,CHAPTER 1 The Foundations: Logic, Sets, and Functions,学习内容,1.1 Logic 逻辑 1.2 Propositional Equivalences 命题等价 1.3 Predicates and Quantifiers 谓词和量词 1.4 Sets 集合 1.5 Set Operations 集合运算 1.6 Functions 函数 1.7 Sequence and Summations 序列与求和 1.8 The Growth of Functions 函数增长,谓词与量词,问题的提出与解决 客体、谓词与量词 谓词公式 命题的符号化 等价式与蕴含式,问题的提出,在命题逻辑中, 一个原子命题只用一个字母表示请看下面的例子 例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) 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 7” which is true.,〖Example 〗Let P(x) denote the statement “x 0.“ Is P(y)  P(0) a proposition? 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 对它进行定量 （由量词产生命题）,由量词产生命题,量 词,例如：有些人是大学生 所有事物都是发展变化的 “有些”,“所有的”,就是对客体量化的词 定义：命题中表示对客体数量化的词，称之为量词量词的种类,(1) 存在量词： 记作，表示“有些”、“一些”、“某些”、“至少一个”等 (2) 全称量词： 记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。

存在量词,Existential quantification 存在量化, 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 （存在量词）,存在量词,Existential quantifier,Assume that the universe of discourse is .  x P(x)=?,Solution:,In 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 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（论域为全体数）,全称量词,Universal quantification 全称量化, 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.,两种量词的区别与联系,由上可知，成立下面两式：,Negations of Quantifiers量词的否定,,Distributing a negation operator across a uantifier changes a universal to an existential and vice versa.,量词的否定,量词的否定,量词的指导变元,定义：量词后边要有一个客体变元，指明对哪个体变元量化，称此客体变元是量词后的指导变元。

例如： 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)、(AB)都是合式公式 4.如果A是合式公式，x是Ａ中的任何客体。