Proof of the three constraintsOur task is to prove the following, for all a and b belonging to a Boolean Algebra K: (a')' = a wrap The following lemma will prove useful: Lemma 1: If a∧b = 0 and a∨b = 1 then b = a'. Proof: b = b∧1 (unit) Similarly, a' = a'∧1 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 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) 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')) (ii) (a∧b)∨(a'∨b') = ((a∧b)∨a')∨b' We can now prove Copy: a∧(a∧b)' = a∧b'. Proof: a∧(a∧b)' = a∧(a'∨b') (Lemma 5)
back to Boolean Algebras on to Finite Boolean Algebras |