# Showing a formula is a tautology

I'm currently enrolled in a introductory course on logic and until now everything has been going great. I'm having some trouble with applying monotonicity and the strengthening/weakening of propositions though.

The general of concept of strengthening/weakening seems clear; I understand $P \land Q$ is a stronger proposition than $P\lor Q$, so: $P \land Q \models P \lor Q$ , since the former has 'less 1s' in its truth table it's a stronger/more restrictive proposition.

Monotonicity is a bit foggier. How I see it, is that it's basically a form of substitution if we have $P \models Q$, then $P \land R \models Q \land R$ . If we substitute the left hand side with the 'same thing' we substitute the right hand side with, the relation with respect to stronger/weaker holds. Any more clarification on this subject is more than welcome.

So much for theory. Now I'm asked to show via a calculation that $(R \land (P \Rightarrow Q)) \Rightarrow ((R \Rightarrow P) \Rightarrow Q)$ is a tautology. To do this I have to show that $(R \land (P \Rightarrow Q)) \models((R \Rightarrow P) \Rightarrow Q)$.

Using some basic calculation/rewriting rules for implication, de Morgan and double negation, I ended up here: $(R \land (\lnot P \lor Q)) \models (Q \lor (R \land \lnot P))$.

Now it gets messy, but by applying distribution to the left hand side twice I end up with this: $((R \land \lnot P) \lor R) \land ((R \land \lnot P) \lor Q) \models (Q \lor (R \land \lnot P))$.

Since the basic rules of strengthening\weakening tell us that $P \land Q \models P$, we also have that $((R \land \lnot P) \lor R) \land ((R \land \lnot P) \lor Q) \models (Q \lor (R \land \lnot P))$.

By applying weakening to: $((R \land \lnot P) \lor R) \land ((R \land \lnot P) \lor Q) \models (Q \lor (R \land \lnot P))$, we have that: $((R \land \lnot P) \lor Q) \models(Q \lor (R \land \lnot P))$, which is what we wanted.

Now, for me this makes sense, but is this actually correct?

Another question along these lines:

Show that: $((P \Rightarrow (Q \lor R)) \land (Q \Rightarrow R)) \Rightarrow (P \Rightarrow R)$ is a tautology. Again, to show this the left hand side should be stronger than the right hand side.

First step is rewriting the implications: $((\lnot P \lor (Q \lor R)) \land (\lnot Q \lor R)) \models (\lnot P \lor R)$

By weakening we now have: $(\lnot P \lor (Q \lor R) \models (\lnot P \lor R)$

But I'm kind of stuck here. I could distribute and apply strengthening, but I'm not sure that would be legal. Any help would be welcome!

• Since I do not know which manipulation rules you already know, I won't give an answer yet. Do you know (or better, see why) $P \wedge Q \models R$ if and only if $P, Q \models R$? In this case, you arrive quickly at $R, P \Rightarrow Q \models (R \Rightarrow P) \Rightarrow Q$. Also, do you know that $P \models Q \Rightarrow R$ iff $P, Q \models R$? Oct 8, 2012 at 12:36
• I think I see this yes, with some help of truth tables... Oct 9, 2012 at 14:34
• In that case, note that you can equally well prove the initial assertion using truth tables... Oct 9, 2012 at 15:46
• Good point actually ^^ Oct 10, 2012 at 10:46 