Proof of the three constraints

Our task is to prove the following, for all a and b belonging to a Boolean Algebra K:

(a')' = a    wrap
a∧1' = a    delete
a∧b' = a∧(a∧b)'    copy

The following lemma will prove useful:

Lemma 1: If a∧b = 0 and a∨b = 1 then b = a'.

Proof:

b = b∧1     (unit)
= b∧(a∨a')     (complements)
= (b∧a) ∨ (b∧a')     (distribution)
= 0 ∨ (b∧a')     (premise)
= b∧a'     (zero)

Similarly,

a' = a'∧1
= a'∧(a∨b)
= (a'∧a) ∨ (a'∧b)
= 0 ∨ (a'∧b)
= a'∧b
= b∧a'.

Therefore, b=a', since they are both equal to b∧a'.

We can now prove

Wrap: (c')'=c

Proof: Because c'∧c=0, c'∨c=1, the premises of Lemma 1 are satisfied, with a = c' and b = c. Therefore, c = (c')'.

Some more lemmas:

Lemma 2: 1'=0

Proof: apply Lemma 1 to 1 and 0.

Lemma 3: a = a∧a

Proof:

a = a ∧1
= a ∧ (a∨a')
= (a∧a) ∨ (a∧a')
= (a∧a) ∨ 0
= a∧a .

Lemma 3B: a = a∨a

Proof: essentially the same as the proof of Lemma 3.

We can now prove

Delete: a∧1' = 1'

Proof:

a∧1' = a∧0 (Lemma 2)
= a∧(a∧a')
= (a∧a)∧a'
= a∧a' (Lemma 3)
= 0
= 1' .

Lemma 4: a∨1 = 1.

Proof: essentially the same as the proof of delete, but using Lemma 3B, and with ∨ everywhere replacing ∧, and 1 replacing 0, and vice versa.

Lemma 5: (a∧b)' = a' ∨ b'.

Proof: we show that a∧b, a'∨b' satisfy the premises of Lemma 1, and are therefore complements.

(i)

(a∧b)∧(a'∨b') = a∧(b∧(a'∨b'))
= a∧((b∧a') ∨ (b∧b'))
= a∧((b∧a') ∨ 0)
= a∧(b∧a')
= (a∧a')∧b
= 0∧b
= 0.

(ii)

(a∧b)∨(a'∨b') = ((a∧b)∨a')∨b'
= ((a∨a')∧(b∨a'))∨b'
= (1 ∧ (b∨a'))∨b'
= (b∨a')∨b'
= (b∨b')∨a'
= 1∨a'
=1 (Lemma 4).

We can now prove

Copy: a∧(a∧b)' = a∧b'.

Proof:

a∧(a∧b)' = a∧(a'∨b') (Lemma 5)
= (a∧a') ∨ (a∧b')
= 0 ∨ (a∧b')
= a∧b'.