This is theprint version ofA-level Computing You won't see this message or any elements not part of the book's content when you print orpreview this page.

A-level Computing is anA-level course run for students in the UK

Note: current version of this book can be found athttp://en.wikibooks.org/wiki/A-level_Computing/AQA

• (AQA) Peter EJ Kemp (editor) - London
• (CIE) Peter Astbury - Alexandria, Egypt

• Students from Christ the King Sixth Form College
• Students from Loxford School
• Students from Wreake Valley Academy
• Peter L Higginson - Reading

Thanks for helping out!

This is a book about A-Level Computer Science. It aims to fit with theAQA GCE A-Level Computer Science 2015 syllabus but is not endorsed by AQA. It should be useful as a revision guide or to find alternative explanations to the ones in your textbook. If you haven't heard of an A-Level then this book probably won't be of much interest to you but you can find out about them atWikipedia.

If any part of this bookis unclear or even wrong then please post a comment on the discussion page or simply fix it yourself! In particular, please say if the book assumes any knowledge or skills which not all A-Level Computer Science students have.

Paper 1 Index

• 1. Fundamentals of programming
• 2. Fundamentals of data structures
• 3. Fundamentals of algorithms
• 4. Theory of computation
• 13. Systematic approach to problem solving
• Skeleton program |A-level |AS-level

Paper 2 Index

• 5. Fundamentals of data representation
• 6. Fundamentals of computer systems
• 7. Fundamentals of computer organisation and architecture
• 8. External hardware devices
• 9. Consequences of uses of computing
• 10. Fundamentals of communication and networking
• 11. Fundamentals of databases
• 12. Fundamentals of functional programming (A-level only)

• 14. The computing practical project (A-level only)

Accepted languages

• Java
• Pascal
• Python
• VB
• C#

A-Level Projects can be written in any language.

• COMP1 - Problem Solving, Programming, Data Representation and Practical Exercise
• COMP2 - Computer Components, The Stored Program Concept and the Internet

• COMP3 - Problem Solving, Programming, Operating Systems, Databases and Networking
• COMP4 - The Computing Project

You will meet several coloured boxes, here are their meanings:

There will be a lot of concepts that you need to be familiar with, definitions are highlighted like so:

This exam is worth 40% of your AS grade (20% of A2). It is examined in June.

Unit 2 definition list

http://www.aqa.org.uk/subjects/ict-and-computer-science/a-level/computing-2510/past-papers-and-mark-schemes

Hardware and Software have asymbiotic relationship, this means that without software hardware is very limited; and without hardware, software wouldn't be able to run at all. They need each other to fulfill their potential.

Standard hardware components	The relationship between Hardware and Software

You have probably used a lot of software over the years, here we are going to study the different classifications (types) of software that are out there.

The two main classifications of software that all programs fit under are:

• System software
• Application software

Whatever you do don't use brand names in answer questions about software types. WritingMicrosoft Word will get you no marks, writingword processor will!

Without software, most hardware would sit there doing nothing or perform specific tasks. To make most hardware run we need to use software, and your task here is to select the correct type of software for each job.

Modern computers are complex machines involving many different parts. To keep it running well you will need system software. System software will handle the smooth running of all the components of the computer. It will also provide the general functionality for other programs to use. These include programs that may be tools to speed up the computer, tools to develop new software and programs to keep you safe from attacks. There are several different types of system software that we will look at in more detail very shortly:

• Operating Systems are a collection of programs thatmake the computer hardware conveniently available to the user and alsohide the complexities of the computer's operation. The Operating System (such as Windows 7, Apples iOS or Linux) interprets commands issued by application software (e.g. word processor and spreadsheets). The Operating System is alsoan interface between the application software and computer. Without the operating system, the application programs would be unable to communicate with the computer.

• Utility programs are small, powerful programs with a limited capability, they are usually operated by the user (or) operator to maintain a smooth running of the computer system. Various examples include file management, diagnosing problems and finding out information about the computer etc. Notable examples of utility programs include copy, paste, delete, file searching, disk defragmenter, disk cleanup. However, there are also other types that can be separately installable from the Operating System.

