Proof Methods

Logical reasoning

• premise in class, hypothesis in zybook
• argument = entire list of hypothesis
• conclusion = final proposition
• using truth tables
  • in the rows where all the hypothesis are true, conclusion needs to be true
    • if not -> argument is not valid

Rules of inference with propositions

• famous rules of inferences
  • modus ponens
    • !Pasted image 20231106235002.png
  • modus tollens
    • 
  • addition
    • 
  • simplification
    • 
  • conjunction
    • 
  • hypothetical syllogism
    • 
  • disjunctive syllogism
    • 
  • resolution
    • 
• logical proof
  • is a sequence of steps, each of which consists of a proposition and a justification.
  • 

Rules of inference with quantifiers

• quantifiers
  • = for all, there exists
• to apply the rules of inference to quantified expressions we need to remove the quantifier by plugging in a value from the domain to replace the variables
  • a value that can be plugged in is called an element
    • arbitrary elements of a domain have no special properties
    • particular elements may have properties that other elements of the domain do not
      • set of all integers -> 3 is a particular element, as not every integer is odd like 3
      • Any element defined in a hypothesis is a particular element
• Rules of inference for quantified statements
  • 
  • 
  • incorrect use of existential instantiation
    • 

Mathematical Definitions

• even and odd
  • An integer x is even if there is an integer k such that x = 2k.
  • An integer x is odd if there is an integer k such that x = 2k+1.
  • parity
    • The parity of a number is whether the number is odd or even. If two numbers are both even or both odd, then the two numbers have the same parity. If one number is odd and the other is even, then the two numbers have opposite parity.
• rational
  • A number r is rational if there exist integers x and y such that y ≠ 0 and r = x/y
• divides
  • An integer x divides an integer y if and only if x ≠ 0 and y = kx, for some integer k
  • The fact that x divides y is denoted x|y
  • If x divides y, then y is said to be a multiple of x, and x is a factor or divisor of y
• prime and composite numbers
  • An integer n is prime if and only if n > 1, and the only positive integers that divide n are 1 and n.
  • An integer n is composite if and only if n > 1, and there is an integer m such that 1 < m < n and m divides n.
• consecutive
  • Two integers are consecutive if one of the numbers is equal to 1 plus the other number
• inequalities
  • 

Introduction to proofs

• theorem
  • a statement that can be proven to be true
• proof
  • consists of a series of steps, each of which follows logically from assumptions, or from previously proven statements, whose final step should result in the statement of the theorem being proven
• axioms
  • statements assumed to be true
    • used in proofs
• methods
  • proof by exhaustion
    • if domain is small, can just check every element of the domain
  • universal generalization
    • names an arbitrary object in the domain and proves the statement for that object
  • counterexamples
    • an assignment of values to variables that shows that a universal statement is false
    • for conditional statements
      • must satisfy all the hypotheses and contradict the conclusion.
  • existential statements
    • existence proof
      • A proof that shows that an existential statement is true
    • constructive proof of existence
      • gives a specific example of an element in the domain or a set of directions to construct an element in the domain that has the required properties
    • to disprove
      • prove that every single element of the domain does not have the required properties

Writing direct proofs

• direct proof of a conditional statement
  • the hypothesis p is assumed to be true and the conclusion c is proven as a direct result of the assumption
    • 

Proof by contrapositive

• called proof by contraposition in lectures
• proves a conditional theorem of the form p → c by showing that the contrapositive ¬c → ¬p is true
  • remember to apply de morgan's to the statements
• with multiple hypothesis
  • 

Proof by contradiction

• starts by assuming that the theorem is false and then shows that some logical inconsistency arises as a result of the assumption
  • assumption ¬t and leads to a conclusion r ∧ ¬r
    • r = a and b are positive
    • 
• sometimes called an indirect proof
• A proof by contrapositive is a special case of a proof by contradiction
  • can be recast as as proof by contradiction
    • Proofs by contradiction are more general than proofs by contrapositive because a proof by contradiction of the theorem p → q could start with the assumption p ∧ ¬q and conclude with a contradiction other than p ∧ ¬p. Also, proof by contrapositive is a proof technique that is specific to proofs of conditional statements, whereas a proof by contradiction can be used to prove theorems that are not of the form p → q.
• the sqrt 2 proof

Proof by cases

• breaks the domain for the variable into different classes and gives a different proof for each class
  • every value in the domain must be in at least one class
    • can also be include in more than one
    • like odd and even for integers
      • 
  • proof for each class is called a case
• WLOG
  • without loss of generality
  • if the proofs of 2 cases are similar
    • 

Mathematical Induction

• The zyBook uses the terms mathematical induction, inductive proof, and base case, while in class we use the terms induction, proof by induction, and basis step instead.
• Induction is a proof technique that is especially useful for proving statements about elements in a sequence
• two components
  • base case
    • proves the theorem true for the first value
  • inductive step
    • proves that if n is true, then n+1 is also true
    • a compact way to state that an infinite sequence is true
  • 
• summation notation
  • 
  • left side means 1 +2 +3 +4 +5