Boolean Identities

There are a number of rules that can be used to simplify boolean expressions. Simplified expressions are cheaper and easier to implement as fewer logic gates are needed.

AND identities

A value AND false returns false.
- $X. 0 = 0$
A value AND true returns the value.
- $X.1 = X$
A value AND the same value returns the value.
- $X.X = X$
A value AND NOT the same value returns false.
- $X.\overline{X} = 0$

OR identities

A value OR false returns the value.
- $X + 0 = X$
A value OR true returns true.
- $X + 1 = 1$
A value OR the same value returns the value.
- $X + X = X$
A value OR NOT the same value returns true.
- $X +\overline{X} = 1$

Example

Using the identities, we can simplify the expression:
- $(X.X)+(X+0)$
- $(X . X) + X$
- $X + X$
- $X$

Rules of Boolean Operations

There are a number of rules that can be used to simplify boolean expressions. Simplified expressions are cheaper and easier to implement as fewer logic gates are needed.

Absorption

We can simplify expressions in the following way:
- $X+(X.Y) = X +X = X$
We can only do this if:
- The value outside the brackets must be present within the brackets.
- The operators inside and outside the brackets must be different.
We say that Y has been absorbed.

Commutative

The commutative rule states that values in AND or OR expressions can be swapped without changing the result:
- $X. Y = Y . X$
- $X + Y = Y + X$

Distributive

A value outside of a set of brackets can be distributed between the values within the brackets:
- $X . (Y + Z) = (X . Y) + (X . Z)$
- $X + (Y . Z) = (X + Y) .(X + Z)$

Associative

The associative rule confirms that the order of operators in an expression has no impact on the result:
- $(X + Y) + Z = X + (Y + Z)$
- $(X . Y) .Z= X . (Y . Z)$

Double Negation

The equivalent of any double-negative is a positive:
- $\overline{(\overline{X})} = X$

De Morgan's Law

De Morgan's law is as follows:
- $\overline{X + Y} = \overline{X} . \overline{Y}$
- $\overline{X . Y} = \overline{X} + \overline{Y}$
We can use this law to convert part of an expression so the whole expression only uses one type of operator.
This reduces the cost as only one type of gate is required.

1Components of a Computer

1.1Structure & Function of the Processor

1.1.1Structure of the CPU

1.1.2Fetch, Decode, Execute Cycle

1.1.3Factors Affecting CPU Performance

1.1.4CPU Architecture

1.2Types of Processors

1.2.1CISC & RISC

1.2.2Multicore & Parallel Cores

1.3Input, Output & Storage

1.3.1Computer Systems

1.3.2Magnetic Storage

1.3.3Optical Storage

1.3.4Types of Optical Storage

1.3.5Types of Memory

1.3.6Flash Memory

1.3.7Virtual Memory

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

4.1Data Types

4.1.1Data Types

4.1.2Arrays & Strings

4.1.3Representing Numbers

4.1.4Binary Arithmetic

4.1.5Hexadecimal

4.1.6Converting Binary Numbers

4.1.7Floating Points in Binary

4.1.8Floating Point Arithmetic

4.1.9Bitwise Manipulation

4.1.10Character Sets

4.2Data Structures

4.2.1Arrays, Linked Lists & Queues

4.2.2Graphs, Hash Tables & Stacks

4.2.3Trees

4.3Boolean Algebra

4.3.1Computational Logic

4.3.2Boolean Logic

4.3.3Karnaugh Maps

4.3.4Boolean Identities

4.3.5Flip Flops & Adder Circuits

5Legal, Moral, Cultural & Ethical Issues

5.1Computing Related Legislation

5.1.1Data Protection Act (1998)

5.1.2Computer Misuse Act (1990)

5.1.3Copyright Designs and Patents Act (1988)

5.1.4Regulation of Investigatory Powers Act (2000)

5.2Moral & Ethical Issues

5.2.1Online Activity Tracking

5.2.2Censorship

5.2.3Cultural Issues

5.2.4Environmental Issues

5.2.5Layout, Colour Paradigms & Character Sets

6Elements of Computational Thinking

6.1Thinking Abstractly

6.1.1Abstraction

6.2Thinking Procedurally

6.2.1Decomposition

6.3Thinking Logically

6.3.1Pseudocode & Flow Diagrams

7Problem Solving & Programming

7.1Programming Techniques

7.1.1Programming Fundamentals

7.1.2Modularity

7.2Programming Construction

7.2.1Integrated Development Environments

7.2.2Testing

8Algorithms

8.1Algorithms

8.1.1Interpreting, Correcting & Completing Algorithm

8.1.2Sort Algorithms

8.1.3Insertion & Merge Sort

8.1.4Search Algorithms

Jump to other topics