• Library programs are a compiled collection of subroutines (e.g. libraries make many functions and procedures available when you write a program)

• Translator software (Assembler, Compiler, Interpreter)

1. Assembler translates assembly language programs into machine code (A binary code that a machine can understand).
2. Compiler translates high level language code into object code (which is the machine language of the target machine).
3. Interpreter analyses and executes a high-level language program a line at a time. Execution will be slower than for the equivalent compiled code as the source code is analyzed line by line.

Application software is designed for people like me and you to perform tasks that we consider useful. This might be the ability of a scientist to work out statistical information using a set of results, or someone who wants to play the latest computer game. There are several categories of Application software that we'll look into shortly:

• General purpose application software.
• Special purpose application software.
• Bespoke application software

Exercise: Software categories What are the two main categories of software? Answer: System Software Application software Why is software important for computer systems? Answer: Without software the tasks that hardware can perform is often fixed and limited For each of the two main classifications of software give three sub categories: Answer: System software Operating system software Utility programs Library programs Translator software (Compiler, assembler, interpreter) Application software General purpose application software. Special purpose application software. Bespoke application software Place each of these software products into its correct category (application or system): Word processor Operating system Defragmenter GPS mapping software Music encoding library Answer: Word processor (Application) Operating system (System) Defragmenter (System) GPS mapping software (Application) Music encoding library (System) Fill in the missing software categories: Answer:

We should know by now that system software is software that helps a computer to run. We will now look at the different types of system software out there and why each is needed:

Anoperating system (OS) is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system. Without an operating system, a user cannot run an application program on their computer (unless the application program is self booting).

Time-sharing operating systems schedule tasks for efficient use of the system and may also include accounting for cost allocation of processor time, mass storage, printing, and other resources.

For hardware functions such as input/output and main memory management, the operating system acts as a middleman between application programs and the computer hardware, although the application code is usually executed directly by the hardware it will frequently call the OS or be interrupted by it. Operating systems can be found on almost any device that contains a computer, from mobile phones and video game consoles to supercomputers and web servers.

Examples of popular modern operating systems include Android, iOS, Linux, Mac OS X and Microsoft Windows, but don't use these names in the exam!

Utility software is a type of system software which has a very specific task to perform related to the working of the computer, for example anti virus software, disk defragment etc.

Utility software should not be confused with application software, which allows users to do things like creating text documents, playing games, listening to music or surfing the web. Rather than providing these kinds of user-oriented or output-oriented functionality, utility software usually focuses on how the computer infrastructure (including the computer hardware, operating system, application software and data storage) operates. Due to this focus, utilities are often rather technical and targeted at people with an advanced level of computer knowledge.

Examples of utility software include:

• Virus scanner - to protect your system from trojans and viruses
• Disk defragmenter - to speed up your hard disk
• System monitor - to look at your current system resources
• File managers - to add, delete, rename and move files and folders

Library programs are collections of compiled routines which are shared by multiple programs, such as the printing function.

Library programs contain code and data that provide services to other programs such as interface (look and feel), printing, network code and even the graphic engines of computer games. If you have ever wondered why all Microsoft Office programs have the same look and feel, that is because they are using the same graphical user interface libraries. For computer games a developer might not have the time and budget to write a new graphics engine so they often buy graphical libraries to speed up development, this will allow them to quickly develop a good looking game that runs on the desired hardware. For example Battlefield 3 and Need for Speed both use the sameFrostbite engine.

Most programming languages have a standard set of libraries that can be used, offering code to handle input/output, graphics and specialist maths functions. You can also create your own custom libraries and when you start to write lots of programs with similar functionality you'll find them very useful. Below is an example of how you might import libraries into VB.NET:

'imports the libraries allowing a program to send emailsImportsSystem.Net.Mail'imports the libraries allowing a program to draw in 2DImportsSystem.Drawing.Drawing2D

The final type of system software that you need to know is translator software. This is software that allows new programs to be written and run on computers, by converting source code into machine code. There are three types that we'll cover in a lot more detail shortly

