Results 1 to 9 of 9
Like Tree3Thanks
  • 2 Post By Deveno
  • 1 Post By Deveno

Math Help - Boolean Algebra

  1. #1
    Super Member
    Joined
    Sep 2013
    From
    Portland
    Posts
    539
    Thanks
    73

    Boolean Algebra

    This question seems easy enough but I want to make sure

    Q) Use the definition of a Boolean Algebra to give reasons for each step in the proof below:

    \forall a \in B, a \cdot a = a

    Proof:

    Let a be any element of B, then

    \begin{array}{cc} a = a \cdot 1 \\=a \cdot (a + \bar{a})\\=(a\cdot a)+(a \cdot \bar{a} \\ =(a \cdot a) + 0 \\ =a \cdot a\end{array}

    first step. a \cdot 1 is like saying a and 1

    second step  1 = a + \bar{a} so we get a \cdot (a + \bar{a})

    third step is distributive, the + is similar to an 'or' in logic

    fourth step  a \cdot \bar{a} = 0 similar to a set and its complement yield the empty set

    fifth step is the left over  a \cdot a which is similar to a set intersect itself
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,449
    Thanks
    1864

    Re: Boolean Algebra

    The problem said "Use the definition of Boolean Algebra" and you never stated what that definition is.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Boolean Algebra

    This is the definition I learned:

    A Boolean algebra is a set $B$, along with two (binary) operations + and $\cdot$, and a unary operation $a \to \overline{a}$ (called complementation), along with two distinguished elements $0,1 \in B$ such that:

    A1) $a + (b + c) = (a + b) + c$, for all $a,b,c \in B$

    A2) $a + b = b + a$, for all $a,b \in B$

    A3) $a\cdot (b\cdot c) = (a\cdot b)\cdot c$, for all $a,b,c \in B$

    A4) $a\cdot b = b\cdot a$ for all $a,b \in B$

    A5) $a \cdot (b + c) = (a\cdot b) + (a\cdot c)$, for all $a,b,c \in B$

    A6) $a + (b\cdot c) = (a + b)\cdot (a+c)$, for all $a,b,c \in B$

    A7) $a + 0 = a$, for all $a \in B$

    A8) $a \cdot 1 = a$, for all $a \in B$.

    A9) $a + \overline{a} = 1$, for all $a \in B$.

    A10) $a \cdot \overline{a} = 0$, for all $a \in B$.

    Thus:

    $a = a\cdot 1$ (A8)

    $= a \cdot (a + \overline{a})$ (A9)

    $= (a \cdot a) + (a\cdot\overline{a})$ (A5)

    $= (a \cdot a) + 0$ (A10)

    $= a \cdot a$ (A7)

    Note that EVERY SINGLE STEP is justified by one of the axioms A1-A10, and not by saying, "this is just like in sets, where we have..."

    This is what you do in a formal proof, as opposed to an "informal argument" (which may indicate the same line of reasoning).
    Thanks from Jonroberts74 and topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2013
    From
    Portland
    Posts
    539
    Thanks
    73

    Re: Boolean Algebra

    I have a list of properties, those properties are what I was told to use as the definition.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Boolean Algebra

    Your job, then, is to see which of my A1-A10 match up with your list of properties, hmm?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Sep 2013
    From
    Portland
    Posts
    539
    Thanks
    73

    Re: Boolean Algebra

    my list of properties is shorter not sure why but yes I will match them up. Next time I will put my more formal version up as opposed to my side work.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Boolean Algebra

    Well, I think I understood your reasoning, but instructors can be nit-picky about these things. They want you to get in the habit of being able to get "more formal" if you need to.

    The reason for this is: when we "think" in our heads, we often "skip ahead", due to "having seen this sort of thing before". Sometimes, that can lead to overlooking a minor detail, which possibly might "ruin everything" (like if we divide by 0 in doing calculations).

    A formal proof, by contrast, is "air-tight", and there is no arguing with it, unless you want to "abolish the rules of the game" (change the definitions).
    Thanks from Jonroberts74
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie Vakarian's Avatar
    Joined
    Sep 2014
    From
    Oklahoma
    Posts
    10

    Re: Boolean Algebra

    I tried to master boolean but I failed even though I found few helpful webpages on the way. I seriously admire those that can go through it smoothly like Deveno I will post the links although feel free to move me to a different spot if there is a room for it somewhere else

    "The most obvious way to simplify Boolean expressions is to manipulate them in the same way as normal algebraic expressions are manipulated. With regards to logic relations in digital forms, a set of rules for symbolic manipulation is needed in order to solve for the unknowns.
    A set of rules formulated by the English mathematician George Boole describe certain propositions whose outcome would be either true or false. With regard to digital logic, these rules are used to describe circuits whose state can be either, 1 (true) or 0 (false). In order to fully understand this, the relation between the AND gate, OR gate and NOT gate operations should be appreciated. A number of rules can be derived from these relations as Table 1 demonstrates.
    P1: X = 0 or X = 1
    P2: 0 . 0 = 0
    P3: 1 + 1 = 1
    P4: 0 + 0 = 0
    P5: 1 . 1 = 1
    P6: 1 . 0 = 0 . 1 = 0
    P7: 1 + 0 = 0 + 1 = 1

    Resources:
    Elements of Boolean Algebra
    Boolean Algebra -- from Wolfram MathWorld
    Boolean Algebra - body, used, form, system, Applications
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,449
    Thanks
    1864

    Re: Boolean Algebra

    In other words, where in your first step you say " a\cdot 1 is like saying a and 1" (which, frankly makes no sense to me) you can cite Deveno's "A8" which says that a\cdot 1= a for all a\in B"
    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, 03:06 PM
  2. Boolean algebra Help
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: January 11th 2010, 02:15 PM
  3. Boolean algebra help
    Posted in the Math Topics Forum
    Replies: 6
    Last Post: November 21st 2009, 02:50 PM
  4. Boolean algebra help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 20th 2009, 05:13 AM
  5. Boolean Algebra
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2008, 08:55 AM

Search Tags


/mathhelpforum @mathhelpforum