Propositional logicPredicate logicPropositional logicPredicate logicLogicSP22 MATH/CS 240: Discrete MathematicsUW-MadisonReference: zyBook chapter 1SP22 MATH/CS 240: Discrete Mathematics Logic 1 / 38Propositional logicPredicate logicWhy study logic? A nonexhaustive list of reasons1Logic dictates what is a correct mathematical argument and what is not.This allows us to prove properties about objects without “trying every possibility”.Applications in algorithms, program verification, computer security, etc.2Logic is much closer to the language of computers than natural language.3Logic enables precise communication and preservation of ideas.SP22 MATH/CS 240: Discrete Mathematics Logic 2 / 38Propositional logicPredicate logicLearning objectives1Determine what is a proposition and what is not2Given a propositional formula, compute its truth table3Understand the relationship between an implication, its converse, and itscontrapositive4Given two propositional formulas, determine whether they are logically equivalentusing truth tables and using laws of propositional logic5Determine whether a given propositional formula is a tautology, a contradiction orneither6Determine what is a predicate and what is not7Understand the relationship between a predicate and its quantifications8Understand how to determine the truth of quantified statements, including whenit is appropriate to give an example or counterexample9Translate English sentences into formulas and vice versaSP22 MATH/CS 240: Discrete Mathematics Logic 3 / 38Propositional logicPredicate logicBasic definitionsWe begin by studying a basic logic known as propositional logic.DefinitionA proposition is a statement that is either true or false, but not both.Which of these are propositions?1Math 240 lectures are held in Van Vleck Hall.2Tomorrow is Friday.3Go Badgers!4Jun Le is wearing jeans.5Jun Le has exactly $1 in his pocket.SP22 MATH/CS 240: Discrete Mathematics Logic 4 / 38Propositional logicPredicate logicTruth valuesSince propositions are either true or false (and not both), we assign them truth valuesT (for true) or F (for false) accordingly.If a proposition is true, we say that it holds, otherwise we say that it fails.What are the truth values of the propositions on the previous slide?SP22 MATH/CS 240: Discrete Mathematics Logic 5 / 38Propositional logicPredicate logicConstructing new propositions from existing propositionsNew propositions can be formed from existing propositions using logical operators.These operators can be applied to any propositions, so we define them on propositionalvariables.DefinitionLet p be a proposition. The negation of p, denoted by ¬p, is the proposition “p doesnot hold.”The truth value of ¬p is the opposite of that of p. We can express this in a truth table:p ¬pT FF TSP22 MATH/CS 240: Discrete Mathematics Logic 6 / 38Propositional logicPredicate logic“And” and “or”The arity of a logical operator is the number of propositions that it applies to.Negation is a unary (i.e., arity 1) operator.Here are some binary (i.e., arity 2) operators:DefinitionLet p and q be propositions.The conjunction of p and q, denoted p ∧ q, is the proposition “p holds and q holds”.The disjunction of p and q, denoted p ∨ q, is the proposition “either p holds or qholds”.p q p ∧ q p ∨ qT T T TT F F TF T F TF F F FDisjunction is also known as inclusive or, in contrast with...SP22 MATH/CS 240: Discrete Mathematics Logic 7 / 38Propositional logicPredicate logicExclusive orDefinitionLet p and q be propositions.The exclusive or or XOR of p and q, denoted p ⊕ q, is the proposition “either p holdsand q does not hold, or q holds and p does not hold”.In natural language, we usually do not distinguish between inclusive or and exclusive or.A: I would like a burger, please.B: Would you like fries or a salad with that?A: Yes.B: ...SP22 MATH/CS 240: Discrete Mathematics Logic 8 / 38Propositional logicPredicate logicImplication“On Wednesdays, we wear pink.”DefinitionLet p and q be propositions. The implication p → q is the proposition “if p holds,then q holds”.p q p → qT T TT F FF T TF F TNote: If p is false, then p → q isalways true!For any two propositions p and q, we can consider the implication p → q, even if pand q are “unrelated”.p → q being true does not suggest a causal relationship between p and q.SP22 MATH/CS 240: Discrete Mathematics Logic 9 / 38Propositional logicPredicate logicExamples of implicationsSuppose A agrees to pay you $10 if you mow their lawn. A also agrees to pay you $10if you paint their house.The following implication is true:If you mow A’s lawn, then A pays you $10.We can see this by checking the four possible situations.The following implication is false:If A pays you $10, then you mow A’s lawn.This is because it might be the case that you painted A’s house, but did not mow theirlawn. In this case A would have paid you $10.SP22 MATH/CS 240: Discrete Mathematics Logic 10 / 38Propositional logicPredicate logicTerminology regarding implicationsIn the implication p → q,p is sometimes called the hypothesis, antecedent, or premiseq is sometimes called the conclusion or consequence.If p → q is true, we say that p implies q. We might also say:q follows from pq unless ¬pp only if q (this does not mean q → p, that would be p if q)p is sufficient for qq is necessary for pp is stronger than qIf p is false (and hence p → q is true), we say that p → q is vacuously true.SP22 MATH/CS 240: Discrete Mathematics Logic 11 / 38Propositional logicPredicate logicPropositional formulasWe have introduced several logical operators:Unary operators: ¬Binary operators: ∧, ∨, ⊕, →DefinitionA propositional formula is a proposition obtained by applying a finite number of theabove logical operators to propositional variables, in some particular order.Examples of propositional formulas:1¬¬p2p ∨ ¬p (law of excluded middle)3p → (q → p)SP22 MATH/CS 240: Discrete Mathematics Logic 12 / 38Propositional logicPredicate logicOperator precedencewhat is the value of 6 ÷ 2(1 + 2)?Is p → q ∨ r a propositional formula? We need to specify whether we mean(p → q) ∨ r or p → (q ∨ r ).Such ambiguities should be resolved according to the following order of precedence(from highest to lowest):¬, ∧, ∨, ⊕, → .For example, p → q ∨ r should be interpreted as p → (q ∨ r) because ∨ has higherprecedence than →.SP22 MATH/CS 240: Discrete Mathematics