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$

  1. 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.

  1. 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.

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

  1. 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.

  1. While the contrapositive $\neg Q \Rightarrow \neg P$ is clearly equivalent to $P \Rightarrow Q$, neither $P \wedge Q$ nor $[P \wedge (P \Rightarrow Q)] \Rightarrow Q$ is equivalent. The only case in which $P \Rightarrow Q$ is false is when $P$ is true and $Q$ is false. The only case when $P \wedge Q$ is true is when both $P$ and $Q$ are true. Finally, $[P \wedge (P \Rightarrow Q)] \Rightarrow Q$ is always true. On the other hand, $\neg P \vee Q$ is equivalent to $P \Rightarrow Q$.

  2. The statement $\neg(P \Rightarrow Q)$ is equivalent to $\neg(\neg P \vee Q)$, which is equivalent to $P \wedge \neg Q$. It is not equivalent to $P \Rightarrow \neg Q$, which is equivalent to $\neg P \vee \neg Q$.

  3. $P \vee Q$ is, however, equivalent to $\neg P \Rightarrow Q$ as well as $\neg Q \Rightarrow P$.

  4. Yes, those are the two tautologies.

The one rule that will likely help you the most is the one that establishes the equivalence of $x \Rightarrow y$ and $\neg x \vee y$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.