Mathematical Proof and the Principles of Mathematics/Logic/Proofs with conjunction and disjunction

We've now looked at direct proofs and indirect proofs, but so far we haven't talked about rules of inference for conjunction and disjunction. We will 'define' these in terms of implication as we did for negation.

Disjunction

We take the statement not $P$ implies $Q$ to be the definition of $P$ or $Q$.

First we must make sure this agrees with the way we defined $P$ or $Q$ earlier. According to that definition, $P$ or $Q$ is only False when $P$ is False and $Q$ is False. But not $P$ implies $Q$ is only False when not $P$ is True, in other words $P$ is False, and $Q$ is False.

We can turn this definition into two new rules of inference by combining it with the rules of inference for implication.

If by making the assumption not $P$ one can derive $Q$, then deduce $P$ or $Q$.

From not $P$, $P$ or $Q$ deduce $Q$.

Example Proof #1

Let's apply these to prove a a basic fact about disjunction.

Prop. 1: $P$ or $Q$ implies $Q$ or $P$.

As before, we set up a basic outline.

Line	Statement	Justification
1	$P$ or $Q$	Hypothesis
(something)
n	$Q$ or $P$	?
n+1	$P$ or $Q$ implies $Q$ or $P$	From 1 and n

From the first rule of inference taken from the definition, the way to prove a disjunction is to assume the negation of the first statement and derive the second statement. Also, the second rule gives us a way to use the assumption. Adding this to the proof:

Line	Statement	Justification
1	$P$ or $Q$	Hypothesis
2	not $P$ implies $Q$	From 1
3	not $Q$	Hypothesis
(something)
n−1	$P$	?
n	$Q$ or $P$	From 2 and n−1
n+1	$P$ or $Q$ implies $Q$ or $P$	From 1 and n

Now we need to combine the not $P$ implies $Q$ with not $Q$, but the previous page had several ways of combining implication and negation. The most useful seems to be Prop. 4, and from this the rest of the proof can be filled in.

Line	Statement	Justification
1	$P$ or $Q$	Hypothesis
2	not $P$ implies $Q$	From 1
3	not $Q$	Hypothesis
4	not $Q$ implies not not $P$	Apply Prop. 4 from the previous page to 2.
5	not not $P$	From 3 and 4
6	$P$	From 5
7	$Q$ or $P$	From 2 and 6
8	$P$ or $Q$ implies $Q$ or $P$	From 1 and 7

To put this in prose form:

Prop. 1: $P$ or $Q$ implies $Q$ or $P$

Proof: Assume $P$ or $Q$. This says not $P$ implies $Q$. Now assume not $Q$. From Prop. 4 on the previous page we have not $Q$ implies not not $P$, so not not $P$ and so $P$. Therefore $Q$ or $Q$. From the original assumption $P$ or $Q$ it follows that $Q$ implies $P$, so we can conclude that $P$ or $Q$ implies $Q$ or $P$.

By combining this proposition with the rules of inference from the definition we get two more:

If by making the assumption not $Q$ one can derive $P$, then deduce $P$ or $Q$.

From not $Q$, $P$ or $Q$ deduce $P$.

Left to the reader (Disjunction)

Prop. 2: $P$ implies $P$ or $Q$.

Prop. 3: $Q$ implies $P$ or $Q$.

Prop. 4: not ($P$ or $Q$) implies not $P$.

Prop. 5: not ($P$ or $Q$) implies not $Q$.

Prop. 6: ($P$ or $Q$) or $R$ implies $P$ or ($Q$ or $R$).

Conjunction

Our definition for conjunction is a bit more complex than the one for disjunction. Specifically, we take the statement not (not $P$ or not $Q$) to be the definition of $P$ and $Q$.

Again, we need to make sure this definition agrees with the one given previously. The statement $P$ and $Q$ is True only when both $P$ is True and $Q$ is True. On the other hand, the statement not (not $P$ or not $Q$) is True when not $P$ or not $Q$ is False. This is the same as saying not $P$ is False and not $Q$ is False, which is the same as saying $P$ is True and $Q$ is True, which matches the previous definition.

The definition is rather cumbersome in terms of generating rules of inference, but it implies some other statements which can be used instead. We just give hints for the proofs and leave the reader to fill in details.

Prop. 7: $P$ and $Q$ implies $P$.

(Apply the definition and Prop. 4.)

This produces the rule of inference

From $P$ and $Q$ deduce $P$.

Prop. 8: $P$ and $Q$ implies $Q$.

(Apply the definition and Prop. 5.)

This produces the rule of inference

From $P$ and $Q$ deduce $Q$.

Prop. 9: $P$ implies ($Q$ implies $P$ and $Q$.

(To prove $P$ and $Q$, assume not $P$ or not $Q$, then derive a contradiction.)

This produces the rule of inference

From $P$, $Q$ deduce $P$ and $Q$.

Conjunction is very useful when listing several assumptions needed for statement, as in $P$ and $Q$ implies $R$. Up to now we've been getting by without it by using $P$ implies ($Q$ implies $R$) for this. We leave it to the reader to prove :

Prop. 10: ($P$ implies ($Q$ implies $R$)) implies ($P$ and $Q$ implies $R$).

and

Prop. 11: ($P$ and $Q$ implies $R$) implies ($P$ implies ($Q$ implies $R$)).

Left to the reader (Conjunction)

Prop. 12: $P$ and $Q$ implies $Q$ and $P$.

Prop. 13: ($P$ and $Q$) and $R$ implies $P$ and ($Q$ and $R$).

Prop. 14: ($P$ and $Q$) or $R$ implies ($P$ or $R$) and ($Q$ or $R$).

Prop. 15: ($P$ or $R$) and ($Q$ or $R$) implies ($P$ and $Q$) or $R$.

Prop. 16: ($P$ or $Q$) and $R$ implies ($P$ and $R$) or ($Q$ and $R$).

Prop. 17: ($P$ and $R$) or ($Q$ and $R$) implies ($P$ or $Q$) and $R$.

Proof by cases

This is a third important method of proof, though it's really just an application of methods we've already seen. The idea is that when you're trying to prove a statement $R$ it's sometimes easier if have a hypothesis to work with. In other words it's easier to prove $P$ implies $R$ than to prove $R$ on its own. Suppose you've already established $P$ or $Q$. If you can prove that $P$ implies $R$, and then prove that $Q$ implies $R$, then it would seem that $R$ follows.

In a proof this might be be phrased something like this:

We have $P$ or $Q$

Case 1: $P$

(something)

$R$

Case 2: $Q$

(something)

$R$

Therefore $R$.

Put this idea in the form of a proposition to get

Prop. 18: ($P$ or $Q$) and (($P$ implies $R$) and ($Q$ implies $R$)) implies $R$

which we can prove using the other rules of inference. This is left as an exercise in indirect proof.

To state this as a rule of inference:

If by making the assumption $P$ one can derive $R$, and by making the assumption $Q$ one can derive $R$, and $P$ or $Q$, $R$.

As an exercise, apply this rule of inference to construct simpler proofs of Propositions 14 through 17.