Karnaugh Maps

Karnaugh Maps:

This is needed in order to simplify a Boolean expression based on the specific variables that you are given
In principle it works in the same way as a truth table
They illustrate a table of possible inputs and mapped against the  required output.
They are used to simplify a Boolean expression. They work in a similar way to a truth table with patterns within the table in order to simplify it. They illustrate a table of possible inputs mapped against the required output.

The rules of Karnaugh Maps:

• NO zeros are allowed
• no diagonal joining blocks
• Groups should be as large as possible
• Everyone must be within a block - NO loners
• Groups must be formed in 2n (1,2,4,8,etc.)
• Overlapping is allowed
• Wrap arounds are allowed

Rules of Boolean algebra:
¬ (¬ A) = A


Karnaugh Maps:

a^ b v a ^ ¬b

A       B	A   0	A   1
B                             0		1
B                           1		1

  When complexity increases this is how the numbers in the second row of the table will be:

00

01

11

10

An example of this:

A^B^CvA^¬B^CvA^B^¬C

	AB     00	AB     01	AB     11	AB     10
C                          0			1
C                          1			1	1

Algorithms

Apple and FBI debate:

• Two sided views
As someone who believes that privacy of data is vital in a day and age where hackers are rather common, I can understand the point of view from Apple, that they want to “protect their customers' privacy” and by making a stand they may be opening this argument for debate, something of which may be of use down the line even if not right now for technology.

I do however understand that, in the situation of the FBI, they have actually made moves to try and protect Apple, such as the ability to make it all happen at their own HQ, and in the case of terrorism it could be argued that it may benefit the world more to know about any other possible plans or terrorists (which could easily pose a threat in the future), than make a stand right now, especially given the potential implications for Apple.

Algorithms:

• Specify what you must accomplish
• Design the algorithm
• Check the correctness (Dry run/ Trace table)
• Analysis of the algorithm
• Implement the algorithm
• Test the resulting program

Basic algorithm:

Input x ---> Algorithm f: ---> output y

Input values = The Domain (For blackjack this would be the cards 1 - 11)
All possible outputted values = The Codomain (For blackjack this would be 21)
The codomain is any whole number 1 or above.

An algorithm will take a set of inputs, process them and give outputs. The input values to an algorithm are called the domain. All the possible values that could be outputted are called the codomain. For blackjack the domain is the value of cards from 1 to 11. The codomain of blackjack is

y = f(x) is a way of writing the algorithm f.

An example in Tax Calculator
The domain would be whole or decimal numbers which are greater than 0 (positive)
The codomain is also whole or decimal numbers


The Tax Calculator:

Basic rate 20%	£0 to £31,785  People with the standard Personal Allowance start paying this rate on income over £10,600
Higher rate 40%	£31,786 to £150,000  People with the standard Personal Allowance start paying this rate on income over £42,385
Additional rate 45%	Over £150,000

Standard Algorithms: 

 

Searching:

• Two of the most common searching algorithms are the linear search and the binary search
• The linear search starts at the beginning of the list and examines every item
• The binary search uses a 'divide and conquer' strategy which halves the search area each time an item is examined
• Only used if the items are in sorted

The Binary search algorithm:

START
         IMPORT list
         imin= 0
         max = (length of list) - 1
         found = false
        WHILE found = false THEN
               middle = int((low + high)/2)
        IF  list(middle) = x THEN
               found = TRUE 
               Output value
        Else IF value> mid THEN
               max = mid - 1
       ELSE
               min = mid +1
       END IF
STOP  


 Time complexity of Algorithms:
Using Big-O notation to describe how long an algorithm will take proportional to the amount of items.

For a linear search: O(n) - time proportional to the amount of numbers
For a binary search: O(log(n)) - time proportional to log on numbers

Therefore a binary search has a better time complexity of O(log(n)) which is smaller than a linear search.
And Linear search time complexity of O(n)

Disadvantages of binary searches:

