Methods of Proof in Propositional Logic (Part 1)

It's fun to know that Comsc56 (Discrete Mathematics) was assigned to me this semester. I finally have the chance to review and clarify things about logic and stuff. I never knew that I had been missing so much in this subject until I scanned our textbook and saw the title "Propositional Logic" (Sparkle! Sparkle!). For this day, I'll talk about one of the 3 methods that we used to prove that a set of propositions is valid.

This is with the assumption that you already know how to represent propositions correctly in symbols...

Chain of Reasoning:
In this method, you just have to remember your goal and the way in which you can reach your goal. Your goal is to arrive at the conclusion given the set of premises. Simple huh? The question now is how we can achieve that goal (ze difficult part). You need to use the premises and some transformations on the premises which will produce new premises until you form the conclusion. How? By using the rules of logic and the rules of inference. (I shall be discussing them in my next blog) .

Let's look at this argument and prove that it's valid...

If Bert eats the cookie then Martha will make a salad.
If Lara kisses Bert then Bert will eat the cookie
Lara kisses Bert
----------------------------------------------------------
Then Martha will make a salad

The set of premises are separated from the conclusion by the broken line. To prove this argument using the chain of reasoning method, we first have to represent them using symbols.

Let B represent the fact the Bert will eat the cookie
Let L represent the fact the Lara will kiss Bert
and let M represent the fact that Martha will make a salad

By using the symbols and the operations available in propositional logic, the argument can be simplified into the following:
B -> M
L -> B
L
-----------
therefore M

Now, let's use Chain of Reasoning to prove that with the stated facts, Martha is sure to make a salad.
Reason
1. B->M Premise
2. L->B Premise
3. L Premise
4. B Modus Ponens ( 2,3)
5. M Modus Ponens (4,1)
We now reach M which is the conclusion. This will be the end of our proof.

Another possible solution could appear like this:

Reason
1. B->M Premise
2. L->B Premise
3. L Premise
4. L->M Hypothetical Syllogism (Transitivity) (2,1)
5. M Modus Ponens ( 3,4)
End of Proof...


The first three reasons are the premises. Stating them is necessary because the succeeding steps can only be done by manipulating them (using the rules of logic and inference).

The other reasons such as Modus Ponens and Transitivity may sound foreign or vague to you
at present. I shall talk about them in my next blog. See you then :)