I'm currently enrolled in a introductory course on logic and I'm until now everything has been going great. I'm having some trouble with applying monotonicity and the strengthening/weakening of propositions.
The general of concept of strengthening/weakening seems clear; I understand is a stronger proposition than , so: , 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 , then . 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 is a tautology. To do this I have to show that .
Using some basic calculation/rewriting rules for implication, de Morgan and double negation, I ended up here:
Now it gets messy, but by applying distribution to the left hand side twice I end up with this:
Since the basic rules of strengthening\weakening tell us that , we also have that .
By applying weakening to: , we have that: , which is what we wanted.
Now, for me this makes sense, but is this actually correct?
Edit: I'd like to add another exercise I'm not quite sure of, since it seems to be a bit harder.
Show that: is a tautology. Again, to show this the left hand side should equal the right hand side.
First step is rewriting the implications:
By weakening we now have:
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!