Boolean Algebra

Boolean Algebra Precedence

the order of precedence for boolean algebra is:

1. Brackets
2. Not
3. And
4. Or

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 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 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 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 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 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.