# 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?

-

## 1 Answer

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.

-
Okay, I revisited my truth table and you're right, I messed up that part. Turns out I actually know what I'm doing (even if it doesn't feel like I do), I just made a careless mistake. Thanks a ton, Johannes. –  Dave Jan 27 '13 at 10:34
Also, as a supplemental question, was I correct when I determined that it could not be further simplified? –  Dave Jan 27 '13 at 10:35
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
Ah, okay. I actually remember reading that one, but I didn't see how to apply the concept here. I've been rushing to learn enumeration/combinatorics, first-order logic, and set-theoretic concepts. I was given one week to familiarize myself with these concepts and do an assignment that has four questions in each category. I guess I haven't had the time to focus on one concept long enough for everything to stick. This is by far the most difficult course I've ever taken, lol. Thanks again for the help. –  Dave Jan 27 '13 at 11:08