Rules of Inference and Basic Proofs

This is a small add-on to this post Propositional Logic and De Morgans Law Knowledge of this post will be required for understanding this post. I am posting this as a hope that i will remember it for my Discrete Math Final Exam.

A rule of inference: is a rule that can be used in proving a theorem or some logic directly and polished.

Addition:  is you just add another proposition onto it using the Logical OR.


p  = 'The sky is blue" 
p v q = "The sky is blue or red"
                
Simplification: is you just subtract a proposition

p ^ q = 2+2= 4 and grass is green
p = 2+2 = 4

Conjunction: adding two separate propositions together.

p = Grass is green.
q = Rome is in Italy
p^q = "Grass is green and Rome is in Italy".

Modus Ponens: Basically the end result of an implication.

P - > Q = "If I study, then i get an A".
Q = " I studied so i got an A"

Modus Tollens: Basically the opposite of Modus Ponens.

p - > q "If I go to the store, I buy milk"
~p = " I did not go to the store" Which means
~q = " I did not buy milk"

Hypothetical Syllogism: Say this out-loud to sound cool.Visually you can see how this works.

p -> q = "If i study, then i pass."
q - > r = " If i pass then i grad".
Therefore
p -> r = "If i study then i grad".

Resolution:

p v q = " I will study or eat dinner".
~p v r  "I will not study or go to the party"

Therefore
 q v r = " I will eat or go to the party"

Disjunctive Syllogism:

p v q = "I will study or I will eat"
~p = " I do not study"
q = "I will eat"


Basic Proofs:

Proofs usually involve implications.

So two ways of solving these can be

Contra-positive: p -> q this is equivalent to ~q - > ~p. So instead of proving p - > q. we test ~p - > ~q to see if this is true. If it is true then we know p - > q is true.

Example:

If n + 2 is odd, then n is odd.

Suppose that "if n is even, then n + 2 is even"

let n = 2k for some integer k. n + 2 = 2k + 2 = 2(k+1). Clearly 2(k+1) is divisible by two thus making it even. Therefore since the contra-positive is true then p -> q is true.

Contradiction: This is a little more difficult. We want to prove that. p - > q is true and p -> ~q is true.
If both of them is true we go with the original as being true. For clearly both q and ~q cannot be true.

Example:

If n + 2 is odd, then n is odd.

Assume that n is odd. Then n = 2L + 1 for some integer L. So n + 2 = 2L + 3. Which is odd.

Suppose that  If n + 2 is odd, then n is even.

Let n = 2k for some integer k. Then n + 2 = 2k + 2. which means n is even.

Since both is true, clearly if n + 2 is odd then n is odd is true.