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.


Apart from true tables.

  • $\begingroup$ Fill a truth table, it takes 10 seconds. $\endgroup$ – Yves Daoust Oct 31 '15 at 22:50
  • $\begingroup$ Not allowed to use truth tables, sadly. That's too easy. $\endgroup$ – Mathy Oct 31 '15 at 22:51
  • $\begingroup$ 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. $\endgroup$ – MarnixKlooster ReinstateMonica Nov 1 '15 at 6:48

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$.
  • $\begingroup$ 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? $\endgroup$ – Mathy Oct 31 '15 at 23:09
  • 1
    $\begingroup$ Yes. $(x \rightarrow y) \wedge (y \rightarrow x)$ is the definition of $x\equiv y$. $\endgroup$ – YoTengoUnLCD Oct 31 '15 at 23:11
  • $\begingroup$ ohhh, I see now. thanks so much! $\endgroup$ – Mathy Oct 31 '15 at 23:13
  • $\begingroup$ Yeah haha! thanks :) $\endgroup$ – Mathy Oct 31 '15 at 23:15
  • 1
    $\begingroup$ @YoTengoUnLCD or one possible definition. Another useful one is $(x\wedge y) \vee (\neg x \wedge \neg y)$. $\endgroup$ – BrianO Oct 31 '15 at 23:16

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


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

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

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.