Boolean Algebra

Boolean Identities

Using AND

$A.1 = A$

This equation means that the output is determined by the value of A. So if A =0, The output is 0, and vice versa.

$0.A = 0$

Because there is a 0 in this equation, the output of this will always be 0 regardless of the value of A.

$A.A = A$

The output is determined by A alone in this equation. This can be simplified to just "A".

$A.\overline{A}=0$

Here the output will be 0, regardless of A's value. A would have to be 1 and 0 for the output to be 1. This means we can simplify this to just 0.

Using OR

$0+A = A$

0 or A can be simplified as just A.

$1+A = 1$

1 or A can be simplified as just 1.

$A+A=A$

A or A can be simplified as just A.

$\overline{A}+A=1$

NOT A or A can be simplified as just 1.

Boolean Laws

Commutative Law

The Commutative Law is where equations are the same no matter what way around the letters are written. For example

$A+B = B+A$

or

$A.B = B.A$

Associate Law

If all of the symbols are the same it doesn't matter which order the equation is evaluated.

$A+(B+C) = B + (A+C)$

$A+(B+C) = B + (A+C)$

$A+(B+C) = C + (A+B)$

So:

$A.(B.C) = B . (A.C)$

$A.(B.C) = B . (A.C)$

$A.(B.C) = C . (A.B)$

Distributive Law

The distributive law is these two equations.

$A.(B+C) = A.B + A.C$

$A+(B.C) = (A+B).(A+C)$

This is essentially factorising or expanding the brackets, but you can also:

$A.B + A.C = A.(B+C)$

$A+B.A+C = A+(B.C)$

Redundancy Law

Law 1 : $A + \overline{A} B = A + B$

Proof :

$= A + \overline{A} B \\ = (A + \overline{A})(A + B) \\ = 1 . (A + B) \\ = A + B$

Law 2: $A.(\overline{A} + B) = A.B$

Proof :

$= A.(\overline{A} + B) \\ = A.\overline{A} + A.B \\ = 0 + A.B \\ = A.B$

Identity Law

This is also in the identities section:

$A.A = A$

$A+A = A$

Negation Law

Just like in any other logic negating a negative is a positive so:

$\overline{ \overline{A} } = A$

Solving Boolean Equations

Solving equations is a matter of applying the laws of boolean algrebra, followed by any of the identities you can find:

Example 1

$\overline{\overline{A}} . \overline{(B+C)} = A. \overline{B} . \overline{C}$

$\overline{\overline{A}} = A$ Use Negation Law

$\overline{(B+C)} = (\overline{B} . \overline{C})$ Use De Morgan's Law

$A . (\overline{B} . \overline{C}) = A . \overline{B} . \overline{C}$ Use Associate Law

Example 2

$(\overline{A} + A) . (\overline{A} + C)$

OR Identity

$(\overline{A} + A) = 1$

AND Identity

$= 1.(\overline{A} + C)$

Simplify

$= (\overline{A} + C)$

Example 3

$(X + Y) . (X + \overline{Y})$
Distributive:
$X . (Y + \overline{Y})$
Identity laws:
$Y + \overline{Y} = 1$

$X.1 = X$

Example 4

Expression Rule(s) Used C + BC Original Expression C + (B + C) DeMorgan's Law. (C + C) + B Commutative, Associative Laws. T + B Complement Law. T Identity Law.

Example 5

Simplify:	AB(A + B)(B + B):
Expression	Rule(s) Used
AB(A + B)(B + B)	Original Expression
AB(A + B)	Complement law, Identity law.
(A + B)(A + B)	DeMorgan's Law
A + BB	Distributive law. This step uses the fact that or distributes over and. It can look a bit strange since addition does not distribute over multiplication
A	Complement, Identity

Example 6

$\overline{A.B}(\overline{A} + B)(\overline{B} + B)$ Original Expression

$\overline{AB}(\overline{A} + B)$ Complement law, Identity law.

$(\overline{A} + \overline{B})(\overline{A} + B)$ DeMorgan's Law

$\overline{A} + \overline{B}.B$ Distributive law. This step uses the fact that or distributes over and.

$\overline{A}$ Complement, Identity.

