Cheap and Secure Web Hosting Provider : See Now

[Solved]: Prove that $\neg 0 = 1$

, , No Comments
Problem Detail: 

Starting from this definition https://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29#Definition, is the following a valid proof that $\neg 0 = 1$?

Instantiate a ∨ ¬a = 1 with a:=0 to get 0 ∨ ¬0 = 1 Then use pattern matching (and commutativity) against a ∨ 0 = a to get a = ¬0 on the LHS and a=1 on the RHS, thus ¬0 = 1.

To clarify the "pattern matching": We have

  • 0 ∨ ¬0 = 1
  • 0 ∨ 1 = 1 (from 0 ∨ a = a)
  • 0 ∨ 0 = 0 (also from from 0 ∨ a = a)

If there are only the two elements 0 and 1 available, ¬0 = 1 should follow from this. But then again, if it were not true that ¬0 = 1, we would have that ¬0 = 0, which wouldn't make too much sense...

Are there other/simpler proofs?

Asked By : Jasper

Answered By : David Richerby

It's a valid proof in the sense that it convinces an appropriately skeptical reader that $\neg 0 = 1$. The argument is as follows.

  1. By an axiom $0\vee \neg 0 = 1$.
  2. We know that either $\neg0=0$ or $\neg0=1$.
  3. We can't have $\neg0=0$ because $0\vee0=0$.
  4. So it must be the case that $\neg0=1$.
  5. Actually, let's check that: $0\vee 1=1$. Good.

However, that's not a proof from the axioms. Of the steps that you've used, only 1 is actually an axiom.

Step 2 is the law of excluded middle, which isn't actually one of the axioms. If you think about it, it's not actually obvious that every formula evaluates to exactly one of 0 and 1 (in particular, there are no formulae that evaluate to both 0 and 1, and none that evaluate to either). The law of excluded middle can be proven from the axioms but it's not an axiom.

Step 3 uses an axiom ($a\vee0=a$ instantiated with $a=0$) to deduce that $0\vee 0=0$ but there's no axiom that says you can use this to conclude that $b\neq 0$ if $a\vee b\neq a$.

Step 4 is restating the law of excluded middle.

In step 5, you could use some axioms to deduce that $0\vee 1=1$ ($0\vee 1 = 1\vee 0 = 1$) but, again, there's no axiom allowing you to draw the ultimate conclusion.

Students often get confused about axiomatic proofs: the usual complaint is "I don't know what I'm allowed to use." Confusion about that is very understandable: you've spent your whole life "knowing" that $\neg0=1$ and treating that as (half of) the definition of negation. If you're not allowed to "know" something as basic as how negation works, what on earth are you allowed to know? (Students have exactly the same problems with elementary group theory.)

For an axiomatic proof, it's actually quite simple: you're allowed to use the axioms, instantiated however you please.1 If you can prove something from the axioms, you're allowed to use that repeatedly, as a lemma: for example, I proved above that $0\vee 1=1$ so you could use that as many times as you want, after proving it once. But that's all.

Alexey Romanov included a proof in his comment to the question. I'll write it out a little more fully.

$$\begin{align*} \neg0 &= \neg0 \vee 0 &\text{($0$ is the identity for $\vee$)}\\ &= 0 \vee \neg0 &\text{(commutativity of $\vee$)}\\ &= 1 &\text{(instantiate $a\vee\neg a=1$ with $a=0$).} \end{align*}$$

Because of the limited resources available to you, axiomatic proofs tend to be rather fiddly and tedious, which is why we don't do them after the first week of the course. Pedagogically, I think it's actually a mistake to start with axiomatic proofs because they confuse the students more than they help. I think it would be better to introduce them later in a course, after the students are already used to proving things.


  1. OK, and transitivity of equality and probably modus ponens. But I'm just putting this here for the experts to think about; for the beginner, this footnote is more likely to confuse than clarify.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35545

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback