# Proof writing involving propositional logic: (x ∨ y) ≡ ( x ∧ y ) → x ≡ y

Prove by using propositional logic:

(x ∨ y) ≡ ( x ∧ y ) → x ≡ y

I'm a bit lost here proving by propositional logic that the statement is valid. I don't know how to start this problem. Any help? I know the statement is true since x ≡ y, thus the premise (x ∨ y) ≡ ( x ∧ y ) does not matter, it will be still true according to the → operation. Any ideas? Any help will be greatly appreciated, thanks.

Edit:

Apart from true tables.

• Fill a truth table, it takes 10 seconds. – Yves Daoust Oct 31 '15 at 22:50
• Not allowed to use truth tables, sadly. That's too easy. – Mathy Oct 31 '15 at 22:51
• Note that the other direction $\;\leftarrow\;$ is trivially true, and that $\;\equiv\;$ is associative, and therefore we have $$x \lor y \;\equiv\; x \land y \;\equiv\; x \;\equiv\; y$$ which Edsger W. Dijkstra et al. called the "golden rule" (source: Dijkstra and Scholten, Predicate Calculus and Program Semantics, page 37). It is really quite versatile, given that $\;\equiv\;$ is not only associative but also symmetric. – MarnixKlooster ReinstateMonica Nov 1 '15 at 6:48

## 2 Answers

You want to show that $x \equiv y$ from the premise $(x\vee y) \equiv (x \wedge y)$. I assume it's enough to derive $(x\to y) \wedge (y \to x)$.

1. $(x\vee y) \equiv (x \wedge y) \qquad \text{(premise)}$
2. Assume $x \qquad\qquad \text{(assumption)}$
3. $x \vee y \qquad\qquad\qquad \text{by$p \to (p \vee q)$}$
4. $x \wedge y\qquad\qquad\qquad \text{by 1.}$
5. $y \quad\qquad\qquad\qquad \text{by$(p\wedge q) \to q$}$
6. $x \to y \quad\qquad\qquad \text{by 2. and 5., discharging 2.}$
7. -- 11. similarly derive $y \to x$.
• I like the step-by-step explanation, thanks but I'm a bit still confused. So we have to show that (x→y) and (y→x) by the premise, thus that proves that the statement is valid? – Mathy Oct 31 '15 at 23:09
• Yes. $(x \rightarrow y) \wedge (y \rightarrow x)$ is the definition of $x\equiv y$. – YoTengoUnLCD Oct 31 '15 at 23:11
• ohhh, I see now. thanks so much! – Mathy Oct 31 '15 at 23:13
• Yeah haha! thanks :) – Mathy Oct 31 '15 at 23:15
• @YoTengoUnLCD or one possible definition. Another useful one is $(x\wedge y) \vee (\neg x \wedge \neg y)$. – BrianO Oct 31 '15 at 23:16

$$a\equiv b=ab+\overline a\overline b$$

Then

$$(x+y)(xy)+\overline{(x+y)}\overline{xy}=xy+\overline x\overline y(\overline x+\overline y)=xy+\overline x\overline y.$$

• Sorry what identity is that? what does "--" above a and b stand for? – Mathy Oct 31 '15 at 22:59
• I don't thank the anonymous downvoter. – Yves Daoust Nov 1 '15 at 10:50
• The overbar is negation in Boolean arithmetic notation. – Yves Daoust Nov 1 '15 at 10:51