4

I got stuck on this development:

$$\begin{align} (¬P ∧ Q) ∨ (P ∧ ¬Q) & \iff ((¬P ∧ Q) ∨ P) ∧ ((¬P ∧ Q) ∨ ¬Q) \tag{1} \\ &\iff (P ∨ Q) ∧ (¬P ∨ ¬Q) \tag{2} \\ \end{align}$$

Can't this also be written as this using the associative and tautology Rules?

$$\begin{align} (¬P ∧ Q) ∨ (P ∧ ¬Q) & \iff ((¬P ∧ Q) ∨ P) ∧ ((¬P ∧ Q) ∨ ¬Q) \tag{1'} \\ &\iff (Q ∧ (¬P ∨ P)) ∧ (¬P ∧ (Q ∨ ¬Q)) \tag{2'} \\ &\iff (Q ∧ ¬P) \tag{2'} \\ \end{align}$$ Is this correct?

Bruno Bentzen
  • 3,362
Lukas Arvidsson
  • 2,376
  • What are you trying to do? – hmakholm left over Monica Jun 16 '15 at 21:40
  • Hi, I am just trying to see if I can simplify the original statement. – Lukas Arvidsson Jun 16 '15 at 21:45
  • Your original statement just means that exactly one of $P$ and $Q$ is true. You can write that in different ways, but none is much simpler than what you have. Maybe the simplest is $\neg(P \leftrightarrow Q)$. Or you may like $\neg\left((P \wedge Q) \vee (\neg P \wedge \neg Q)\right)$. – mjqxxxx Jun 16 '15 at 21:50
  • Hmm I don't understand, am I using the associativity and tautology rules incorrect? – Lukas Arvidsson Jun 16 '15 at 21:51
  • Is that '=>' operator an implication or does it denote equivalence? – Max Herrmann Jun 16 '15 at 21:54
  • Thank you for your comments! Ok I understand, but then information was lost along the way... I didn't think using the rules would be "destructive"... Clearly something I have not understood :) – Lukas Arvidsson Jun 16 '15 at 21:55
  • It was meant to imply equivalence, sorry for the confusion. – Lukas Arvidsson Jun 16 '15 at 21:57
  • Associativity applies when both operators are the same. For a mixed expression like $p \vee (q \wedge r)$, you need distributivity instead. Specifically, $p \vee (q \wedge r)$ is equivalent to $(p \vee q) \wedge (p \vee r)$. Also, $p \wedge (q \vee r) \iff (p \wedge q) \vee (p \wedge r)$. – mjqxxxx Jun 16 '15 at 21:58

3 Answers3

3

$(\neg P\land Q)\lor(P\land\neg Q)$ is not equivalent to $Q\land \neg P$ -- for example when $Q$ is false and $P$ is true, the former is true and the latter is false.

It looks like you've been fooled into thinking that $(A\land B)\lor C$ is the same as $A\land(B\lor C)$. This is not the case. For example, when $C$ is true but $A$ and $B$ are false, $(A\land B)\lor C$ will be true but $A\land(B\lor C)$ will be false.

$\land$ is associative by itself, and $\lor$ is associative by itself, but they don't associate with each other.

hmakholm left over Monica
  • 286,031
2

The statement means: “$P$ or $Q$, the ‘or’ being exclusive,” or “exactly one of $P$ and $Q$.” This is the same as “$P$ or $Q$, but not both:” $$(P\vee Q)\wedge\lnot (P\wedge Q).$$

triple_sec
  • 23,377
0

In this case, you can tell directly by looking at the form of the formula in question that it cannot be simplified in the way you're looking for: it is already "maximally simple" in the sense that it is in disjunctive normal form. A propositional formula with k variables $P_1, \ldots, P_k$ has a unique representation as a disjunction of 0 or more subformulas of the form $(\neg)^{\pm 1}P_1 \wedge \cdots \wedge (\neg)^{\pm 1}P_k$, where $(\neg)^{\pm 1}P$ can either be $P$ or $\neg P$.

Dorebell
  • 4,154