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.

DisjunctionEdit

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

First we must make sure this agrees with the way we defined   or   earlier. According to that definition,   or   is only False when   is False and   is False. But not   implies   is only False when not   is True, in other words   is False, and   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   one can derive  , then deduce   or  .
From not  ,   or   deduce  .

Example Proof #1Edit

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

Prop. 1:   or   implies   or  .

As before, we set up a basic outline.

Line Statement Justification
1   or   Hypothesis
(something)
n   or   ?
n+1   or   implies   or   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   or   Hypothesis
2 not   implies   From 1
3 not   Hypothesis
(something)
n−1   ?
n   or   From 2 and n−1
n+1   or   implies   or   From 1 and n

Now we need to combine the not   implies   with not  , 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   or   Hypothesis
2 not   implies   From 1
3 not   Hypothesis
4 not   implies not not   Apply Prop. 4 from the previous page to 2.
5 not not   From 3 and 4
6   From 5
7   or   From 2 and 6
8   or   implies   or   From 1 and 7

To put this in prose form:

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

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

If by making the assumption not   one can derive  , then deduce   or  .
From not  ,   or   deduce  .

Left to the reader (Disjunction)Edit

Prop. 2:   implies   or  .
Prop. 3:   implies   or  .
Prop. 4: not (  or  ) implies not  .
Prop. 5: not (  or  ) implies not  .
Prop. 6: (  or  ) or   implies   or (  or  ).

ConjunctionEdit

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

Again, we need to make sure this definition agrees with the one given previously. The statement   and   is True only when both   is True and   is True. On the other hand, the statement not (not   or not  ) is True when not   or not   is False. This is the same as saying not   is False and not   is False, which is the same as saying   is True and   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:   and   implies  .
(Apply the definition and Prop. 4.)

This produces the rule of inference

From   and   deduce  .


Prop. 8:   and   implies  .
(Apply the definition and Prop. 5.)

This produces the rule of inference

From   and   deduce  .


Prop. 9:   implies (  implies   and  .
(To prove   and  , assume not   or not  , then derive a contradiction.)

This produces the rule of inference

From  ,   deduce   and  .


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

Prop. 10: (  implies (  implies  )) implies (  and   implies  ).

and

Prop. 11: (  and   implies  ) implies (  implies (  implies  )).

Left to the reader (Conjunction)Edit

Prop. 12:   and   implies   and  .
Prop. 13: (  and  ) and   implies   and (  and  ).
Prop. 14: (  and  ) or   implies (  or  ) and (  or  ).
Prop. 15: (  or  ) and (  or  ) implies (  and  ) or  .
Prop. 16: (  or  ) and   implies (  and  ) or (  and  ).
Prop. 17: (  and  ) or (  and  ) implies (  or  ) and  .

Proof by casesEdit

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   it's sometimes easier if have a hypothesis to work with. In other words it's easier to prove   implies   than to prove   on its own. Suppose you've already established   or  . If you can prove that   implies  , and then prove that   implies  , then it would seem that   follows.

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

We have   or  
Case 1:  
(something)
 
Case 2:  
(something)
 
Therefore  .

Put this idea in the form of a proposition to get

Prop. 18: (  or  ) and ((  implies  ) and (  implies  )) implies  

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   one can derive  , and by making the assumption   one can derive  , and   or  ,  .

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