Deductive Proof - Justify each step with law or inference rule
Matthew Martinez 
My Professor gave me the following:
a) If $P \to Q, \neg R \to \neg Q$, and $P$ then prove $R$.
b) If $P \to (Q\wedge R)$ and $\neg R\wedge Q$ then prove $\neg P$.
I understand how to do truth tables, but we've barely started on using laws and inference rules for proofs. I feel like this hw is a huge leap from what we covered in class, and I don't even know how to begin.
For a, this is what I understand:
Premise: $P \to Q$
Premise: $\neg R \to \neg Q$
Premise: $P$
Conclusion: $R$
Then for b:
Premise: $P \to (Q\wedge R)$
Premise: $\neg R\wedge Q$
Conclusion: $\neg P$
Laws (provided by prof.):
Inference Rules:
2 Answers
$\begingroup$The trick to this is to be very familiar with these laws and inference rules your professor has given you. You need to be able to recognize which rule to apply on the spot and this kind of logical thinking will take lots of practice, especially because there are a lot of laws, but getting the hang of these basic logic skills is crucial to understanding more complicated mathematical proofs later on. Proofs later on will often skip these logical steps and will use all of these rules without even naming them because if they did that, then the proofs would be unnecessarily long. Therefore, you have to be able to manipulate these laws and inference rules very quickly to be able to follow the reasoning of a mathematical proof.
By practicing manipulating these rules for yourself, you'll eventually just get an intuition for following how these complicated logical expressions have certain conclusions by looking at the expressions and manipulating them in your head. It might take a while, but once you get the hang of it, you won't need to look at all of these laws because you'll just be able to see which logical laws apply in a certain situation. I know that when I was learning these rules for the first time, they were very confusing and intimidating, much more than truth tables, but now, I use them all of the time and I think using them is often faster than using truth tables.
However, before you have this intuition on which law to apply, just go through the list and try applying different laws. Try to see which laws work and which laws don't in certain situations. By experimenting with these laws with many, many practice problems, you'll be able to gain an intuition for which laws should be used in which situations.
Problem a:
We have $P$ and $P \implies Q$. Therefore, by Modus Ponens, we know that $Q$.
By Double Negation, we know that from $Q$, we can deduce $\sim \sim Q$.
We have $\sim \sim Q$ and $\sim R \implies \sim Q$. Thus, by Modus Tollens, we have $\sim \sim R$.
By Double Negation, we know that from $\sim \sim R$, we have $R$, concluding the proof.
Problem b:
We have $\sim R \wedge Q$. By Simplification, we thus have $\sim R$.
By Addition, this means we have $\sim R \vee \sim Q$.
By De Morgan's Law, $\sim R \vee \sim Q$ is the same as $\sim (R \wedge Q)$.
By Commutative, this is the same as $\sim (Q \wedge R)$.
Thus, we have $P \implies (Q \wedge R)$ and $\sim (Q \wedge R)$. Therefore, by Modus Tollens, we have $\sim P$, concluding the proof.
$\endgroup$ $\begingroup$You missed a few steps, and those are what you are asked to show.
$\boxed{\begin{array}{r|c:l c} \text{Line} & \text{Statement} & \text{Justification} & \text{Notes} \\\hline 1 & P\to Q & \textsf{Premise 1} \\ 2 & \neg R\to \neg Q &\textsf{Premise 2} \\ 3 & P & \textsf{Premise 3} \\ \hdashline 4 & Q & \textsf{Modus Ponens, 1, 3} & P{\to}Q,\, P \vdash Q \\ 5 & \neg\neg Q & \textsf{Double Negation, 4} & \neg\neg Q\dashv\vdash Q \\ 6 & \neg\neg R &\textsf{Modus Tollens, 2, 5}& \neg R{\to}\neg Q,\, \neg\neg Q \vdash \neg\neg R \\ \hline \Box & R & \textsf{Double Negation, 6} & \neg\neg R\dashv\vdash R \end{array}}$
In short, you take your premises, look for any equivalences or rules of inferences whose pattern they can match, then substitute and obtain the result.
$\endgroup$ 2
