Proof-Writing

  • Do scrapwork to work out the details of the proof.
  • Write out a careful proof once the scrapwork is complete: Write out the assumptions. Write out what you want to show. Reword what you want to show in terms of known definitions. Justify each step in your proof. Arrive at conclusion. Restate your conclusion.
  • Check over your proof using the checklist points, and check for readability.

    Some Types of Proofs

    Proof of A and B

    To prove A and B, we must prove that both of them always hold.

    Proof of A or B

    To prove A or B, we must prove that at least one of them holds in any given situation (This does not mean that A always holds - it could be false some of the time and true the rest of the time, as long as B is true whenever A is false. Note that if we have already proven A then A OR B is true by default, since one of A or B (A in this case) always holds in any situation.)

    Proof of A ---> B

    Assume that A is true and prove that B is true.

    Proof of A <---> B (A If and Only If B)

    Prove A --->B and then also prove B--->A (ie A<---B)

    Negations

    For all, every, turns into there is or there exits
    There is or there exists turns into for all, every
    A AND B turns into ~A OR ~B
    A OR B turns into ~A AND ~B
    A--->B turns into A AND ~B
    A <--->B (ie A--->B AND B--->A) turns into (A AND ~B) OR (B AND ~A).

    Proof By Contradiction

    To prove something via contradiction, we assume the negation of the statement and eventually arrive at a contradiction.

    Proof of a Statement By Examining All Possible Cases

    Sometimes one must examine lots of cases in order to prove a statement - for example, one might have different proofs for a statement about numbers which depend on whether a certain number is zero or not.

    Samples of Proofs and Comments in Italics

    Problem 1

    Prove that if a minesweeper square S is a 1, and an adjacent square to S is a bomb, then every other square adjacent to S must be a number.

    Proof of Problem 1

    Assume that S is a minesweeper square with a 1 in it, and that some adjacent square to S, call it B, is a bomb. We will show that every other square adjacent to S must be a number. By definition of the type of a minesweeper square, this is equivalent to showing that every other square adjacent to S cannot be a bomb, since every square is either a bomb or a number. Notice that I have reworded the desired conclusion in terms of the definitions.

    Assume for contradiction that some other square adjacent to S, call this square P, is a bomb. Notice that I have assumed the negation of the desired result for contradiction - every other adjacent square cannot be a bomb turns into there is an adjacent square which is a bomb.
    Now P and B are both distinct bombs adjacent to S, by assumption, and S is not a bomb, since it has a 1 in it by assumption, and so by minesweeper rules, we know that S is a number which must be at least 2. Yet, S has a 1 in it, and so we have arrived at a contradiction to the fact that some other square adjacent to S is a bomb, as desired.

    Therefore, if a minesweeper square S is 1 and an adjacent square is a bomb, then every other square adjacent to S is a number.

    Problem 2

    Prove that if we have a 2x2 minesweeper game where A1=1 and A2=* then B1 is 1 AND B2 is 1.

    Proof of Problem 2

    Assume that we have a 2x2 minesweeper game with A1=1 and A2=*. We must show that B1=1 and B2=1, ie we must show that B1 and B2 are not bombs and that they each have exactly 1 bomb near them. Notice that I have reworded what it means for a square to be 1 in terms of the definitions.

    We will first show that B1 and B2 are not bombs. Since A1 is 1 and A2 is a bomb adjacent to it, we can apply problem 1 to see that any other adjacent square to A1 cannot be a bomb. Notice that I used proposition 1. I had to check that the assumptions of prop 1 were satisfied. They were, so prop 1 gave me the conclusion that any other adjacent square was not a bomb.
    Since B1 and B2 are both adjacent to A1, then we know that they cannot be bombs, as desired. I then used the fact that B1 and B2 are both adjacent to A1 to get the desired conclusion.

    We will now show that B1 and B2 are both 1. Notice that B1 has A1=1, A2=*, and B2=number adjacent to it, and B1 is a number since it is not a bomb, and so B1=1 since it it is a number and it has exactly one bomb next to it. Notice that I wrote out all the details to prove that B1 is 1. It would not have been ok to say that it is obvious that B1 is a 1.
    Similarly, B2=1, since B2 is not a bomb and A1=1, A2=*, and B1=1 are the adjacent squares to it. Since the proof that B2=1 is basically the same, I do not have to write it all out again, but I do need to include enough detail so that the similarity is clear

    Therefore, if we have a 2x2 minesweeper game with A1=1 and A2=*, then B1=1=B2, as desired.