《111 命題邏輯》由會(huì)員分享，可在線閱讀，更多相關(guān)《111 命題邏輯（41頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,2/22/2009 8:44 PM,Deren Chen,ZheJiang Univ.,#,Logic,命題邏輯,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,1,基礎(chǔ)部分,:,邏輯,(Logic),集合,(Sets),算法,(Algorithms),數(shù)論,(Number Theory),11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,2,1.1.1,命題邏輯,Proposition Logic,11/30/2024 3:40 PM,Deren Chen,

2、ZheJiang Univ.,3,邏輯學(xué)：,研究推理的一門學(xué)科,數(shù)理邏輯：,用數(shù)學(xué)方法研究推理的一門數(shù)學(xué)學(xué)科,-,一套符號(hào)體系,+,一組規(guī)則,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,4,數(shù)理邏輯的內(nèi)容：,古典數(shù)理邏輯：,命題邏輯、謂詞邏輯,現(xiàn)代數(shù)理邏輯：,公理化集合論、遞歸論、模型論、證明論,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,5,Proposition:,一個(gè)有確定真或假意義的語(yǔ)句,.,命題邏輯,Proposition Logic,11/30/2024 3:40 PM,Deren Chen

3、,ZheJiang Univ.,6,EXAMPLE,1,All the following statements are propositions.,1.Washington,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.,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,7,E

4、XAMPLE 2,Consider the following sentences.,1.What time is it?,2.Read this carefully.,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

5、 been assigned values.Various ways to form propositions from sentences of this type will be discussed in Section 1.3.,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,8,命題的語(yǔ)句形式,陳述句,非命題語(yǔ)句：,疑問句,命令句,感態(tài)句,非命題陳述句：悖論語(yǔ)句,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,9,命題的符號(hào)表示：,大小寫英文字母：,P,、,Q,、,R,、,p,、,q,、,r,、。,命題

6、真值（,Truth Values,）的表示：,真：,T,、,1,假：,F,、,0,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,10,命題語(yǔ)句真值確定的幾點(diǎn)說明：,1,、時(shí)間性,2,、區(qū)域性,3,、標(biāo)準(zhǔn)性,命題真值間的關(guān)系表示：,真值表（,Truth Table),11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,11,DEFINITION 1.,Let p be a proposition.The statement,It is not the case that p.,is another proposit

7、ion,called the negation of p.,The negation of p is denoted by p.The proposition p is read not p.,p,的否定,11/30/2024 3:40 PM,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 F

8、riday.,This negation can be more simply expressed by,Today is not Friday.,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,13,Table 1,11/30/2024 3:40 PM,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

9、p and q are true and is false otherwise.The proposition pq is called the conjunction of p and q.,The truth table for pq is shown in Table 2.,p,和,q,的合取,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,15,Table 2,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,16,EXAMPLE 4,Find the conjunction of the proposi

10、tions p and q where p is the proposition Today is Friday and q is the proposition It is raining 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

11、and on Fridays when it does not rain.,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,17,DEFINITION 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

12、.,The truth table for pq is shown in Table 3.,p,和,q,的析取,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,18,Table 3,11/30/2024 3:40 PM,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 disjunc

13、tion ofp and q,pq,is the proposition,Today is Friday or it is raining today.,This proposition 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.,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,20,D

14、EFINITION 4.,Let p and q be propositions.The exclusive or of p and q,denoted by p q,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,的對(duì)稱差,11/30/2024 3:40 PM,Deren Chen,Z

15、heJiang Univ.,21,Table 4,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,22,DEFINITION 5.,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 cal

16、led the conclusion(or consequence).,如果,p,則,q,單條件,蘊(yùn)涵,P:,前提,Q:,結(jié)論,11/30/2024 3:40 PM,Deren Chen,ZheJiang Univ.,23,Table 5,11/30/2024 3:40 PM,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 assignment 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