Tuesday 29 January 2013

discrete mathematics - 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.


Answer



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$.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...