• Assembler - converts assembly code into machine code
• Interpreter - converts 3rd generation languages such as javascript into machine code one line at a time
• Compiler - converts 3rd generation languages such as C++ into machine code all at once

General purpose application software (GPS) is a kind of application that can be used for a variety of tasks. It is not limited to one particular function. They provide a large number of features for its users. For example, a word processor could be classed as general purpose software as it would allow a user to write a novel, create a restaurant menu or even make a poster.

Examples of General purpose application software include: Word processors, Spreadsheet and Presentation software. Whatever you do, do not use brand names!

Special purpose application software (SPS) is a type of software created to execute one specific task. For example, a camera application on your phone will only allow you to take and share pictures. Another example would be a chess game, it would only allow you to play chess.

Other examples of special purpose application software are web browsers, calculators, media players, calendar programs etc. Again, make sure that you don't use brand names!

Bespoke application software (BPS) is tailor made for a specific user and purpose. For example a factory may require software to run a robot to make cars, however, it is the only factory making that car in the world, so the software required would have to be specially built for the task.

Other examples might include software for the military, missile/UAV operations, software for hospitals and medical equipment, software being written inside banks and other financial institutions.

There are several things to consider before purchasing bespoke software, on the plus side:

Software is built for and will meet your precise needs

However, you must also consider

Software will be expensive as you have to cover all of the production costs

It may take some time to develop the software, when special purpose software could be brought straight away

The software is more likely to be buggy as it probably won't have thousands of clients using and testing it

There are many types of programming languages out there and you might already have heard of a few of them, for example: C++, VB.NET, Java, Python, Assembly. We will now look at the history of how these languages came about and what they are still useful for. In all cases keep in mind that the only thing a computer will execute is machine code orobject code when it has been converted from a language to run on a processor.

LDA34ADD#1STO34

x=x+1

body.top{color:red;font-style:italic}

Thefirst generation program language is pure machine code, that is just ones and zeros, e.g.${\displaystyle 0010010010101111101010110}$. Programmers have to design their code by hand then transfer it to a computer by using a punch card, punch tape or flicking switches. There is no need to translate the code and it will run straight away. This may sound rather archaic, but there are benefits:

Code can be fast and efficient

Code can make use of specific processor features such as special registers

And of course drawbacks

Code cannot be ported to other systems and has to be rewritten

Code is difficult to edit and update

Second-generation programming languages are a way of describing Assembly code which you may have already met.

By using codes resembling English, programming becomes much easier. The usage of thesemnemonic codes such asLDA for load andSTA for store means the code is easier to read and write. To convert an assembly code program into object code to run on a computer requires anAssembler and each line of assembly can be replaced by the equivalent one line of object (machine) code:

LDAAADD#5STAAJMP#3

Assembly code has similar benefits to writing in machine code, it is a one to one relationship after all. This means that assembly code is often used when writing low level fast code for specific hardware. Until recently machine code was used to program things such as mobile phones, but with the speed and performance of languages such asC being very close to Assembly, and with C's ability to talk to processor registers, Assembly's use is declining.

As you can hopefully see there are benefits to using Second-Generation Languages over First-Generation, plus a few other things that makes Assembly great:

Code can be fast and efficient

Code can make use of specific processor features such as special registers

As it is closer to plain English, it is easier to read and write when compared to machine code

And of course drawbacks

Code cannot be ported to other systems and has to be rewritten

Even though Assembly code is easier to read than machine code, it is still not straight forward to perform loops and conditionals and writing large programs can be a slow process creating a mish-mash ofgoto statements and jumps.Third-generation programming languages brought many programmer-friendly features to code such as loops, conditionals, classes etc. This means that one line of third generation code can produce many lines of object (machine) code, saving a lot of time when writing programs.

Third generation (High Level Languages) codes are imperative. Imperative means that code is executed line by line, in sequence. For example:

dimxasintegerx=3dimyasintegery=5x=x+yconsole.writeline(x)

Would output:8

Third generation languages can be platform independent, meaning that code written for one system will work on another. To convert a 3rd generation program into object code requires aCompiler or anInterpreter.

To summarise:

Hardware independence, can be easily ported to other systems and processors

Time saving programmer friendly, one line of 3rd gen is the equivalent of many lines of 1st and 2nd gen

However

Code produced might not make the best use of processor specific features unlike 1st and 2nd gen

Fourth-generation languages are designed to reduce programming effort and the time it takes to develop software, resulting in a reduction in the cost of software development. They are not always successful in this task, sometimes resulting in inelegant and hard to maintain code. Languages have been designed with a specific purpose in mind and this might include languages to query databases (SQL), languages to make reports (Oracle Reports) and languages to construct user interface (XUL). An example of 4th generation programming type is the declarative language.

--an example of a Structured Query Language (SQL) to select criminal details from a databaseSELECTname,height,DoBFROMcriminalsWHEREnumScars=7;

An example of a declarative language isCSS which you might learn more about when completing any web design unit

/*code to change the headings on a page to green and the paragraphs to red and italic*/h1{color:#00FF00;}p{color:#FF0000;font-style:italic}

In 1854 a British mathematician,George Boole, developed Boolean Algebra. Instead of an algebra that uses numbers, boolean algebra uses truth values,true(1) andfalse(0). By defining sentences using truth values and performing operations on these truth values you can work out the overall conclusion of complex statements. Boolean Algebra has had a massive impact on Computer Science and the language that computers understand is a language of 1s and 0s, boolean.

Examples of Boolean Algebra shown in a truth table

${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x.y}$ ${\displaystyle x+y}$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

${\displaystyle x}$ ${\displaystyle \overline{x}}$ 0 1 1 0

Logic gates are pieces of hardware that perform operations on boolean inputs, allowing us to create complex devices out of abstract boolean algebra. Logic gates are the fundamental building blocks of hardware and processors will be made out of billions of them. A logic gate will typically have one or two inputs, in the examples here defined by A and B, There are six types of gate that you need to know:

• 
  NOT
• 
  AND
• 
  OR
• 
  XOR
• 
  NAND
• 
  NOR

ANOT gate will always give an outputopposite to what the input is e.g. 1 (not gate) 0. A NOT gate takes one boolean input and flips it. It is possible to have a double NOT. This will reverse the original NOT. The symbol would have an extra bar over it.

In Boolean Algebra we write aNOT symbol by placing a bar on top of a letter(${\displaystyle \overline{A}}$) or letters (${\displaystyle \overline{C+B}}$).

To summarise here is a truth table showing the relationship between A and${\displaystyle \overline{A}}$

A	${\displaystyle \overline{A}}$
0	1
1	0

AnAND gate will combine the boolean values of two inputs (you can get more than two inputs but we don't need to know about that type of gate here). If and only ifboth inputs are true will it output true. If any of the inputs are false it will out put false.

In Boolean Algebra we write anAND symbol by placing a bullet point between two (${\displaystyle A.B}$) or more (${\displaystyle A.B.C}$) values.

An easy way to remember how an AND gate works is thinking about a circuit to turn a light bulb on. If both switches are on then the bulb will light up, if any switch is off then the bulb won't light.

To summarise here is a truth table showing all the different values for two inputs A and B and the result of ANDing those values together

AnOR gate will combine the boolean values of two inputs. Ifone or more inputs are true then the output will be true. If both the inputs are false then the output will be false.

In Boolean Algebra we write anOR symbol by placing a plus symbol between two (${\displaystyle A+B}$) or more (${\displaystyle A+B+C}$) values.

An easy way to remember how an OR gate works is thinking about a circuit to turn a light bulb on. If one or more switches are on then the bulb will light up, if both switch are off then the bulb won't light.

To summarise here is a truth table showing all the different values for two inputs A and B and the result of ORing those values together

An exclusive- OR,XOR, gate will combine the boolean values of two inputs. Ifexactly one input is true then the output will be true. If both the inputs are false or both the inputs are true then the output will be false.

In Boolean Algebra we write anXOR symbol by placing a plus symbol surrounded by a circle between two (${\displaystyle A\oplus B}$) or more (${\displaystyle A\oplus B\oplus C}$) values.

To summarise here is a truth table showing all the different values for two inputs A and B and the result of XORing those values together

A	B	${\displaystyle A\oplus B}$
0	0	0
0	1	1
1	0	1
1	1	0

ANAND gate will combine the boolean values of two inputs, AND them together, and NOT the result. Ifone or less input is true then the output will be true. If both the inputs are true then the output will be false. To draw a NAND gate you draw an AND gate and add a circle to the front, as you can see above.

In Boolean Algebra we write anNAND symbol by taking an AND equation and NOTing the result (${\displaystyle \overline{A.B}}$).

To summarise here is a truth table showing all the different values for two inputs A and B and the result of NANDing those values together

A	B	${\displaystyle A.B}$	${\displaystyle \overline{A.B}}$
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

ANOR gate will combine the boolean values of two inputs, OR them together, and NOT the result. Ifno input is true then the output will be true. If either or both inputs are true then the result will be false. To draw a NOR gate you draw an OR gate and add a circle to the front, as you can see above.

In Boolean Algebra we write anNOR symbol by taking an OR equation and NOTing the result (${\displaystyle \overline{A+B}}$).

A	B	${\displaystyle A+B}$	${\displaystyle \overline{A+B}}$
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

Exercise: Logic Gates Give the symbol and gate diagram for an OR statement Answer: + Give the symbol and gate diagram for an AND statement Answer: . Give the symbol and gate diagram for a XOR statement Answer: ${\displaystyle \oplus }$ Give answers to the following equations: TRUE AND TRUE Answer: TRUE TRUE + FALSE Answer: TRUE TRUE + TRUE Answer: TRUE TRUE${\displaystyle \oplus }$ TRUE Answer: FALSE NOT(TRUE) . TRUE Answer: FALSE ${\displaystyle \overline{\overline{TRUE}}+FALSE}$ Answer: TRUE Draw a NAND gate and truth table Answer: A B ${\displaystyle A.B}$ ${\displaystyle \overline{A.B}}$ 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 Complete the following table: Name NAND NOR AND NOT OR XOR Gate Symbol Truth Table Answer: Name NAND NOR AND NOT OR XOR Gate Symbol ${\displaystyle \overline{A.B}}$ ${\displaystyle \overline{A+B}}$ ${\displaystyle .}$ ${\displaystyle \overline{A}}$ ${\displaystyle +}$ ${\displaystyle \oplus }$ Truth Table A B ${\displaystyle A.B}$ ${\displaystyle \overline{A.B}}$ 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 A B ${\displaystyle A+B}$ ${\displaystyle \overline{A+B}}$ 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 A B A.B 0 0 0 0 1 0 1 0 0 1 1 1 A ${\displaystyle \overline{A}}$ 0 1 1 0 A B A+B 0 0 0 0 1 1 1 0 1 1 1 1 A B ${\displaystyle A\oplus B}$ 0 0 0 0 1 1 1 0 1 1 1 0

Now you have learnt logic gates we will take a look at how they are combined inside hardware. You may well be asked in an exam to draw your own logic gates or to work out what a combination of logic gates will output. In this section we will look at the best way to describe what a set of logic gates is in boolean algebra. Let's take a look at a quick example:

Sometimes you might get an ambiguous equation such as${\displaystyle A.B+C}$. Do you work out the AND or the OR first? The rule is to treat the AND part first so we would treat${\displaystyle A.B+C=(A.B)+C}$

A common question in the exam is to be given some boolean algebra and be asked to express it as logic gates. Let's take a look at an addition and subtraction example that you should be familiar with:

${\displaystyle 9-(7+1)}$

First we are going to deal with the inner-most brackets

${\displaystyle (7+1)=8}$

Finally we combine this answer with the${\displaystyle 9-}$

${\displaystyle =9-(8)=1}$

It will work exactly in the same way for boolean algebra, but instead of using numbers to store our results, we'll use logic gates:

${\displaystyle C.(A+B)}$

A common question in the exam is to give you a description of a system. You'll then be asked to create a boolean statement from this description, and finally build a logic gate circuit to show this system:

Sometimes it is cheaper to create circuits using only one sort of gate, and you might be asked to do so in the exam. These gates tend to be NAND & NOR gates. "But how can you create complex circuits by using only one type of gate?!" you may well ask. We'll now cover how other gates can be made from NAND & NOR gates:

Step	NOR Gate	Equivalent
Diagram
Description	If you split the same input (A) and feed it into NOR both gate inputs you create a NOT Gate
Truth Table	Because: A A ${\displaystyle A+A}$ ${\displaystyle \overline{A+A}}$ ${\displaystyle \overline{A}}$ 0 0 0 1 1 1 1 1 0 0

Step	NAND Gate	Equivalent
Diagram
Description	If you split the same input (A) and feed it into both NAND gate inputs you create a NOT Gate
Truth Table	Because: A A ${\displaystyle A.A}$ ${\displaystyle \overline{A.A}}$ ${\displaystyle \overline{A}}$ 0 0 0 1 1 1 1 1 0 0

We have met gate logic and combinations of gates. Another way of representing gate logic is through boolean algebra, a way of algebraically representing logic gates. You should have already covered the symbols, below is a quick reminder:

Bitwise Operator	NOT(${\displaystyle \overline{A}}$)	AND(.)	OR(+)	XOR(${\displaystyle \oplus }$)	NAND(${\displaystyle \overline{A.B}}$)	NOR(${\displaystyle \overline{A+B}}$)
Description	invert input	where exactly two 1s	where one or more 1s	where exactly one 1	where less than two 1s	where exactly two 0s

For the exam you might have:

• to convert logic gates into boolean algebra,
• build logic gate combinations from boolean algebra,
• simplify boolean algebra.

A common question is to give you a complex boolean equation, which you will then have to work out a simpler exact equivalent. This is useful when you are designing circuits and want to minimise the number of gates you are using or make circuits that only use particular types of gates. To simplify boolean equations you must be familiar with two methods. You can normally use either, but try to master both:

• Truth tables
• Boolean algebra - identities and De Morgans Law

Example: Simplifying boolean equations with Truth Tables Draw the truth table for the following: ${\displaystyle (A.B)+A}$ We are going to solve this using a truth table and we need to break the problem down into its component parts: As the equation uses A and B list the different values they can take (4 in total) ${\displaystyle A}$ ${\displaystyle B}$ 0 0 0 1 1 0 1 1 Next we are going to work out the brackets first:${\displaystyle A.B}$ and add this to our truth table ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A.B}$ 0 0 0 0 1 0 1 0 0 1 1 1 Finally we will OR this result (${\displaystyle A.B}$) with A to find${\displaystyle (A.B)+A}$, the final column of the truth table ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A.B}$ ${\displaystyle (A.B)+A}$ 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 Now that our truth table is complete, look at the final column, is there a simpler way of writing this? Why aye! The final column is true when, and only when, A is true, it doesn't require B's input at all. So we can simplify toA telling us that: ${\displaystyle (A.B)+A=A}$

Example: Simplifying boolean equations with Truth Tables Let's look at another example ${\displaystyle \overline{A.\overline{B}}}$ We first of all need to break down the equation into its component parts. Starting off with A and B we the work out${\displaystyle \overline{B}}$, then${\displaystyle A.\overline{B}}$ and finally${\displaystyle \overline{A.\overline{B}}}$. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \overline{B}}$ ${\displaystyle A.\overline{B}}$ ${\displaystyle \overline{A.\overline{B}}}$ 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 This can be simplified to${\displaystyle \overline{A}+B}$ telling us that:${\displaystyle \overline{A.\overline{B}}=\overline{A}+B}$. How did we jump to this conclusion? Let's take a look at all the places where the result is true: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \overline{A.\overline{B}}}$ 0 0 1 0 1 1 1 0 0 1 1 1 When simplifying boolean equations, if the final column of the truth table has one true value, apply an AND(.), if the final column of the truth table has more than one true value, apply an OR(+) We need to get a combination of A, B that gives the result shown above. We can see that whenever A is false (${\displaystyle \overline{A}}$)the answer is true: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \overline{A.\overline{B}}}$ 0 0 1 0 1 1 1 0 0 1 1 1 We can also see that whenever the B value is true then the answer is also true: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \overline{A.\overline{B}}}$ 0 0 1 0 1 1 1 0 0 1 1 1 So we know that we need to combine${\displaystyle \overline{A}}$ with${\displaystyle B}$ to get an equation solving all cases. If we AND them${\displaystyle \overline{A}.B}$ this only gives us one of the scenarios, so that's not the answer. If we OR them${\displaystyle \overline{A}+B}$ then this gives us three answers, matching all the responses above. This is our solution. Tip: In the case where all the answers output are 1, The answer is plainly 1

