# Clarifications on some types of proofs

1. Mar 19, 2014

### Panphobia

1. The problem statement, all variables and given/known data

So I would know how to prove a statement like $\sqrt{2}$ by contradiction, all you have to do is assume to negation. But what about something like

p → q
Like if p = (bc mod a != 0), q = (b mod a != 0), how would I prove this, would I negate q or p, or both?

2. Mar 20, 2014

### Staff: Mentor

First off, $\sqrt{2}$ is not a statement. Since you are using logic to prove or disprove statements, it's important to understand what a statement is. The statement you're referring to is probably "$\sqrt{2}$ is an irrational number."

To prove an implication p $\Rightarrow$ q by contradiction, assume that p is true and that q is false. If you arrive at a contradiction, that means that the assumption itself was faulty, and that the implication must be true. The reason for this is that p $\Rightarrow$ q is equivalent to ~p $\vee$ q. The negation of the implication is equivalent to ~(~p $\vee$ q), which is equivalent to p $\wedge$ ~q. In other words, that p is true and that q is false.

A proof by contradiction entails assuming that the given statement is false, and then showing that that assumption must itself be false, thereby making the original statement true.