Example 7

SIMPLIFY $(A + C)A + AC + C$

$(A + C)A + AC + C$ Complement, Identity.

$A((A + C) + C) + C$ Commutative, Distributive.

$A(A + C) + C$ Associative, Idempotent.

$AA + AC + C$ Distributive.

$A + (A + T)C$ Idempotent, Identity, Distributive.

$A + C$ Identity, twice.

Simplify

$(X+Y).(X+\overline{Y})$

solution

$X.X + X.\overline{Y} + Y.X + Y.\overline{Y}$ Expanding the brackets

$X + X.\overline{Y} + Y.X + 0$ Use of $X.X = X$ and $Y.\overline{Y} = 0$

$X + X(\overline{Y}+Y)$ Taking X out of the brackets

$X + X(1)$ Use of $Y + \overline{Y} = 1$

$X(1)$

$X$

Example 9

$(X + Y) . (X + \overline{Y})$

$X + (Y.\overline{Y})$ after distributive law applied

$(Y.\overline{Y}) = 0$

$X + 0$

$X$

$(X + Y) . (X + \overline{Y}) = X$

Example 10

Simplify:

$\overline {AB} (\overline {A}+B)(\overline {B}+B)$

Complement law, Identity law

$\overline {AB} (\overline {A}+B).1$

DeMorgan's law

$(\overline {A}+\overline {B})(\overline {A}+B)$

Distributive law

$\overline {A}+\overline {B}B$

Complement, Identity

$\overline {A}$

Example 11

$\overline{A} . (A + B) . (A.C) \\ (\overline{A} . A + \overline{A} . B) . (A + C) \\ \overline{A} . A . A + \overline{A} . A . B + \overline{A} . A . C + \overline{A} . B . C \\ 0 + 0 + 0 + \overline{A} . B . C \\ \overline{A} . B . C$

Example 12

Simplify

$\overline{\overline{A} + \overline{(B.A)}}$

First, using De Morgan’s Law simplify it to

$\overline{\overline{A} + \overline{B} + \overline{A}}$

This can then be simplified to

$\overline{\overline{A} + \overline{B}}$

Then using De Morgan’s Law again, you get

$\overline{\overline{A}} + \overline{\overline{B}}$

Then there are double negatives, so you end up with

$A + B$

Example 13

Simplify: $X.(\overline{X}+Y)$

$(X.\overline{X})+(X.Y)$ using the Distributive Law

$0 + (X.Y)$ using the identity $A.\overline{A}=0$

$X.Y$ using the identity $A+0=A$

Fully simplified the equation

Example 14

Simplify the following: $\overline{ \overline{(A.A)}. \overline{(B.B)}}$

Using De Morgan's law we can put the equation into another form:

1. Change All operations,

$\overline{ \overline{(A+A)}+ \overline{(B+B)}}$

2. Negate letters:

$\overline{ (A+A)+(B+B) }$

3. Negate the whole expression:

$(A+A)+(B+B)$

Using the identity law, we can then simplify this expression to:

$A+B$

Example 15

For this example the Boolean Algebra itself is shown above while the description/the rules that have been used are listed below it:

$\overline{A}(A + B) + (B + AA)(A + \overline{B})$

Original expression

$\overline{A}A + \overline{A}B + (B + A)A + (B + A)\overline{B}$

Idempotent (AA to A), then Distributive, used twice.

$\overline{A}B + (B + A)A + (B + A)\overline{B}$

Complement, then Identity. (Strictly speaking, we also used the Commutative Law for each of these applications.)

$\overline{A}B + BA + AA + B\overline{B} + A\overline{B}$

Distributive, two places.

$\overline{A}B + BA + A + A\overline{B}$

Idempotent (for the A's), then Complement and Identity to remove BB.

$\overline{A}B + AB + AT + A\overline{B}$

Commutative, Identity; setting up for the next step.

$\overline{A}B + A(B + T + \overline{B})$

Distributive.

$\overline{A}B + A$

Identity, twice (depending how you count it).

$A + \overline{A}B$

Commutative.

$(A + \overline{A})(A + B)$

Distributive.

$A + B$

Complement, Identity.