Understanding Logic in Mathematics and Computer Science
Logic is a branch of mathematics that deals with true or false values. It is essential for fields like computer science, aiding in AI, automated reasoning, and digital logic design. Propositions, logical operations like conjunction and disjunction, and the use of propositional variables are fundamental concepts in logic. Knowing how to work with compound propositions is key to making precise statements and reasoning systematically.
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
ICS 6D Logic Overview Instructor: Sandy Irani
What is logic? Branch of mathematics in which variables and expressions have value true (T) or false (F) Particularly relevant to CS: AI: automated reasoning Digital logic design Useful in any area in which it is important to make precise statements and reason in a systematic way.
Proposition A proposition is a statement that is either true or false: 2 + 3 = 5 3 + 4 = 6 4 is a prime number It is raining today It will rain tomorrow (unknown truth value) Chocolate is the best flavor of ice cream (matter of opinion)
Propositions Statements that are not propositios: How are you doing? (Question) Have a nice day! (Command) Bummer! (exclamation) Propositional variables Typically: p, q, r, s Have value T or F.
Logical Operations: Conjunction Conjunction (AND) p q is true when p is true and q is true, false otherwise p q p q Truth table shows the truth value of an expression for every possible combination of truth values for the individual propositions In the expression.
Logical Operations: Disjunction Disjunction (OR) p q is true when p is true or q is true or both are true. p q only when p and q are both false. p q p q
Inclusive vs. Exclusive OR Inclusive OR (True if either or both propositions are true) The patient should not take the medication if she has a history of migraines or she has diabetes. Exclusive OR (True if exactly one of the propositions is true. False if both propositions are true) I will drive or ride my bike to work today. In logic: OR is always the inclusive OR unless explicitly stated otherwise.
Logical Operations: Complement Complement (NOT) p p p
Compound Propositions p q r Order of precedence: Complement Conjunction Disjunction Good to use parens: Except for complement, multiple , multiple
Compound Propositions p: true q: false r: true p (q r) (p q r)
Truth table for: p (q r) p r q r p (q r) p q r
Logical Equivalence Two compound propositions are logically equivalent if they have the same truth value for every combination of truth values for their individual propositions. (p q) p q (p q) p q p q
De Morgans Law: (p q) p q p: The applicant is over 18 years old q: the applicant has a valid driver s license (p q):It is not true that the applicant is over 18 years old and has a valid driver s license. p q: The applicant is not over 18 years old or does not have a valid driver s license.
De Morgans Law: (p q) p q p: the patient has a history of migraines q: the patient has diabetes (p q):It is not true that the patient has a history of migrains or has diabetes. p q: The does not have a history of migraines and does not have diabetes.
The conditional operation Implies p q p is the hypothesis and q is the conclusion p q p q If p, then q. q, if p. p implies q
The conditional operation h: you mow my lawn c: I pay you $20 h c: If you mow my lawn, I will pay you $20. You mow my lawn You don t mow my lawn I pay you $20 I don t pay you $20
The conditional operation s: Suzy studied for her test p: Suzy passed her test p q p q: If Suzy studied for her test then she passed her test. Either Suzy did not study for her test or she passed her test.
Contrapositive s: Suzy studied for her test p: Suzy passed her test The contrapositiveof p q is q p. p q q p If Suzy studied for her test then she passed her test. If Suzy did not pass her test, then she did not study for it.
The bi-conditional operation If and only if p p q is true whenever p and q have the same truth value. q p q p q
Convenient logical equivalences p q p q De Morgans Laws: (p q) p q (p q) p q Associative Laws: (p q) r p (q r ) (p q) r p (q r )
Disjunction/Conjunction p1 p2 p3 p4 . pn p1 p2 p3 p4 . pn
Predicate P(x): x is prime is a predicate (not a proposition) Truth value depends on the value of x. P(5): 5 is prime. P(5) is a proposition. P(6): 6 is prime. P(6) is a proposition. Variable x in a predicate has a domain Set of possible values for x. For x is prime a natural domain is the set of positive integers.
Predicate Domain: set of students in a class: {Abigail, Bernice, Charlie, , Zachary} Predicate T(x): x got an A on the test. T(Bernice): Bernice got an A on the test. T(Charlie) T(Zachary): Charlie and Zachary both got an A on the test. T(Zachary) T(Bernice): If Zachary got an A on the test then Bernice got an A on the test. (All propositions.)
Existential Quantifier Domain: set of students in a class: {Abigail, Bernice, Charlie, , Zachary} Predicate T(x): x got an A on the test. x T(x) There is a student who got an A on the test. Some student got and A on the test. At least one student got an A on the test. For finite domains: x T(x) (T(Abigail) T(Bernice) T(Charlie) T(Zachary))
Existential Quantifier x T(x) True if T(n) is true for at least one value for x in the domain. False if T(n) is false for every value of x in the domain. Example: domain is the set of all positive integers. x (x2 = x) x (x + x = x)
Universal Quantifier Domain: set of students in a class: {Abigail, Bernice, Charlie, , Zachary} Predicate P(x): x passed the test. x P(x) Every student passed the test. All students passed the test. For finite domains: x P(x) (P(Abigail) P(Bernice) P(Charlie) P(Zachary))
Universal Quantifier x T(x) True if T(n) is true for every value for x in the domain. False if T(n) is false for at least one value for x in the domain. (counterexample) Example: domain is the set of all positive integers. x (x2 = x) x (x2 x) x (x2> x)
Universal Quantifier Examples P(x): x is prime. D(x): x is odd The domain for x is the set of all positive integers x (P(x) D(x)) x (P(x) (D(x) (x = 2))) x ((x < 0) P(x))
