Discrete mathematics Yi Li Software school Fudan universit March 20. 2012
Discrete Mathematics Yi Li Software School Fudan University March 20, 2012 Yi Li (Fudan University) Discrete Mathematics March 20, 2012 1 / 24
Review Introduction Tr o Konig lemma
Review Introduction Tree K¨onig lemma Yi Li (Fudan University) Discrete Mathematics March 20, 2012 2 / 24
utline Propositions Truth table ● Adequacy
Outline Propositions Truth table Adequacy Yi Li (Fudan University) Discrete Mathematics March 20, 2012 3 / 24
Connectives amp dle Consider the following statements o am a student @ I am not a student o I am a student and i study computer science o I am a boy or I am a girl o If I am a student I have a class in a week o I am student if and only if I am a member of some unIversity
Connectives Example Consider the following statements: 1 I am a student. 2 I am not a student. 3 I am a student and I study computer science. 4 I am a boy or I am a girl. 5 If I am a student, I have a class in a week. 6 I am student if and only if I am a member of some university. Yi Li (Fudan University) Discrete Mathematics March 20, 2012 4 / 24
Connectives We don t care about the following Are you a student? o Sit down please o What are you doing
Connectives We don’t care about the following: Are you a student? Sit down please. What are you doing? Yi Li (Fudan University) Discrete Mathematics March 20, 2012 5 / 24
Connectives a summary of connectives Symbol Verbose name Remark V disjunction ∧ conjunction and negation not conditional if. then biconditional if and only if
Connectives A summary of connectives: Symbol Verbose name Remark ∨ disjunction or ∧ conjunction and ¬ negation not → conditional if ..., then ... ↔ biconditional if and only if Yi Li (Fudan University) Discrete Mathematics March 20, 2012 6 / 24
anguage o Symbols of propositional logic Connectives:V,∧,,→,分 e Parentheses O Propositional Letters: A, A1, A2, ...,B, B1, B2 o A propositional letter is the most elementary object
Language Symbols of propositional logic: 1 Connectives: ∨, ∧, ¬,→,↔ 2 Parentheses: ), ( 3 Propositional Letters: A, A1, A2, · · · , B, B1, B2, · · · . A propositional letter is the most elementary object. Yi Li (Fudan University) Discrete Mathematics March 20, 2012 7 / 24
Propositions Definition(Proposition) o Propositional letters are propositions o if a and B are propositions, then (aV3),(a^B),(-a),(a→B)and(a分)are propositions o A string of symbols is a proposition if and only if it can be obtained by starting with propositional letters(1)and repeatedly applying(2)
Propositions Definition (Proposition) 1 Propositional letters are propositions. 2 if α and β are propositions, then (α ∨ β),(α ∧ β),(¬α),(α → β) and (α ↔ β) are propositions. 3 A string of symbols is a proposition if and only if it can be obtained by starting with propositional letters (1) and repeatedly applying (2). Yi Li (Fudan University) Discrete Mathematics March 20, 2012 8 / 24
Propositions Definition of Proposition is well-defined or well-formed Or The proposition constructed according to the definition Example Check the following strings (AV∨B),(A∧B)→C eAV-,(A∧B
Propositions Definition The proposition constructed according to the definition of Proposition is well-defined or well-formed. Example Check the following strings: 1 (A ∨ B),((A ∧ B) → C) . 2 A ∨ ¬,(A ∧ B Yi Li (Fudan University) Discrete Mathematics March 20, 2012 9 / 24
Truth tables bAve aBa∧B
Truth Tables α β α ∨ β T T T T F T F T T F F F α β α ∧ β T T T T F F F T F F F F α β α → β T T T T F F F T T F F T Yi Li (Fudan University) Discrete Mathematics March 20, 2012 10 / 24