Exercise: Simplifying boolean equations with Truth Tables Give a simplified boolean description, ?, for the following truth tables: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle ?}$ 0 0 0 0 1 1 1 0 0 1 1 1 Answer: ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle ?}$ 0 0 0 0 1 0 1 0 0 1 1 1 Answer: ${\displaystyle A.B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle ?}$ 0 0 1 0 1 1 1 0 1 1 1 1 Answer: ${\displaystyle 1}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle ?}$ 0 0 1 0 1 0 1 0 1 1 1 1 Answer: ${\displaystyle A+\overline{B}}$ Simplify the following boolean equations using truth tables: ${\displaystyle (\overline{A.B}).A}$ Answer: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A.B}$ ${\displaystyle \overline{A.B}}$ ${\displaystyle \overline{A.B}.A}$ 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 This can be simplified to:${\displaystyle A.\overline{B}}$ ${\displaystyle (\overline{A.B})+A}$ Answer: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A.B}$ ${\displaystyle \overline{A.B}}$ ${\displaystyle \overline{A.B}+A}$ 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 The answer in all cases is a plain${\displaystyle 1}$ ${\displaystyle (A.\overline{B})+B}$ Answer: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \overline{B}}$ ${\displaystyle (A.\overline{B})}$ ${\displaystyle (A.\overline{B})+B}$ 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 1 This can be simplified to:${\displaystyle \overline{\overline{A}.\overline{B}}}$ OR${\displaystyle A+B}$ (because of De Morgan's Laws) ${\displaystyle \overline{B}+A.B}$ Answer: Remember that we deal with the AND before the OR, meaning we can read the equation as:${\displaystyle \overline{B}+(A.B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle (A.B)}$ ${\displaystyle \overline{B}}$ ${\displaystyle \overline{B}+(A.B)}$ 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 This can be simplified to:${\displaystyle A+\overline{B}}$ ${\displaystyle (\overline{A}+\overline{B}).B}$ Answer: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \overline{A}}$ ${\displaystyle \overline{B}}$ ${\displaystyle (\overline{A}+\overline{B})}$ ${\displaystyle (\overline{A}+\overline{B}).B}$ 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 This can be simplified to:${\displaystyle \overline{A}.B}$

Sometimes a very complex set of gates can be simplified to save on cost and make faster circuits. A quick way to do that is through boolean identities. Boolean identities are quick rules that allow you to simplify boolean expressions. For all situations described below:

A = It is raining upon the British Museum right now (or any other statement that can be true or false)B = I have a cold (or any other statement that can be true or false)

Identity	Explanation	Truth Table
${\displaystyle A.A=A}$	It is raining AND It is raining is the same as saying It is raining	${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A.A}$ 0 0 0 1 1 1
${\displaystyle A.\overline{A}=0}$	Itis raining AND Itisn't raining is impossible at the same time so the statement is always false	${\displaystyle A}$ ${\displaystyle \overline{A}}$ ${\displaystyle A.\overline{A}}$ 0 1 0 1 0 0
${\displaystyle 1+A=1}$	2+2=4 OR It is raining. So it doesn't matter whether it's raining or not as 2+2=4 and it is impossible to make the equation false	1 ${\displaystyle A}$ ${\displaystyle 1+A}$ 1 0 1 1 1 1
${\displaystyle 0+A=A}$	1+2=4 OR It is raining. So it doesn't matter about the 1+2=4 statement, the only thing that will make the statement true or not is whether it's raining	${\displaystyle 0}$ ${\displaystyle A}$ ${\displaystyle 0+A}$ 0 0 0 0 1 1
${\displaystyle A+A=A}$	It is raining OR It is raining is the equivalent of saying It is raining	${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A+A}$ 0 0 0 1 1 1
${\displaystyle A+\overline{A}=1}$	Itis raining OR Itisn't raining is always true	${\displaystyle A}$ ${\displaystyle \overline{A}}$ ${\displaystyle A+\overline{A}}$ 0 1 1 1 0 1
${\displaystyle 0.A=0}$	1+2=4 AND It is raining. It is impossible to make 1+2=4 so this equation so this equation is always false	${\displaystyle 0}$ ${\displaystyle A}$ ${\displaystyle 0.A}$ 0 0 0 0 1 0
${\displaystyle 1.A=A}$	2+2=4 AND It is raining. This statement relies totally on whether it is raining or not, so we can ignore the 2+2=4 part	${\displaystyle 1}$ ${\displaystyle A}$ ${\displaystyle 1.A}$ 1 0 0 1 1 1
${\displaystyle A+B=B+A}$	It is raining OR I have a cold, is the same as saying: I have a cold OR It is raining	${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A+B}$ ${\displaystyle B+A}$ 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1
${\displaystyle A.B=B.A}$	It is raining AND I have a cold, is the same as saying: I have a cold AND It is raining	${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A.B}$ ${\displaystyle B.A}$ 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1
${\displaystyle A+(A.B)=A}$	It is raining OR (It is raining AND I have a cold). If It is raining then both sides of the equation are true. Or if It is not raining then both sides are false. Therefore everything relies on A and we can replace the whole thing with A. Alternatively we could play with the boolean algebra equation: ${\displaystyle A+(A.B)=(1.A)+(A.B)}$ Using the identity rule${\displaystyle 1.A=A}$ ${\displaystyle (1.A)+(A.B)=A.(1+B)}$ Take out the A, common to both sides of the equation ${\displaystyle A.(1+B)=A.1}$ Using the identity rule${\displaystyle 1+B=1}$ ${\displaystyle A.1=A}$ Using the identity rule${\displaystyle 1.A=A}$	${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A.B}$ ${\displaystyle A+(A.B)}$ 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1
${\displaystyle A.(A+B)=A}$	It is raining AND (It is raining OR I have a cold). If It is raining then both sides of the equation are true. Or if It is not raining then both sides are false. Therefore everything relies on A and we can replace the whole thing with A. Alternatively we could play with the boolean algebra equation: ${\displaystyle A.(A+B)=(0+A).(A+B)}$ Using the identity rule${\displaystyle 0+A=A}$ ${\displaystyle (0+A).(A+B)=A+(0.B)}$ Take out the A, common to both sides of the equation ${\displaystyle A+(0.B)=A+0}$ Using the identity rule${\displaystyle 0.B=0}$ ${\displaystyle A+0=A}$ Using the identity rule${\displaystyle 0+A=A}$	${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A+B}$ ${\displaystyle A.(A+B)}$ 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1

Examples of manipulating and simplifying simple Boolean expressions.

${\displaystyle A+B+B}$

${\displaystyle A+B+B=A+B}$

${\displaystyle (A.0)+B}$

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

Sometimes we'll have to use a combination of boolean identities and 'multiplying' out the equations. This isn't always simple, so be prepared to write truth tables to check your answers:

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

${\displaystyle (A+B).(\overline{B}+B)}$ multiplying out${\displaystyle (A+B).(1)}$${\displaystyle (A+B)}$

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

${\displaystyle B.(A+(A.B))}$ treat the brackets first and the AND inside the brackets first${\displaystyle (B.A)+(B.A.B)}$ multiply it out${\displaystyle (B.A)+(A.B)}$ as${\displaystyle B.A.B=A.B}$${\displaystyle A.B}$ as${\displaystyle (B.A)=(A.B)}$