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’)
- Presburger arithmetic
- What is finite in a finite model
- Difference between elementary logic and formal logic
- Decidability of the Riemann Hypothesis vs. the Goldbach Conjecture
- Is it possible to iterate a function transfinite times?
- Does elementary embedding exist between two elementary equivalent structures?
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?
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)$.