Logical Connectives and Truth Tables in Discrete Mathematics
Dive into the world of logical connectives and truth tables in discrete mathematics. Explore topics such as propositional logic, truth tables, and the intuitive sense behind different outputs. Learn about operators, operator precedence, and how to make sense of complex propositional formulas. Examples and explanations included.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
CSE 20: Discrete Mathematics for Computer Science Prof. Shachar Lovett
2 Today s Topics: Propositional logic Truth tables for basic logical connectives not, and, or, xor, implies Truth table for new/made-up connectives Step-by-step truth tables for complex propositional formulas Equivalence rules 1. 2. 3. 4.
3 1. Truth table for basic logical connectives not, and, or, xor, implies
4 Logical connectives math p q p q p q p p q p q Java/C++ p && q p || q p ^ q !p and or xor not If/then, implies If and only if, iff We will use the math notation
5 Logical connectives: Operator precedence Operator Precedence 1 2 3 4 5 (not) (and) (or) (implies) (iff) As with programming, it is good practice to use parenthesis for clarity
Truth tables: AND Is it: A. F,F,F,F B. F,T,T,T C. T,T,T,F D. F,F,F,T E. None/More/Other p F F T T q F T F T p q ? ? ? ? I m interested in seeing if this makes intuitive sense to you can you explain why each output makes sense, using example sentences?
Truth tables: AND Is it: A. F,F,F,F B. F,T,T,T C. T,T,T,F D. F,F,F,T E. None/More/Other p F F T T q F T F T p q F F F T I m interested in seeing if this makes intuitive sense to you can you explain why each output makes sense, using example sentences?
Truth tables: AND OR p F F T T q F T F T p q F F F T p F F T T q F T F T p q F T T T I m interested in seeing if this makes intuitive sense to you can you explain why each output makes sense, using example sentences?
9 OR is tricky in English OR XOR p F F T T q F T F T p XOR q F T T F p F F T T q F T F T p OR q F T T T Birthday party host: Do you want some cake OR ice- crem? YOU CAN HAVE BOTH (imagine it is rude to have nothing) Diner breakfast special: Pancake, two eggs and bacon XOR sausage. YOU MUST PICK EXACTLY ONE
10 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? A. You won the lottery and got an A+ B. You won the lottery and got a B+ C. You did not win the lottery and got an A+ D. You did not win the lottery and got a B+ E. None/More/Other
11 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
Truth tables: IMPLIES A. T, F, F, T B. F, T, T, T C. F, F, F, T D. F, T, T, F None/more/other p F F T T q F T F T p q E. I m interested in seeing if this makes intuitive sense to you can you explain why each output makes sense, using example sentences?
Truth tables: IMPLIES A. T, F, F, T B. F, T, T, T C. F, F, F, T D. F, T, T, F None/more/other p F F T T q F T F T p q T T F T E. I m interested in seeing if this makes intuitive sense to you can you explain why each output makes sense, using example sentences?
14 2. Truth table for new/made- up connectives
15 Making our own connective: AtLeastOneOfTheseThree ALOOTT(p,q,r) p q p OR q F F F F T T T F T T T T Let s make a truth table for ALOOTT. How many rows and columns should be in our truth table (ignoring header row)? A. 5 rows, 4 columns B. 6 rows, 4 columns C. 7 rows, 4 columns D. 8 rows, 4 columns E. 9 rows, 4 columns
16 Making our own connective: AtLeastOneOfTheseThree ALOOTT(p,q,r) p q p OR q F F F F T T T F T T T T Let s make a truth table for ALOOTT. How many rows and columns should be in our truth table (ignoring header row)? A. 5 rows, 4 columns B. 6 rows, 4 columns C. 7 rows, 4 columns D. 8 rows, 4 columns E. 9 rows, 4 columns N variables 2N rows (ignoring header row)
17 Making our own connective: AtLeastOneOfTheseThree ALOOTT(p,q,r) p q r ALOOTT(p,q,r) F F F F F T F T F F T T T F F T F T T T F T T T
18 3. Step-by-step truth tables for complex propositional formulas
19 Truth table for (p q) p p F F T T q F T F T p p q (p q) p ? ? ? ? A. F,F,T,T B. T,F,T,F C. T,T,F,F D. F,F,F,T E. Other Use truth tables of IMPLIES,NOT,AND!
20 Truth table for (p q) p p F F T T q F T F T p p q T T F T (p q) p p q p q F F T F T T T F F T T T
21 Truth table for (p q) p p F F T T q F T F T p T T F F p q T T F T (p q) p p p F T T F
22 Truth table for (p q) p p F F T T q F T F T p T T F F p q T T F T (p q) p T T F F p q p q F F F F T F T F F T T T
Truth tables for complex formulas Intermediate columns: build complex expression step by step Each intermediate column is a basic connective (NOT,AND,OR, ) applied to already calculated previous columns Use truth tables of basic connectives to compute the value of new column, one at a time
24 4. Proving equivalence of two propositions using truth tables
25 Which pair of propositions are equivalent to each other? p q T F T T p T T F F q T F T F q F T F T p F F T T p q T F T T A. p, p B. p q, p C. q, p q D. q, p E. Other/none/ more than one
26 Truth table for (p q) p p q p q p T T T F T F F F F T T T F F T T (p q) p F F T T A. q B. p q C. p q D. p E. Other/none/m ore than one (p q) p is equivalent to:
27 Hardware for (p q) p Hardware for p Back to the Algebra analogy: we do similar simplification in jr. high math: a + b 2a + 3b + a (8b/2) + a = a
28 Hardware design efficiency Improved performance of CPUs depends in part on squeezing logic onto as tiny amount of silicon as possible, and using as little electricity/heat as possible. Minimizing logic gates helps both.
29 How can we prove that two propositions are not equivalent? A. Make a truth table that has columns for both, and verify that not all the entries in the two columns are T B. Make a truth table that has columns for both, and verify that at least one of the entries in the two columns is F C. Make a truth table that has columns for both, and make sure that the two columns are not identical to each other. D. Make a truth table that has columns for both, and make sure that in the row where the input variables are all T, the propositions are both F
