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$
6
  • $\begingroup$ It depends if you mean commutativity with respect to $\lor$ or with respect to $\land$. $\endgroup$
    – Git Gud
    May 18, 2014 at 23:46
  • $\begingroup$ Distribute $\neg$ over $P\land Q$ to find $\top$. $\endgroup$
    – Git Gud
    May 18, 2014 at 23:53
  • $\begingroup$ Do you mean P∧~P instead? P∨~(P∧Q) = P∨~P∨~Q, then replace P∨~P with T? $\endgroup$ May 18, 2014 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, 2014 at 0:03
  • $\begingroup$ I see you're a new user. Please read about accepting answers here and here. $\endgroup$
    – Git Gud
    May 19, 2014 at 0:04

1 Answer 1

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$
2
  • $\begingroup$ Does this mean we'll always need to apply DeMorgan's law first then only I can do communtativity and identity law? $\endgroup$ May 19, 2014 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$ May 19, 2014 at 0:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .