I apologize for this bulky, cumbersome post but in reviewing for a proofs midterm I have tomorrow I was asked some questions on logical equivalence and tautologies that I want to make sure I understand.
We're asked to consider the following statements:
a) $P \land Q$
b) $P\land\neg Q$
c) $\neg P\land Q$
d) $\neg P\land\neg Q$
e) $P\land\neg P$
f) $P\lor Q$
g) $P\lor\neg Q$
h) $\neg P\lor Q$
i) $\neg P \lor \neg Q$
j) $P\lor \neg P$
k) $P\Rightarrow Q$
l) $P\Rightarrow \neg Q$
m) $\neg Q\Rightarrow P$
n) $\neg P \Rightarrow \neg Q$
o) $\neg Q \Rightarrow \neg P$
p) $[P\land(P\Rightarrow Q)]\Rightarrow Q$
q) $[Q\land(P\Rightarrow Q)]\Rightarrow P$
- Find all statements logically equivalent to $P\Rightarrow Q$.
While $P\Rightarrow Q$ and itself are obviously equivalent, its contrapositive version $\neg Q \Rightarrow \neg P$ also works. However, I'm unsure if $P\land Q$ and $[P\land(P\Rightarrow Q)]\Rightarrow Q$ should also be included.
- Find all statements logically equivalent to $\neg(P\Rightarrow Q)$.
I want to say $P\Rightarrow\neg Q$ and $P\land\neg Q$ are equivalence statements but I feel like there may be more.
- Find all statements logically equivalent to $P\lor Q$.
I thought about using a negation of negations via DeMorgan's Laws but no such thing was listed as a possibility, so I can't think of any above statements being equivalent to this one (except itself).
- Which of these are tautologies?
$P\lor\neg P$ is an obvious tautology since $P$ is either true or false.
$[P\land(P\Rightarrow Q)]\Rightarrow Q$ is a tautology because if $P$ implies $Q$ and $Q$ is true, then $P$ must be true.
Again, I'm sorry for how bulky this question is but I need to assure myself that I'm not overlooking any equivalences or tautologies. Thanks for taking the time to read this.