# Boolean Algebra and proofs

• Feb 2nd 2013, 01:57 AM
lunapt
Boolean Algebra and proofs
Prove using Prove algebraically : 1) x'′⊕ y = x⊕y' = (x⊕y)'
2) x⊕1 = x'
3) x⊕x' = 1
4) (A+B)(A'C'+C)(B'+AC') = A'B (A+B)(A.C+C)(B+AC)=AB
I know x⊕y = xy'+x'y But how do i deal with X'⊕Y? What does that become?
And for 4) I did:
(A+B)[(X+Y)'+C] [B.(AC)']
(A+B)[(A+B)'+C] [(B.(A'+B')]
then what do I do from here?
http://i.imgur.com/CPlRB91.png[/FONT][/COLOR]
Been having trouble solving these questions of my homework. Thank You!
• Feb 2nd 2013, 04:28 AM
jakncoke
Re: Boolean Algebra and proofs
I tried to do the monster one, i have no experience with boolean functions or circuit design but here is what i came up with

if $a_1a_0$ and $b_1 b_0$ represent 2, 2-digit binary numbers, then
addition can be done as follows with the result being $m_2m_1m_0$ a 3 bit binary number

$m_0 = a_0 XOR b_0$
$m_1 = (a_0 AND b_0) XOR (a_1 XOR b_1)$
$m_2 = [(b_0 AND a_0) XOR (a_1 XOR b_1)] OR (a_1 AND b_1)$ (OR $m_2 = m_1 OR (a_1 AND b_1)$

this adds 2 digit binary numbers. I used 3 half adders to get this. I dont know if it could be done more simply

and multiplication can be done by just using the AND operator on every pair you get from this cross product $\{a_0,a_1\} X \{b_0, b_1\}$ and then adding a 2 bit binary to a one bit binary (addition using the above method by using 0 for the leading digit of one 2 bit number).

For ex

11
x 11
-----------
11 ----(save this digit without any operation and add 11 + 01 using the addition method above)
11x (+)
------------
1001
• Feb 2nd 2013, 05:36 AM
jakncoke
Re: Boolean Algebra and proofs
As for

1)

using the OR,AND,NOT def of XOR is the way to go

for example
$\bar{x} \oplus y = \neg{} (\bar{x} \text{ v } y)$ ^ $\neg(\bar{x}$ ^ $y)=$ (take the negation inside) $\neg (x$ ^ $\bar{y})$ ^ $(x$ v $\bar{y})$ = $x \oplus \bar{y}$

2)
$x \oplus \bar{x} = (x$ v $\bar{x} )$ ^ $\neg (x$ ^ $\bar{x} )$ = 1 ^ $\neg 0$ = 1 ^ 1 = 1

3)

$x \oplus 1 = (x$ v $1)$ ^ $\neg (x$ ^ $1) = 1$^ $\neg ( x$ ^ $1) = 1$ ^ $(\neg x$ v $0 )$ = 1 ^ ( $\neg x$) = $\neg x$
• Feb 2nd 2013, 02:05 PM
lunapt
Re: Boolean Algebra and proofs
thank you, you are a beautiful human being.

How would I solve this question?
imgur: the simple image sharer

I tried and got to:
(A+B)[(A+C)' +C) [(B.A'+C')]

This pic is also part of the "monster question" that I forgot to attach.
Absolutely no idea how to take this, I shouldn't have taken an intro online course.. ><
imgur: the simple image sharer
• Feb 2nd 2013, 02:49 PM
jakncoke
Re: Boolean Algebra and proofs
Alrighty.

So for that problem
I rewrote is as $(A+B)(\bar{A}\bar{C} + C) \neg{ (\bar{B} + AC)}$ Now i can rewrite the last term in parenthesis as $(B\bar{A} + \bar{C})$
So using commutativity and distributavity, i will distribute the $(A+B)(B\bar{A} + \bar{C}) = AB\bar{A} + BB\bar{A} + A\bar{C} + B\bar{C}$
This evaluates to since $(A\bar{A} = 0$ and $AA = A)$ $0 + B\bar{A} + A\bar{C} + B\bar{C}$ I will then distribute this term against the middle parenthetical term. to get $B\bar{A}\bar{A}C + B\bar{A}C + A\bar{C}\bar{A}\bar{C} + A\bar{C}C + B\bar{C}\bar{A}\bar{C} + B\bar{C}\bar{C}$ again note alot of terms cancel $(A\bar{A} = 0)$ so this equals $B\bar{A}C + B\bar{A}C + 0 + 0 + B\bar{A}\bar{C} + 0 = B\bar{A}C + B\bar{A}\bar{C} = B(\bar{A}C + \bar{A}\bar{C}) = B(\bar{A}(C + \bar{C})) = (Since (A + \bar{A} = 1)) = B(\bar{A} 1) = B(\bar{A}) = \bar{A}B$
• Feb 2nd 2013, 03:03 PM
lunapt
Re: Boolean Algebra and proofs
thanks!!
• Feb 2nd 2013, 04:53 PM
jakncoke
Re: Boolean Algebra and proofs
• Feb 2nd 2013, 05:42 PM
lunapt
Re: Boolean Algebra and proofs
Thanks, I'll def look into that.
Are you able to help me with my last two questions? They got me stumped after I write the booleans

imgur: the simple image sharer
imgur: the simple image sharer

For Question 1, I got:

[(A+B).(C+D)] + [(C+D)' . (A+B)] + C
C+(A+B+C+D) + (A+B+D) + (C+D)' + (C+D)+B
A+B+C+(C+D)'

I"m not sure how to simplify this further.

Question 2 is really long and I would appreciate help. I got:
A' + (D'+C') + A + (A' + C'+ D') + B' .D ' + (D+B)' = F

I'm not even sure if this is correct, and these two questions are due as homework tonight.

Any help would be much appreciated, thanks!
• Feb 2nd 2013, 06:11 PM
jakncoke
Re: Boolean Algebra and proofs
Maybe I'm looking at it wrong but for 1 I got (A+B)(C+D)+~(C+D)(A+B)+C which simplify to A+B+C
• Feb 2nd 2013, 06:18 PM
lunapt
Re: Boolean Algebra and proofs
could you please list the steps you did to get to a+b+c? I believe your answer is right, only our first expression is the same :(

I tried distributing the (C+D) ' (A +B) and ended up with BABD +C as the final answer ><
• Feb 2nd 2013, 06:35 PM
jakncoke
Re: Boolean Algebra and proofs
(a+b)(c+d)+~(c+d)(a+b)+c = (a+b)((c+d)+~(c+d))+c = (a+b)(1)+c= a+b+c
• Feb 2nd 2013, 07:14 PM
jakncoke
Re: Boolean Algebra and proofs
As for the last one.

The expression is ((~A + ~(C v D))A)((~ $B \oplus D$) + (~BC)) = A~B~C~D