2015離散數(shù)學命題及聯(lián)結(jié)詞

1、2024/3/20,1,Propositional Logic,,Three tasks,1. What is a proposition?2. Translate natural languages into logical expression. 3. How to make a truth table?,2024/3/20,2,2024/3/20,3,Proposition,Proposition (statement)

2、 A declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.,Truth value:The value (result) of the proposition(真值，是命題最重要的屬性）One of the element from set {True, False}

3、,2024/3/20,4,More Examples of Proposition,Do you speak English? --This is a question, not a statement.這個人太有才了！Let’s go! 我們要努力學習。Teenagers shouldn’t indulge in game. -- It is not a statement, but

4、 an advice.2+2=5 結(jié)論：疑問句、感嘆句和祈使句都不是命題,2024/3/20,5,More Examples of Proposition,3-x=5. x is a variable, so the truth value of this sentence is open.這盤菜很咸。這個人個很高。,結(jié)論：聰明的你如果給不出真值那就不是命題,2024/3/20,6,More Examples of P

5、roposition,有兩個特例需要記?。?. 未來命題真值會水落石出的我們認為是命題10年之后你一定是千萬富翁?；鹦巧嫌猩?. 悖論我正在說謊我專門為不為自己理發(fā)的人理發(fā),2024/3/20,7,Propositional Variable,A proposition can be represented by a proposition variable A propositional variable is oft

6、en denoted as p, q, r, etc.e.g.p: Today is Tuesday.q: 2+2=4r: 2+3=6,2024/3/20,8,Logical Connectives,A simple statement can be represented by an atom proposition.More than one atom propositions can be combined into a

7、 compound statement.The combination is achieved using “connectives”. Usually, the connective roughly corresponds some conjunctive in the natural language.,2024/3/20,9,,Negation,p(also denoted by : it is not the case

8、 that p,,,,,p,p,T,F,F,T,Truth table for p,All possible value of p,,2024/3/20,10,否定聯(lián)結(jié)詞Conectives: 非 不,例：他說的并非都是對的。 太原是一個不大的城市。 太原并不是一個大城市。,2024/3/20,11,,,Conjunction,The conjunction of p and

9、q, denoted by p?q ,is the proposition “p and q”,,,,,p q,T TT FF TF F,p?q,T FF F,All possible value of ,,p?q=true iff both p and q,,2024/3/20,12,合取聯(lián)結(jié)詞key word: 一邊 一邊

10、一面 一面 雖然 但是 不但 而且 既 又 和 與表示的邏輯關(guān)系是：p與q同時成立,……,……,……,……,……,……,……,……,……,……,,例:,2024/3/20,13,(1) 2與3的最小公倍數(shù)是6。,(2)王麗和王娟是親姐妹。,(3) 8能2整除，但不能被6整除。,(4) 2015年的春節(jié)下雪了 ,《我是歌手》很

11、好看。,2024/3/20,14,,,Disjunction,“p or q” is denoted as p?q. The disjunction p?q is false when both p and q are false and is true otherwise.,,,,,p q,T TT FF TF F,p ? q,T TT F,All possib

12、le value of ,,p?q=false iff both ~p and ~q,,2024/3/20,15,析取聯(lián)結(jié)詞key word: 或 表示的邏輯關(guān)系是：至少有一個成立,例：小王學過日語或俄語。,2024/3/20,16,,,Conditional,“if p, then q” is denoted as p q, asserts that q is true on the condition that p hold

13、s. p is called the hypothesis(or antecedent or premise ) and q is called the conclusion(or consequence). It is also called an implication.,,,,,p q,T TT FF TF F,p q,T FT T,All possi

14、ble value of ,,p q=false iff p is true and q is false,,2024/3/20,17,Conditional,Sentence:If I am elected, then I will lower taxes.If you get 100% on the final, then you will get an A.表示的邏輯關(guān)系是：q是p的必要條件,Conditional,p

15、 is a sufficient condition for q所謂充分條件就是指：如果有了P條件，則必然有結(jié)果Q，并且如果沒有條件P，則不一定有結(jié)果Qq is a necessary condition for p所謂必要條件就是指：如果沒有條件Q，則必然沒有結(jié)果P，并且如果有了條件Q，則未必有結(jié)果P,2024/3/20,18,Express conditional statement p q :,“if p,the

16、n q” “if p,q”“p is sufficient for q”“q if p”“q when p”“q unless p ” “a necessary condition for p is q”“a sufficient condition for q is p”,2024/3/20,19,“p implies q”“p only if q”“q whenever

17、 p”“q follows from p”,The most confusion:,“p only if q” says that p cannot be true when q is not true. That is, the statement is false if p is true , but q is false . when p is false, q may be either true or fa

18、lse, because the statement says nothing about truth value of q.example: 王蓉取得好成績，僅當她努力學習了。 僅當你走，我將留下。,2024/3/20,20,The most confusion:,“q unless p” means that if p is false , then q must be true .That is,

19、the statement is false when p is true but q is false , but it is true otherwise. Consequently , “q unless p” and “p q always have the same truth value. example: 除非你努力，否則你將失敗。 我今天進城，除非下雨。,2024/3/20,21,202

20、4/3/20,22,Biconditional,,,,,p q,T TT FF TF F,p q,TFF T,(p q) ( q p),“p if and only if q” is denoted as p q, The statement is true when p and have the same truth val

21、ues , and is false otherwise . It is also called bi-implications.,2024/3/20,23,Biconditional,Sentence:You can take the flight if and only if you buy a ticket.兩個三角形全等，當且僅當它們的三組對邊相等。表示的邏輯關(guān)系：p與q互為充分必要條件 “p is necess

22、ary and sufficient for q” “if p then q, and conversely” “p iff q”,2024/3/20,24,How to make a truth table?,What is wff(well-formed formula)?,定義1-3.1 命題演算的合式公式（wff）(1)單個命題變元本身是一個合式公式。(2)如果A是合式公式，那么?A是合式公式。

23、(3)如果A和B是合式公式，那么(A?B), (A?B), (A?B), (A B)是合式公式。(4)當且僅當能夠有限次地應用(1)、(2)、(3)所得到的包含命題變元、聯(lián)結(jié)詞和括號的符號串是合式公式。,2024/3/20,25,定義1-3.1 well-formed formula（wff）The formulas are inductively defined as follows:Each proposition

24、al variable is, on its own, a formula.If φ is a formula, then φ is a formula.If φ and ψ are formulas, and ? is any binary connective, then ( φ ? ψ) is a formula. Here ? could be (but is not limited to) the usual operat

25、ors? , ∨, ∧, →, or,2024/3/20,26,How to make a truth table?,To create a truth table, follow these steps: 1. Determine the number of variables; for n variables, create a table with 2n rows. ? If there are two variables (

26、p, q), then you will need 22 or 4 rows. If there are three variables (p, q, and r), you will need 23 or 8 rows. 2. List the variable and every combination of T and F for the given variables.,2024/3/20,27,How to make a

27、truth table?,3. Then start with negations (“not” or “~”), create a new column for each “piece” of the statement or argument, filling in the truth values as you go. Work from simple pieces to more difficult piec

28、es until you have the truth values for the whole problem.,2024/3/20,28,How to make a truth table?,For example:,2024/3/20,29,How to make a truth table?,For example:,2024/3/20,30,How to make a truth table?,For example:,Thr

29、ee tasks,1. What is a proposition?2. Translate natural languages into logical expression. 3. How to make a truth table?,2024/3/20,31,Practice,1.Which of these sentences are propositions ? What are the truth value of t

30、hose that are propositions? (1) 2是素數(shù)嗎？ (2) x+2=7 (3) 歡迎大家來上離散數(shù)學課！ (4) 2+3=8 (5) 宇宙間只有地球上有生命。 (6) 3+4 (7) 我說的是謊話,2024/3/20,32,Practice,2.Write these propositions using p , q , r… and logical co

31、nnectives(including negations). (1) 李秀和張華都是東北人。 (2) 雖然天氣很冷，可人們情緒很高。 (3) 張海燕去過美國或去過加拿大。 (4) 劉文虎現(xiàn)在在宿舍或在圖書館里。 (5) 李梅與李珊是親姐妹。 (6) 趙志全與張鐘山是同鄉(xiāng)人。 (7) 除非李聯(lián)不怕吃苦，否則她不會取得好成績。 (8) 只有李聯(lián)努力學習，她才能取得好成績。,2024/3/20