Results 1 to 2 of 2

Math Help - Boolean algebra question

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello jonnyrex
    Quote Originally Posted by jonnyrex View Post
    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 \Rightarrow

    (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 \subseteq


    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] boolean algebra help
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 10th 2011, 02:06 PM
  2. [SOLVED] Boolean Algebra
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: December 7th 2010, 06:12 PM
  3. Boolean Algebra Help
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 3rd 2010, 04:16 AM
  4. Boolean algebra Help
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: January 11th 2010, 01:15 PM
  5. Boolean Algebra
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 16th 2009, 08:46 AM

Search Tags


/mathhelpforum @mathhelpforum