Discrete Structures Lecture 5: Logic and Propositions, Study notes of Discrete Structures and Graph Theory

Download Discrete Structures Lecture 5: Logic and Propositions and more Study notes Discrete Structures and Graph Theory in PDF only on Docsity! 9/6/2002 1 CSci 243 Discrete Structures Lecture 5 Logic 1 9/6/2002 2 Outline • Introduction, Propositions • Compound Propositions • Truth Tables • Tautologies and Contradictions • Predicates and Quantification 9/6/2002 5 Propositions • Propositions: • My name is Maximillian. • 1+1=2 • Not propositions: • Hello! • Where is McGloughlin-Street 020? • Stop sleeping. 9/6/2002 6 Compound Propositions: Easy Ones • Assume P and Q are propositions • !P (negation): P is not true • P¶Q (conjunction): both P and Q are true • PvQ (disjunction): either P or Q is true, or that both are true • P±Q (exclusive or): either P or Q is true, but not both are true 9/6/2002 7 Compound Propositions: Implication • Assume P and Q are propositions • PfQ (implication): false if P is true and Q is false; true otherwise • P is the antecedent or premise • Q is the conclusion or consequence • Z: PfiQ (because f means a function) 9/6/2002 10 Compound Propositions: Dbl. Implic. • Assume P and Q are propositions • PjQ (biconditional): true if P and Q values match; false otherwise • AKA: double implication • Note: PjQ is really just (PfQ)¶(QfP) • Z: P¤Q (because j means a relation) 9/6/2002 11 Negation Fun • Can write with overbars: !P = • DeMorgan’s Laws • !(P¶Q) ¤ !P v !Q • !(PvQ) ¤ !P ¶ !Q • Negated Implication • !(PfiQ) fi P ¶ !Q • We’ll prove this in a bit P 9/6/2002 12 • Given: It is not the case that the sky is always blue and dogs always chase cats • Abstract: • Simplify: • Make Concrete: Quick Question 9/6/2002 15 Tautologies and Contradictions • Tautology: always true regardless of the truth of the propositions • Ex: P v !P • Contradiction: always false regardless of the truth of the propositions • Ex: P ¶ !P 9/6/2002 16 Quick Question • Is (!P ¶ (PfQ)) f !Q a tautology? 9/6/2002 17 Predicates • Predicate: a property which may true or false • Ex: x>3 “x” is the subject of the statement “>3” is the predicate • Propositional function: some proposition which depends on a variable • Ex: P(x)=x>3 (P(x) is the value, P is the func) 9/6/2002 20 Quantification in Z • Recall set construction: { x:Z | x > 1 • x2 } • Quantification: Ax:Z | x > 1 • x2>0 • We can specify • The type of the variable • A condition to limit the variable 9/6/2002 21 Negated Quantification • !(Ax P(x)) = Ex !P(x) • Ex: “Every dog has its day.” “There exists a dog which does not have its day.” • !(Ex P(x)) = Ax !P(x) • Ex: “A president’s name is Hoover.” “All presidents do not have the name Hoover.” 9/6/2002 22 Quick Questions • Given: P(x,y) = x+y=0 • What is the natural language translation of: EyAx P(x,y)? • True or false? • What is the natural language translation of: AyEx P(x,y)? • True or false?