1、9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,1,基礎(chǔ)部分: 邏輯(Logic) 集合(Sets) 算法(Algorithms) 數(shù)論(Number Theory),9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,2,1.1.1 命題邏輯 Proposition Logic,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,3,邏輯學： 研究推理的一門學科 數(shù)理邏輯： 用數(shù)學方法研究推理的一門數(shù)學學科,- 一套符號體系 + 一組規(guī)則,9/24/2020 5:52 AM,

2、Deren Chen, ZheJiang Univ.,4,數(shù)理邏輯的內(nèi)容： 古典數(shù)理邏輯： 命題邏輯、謂詞邏輯 現(xiàn)代數(shù)理邏輯： 公理化集合論、遞歸論、模型論、證明論,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,5,Proposition: 一個有確定真或假意義的語句.,命題邏輯 Proposition Logic,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,6,EXAMPLE 1,All the following statements are propositions. 1. Washington,

3、D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1+1=2. 4. 2+2=3.,Propositions 1 and 3 are true, whereas 2 and 4 are false.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,7,EXAMPLE 2,Consider the following sentences. 1. What time is it? 2. Read this careful

4、ly. 3. x+1 =2. 4. x+y = z.,Sentences 1 and 2 are not propositions because they are not statements. Sentences 3 and 4 are not propositions because they are neither tree nor false, since the variables in these sentences have not been assigned values. Various ways to form propositions from sentences of

5、 this type will be discussed in Section 1.3.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,8,命題的語句形式 陳述句 非命題語句： 疑問句 命令句 感態(tài)句 非命題陳述句：悖論語句,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,9,命題的符號表示： 大小寫英文字母：P、Q、R、 p 、q 、r、。 命題真值（Truth Values）的表示： 真：T、1 假：F、0,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,10,命

6、題語句真值確定的幾點說明： 1、時間性 2、區(qū)域性 3、標準性 命題真值間的關(guān)系表示： 真值表（Truth Table),9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,11,DEFINITION 1.,Let p be a proposition. The statement It is not the case that p. is another proposition, called the negation of p. The negation of p is denoted by p. The proposition p is read n

7、ot p.,p的否定,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,12,EXAMPLE 3,Find the negation of the proposition Today is Friday and express this in simple English.,The negation is It is not the case that today is Friday. This negation can be more simply expressed by Today is not Friday.,9/24/2020 5:52 AM,

8、Deren Chen, ZheJiang Univ.,13,Table 1,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,14,DEFINITION 2.,Let p and q be propositions. The proposition p and q, denoted by pq, is the proposition that is true when both p and q are true and is false otherwise. The proposition pq is called the conjunction of

9、p and q. The truth table for pq is shown in Table 2.,p和q的合取,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,15,Table 2,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,16,EXAMPLE 4,Find the conjunction of the propositions p and q where p is the proposition Today is Friday and q is the proposition It is rai

10、ning today.,Solution: The conjunction of these propositions, pq, is the proposition Today is Friday and it is raining today. This proposition is true on rainy Fridays and is false on any day that is not a Friday and on Fridays when it does not rain.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,17,DE

11、FINITION 3.,Let p and q be propositions.The proposition p or q, denoted by pq,is the proposition that is false when p and q are both false and true otherwise. The proposition pq is called the disjunction of p and q. The truth table for pq is shown in Table 3.,p和q的析取,9/24/2020 5:52 AM,Deren Chen, Zhe

12、Jiang Univ.,18,Table 3,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,19,EXAMPLE 5,What is the disjunction of the propositions p and q where p and q are the same propositions as in Example 4?,Solution: The disjunction ofp and q, pq, is the proposition Today is Friday or it is raining today. This propo

13、sition is true on any day that is either a Friday or a rainy day (including rainy Fridays). It is only false on days that are not Fridays when it also does not rain.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,20,DEFINITION 4.,Let p and q be propositions.The exclusive or of p and q, denoted by p q,

