# How to verify if a compound logical statement is a tautology using substitution

I have two examples to figure out, and I've verified the first. The second one is giving me trouble, though. Here is the statement:

$[(p \lor q)\to r] \leftrightarrow [\lnot r \to \lnot(p \lor q)]$

All I've done is substitute $(p \lor q)$ with s, giving me:

$[s\to r] \leftrightarrow [\lnot r \to \lnot s]$

Since I couldn't figure out a way to simplify further, I made a truth table. When I made up a truth table based on this simplified statement, it doesn't seem to be a tautology. When s and r are the same value ($s = 1$ and $r = 1$, for example) then the biconditional ends up being true, but that's not enough for this to be a tautology, is it?

-

The substitution leading to $(s \to r) \leftrightarrow (\neg r \to \neg s)$ is correct, and this formula is a well-known tautology. You are right in saying that it's not enough to consider the case $r = s$; maybe there's an error in your truth table somewhere? It should yield true in every row.
By substitution, no further simplification seems to be possible. You could use some other equivalences, though (e.g., $P \to Q \equiv \neg P \vee Q$), if you know about them. –  Johannes Kloos Jan 27 '13 at 10:56