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!

  • $\begingroup$ 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$? $\endgroup$ – Johannes Kloos Oct 8 '12 at 12:36
  • $\begingroup$ I think I see this yes, with some help of truth tables... $\endgroup$ – DiligoDiligentia Oct 9 '12 at 14:34
  • $\begingroup$ In that case, note that you can equally well prove the initial assertion using truth tables... $\endgroup$ – Johannes Kloos Oct 9 '12 at 15:46
  • $\begingroup$ Good point actually ^^ $\endgroup$ – DiligoDiligentia Oct 10 '12 at 10:46

Why don't you use the table as follows. I think it is easy to understand:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.