Discrete Mathematics for Computer Science: Propositional Logic and DeMorgan's Law
Explore the concepts of propositional logic, necessary and sufficient conditions, DeMorgan's Law, and converting truth tables to propositions in this informative presentation by Prof. Shachar Lovett. Dive into discussions on winning arguments, logical reasoning, and practical applications in a computer science context.
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: More Propositional Logic 1. Necessary and sufficient 2. Negating a Disjunctive or Conjunctive Proposition DeMorgan s Law 3. Converting from Truth Table to Proposition
3 1. Necessary and sufficient Or, how to sound smart and win arguments on Reddit or other blog/forum of your choice
4 Necessary and Sufficient p is NECESSARY for q p q p is SUFFICIENT for q p q Note that p q is equivalent to q p So if p is necessary and sufficient for q, then p iff q. ( no p, no q! ) ( p is all we need to know! )
5 Your turn: Practice p = Get an A on the final. q = Get an A in the class. r = Do the homework. s = Get an A on everything. p is necessary for q p is sufficient for q r is necessary for p r is sufficient for s s is sufficient for q i. ii. iii. How many of the necessary / sufficient sentences are true? A. 0 or 1 B. 2 C. 3 D. 4 E. 5 iv.
6 Be a beacon of rational thought in the online world 1 point extra credit on the midterm: Make correct, good, topical use necessary or sufficient (1/2 pt each) in an online discussion Link to your comment/post on TED to collect your points. Obviously no venues or topics that are NSFW/racist/sexist/etc. Max 1pt per person
7 2. Negating a Disjunctive or Conjunctive Proposition DeMorgan s Law
8 Be the fact-checker! My opponent says I have 10 speeding tickets and took bribes from that oil company. That is not true! p = has 10 speeding tickets q = took bribes Which of the following is equivalent to (p q)? A. p q B. p q C. p q D. p q E. p q
9 Laws to memorize DeMorgan s (p q) p q (p q) p q Distributive Associative
10 2. Converting from Truth Table to Proposition Disjunctive and Conjunctive Normal Forms
11 DNF and CNF DNF: Disjunctive Normal Form OR of ANDs (terms) e.g. (p q) ( p r) CNF: Conjunctive Normal Form AND of ORs (clauses) e.g. (p q) ( p r)
12 DNF and CNF (p q) ( p r) ( p (p q) r) (p r) (p r) (r q) IV. (p q r) (p q) I. II. III. Categorize the above propositions: A. I is CNF and IV is DNF B. I and III are DNF and IV is CNF C. I is DNF and IV is CNF D. I, II and III are DNF and IV is CNF E. None/more/other
13 Equivalence of p q and p q When we write a proposition, we are trying to describe what is true One way to think about this: Look for the rows that are true Describe the input values for that row or them together p q T F T T p T T F F q T F T F p F F T T p q T F T T
14 Disjunctive normal form (DNF) p T T F F q T F T F p q T F T T p q OR p q p q p q (p q) ( p q) ( p q)
15 Disjunctive normal form (DNF) Convert the predicate p A. (p q) ( p q) B. (p q) ( p q) C. (p q) ( p q) D. (p q) ( p q) E. None/more/other q to DNF
16 Conjunctive normal form (CNF) p T T F F q T F T F p q T F F T p q p q AND p q ( p q) (p q)
17 Conjunctive normal form (CNF) Convert the predicate p A. p q B. p q C. (p q) ( p q) D. (p q) ( p q) E. None/more/other q to CNF
CNF vs DNF Every predicate can be written both as a CNF and as a DNF Which one is more effective (requires less connectives to write): A. CNF B. DNF C. Both require the same number D. Depends on predicate E. None/more/other
Negating a CNF Say s is a predicate with a DNF s (p q) ( p r) (p r) ( p q) We want to compute s. Which one of the following is easiest to compute: A. CNF for s B. DNF for s C. Both are equally easy to compute D. None/more/other
