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'm having a bit of a hard time understanding logic and truth tables.

Determine whether the first formula logically implies the second or the second logically implies the first, or both, or neither.

~p -> (q ^ p) and (p ^ q) -> q (note: '->' means 'implies')

Firstly, I use the commutative law so (q ^ p) <=> (p ^ q) and hence ~p -> q.

Then I construct my truth table:

| p | q | ~p | ~p->q |
| T | T |  F |   T   |
| T | F |  F |   T   |
| F | T |  T |   T   |
| F | F |  T |   F   |

From the table how do I show that it logically implies or not?

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

One way to check whether a formula $A$ implies another $B$ is to check whether $A \to B$ is a tautology.

Let $A = \lnot p \to (q \land p)$, and $B = (p \land q) \to q$.

Constructing the truth table for the first case, $A \to B$, we see:

p | q |  (¬p -> q ^ p) -> (p ^ q -> q)
T | T | T
T | F | T
F | T | T
F | F | T

We see that $A \to B$ is true for all values of $p$ and $q$, and therefore it is a tautology. Hence, $A$ does imply $B$.

Constructing the truth table for the second case, $B \to A$, we see:

p | q | (p ^ q -> q) -> (¬p -> q ^ p)
T | T | T
T | F | T
F | T | F
F | F | F

We see that there are values of $p$ and $q$ for which $B \to A$ is not true, and therefore it not a tautology. Hence, $B$ does not imply $A$.

Thus, $\lnot p \to (q \land p)$ implies $(p \land q) \to q$, but $(p \land q) \to q$ does not imply $\lnot p \to (q \land p)$.

share|cite|improve this answer
Okay, we simply show for both directions. Thanks! – meiryo Apr 30 '11 at 7:06
@meiryo -- Yep! A good resource for learning how to compute complex truth tables is:… (see the example near the bottom of the page). – dsg Apr 30 '11 at 7:11

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.