Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|improve this answer
    
Okay, we simply show for both directions. Thanks! –  meiryo Apr 30 '11 at 7:06
1  
@meiryo -- Yep! A good resource for learning how to compute complex truth tables is: en.wikibooks.org/wiki/Formal_Logic/Sentential_Logic/… (see the example near the bottom of the page). –  dsg Apr 30 '11 at 7:11
add comment

Your Answer

 
discard

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.