Thread: Boolean algebra question

Suppose (b,∧,V,¬) is a boolean algebra.
1) Define a relation ≤ on B by a ≤ b iff a = a ∧ b.
2) show that a = a ∧ b iff b = a V b
3) Prove that ≤ is a partial order on the set B and that 0≤a≤1 for all a EB
4) What is the relation ≤in the case that B is a boolean algebra (B,intersection,U,compliment) of sets?
thanks in advance

Hello jonnyrex

Originally Posted by jonnyrex

Suppose (b,∧,V,¬) is a boolean algebra.
1) Define a relation ≤ on B by a ≤ b iff a = a ∧ b.
2) show that a = a ∧ b iff b = a V b
3) Prove that ≤ is a partial order on the set B and that 0≤a≤1 for all a EB
4) What is the relation ≤in the case that B is a boolean algebra (B,intersection,U,compliment) of sets?
thanks in advance

Welcome to Math Help Forum!

To make it easier to type, I'm going to use

• ab to represent a ∧ b
• a + b to represent a V b
• a' to represent ¬a
• -> to represent

(2) a = ab

-> ab' = (ab)b'

=a(bb')

=a0

=0

-> (ab')' = (0)'

-> a' + b = 1

-> (a' + b)(a + b) = 1(a + b)

-> (a'a) + b = a + b

-> 0 + b = a + b

-> b = a + b

So (a = ab) -> (b = a + b)

The proof of the reverse implication is just the dual of this:

b = a + b

-> a' + b = a' + (a + b)

= (a + a') + b

= 1 + b

= 1

-> (a' + b)' = (1)'

-> ab' = 0

-> ab' + ab = 0 + ab

-> a(b' + b) = ab

-> a1 = ab

-> a = ab

So (b = a + b) -> (a = ab)

We therefore have (a = ab) <-> (b = a + b)


(3) To prove a partial order we must show:

(a) Reflexivity: a ≤ a. This is trivial, since a = aa

(b) Antisymmetry: (a ≤ b and b ≤ a) -> a = b.

Proof: a ≤ b -> a = ab (1)

b ≤ a -> b = ba = ab = a from (1)

(c) Transitivity: (a ≤ b and b ≤ c) -> a ≤ c

Proof: b ≤ c -> b = bc

a ≤ b -> a = ab = a(bc) = (ab)c = ac

-> a ≤ c


For the second part of (3), we have

0 = 0a -> 0 ≤ a

and 1 = 1 + a -> a ≤ 1

Hence 0 ≤ a ≤ 1


(4) In the case of sets ≤ is simply


Grandad