2015離散數(shù)學(xué)謂詞量詞、變元的約束、翻譯

1、謂詞和量詞,Predicates and Quantifiers,,所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。,Three tasks: 1. 謂詞、個體詞、量詞 2. 謂詞公式 3. Translate in two ways each of these statements into logical expressions using predicates, quantifiers, a

2、nd logical connectives. First, let the domain consist of the students in our class and second , let it consist of all people. a) Everyone in our class has a mobile phone. b) Somebody in our class has seen a foreign m

3、ovie. c) All students in our class can solve quadratic equations. d) Some student in our class does not want to be rich.,,(1) 是無理數(shù) .(2) x是有理數(shù).(3) 小王與小李同歲.(4) x 與y具有同學(xué)關(guān)系.,個體詞the subject,個體詞是指所研究對象中可以獨立存在的具體

4、的或抽象的客體。 將表示具體或特定的客體的個體詞稱作個體常項，一般用a,b,c,……表示。將表示抽象或泛指的個體詞稱為個體變項，用x,y,z……表示。,Predicate,謂詞是用來刻畫個體詞性質(zhì)及個體詞之間相互關(guān)系的詞。The statement “x is greater than 3” has two parts.The first part, the variable x, is the subject of the

5、 statement. The second part—the predicate, “is greater than 3”—refers 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

6、 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 been assigned to the variable x, the statement P(x) becomes a proposition an

7、d 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

8、domain 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) 是無理數(shù) .(2) x是有理數(shù).(3) 小王與小李同歲.(4) x 與y具有同學(xué)關(guān)系.,

9、,(1) 凡人都呼吸 .(2) 所有的人都長著黑頭發(fā).(3) 兔子比烏龜跑得快.(4) 在美國留學(xué)的學(xué)生未必都是亞洲人.,Universal Quantifier,The universal quantification of P(x) is the statementThe notation ?xP(x) denotes the universal quantification of P(x). Here ? is

10、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 domain. The domain must always be sp

11、ecified 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) 有

12、的人用左手寫字.(3) 不存在比所有火車都快的汽車.(4) 存在x,使得x+5=3.,Existential quantifier,Many mathematical statements assert that there is an element with a certain property. Such statements are expressed using existential quantification.

13、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 domain.,Existential quantifier,A domain must always be specified when a statement ?xP(

14、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 a

15、ll 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都是謂詞公式，則(A∧B),(A∨B),(A→B)， (A?B)和都是謂

16、詞公式。(4)如果A是謂詞公式,x是A中出現(xiàn)的任何變元,則(?x)A,(?x)A，和(?!x)A都是謂詞公式。(5)只有經(jīng)過有限次的應(yīng)用規(guī)則(1),(2),(3),(4)所得到的公式是謂詞公式,,例：說明以下各式的作用域與變元約束的情況.,定義1：約束變元謂詞公式中?，?，后面所跟的x，稱為相應(yīng)量詞的指導(dǎo)變元或作用變元或約束變元。定義2：量詞作用域（量詞轄域）給定謂詞公式中，形式為(?x)P(x)， (?x) P(x)中的P(

17、x)稱為相應(yīng)量詞的作用域（轄域）。定義3：自由變元在謂詞公式中，除去約束變元以外所出現(xiàn)的變元，稱作自由變元。,Quantifiers,Quantifiers with restricted domainThe part of a logical expression to which a quantifier is applied is called the scope of this quantifier. Consequent

18、ly, 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

19、 bound. An occurrence of a variable that 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 prop

20、osition which is true or false,,換名規(guī)則 （1）對于約束變元可以換名，其更改的變元名稱范圍是量詞中的指導(dǎo)變元，以及該量詞轄域中出現(xiàn)的該變元，在公式的其余部分不變。 （2）換名是一定要更改為作用域中沒有出現(xiàn)的變元名稱。,,代入規(guī)則 （1）對于謂詞公式中的自由變元，可以代入，代入時需對公式中出現(xiàn)該自由變元的每一處進(jìn)行。 （2）用以代入的變元與原公式中所有變元的名稱不能相同。,,Rem

21、ark: 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

22、) rather than ?x(P(x) ∨ Q(x)).,b) Order of the quantification is important,,c)謂詞公式的解釋公式?x(F(x)?G(x))解釋1 個體域:全總個體域, F(x): x是人, G(x): x是黃種人 假命題解釋2 個體域:實數(shù)集, F(x): x>10, G(x):

23、 x>0 真命題,d)閉式 定義 設(shè)A是任意的公式，若A中不含自由出現(xiàn)的個體變項，則稱A為封閉的公式，簡稱閉式。 定理 閉式在任何解釋下都是命題。 ?x(F(x) G(x)) ? x(F(x)∧G(x))

24、 ?x?y Q(x,y),,,例：將下列命題符號化，并分別討論個體域限制為(a)有理數(shù) ,(b) 實數(shù)時是命題的真值。 (1) 凡有理數(shù)都能被2整除 (2) 有的有理數(shù)能被2整除,,例：將下列命題符號化，并分別討論個體域限制為(a)自然數(shù) ,(b) 實數(shù) 時是命題的真值。 (1) 對于任意的 ,均有 (2) 存在 ，使得,將下列命題符號化,（1）所有的人

25、都長著黑頭發(fā)（2）有的人登上過月球（3）沒有人登上過木星（4）在美國留學(xué)的學(xué)生未必都是亞洲人,將下列命題符號化,（1）兔子比烏龜跑得快（2）有的兔子比烏龜跑得快（3）并不是所有的兔子都比烏龜跑得快（4）不存在跑得同樣快的兩只兔子,將下列命題符號化,（1）火車都比汽車快（2）有的火車比有的汽車快（3）不存在比所有火車都快的汽車（4）說凡是汽車就比火車慢是不對的,將下列命題符號化,（1）有的汽車比有的火車跑得快（2）有的