# Showing a formula is a tautology

• Oct 7th 2012, 03:40 AM
Diligo
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 $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)) \equiv((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)) \equiv (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) \equiv (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) \equiv (Q \lor (R \land \lnot P))$, we have that: $((R \land \lnot P) \lor Q) \equiv (Q \lor (R \land \lnot P))$, which is what we wanted.

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

Edit: I'd like to add another exercise I'm not quite sure of, since it seems to be a bit harder.

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 equal the right hand side.

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

By weakening we now have:
$(\lnot P \lor (Q \lor R) \equiv (\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!
• Oct 8th 2012, 05:18 AM
emakarov
Re: Showing a formula is a tautology
Quote:

Originally Posted by Diligo
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)) \equiv((R \Rightarrow P) \Rightarrow Q)$.

The implication is a tautology, but the biconditional is not: consider R = False and Q = True.
• Oct 8th 2012, 05:40 AM
Diligo
Re: Showing a formula is a tautology
I've made an error while typing this, wherever you see $\equiv$ it should read $\models$. But I'm unable to edit my post :(
• Oct 8th 2012, 12:33 PM
emakarov
Re: Showing a formula is a tautology
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.
• Oct 10th 2012, 04:19 AM
Diligo
Re: Showing a formula is a tautology
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.