0

I am trying to prove that $\neg 0 = 1$ in every boolean algebra by using the laws of boolean algebra.

The assistant told us to start by using the identity law and form $\neg 0 = 1$ to $\neg 0 = \neg 0 \cdot 1$. However I don't know how to proceed from there.

  • Not sure how the assistant expects you to use the identity law for mutiplication but the indentity law for addition give you $\lnot 0 = \lnot 0 + 0$. And what does $\lnot x + x$ equal? – fleablood Oct 02 '18 at 22:30
  • For $\neg 0 = \neg 0 + 0 = 1$ to be true, then it must be $\neg x + x = 1$. Is that right? –  Oct 03 '18 at 08:41

2 Answers2

1

Identity Law: $\lnot 0 = \lnot0\circ 1$

Double Negation: $\lnot 0 \circ 1 = \lnot 0 \circ \lnot \lnot 1$

De Morgan: $\lnot 0 \circ\lnot \lnot 1 = \lnot(0 + \lnot 1)$

Indentity: $\lnot (0 + \lnot 1) = \lnot \lnot 1$

Double Negation: $\lnot\lnot 1 = 1$.

....

Oh this is better: $\lnot 0 + 0 = 1$ by the complement law.

But $\lnot 0 + 0 = \lnot 0$ by the identity law.

fleablood
  • 124,253
1

Well, think about the defining property of $\neg$ in a Boolean algebra: $$(\neg x)\vee x=1.$$ Taking $x=0$, this gives $(\neg 0)\vee 0=1$.

Now, you know a rule for simplifying expressions of the form $a\vee 0$. Can you see how to use it here to get what you want?

Noah Schweber
  • 245,398
  • I know that $a \vee 0 = a$, so in this case it means that $\neg 0 \vee 0 = \neg 0$ –  Oct 03 '18 at 08:36
  • @exhausend Exactly. So you know $(\neg 0)\vee 0=\neg 0$ as you've just pointed out. But we also already know $(\neg 0)\vee 0=1$ (we got that earlier, from the behavior of "$\neg$"). Putting these together ... – Noah Schweber Oct 03 '18 at 15:07
  • Ahh yes of course, we get to $\neg 0 = 1$. Thank you. –  Oct 03 '18 at 19:21