Boolean Algebra

From TRCCompSci - AQA Computer Science
Revision as of 12:17, 9 May 2018 by Jmiester26 (talk | contribs) (Redundancy Law)
Jump to: navigation, search

Any equation must be within the <math> </math> tags. For Boolean alegbra the main issue is how to negate a term like:

[math] \overline{a}[/math] or [math] \overline{\overline{a}+b}[/math]

this can be done by adding the following around any term you wish to negate.:

<math> \overline{} </math>  

[math] \overline{a}[/math]

is

 <math> \overline{a} </math>

[math] \overline{\overline{a}+b}[/math]

is

 <math> \overline{\overline{a}+b} </math>.

Identities

AND Identities

[math] A.1 = A [/math]

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

[math] 0.A = 0 [/math]

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

[math] A.A = A[/math]

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

[math] A.\overline{A}=0 [/math]

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.

OR Identities

[math] 0+A = A [/math]

0 or A can be simplified as just A.

[math] 1+A = 1 [/math]

1 or A can be simplified as just A.

[math] A+A=A[/math]

A or A can be simplified as just A.

[math] \overline{A}+A=1[/math]

NOT A or A can be simplified as just 1.

Laws

Commutative Law

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

[math] A+B = B+A [/math]

or

[math] A.B = B.A [/math]

Associate Law

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

[math] A+(B+C) = B + (A+C) [/math]

[math] A+(B+C) = B + (A+C) [/math]

[math] A+(B+C) = C + (A+B) [/math]

So:

[math] A.(B.C) = B . (A.C) [/math]

[math] A.(B.C) = B . (A.C) [/math]

[math] A.(B.C) = C . (A.B) [/math]

Distributive Law

The distributive law is these two equations.

[math] A.(B+C) = A.B + A.C [/math]

[math] A+(B.C) = (A+B).(A+C) [/math]

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

[math] A.B + A.C = A.(B+C)[/math]

[math] A+B.A+C = A+(B.C) [/math]

Redundancy Law

Law 1 : [math] A + B \overline{A} = A + B [/math]

Proof :

[math]= A + B \overline{A} \\ = (A + \overline{A})(A + B) \\ = 1 . (A + B) \\ = A + B [/math]


Law 2: [math] A.(\overline{A} + B) = A.B[/math]

Proof :

[math]= A.(\overline{A} + B) \\ = A.\overline{A} + A.B \\ = 0 + A.B \\ = A.B [/math]

Identity Law

This is also in the identities section:

[math] A.A = A [/math]

[math] A+A = A [/math]

Negation Law

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

[math] \overline{ \overline{A} } = A [/math]

Equations

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

Example 1

[math] \overline{\overline{A}} . \overline{(B+C)} = A. \overline{B} . \overline{C} [/math]

[math] \overline{\overline{A}} = A [/math] Use Negation Law

[math] \overline{(B+C)} = (\overline{B} . \overline{C}) [/math] Use De Morgan's Law

[math] A . (\overline{B} . \overline{C}) = A . \overline{B} . \overline{C} [/math] Use Associate Law

Example 2

[math] (\overline{A} + A) . (\overline{A} + C) [/math]

OR Identity

[math](\overline{A} + A) = 1[/math]

AND Identity

[math]= 1.(\overline{A} + C)[/math]

Simplify

[math]= (\overline{A} + C)[/math]

Example 3

[math](X + Y) . (X + \overline{Y})[/math]
Distributive:
[math]X . (Y + \overline{Y})[/math]
Identity laws:
[math]Y + \overline{Y} = 1[/math]

[math] X.1 = X[/math]

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

[math] \overline{A.B}(\overline{A} + B)(\overline{B} + B) [/math] Original Expression

[math] \overline{AB}(\overline{A} + B) [/math] Complement law, Identity law.

[math] (\overline{A} + \overline{B})(\overline{A} + B) [/math] DeMorgan's Law

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

[math] \overline{A} [/math] Complement, Identity.

Example 7

SIMPLIFY [math](A + C)A + AC + C[/math]


[math](A + C)A + AC + C[/math] Complement, Identity.


[math]A((A + C) + C) + C[/math] Commutative, Distributive.


[math]A(A + C) + C[/math] Associative, Idempotent.


[math]AA + AC + C[/math] Distributive.


[math]A + (A + T)C[/math] Idempotent, Identity, Distributive.


[math]A + C[/math] Identity, twice.

Example 8

Simplify

[math] (X+Y).(X+\overline{Y}) [/math]

solution

[math] X.X + X.\overline{Y} + Y.X + Y.\overline{Y} [/math] Expanding the brackets

[math] X + X.\overline{Y} + Y.X + 0 [/math] Use of [math] X.X = X [/math] and [math] Y.\overline{Y} = 0 [/math]

[math] X + X(\overline{Y}+Y) [/math] Taking X out of the brackets

[math] X + X(1) [/math] Use of [math] Y + \overline{Y} = 1 [/math]

[math] X(1) [/math]

[math] X [/math]

Example 9

[math] (X + Y) . (X + \overline{Y}) [/math]

[math] X + (Y.\overline{Y}) [/math]

[math] (Y.\overline{Y}) = 0 [/math]

[math] X + 0 [/math]

[math] X [/math]

[math] (X + Y) . (X + \overline{Y}) = X [/math]

Example 10