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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit]

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 #1[edit]

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 ).

Conjunction[edit]

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 cases[edit]

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.