The two column format looks like this:
\(\begin{array}{l l l} & \textrm{Column 1} & \textrm{Column 2} \\ \hline 1. & \textrm{Your conclusion} & \textrm{How you came to that conclusion} \\ 2. & \ldots\\ 3. & \ldots\\ \vdots \\ \square \end{array}\)
Here are some common rewrites you might see when constructing your proofs:
The first type of proof we will discuss is called a direct proof. Basically, we are trying to to prove \(p \rightarrow q\) by starting at \(p\) and getting to \(q\).
For example, say we want to prove the following: “If \(x\) is even, \(x^2\) is even”.
Then \(p\) is “\(x\) is even” and \(q\) is “\(x^2\) is even”
The first type of proof we will discuss is called a direct proof. Basically, we are trying to to prove \(p \rightarrow q\) by starting at \(p\) and getting to \(q\).
For example, say we want to prove the following: “If \(x\) is even, \(x^2\) is even”.
Then \(p\) is “\(x\) is even” and \(q\) is “\(x^2\) is even”
\(\begin{array}{l l l} 1. & x \textrm{ is even} & \textrm{Given (In other words, this is our } p \textrm{)}\\ 2. & x = 2k, {} k \in \mathbb{Z} & \textrm{Definition of Even Number}\\ 3. & x^2 = (2k)^2 & \textrm{Squared both sides of Line 2} \\ 4. & x^2 = 4k^2 & \textrm{Simplified Line 3} \\ 5. & x^2 = 2(2k^2) & \textrm{Rewrote Line 4} \\ 6. & x^2 \textrm{ is even} & \textrm{Definition of Even Number } \square \end{array}\)
Note that at every step you’re basically saying, “Therefore…” this is where your implication \(\rightarrow\) is coming in.
We want to show \(x-1 < \left \lfloor{x}\right \rfloor\)
We want to show \(x-1 < \left \lfloor{x}\right \rfloor\)
\(\begin{array}{l l l} 1. & x = y + d, y \in \mathbb{Z}, d \in [0,1) & \textrm{Rewrite of x} \\ 2. & d < 1 & \textrm{Defined in Line 1}\\ 3. & d - 1 < 0 & \textrm{Subtracted }1 \textrm{ from both sides of Line 2}\\ 4. & y + d - 1 < y & \textrm{Added } y \textrm{ to both sides}\\ 5. & x - 1 < y & \textrm{Plugged in Line 1 to Line 4.} \\ 6. & y = \left \lfloor{x}\right \rfloor & \textrm{Applied definition of floor to line 1.} \\ 7. & x - 1 < \left \lfloor{x}\right \rfloor & \textrm{Plugged line 6 into line 5. } \square \end{array}\)
Note that this is still a direct proof (\(p \rightarrow q\)) but \(p\) is never directly stated. If \(p\) is never directly stated, you can just think of \(p\) as your set of knowledge of the world.
Another example of this is when we do our logical equivalences.
For example, you’ve previously proved \(\neg a \lor \neg(b \land \neg c) \equiv a \rightarrow (b \rightarrow c)\).
Since you are showing \(p \equiv q\), you actually are showing \(p \leftrightarrow q\) rather than just \(p \rightarrow q\).
We could do this two ways. We could prove both \(p \rightarrow q\) and \(q \rightarrow p\), or we can consolidate it into one proof by using \(\leftrightarrow\) at any step.
We start at \(p\): \(\neg a \lor \neg(b \land \neg c)\) and use our equivalences to get to \(q\): \(a \rightarrow (b \rightarrow c)\).
We start at \(p\): \(\neg a \lor \neg(b \land \neg c)\) and use our equivalences to get to \(q\): \(a \rightarrow (b \rightarrow c)\).
\(\begin{array}{l l l} 1. & \neg a \lor \neg(b \land \neg c) & \textrm{Given} \\ 2. & \equiv a \rightarrow \neg(b \land \neg c) & \textrm{Implication Definition}\\ 3. & \equiv a \rightarrow (\neg b \lor c) & \textrm{DeMorgan's}\\ 4. & \equiv a \rightarrow (b \rightarrow c) & \textrm{Implication Definition } \square \\ \end{array}\)