0
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ For me, pattern matching is weird here. It is not an axiom. $\endgroup$ – hengxin Dec 20 '14 at 11:08
  • $\begingroup$ You can first prove the DeMorgan's law. $\lnot 0 = 1 \Leftrightarrow \lnot (a \land \lnot a) = \lnot a \lor a$. However, this cannot be the simple one. $\endgroup$ – hengxin Dec 20 '14 at 11:42
  • 2
    $\begingroup$ Instead of "pattern matching", I'd just say $¬0 = ¬0 ∨ 0 = 0 ∨ ¬0 = 1$. I don't think there is a simpler proof, since it must involve one of the two negation axioms, and they don't give the result immediately. $\endgroup$ – Alexey Romanov Dec 20 '14 at 12:12
  • $\begingroup$ That's it, thanks! I guess what you call "negation axioms" are the "complements" on wikipedia? $\endgroup$ – Jasper Dec 20 '14 at 12:19
2
$\begingroup$

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

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.