Thread: Showing a formula is a tautology

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!

Originally Posted by Diligo

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 .

The implication is a tautology, but the biconditional is not: consider R = False and Q = True.

I've made an error while typing this, wherever you see it should read . But I'm unable to edit my post

In calculus, a function f is called monotonic if x <= y implies f(x) <= f(y) for all x, y. Monotonicity in Boolean logic is the same as monotonicity of functions when Boolean formulas are considered as expressions defining function from {0, 1} to {0, 1}, where 0 represents False and 1 represents True. For example, P /\ R defines the function min(P, R). If we keep R constant, this function is monotonic in P, i.e., if P <= Q, then min(P, R) <= min(Q, R).

I believe your solution to the first problem makes sense. However, your method is a curious mix of using equivalences and logical implications. Why do you convert some => into disjunctions but other => into |=? Are you required to use this method?

I personally try not to convert P => Q into ~P \/ Q. Here is how to show R /\ (P => Q) => (R => P) => Q treating implication as "if ... then ...". Assume (1) R, (2) P => Q and (3) R => P. From (3) and (1) we get P, and from it and (2) we get Q, as required. The second formula can be proved in a similar way.

Well basically in this part of the course we are required to use these steps, the second part is more about reasoning, more in line with your method

We're using this book Logical Reasoning: A First Course: R Nederpelt,F Kamareddine: 9780954300678: Amazon.com: Books the methods it teaches seem to be pretty tied to Dijkstra's/specific methods.