2015离散数学谓词量词、变元的约束、翻译

1、谓词和量词,Predicates and Quantifiers,所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。,Three tasks: 1. 谓词、个体词、量词 2. 谓词公式 3. Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in our class and second , l

2、et it consist of all people. a) Everyone in our class has a mobile phone. b) Somebody in our class has seen a foreign movie. c) All students in our class can solve quadratic equations. d) Some student in our class does not want to be rich.,(1) 是无理数 . (2) x是有理数. (3) 小王与小李同岁. (4) x 与y具有同学关系.,个体词the su

3、bject,个体词是指所研究对象中可以独立存在的具体的或抽象的客体。 将表示具体或特定的客体的个体词称作个体常项，一般用a,b,c,表示。将表示抽象或泛指的个体词称为个体变项，用x,y,z表示。,Predicate,谓词是用来刻画个体词性质及个体词之间相互关系的词。 The statement “x is greater than 3” has two parts. The first part, the variable x, is the subject of the statement. The second partthe predicate, “is greater than 3”r

4、efers to a property that the subject of the statement can have. We can denote the statement “x is greater than 3” by P(x). where P denotes the predicate “is greater than 3” and x is the variable. The statement P(x) is also said to be the value of the propositional function P at x. Once a value has b

5、een assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.,Domain of discourse论域,个体变项的取值范围为个体域（或称论域）。有一个特殊的个体域，它是由宇宙间一切事物组成的，称为全总个体域。 Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domai

6、n of discourse (or the universe of discourse), often just referred to as the domain. Note that the domain specifies the possible values of the variable x.,(1) 是无理数 . (2) x是有理数. (3) 小王与小李同岁. (4) x 与y具有同学关系.,(1) 凡人都呼吸 . (2) 所有的人都长着黑头发. (3) 兔子比乌龟跑得快. (4) 在美国留学的学生未必都是亚洲人.,Universal Quantifier,The univer

7、sal quantification of P(x) is the statement The notation xP(x) denotes the universal quantification of P(x). Here is called the universal quantifier. Note that the domain specifies the possible values of the variable x. The meaning of the universal quantification of P(x) changes when we change the d

8、omain. The domain must always be specified when a universal quantifier is used; without it, the universal quantification of a statement is not defined. the key word：所有的、一切的、每一个、任意的、 凡、都,“P(x) for all values of x in the domain.”,(1) 有的人登上过月球 . (2) 有的人用左手写字. (3) 不存在比所有火车都快的汽车. (4) 存在x,使得x+5=3.,Existen

9、tial quantifier,Many mathematical statements assert that there is an element with a certain property. Such statements are expressed using existential quantification. With existential quantification, we form a proposition that is true if and only if P(x) is true for at least one value of x in the dom

10、ain.,Existential quantifier,A domain must always be specified when a statement xP(x) is used. Furthermore, the meaning of xP(x) changes when the domain changes. Without specifying the domain, the statement xP(x) has no meaning. the key word:有的，存在，有一个，至少有一个，某个，某些,Truth value?,We read xP(x) as “for al

11、l xP(x)” or “for every xP(x).”An element for which P(x) is false is called a counterexample of xP(x).,谓词公式： (1) A(x1,x2,xn)称为原子谓词公式，原子谓词公式是谓词公式。 (2)若A是谓词公式，则(A)是一个谓词公式。 (3)若A和B都是谓词公式，则(AB),(AB),(AB)， (AB)和都是谓词公式。 (4)如果A是谓词公式,x是A中出现的任何变元,则(x)A,(x)A，和(!x)A都是谓词公式。 (5)只有经过有限次的应用规则(1),(2),(3),(4)所得到的公式是谓

12、词公式,例：说明以下各式的作用域与变元约束的情况.,定义1：约束变元 谓词公式中，后面所跟的x，称为相应量词的指导变元或作用变元或约束变元。 定义2：量词作用域（量词辖域） 给定谓词公式中，形式为(x)P(x)， (x) P(x)中的P(x)称为相应量词的作用域（辖域）。 定义3：自由变元 在谓词公式中，除去约束变元以外所出现的变元，称作自由变元。,Quantifiers,Quantifiers with restricted domain The part of a logical expression to which a quantifier is applied is called t

13、he scope of this quantifier. Consequently, a variable is free if it is outside the scope of all quantifiers in the formula that specify this variable.,Binding Variable,When a quantifier is used on the variable x, we say that this occurrence of the variable is bound. An occurrence of a variable that

14、is not bound by a quantifier or set equal to a particular value is said to be free. All variables in a propositional function P(x1,x2,xn) have to be bound to turn it into a proposition which is true or false,换名规则 （1）对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词辖域中出现的该变元，在公式的其余部分不变。 （2）换名是一定要更改为作用域中没有出现的变元名称。

15、,代入规则 （1）对于谓词公式中的自由变元，可以代入，代入时需对公式中出现该自由变元的每一处进行。 （2）用以代入的变元与原公式中所有变元的名称不能相同。,Remark: The quantifiers and have higher precedence than all logical operators from propositional calculus. For example, xP(x) Q(x) is the disjunction of xP(x) and Q(x). In other words, it means (xP(x) Q(x) rather than x(P(

16、x) Q(x).,b) Order of the quantification is important,c)谓词公式的解释 公式x(F(x)G(x) 解释1 个体域:全总个体域, F(x): x是人, G(x): x是黄种人 假命题 解释2 个体域:实数集, F(x): x10, G(x): x0 真命题,d)闭式 定义 设A是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式。 定理 闭式在任何解释下都是命题。 x(F(x) G(x) x(F(x)G(x) xy Q(x,y),例：将下列命题符号化，并分别讨论个体域限制为(a)有理数 ,(b) 实数时是命题的真值。 (1) 凡有理数都能被2整除 (2) 有的有理数能被2整除,例：将下列命题符号化，并分别讨论个体域限制为(a)自然数 ,(b) 实数 时是命题的真值。 (1) 对于任意的 ,均有 (2) 存在 ，使得,将下列命题符号化,（1）所有的人都长着黑头发 （2）有的人登上过