14、is the proposition that is true when exactly one of p and q is true and is false otherwise. The truth table for the exclusive or of two propositions is displayed in Table 4.,p和q的對稱差,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,21,Table 4,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,22,DEFINITION 5.,

15、Let p and q be propositions.The implication pq is the proposition that is false when p is true and q is false and true otherwise. In this implication p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).,如果p,則q,單條件, 蘊涵 P:前提 Q:結(jié)論,9/24/2020 5:52 AM,Dere

16、n Chen, ZheJiang Univ.,23,Table 5,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,24,EXAMPLE 6,What is the value of the variable x after the statement if 2+2=4 then x := x+ 1 if x = 0 before this statement is encountered? (The symbol: = stands for assignment. The statement x: = x + 1 means the assignme

17、nt of the value of x + 1 to x.),Solution: Since 2 + 2 = 4 is true, the assignment statement x: = x + 1 is executed. Hence, x has the value 0+1=1 after this statement is encountered.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,25,EXAMPLE 7,Find the converse and the contrapositive of the implication

18、If today is Thursday, then I have a test today.,Solution: The converse is If I have a test today, then today is Thursday. And the contrapositive of this implication is If I do not have a test today, then today is not Thursday.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,26,DEFINITION 6.,Let p and q

19、 be propositions, The biconditional p q is the proposition that is true when p and q have the same truth values and is false otherwise. The truth table for p q is shown in Table 6.,P當且僅當q,雙條件，等價,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,27,Table 6,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,28,E

20、XAMPLE 8,How can the following English sentence be translated into a logical expression? You can access the Internet from campus only if you are a computer science major or you are not a freshman,Solution: a (c f ).,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,29,EXAMPLE 9,How can the following Engl

21、ish sentence be translated into a logical expression? You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.,Solution: (r s) q.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,30,EXAMPLE 10,說離散數(shù)學是枯燥無味的或毫無價值的，那是不對的。 P：離散數(shù)學是有味道的； Q：離散數(shù)學是有價值的；,9/24/2020 5:5

22、2 AM,Deren Chen, ZheJiang Univ.,31,EXAMPLE 11,Web Page Searching. Most Web search engines support Boolean searching techniques, which usually can help find Web pages about particular subjects. For instance, using Boolean searching to find Web pages about universities in New Mexico, we can look for p

23、ages matching NEW AND MEXICO AND UNIVERSITIES. The results of this search will include those pages that contain the three words NEW, MEXICO, and UNIVERSITIES.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,32,DEFINITION 7.,A bit string is a sequence of zero or more bits.The length of this string is th

24、e number of bits in the string.,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,33,Table 7,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,34,EXAMPLE 12,Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101. (Here, and throughout this book, bit strings will be

25、split into blocks of four bits to make them easier to read.),Solution: The bitwise OR, bitwise AND, and bitwise XOR of these strings are obtained by taking the OR, AND, and XOR of the corresponding bits, respectively. This gives us 01 1011 0110 11 0001 1101 11 1011 1111 bitwise OR 01 0001 0100 bitwi

26、se AND 10 1010 1011 bitwise XOR,9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,35,P、Q、R 稱為原子命題（Atomic Proposition）。 原子命題或加上邏輯聯(lián)結(jié)詞組成的表達式成為復(fù)合命題（Compositional Proposition）。 從命題常量 到 命題變量(Propositional Variable),命題公式： 1、原子命題是命題公式； 2、設(shè)P是命題公式，則P也是命題公式； 3、設(shè)P、Q是命題公式，則（P Q）、（P Q）、（P Q）、（P Q）也是命題公式； 4、有限次地使用1、2、3所得到的也是命題公式。 Proposition Formulas, Well-Formed Formulas(wff),9/24/2020 5:52 AM,Deren Chen, ZheJiang Univ.,36,命題公式的運算規(guī)則