cse16

• Invertible function


  1. A→B is invertible iff bijective
• Invertible functions is a function f that has an inverse
• Sequence


  A function whose domain is a subset of ℕ
• Geometric sequence

  a type of sequence where each succeeding term is produced by multiplying each preceding term by a fixed number
• Recurrence relation


  An equation that expresses aₙ in terms of earlier terms: aₙ₋₁, aₙ₋₂, ...
• Closed formula

  A function of n that satisfies the recurrence relation
• Summation (or series)

  is the sum of a sequence
• A way to define a sequence of numbers or values by providing a formula that specifies how the next term is related to previous terms

  A recurrence relation
• Proposition


  A statement that can be assigned a truth value (True or False)
• Propositionsexamples

  • It is raining today
  • 2+3=5
  • 2+3=7
• Negation (not)


  The negation of a proposition P is 'not P'
• Conjunction 'P and Q'
• Disjunction (or, inclusive or)


  The disjunction of propositions P and Q is 'P or Q'
• Exclusive or


  The exclusive or of propositions P and Q is 'P or Q, but not both'
• Implication (if-then)


  The implication of P to Q is 'if P, then Q'
• Biconditional (if and only if)


  The biconditional of P and Q is 'P if and only if Q'
• Atomic Proposition


  A basic proposition that cannot be broken down further
• Compound Proposition


  A proposition built from atomic propositions and logical operations
• P → (Q > R) is a meaningful compound proposition, but P → Q → R is meaningless
• Tautology


  A compound proposition that is true for every assignment of truth values to its propositional variables
• Contradiction


  A compound proposition that is false for every assignment of truth values to its propositional variables
• Satisfiable


  A proposition that is not a contradiction
• Contingency


  A proposition that is neither a tautology nor a contradiction
• Logically Equivalent


  Two propositions A and B are logically equivalent if A↔B is a tautology
• P→Q = ¬P∨Q (implication is equivalent to disjunction of negation and consequent)
• P→Q = ¬Q→¬P (implication is equivalent to the contrapositive)
• P→Q ≠ ¬P→P (the inverse of an implication is not equivalent)
• P↔Q = (P→Q)∧(Q→P) (biconditional is equivalent to the conjunction of two implications)
• P


  9 unless
• Equivalences


  1.3
• Tautology


  A compound Prop. that is true for every assignment of truth Values to its Propositional Variables
• Contradiction


  A compound Prop. that is false for every assignment
• Tautology

  • P v ~P
• Contradiction


  • P ^ ~P
• P -> (P v q) is a tautology
• Contingency


  A prop. that is neither a tautology nor a contradiction
• Logically equivalent


  Two Propositions A,B are said to be logically equivalent iff A&B is a tautology
• Notation: A = B
• A = B iff A&B have the same truth table
• Logically equivalent


  • P -> q = ~P v q
  • P => q = ~P v q