1
$\begingroup$

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?

1 Answers 1

4

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)$.

  • 1
    @meiryo -- Yep! A good resource for learning how to compute complex truth tables is: http://en.wikibooks.org/wiki/Formal_Logic/Sentential_Logic/Truth_Tables (see the example near the bottom of the page).2011-04-30