• When the list is not in order binary searches are not very useful and this is because you can not eliminate halve of the possibilities when an item is not found.
• Binary search algorithms are harder to write than others.
• If the values are completely random the only choice is linear/serial search.
• If the list is really short then discarding halve has no advantages.
• If the list changes often the list would need to be resorted every time which would take a very long time so this may outweigh the advantages of the search
• if the elements you are searching for appear earlier on, a linear search would be more efficient.

 

Boolean Homework

Logic Gates perform a logical operation one or more logical inputs and produces a single logical output. Logic gates are implemented using diodes or transistors acting as electronic switches. Billions of gates are in a computer.

Types of logic gates:
- AND - outputs true if both inputs are true
- OR - outputs true if either are true
- NOT - outputs the inverse of the input

Boolean Algebra:
Logic gates can be represented using boolean algebra. They all have names and symbols. A proposition is a statement that can be defined as either true for false, for example 'Let P be it is raining' as this can be either true or false. These statements are booleans as they only have 1 answers whereas 'what is the weather' can have many answers.

Example of boolean algebra:
x=a^b


Conjunction:
The informal term is AND, it behaves the same as the AND logic gate. For the statement to be true all inputs must also be true. When used in boolean algebra is has the symbol ^.

The truth table for conjunction is as follows:

P	Q	P AND Q
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction:
The informal term is OR. Either of the inputs can be true for the whole statement to be true. When used in boolean algebra it has the symbol ∨.

The truth table for disjunction is as follows:

P	Q	P OR Q
T	T	T
T	F	T
F	T	T
F	F	F

Negation:
The informal term is NOT. It gives the reverse of the input. It has the symbol ¬ and will apply to the proposition following it.

The truth table for negation is as follows:

P	NOT P
T	F
F	T

Equivalence:

The informal term is equality. It has two possible symbols ↔ or ≡. It means that the truth on both sides are equivalent. For this to be true both sides must evaluate to the same truth value.

The truth table for equivalence is as follows:

P	Q	P ↔ Q
T	T	T
T	F	F
F	T	F
F	F	T

There is no logic gate for equivalence.

Exclusive Disjunction

The informal term is XOR. It has a symbol of ⊕. It will only output true if both values are true or both values are false. The logic gate is shown earlier.

The truth table for this is as follows:

p	q	p⊕q
F	F	F
F	T	T
T	F	T
T	T	F

Boolean Algebra Questions:
1. The missile will be activated (M) when the key is turned (K) and the button is pressed (B)

2. I will go to the party (P) if Sam is going (S), but not Alex (A) as I don’t get on with him anymore 

3.When the new iPhone comes out it will have a secret key combination to take selfies (S). You have to press the main button (M), the on button (O) and the volume button (V)

4.I will only go outside (O) if it is sunny (S), I have an umbrella (U) or I have to put out the trash (T)

5.The burglar alarm will only be activated (B) when the door sensor (D) or the window sensor (W) is activated, but ONLY if the alarm system is turned on (A)

6.When applying to college (C) you have to choose Physics (P) and Geography (G) or History (H)

7.When feeding the dog (D) you must not feed it with chocolate (C) or sharp objects (S)

8.The heating system will activate (H) when the thermostat setting has not been reached (T)

1. M = K ^ B

2. P = S ^ ¬ A

3. S = M ^ O ^ V

4. O = S ∨ U ∨ T

5. B = A ^ (D ∨ W)

6. C = P ∨ G ∨ H

7. D = ¬ (C ∨ S)

8. H = ¬ T

Exam Question:


t = (g) ^ (s ∨ c) ^ (f)



Question from the board:
t = False
If (g and (s or c) and f)
       t = True
 

Post Mock Analysis

What I need to revise:

• The floating point binary methods
• MICR-Magnetic ink character reader
• OCR-Optical character reader
• OMR-
• Interrupts
• Scheduling
• Learn definitions of procedure, parameters and function
• Learn definition and characteristics of local and global variables.