Understanding Boolean Logic and Contrapositive Forms in Discrete Math
Delve into the world of Boolean logic and contrapositive forms in discrete math through topics such as simplifications, DeMorgan's Laws, and conditional operators. Explore how to identify equivalent Boolean expressions and prove contrapositive statements using logical reasoning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Boolean logic: simplifications, derivation rules Sections 3.2-3.4 in Jenkyns, Stephenson
Simplifications Which of the following Boolean expressions is equivalent to A. B. C. D. E. None of the above / more than one of the above.
Simplifications Which of the following Boolean expressions is equivalent to A. B. C. D. E. None of the above / more than one of the above.
Simplifications DeMorgan s Laws Identity Idempotence Commutativity Distributivity Absorption
Conditional operator JS p. 85 P T T F F Q T F T F P Q T F T T
Conditional operator ~(P ~Q) P T T F F Q T F T F P Q T F T T ~P v Q Antecedent aka hypothesis or assumption or given Consequent aka conclusion or goal
Contrapositive form P Q is equivalent to ~Q ~P How can we prove it? A. Compare truth tables B. Derive one from the other using simplification rules C. Both D. Neither
Contrapositive form Proof sequence: Formulas are equivalent in consecutive steps 1. ~Q ~P 2. ~(~Q) (~P) 3. Q ~P 4. ~P Q 5. P Q (given) (definition of ) (double negation) (commutativity) (definition of )
Contrapositive form What s the contrapositive of the statement If you know Java, then you know a programming language? A. If you know a programming language, then you know Java. B. If you don t know a programming language, then you don t know Java. C. If you don t know Java, then you don t know a programming language. D. None of the above.
Implication JS p. 86 vs.
Implication JS p. 86 vs. What s enough to make a conditional statement false? A. P being false. B. Q being false. C. P and Q both false. D. Either P or Q (or both) false. E. None of the above / more than one of the above.
14 What does it mean: IMPLIES Your roommate: If you come to my party Friday, you will have fun Under which of the following scenarios is your roommate a liar? A. You stayed home studying Friday and you did not have fun. B. You stayed home studying Friday and you had fun. C. You went to the party Friday and did not have fun. D. You went to the party Friday and you had fun E. None/More/Other
15 What does it mean: IMPLIES Prof Lovett says: If you win the CA state lottery between now and the end of quarter, you will get an A+ in this class. 4 months later under which of the following scenarios is Prof. Lovett a liar? You won the lottery and got an A+ You won the lottery and got a B+ You did not win the lottery and got an A+ You did not win the lottery and got a B+ None/More/Other A. B. C. D. E.
Implication Is P Q equivalent to Q P? A. Yes B. No
Implication Is P Q equivalent to Q P? A. Yes B. No P T T F F Q T F T F P Q T F T T Q T T F T P
18 Converse error Here is an example with the same form: If this shape is a square, then this shape is a rectangle. Therefore, if this shape is a rectangle, then this shape is a square. No! p q and q p are the converseof each other. It is not safe to assume that if p q is true, then q p is also true! The converse couldbe true though as in the equal sides/square example. If both p q and q p are true, then we say p q ( p iff q ).
20 Converse error If something is made out of wood, then it floats. Therefore, if she floats, then she is made out of wood [and therefore a witch!]
Contradictions Recall definition of IMPLIES P T T F F Q T F T F P Q T F T T If P is false, then P Q is true, doesn t matter what Q is Example: If pigs can fly, then hell freezes over If 1+1=3 then 2+2=5
Next class Sets Read section 2.1 in Jenkyns, Stephenson
