Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.