1CMSC 250• Syllabus• Lecture Section: TuTh 12:30-1:45• Lab/Discussion Section M & W 10-10:50 or 11-11:50• Every Week:– Worksheet– Quiz – Homework• 2 Hourly Exams +Final - as noted on Syllabus• Web PageMotivationWhy Learn This Material??• Some things can be "directly applied"• Some things are "good to know"• Some things just teach "a way of thinking“and expressing yourselfOverall Theme:• Proofs2Course Content• Propositional Logic (and circuits)• Predicate Calculus - quantification• Number Theory• Mathematical Induction• Counting - Combinations and Probability• Functions• Relations• Graph TheoryStatement / Proposition• declarative – makes a statement– can be understood to be either true or false in an interpretation• symbolized by a letter• Examples:– Today is Wednesday.– 5 + 2 = 7– 3 * 6 > 18 – The sky is blue.– Why is the sky blue?– Brett Favre– This sentence is false.3Other Symbols and Definitionsto make compound statements• Conjunction– and --- symbolized by ∧∧∧∧• Disjunction– or ---- symbolized by ∨∨∨∨• Negation– not ---- symbolized by ~• Truth Tables for these operatorsTranslation of English to Symbolic Logic Statements• The sky is blue.– one simple (atomic) statement - assign to a letter i.e. b• The sky is blue and the grass is green.– one statement– conjunction of two atomic statements– each single statement gets a letter i.e. b g– and join with ^ i.e. b ^ g• The sky is blue or the sky is purple.– one statement– disjunction of two atomic statements– each single statement gets a letter i.e. b p– and join with ∨∨∨∨ i.e. b ∨∨∨∨ p4Trickier Translation 1• The sky is blue or purple.– two statements• the sky is blue assign this to b• the sky is purple assign this to p– still a disjunction• the sky is blue or the sky is purple • b v pTrickier Translation2• The sky is blue but not dark.– two statements• the sky is blue assign this to b• the sky is dark assign this to d– conjunction with negation• the sky is blue and the sky is not dark • the sky is blue and it is not the case that the sky is dark• "it is not the case that the sky is dark" is ~d• b ^ ~ d5Trickier Translation 3• 2 ≤ x ≤ 6• English: x is greater than or equal to 2 and less than or equal to 6• two statements:– x is greater than or equal to 2 assign this to p– x is less than or equal to 6 assign this to q• becomes– p ^ q#3 Continued --- 2 ≤ x ≤ 6• p is actually a compound statement– x is greater than 2 or x is equal to 2 r ∨∨∨∨ s– x is greater than 2 is symbolized by r– x is equal to 2 is symbolized by s• q is actually a compound statement– x is less than 6 or x is equal to 6 m ∨∨∨∨ n– x is less than 6 is symbolized by m– x is equal to 6 is symbolized by n• p ^ q becomes (r ∨∨∨∨ s) ^ (m ∨∨∨∨ n)6More about Operators• exclusive or: p, q p or q but not both– p⊕q – same as (p ∨∨∨∨ q) ^ ~(p ^ q)• Precedence between the operators– ~ (not) highest precedence– ^ (and) / ∨ (or) have equal precedence– use parentheses to override default precedence– a ^ b ∨ cOther "More Advanced" Truth Tables• (p ^ r) ∨ (q ^ r)• (p ^ ~r) ∨ (p ^ r)• (p ^ q) ∨ (~q ∨ ~p)7Special Results in the Truth Table• Tautological Proposition– a tautology is a statement that can never be false– when all of the lines of the truth table have the result "true"• Contradictory Proposition– a contradiction is a statement that can never be true– when all of the lines of the truth table have the result "false"• Logical Equivalence of two propositions– two statements are logically equivalent if they will be true in exactly the same cases and false in exactly the same cases– when all of the lines of one column of the truth table have all of the same truth values as the corresponding lines from another column of the truth tableSpecial Truth Tables ??• p ∨ ~p• p ^ ~p • (p ^ r) ^ ~(p ∨ r)• (p ^ ~q) ≡?≡ (~q ^ p)• (p ^ q) ≡?≡ ~ (~q ∨ ~p)8Logical Equivalences Theorem 1.1.1 - Page 14• Double Negative: – ~(~p) ≡ p• Commutative: – p ∨ q ≡ q ∨ p and p ^ q ≡ q ^ p• Associative:– (p∨q)∨r ≡ p∨(q∨r) and (p^q)^r ≡ p^(q^r)• Distributive:– p^(q∨r) ≡ (p^q)∨(p^r) and p∨(q^r) ≡ (p∨q)^(p∨ r) More Logical Equivalences• Idempotent: – p ^ p ≡ p and p ∨ p ≡ p• Absorption: – p ∨ (p ^ q) ≡ p and p ^ (p∨q) ≡ p• Identity: – p ^ t ≡ p and p ∨ c ≡ p • Negation: – p ∨ ~p ≡ t and p ^ ~p ≡ c• Universal Bound:– p ^ c ≡ c and p ∨ t ≡ t • Negations of t and c:– ~t ≡ c and ~c ≡ t9DeMorgan's Laws• ~( p ∨ q ) ≡ ~p ^ ~q• ~( p ^ q ) ≡ ~p ∨ ~q• It is not the case that Pete or Quincy went to the store. ≡ Pete did not go to the store and Quincy did not go to the store.• It is not the case that both Pete and Quincy went to the store. ≡ Pete did not go to the store or Quincy did not go to the store.Prove by Truth Table & by Rules• ~(p ∨ ~q) ∨ (~q ^ ~p) ≡ ~p• ~((~p^q) ∨ (~p^~q)) ∨ (p^q)≡ p• (p ∨ q) ^ ~(p ^ q) ≡ (p ^ ~q) ∨ (q ^ ~p)10Conditional Statements• Hypothesis → Conclusion• If this, then that. Hypothesis implies Conclusion• → has lowest precedence (~ / ^ ∨ / →)• If it is raining, I will carry my umbrella.• If you don’t eat your dinner, you will not get desert.100110001111p →→→→ qqpConverting: → to ∨• p → q ≡ ~p ∨ q• Show with Truth Table• ~(p → q ) ≡ p ^ ~q• Show with Truth Table and Rules11Contrapositive• Negate the conclusion and negate the hypothesis• Use the negated Conclusion as the new Hypothesis and the negated Hypothesis as the Conclusion• p → q ≡ ~q → ~p• English:– If Paula is here, then Quincy is here.– If Quincy is not here, then Paula is not here.Converse and Inverse• p → q • If Paula is here, then Quincy is here.• Converse: – swap the hypothesis and the conclusion–q → p– If Quincy is here, then Paula is here.• Inverse: – negate the hypothesis and negate the conclusion–~p → ~q– If Paula is not here, then Quincy is not here.12biconditional• p if and only if q• p
View Full Document
Unlocking...