0
$\begingroup$

How do I apply Commutivity law to a tautology: $P\lor \neg(P \land Q)$?

I understand the it is $A\lor B = B\lor A$, but how can this apply to the above tautology?

Do I assume $P$ as $A$, and $\neg (P\land Q)$ as $B$?


I just checked the answer, the answer is: $\neg Q \lor \top$. Where did the $\top$ come from?

$\endgroup$
  • $\begingroup$ It depends if you mean commutativity with respect to $\lor$ or with respect to $\land$. $\endgroup$ – Git Gud May 18 '14 at 23:46
  • $\begingroup$ Distribute $\neg$ over $P\land Q$ to find $\top$. $\endgroup$ – Git Gud May 18 '14 at 23:53
  • $\begingroup$ Do you mean P∧~P instead? P∨~(P∧Q) = P∨~P∨~Q, then replace P∨~P with T? $\endgroup$ – user3650172 May 18 '14 at 23:58
  • $\begingroup$ No, the only four possible commutations (there are infinite possibilities, but all of them yield one of these four) are $P\lor \neg (P\land Q), \, P\lor \neg (Q\land P), \, \neg (P\land Q)\lor P, \, \neg(Q\land P)\lor P$. The answer to the second question in your comment is yes. $\endgroup$ – Git Gud May 19 '14 at 0:03
  • $\begingroup$ I see you're a new user. Please read about accepting answers here and here. $\endgroup$ – Git Gud May 19 '14 at 0:04
2
$\begingroup$

You don't simplify the statement using commutativity.

Take the statement: $$P \lor \neg (P \land Q)$$ Apply DeMorgan's Laws: The negation of a conjunction is the disjunction of the negations. $$= P\lor (\neg P \lor \neg Q)$$ Disjunctions are associative. $$= (P\lor \neg P)\lor \neg Q$$ The disjunction of a preposition and its negation is a tautology. $$= {\large\top}\lor \neg Q$$ The disjunction of a tautology and a preposition is a tautology. $$= {\large\top}$$

$\endgroup$
  • $\begingroup$ Does this mean we'll always need to apply DeMorgan's law first then only I can do communtativity and identity law? $\endgroup$ – user3650172 May 19 '14 at 0:46
  • $\begingroup$ @user3650172 It's associativity; but yes, a negation of something in brackets is a strong indication that DeMorgan's Laws will be needed. $\endgroup$ – Graham Kemp May 19 '14 at 0:55

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.