Notes For You: December 2016

Thursday 29 December 2016

SET

Before we get into the details of Theory of Computations. The set is an essential topic which is required to be reviewed. So, let's have a quick review of this topic.

What is a Set?

- Set is a group of elements, having a common characteristic or property.
- Example: A = {1,2,3,4,5}
- Another way to specify a set is to give the properties that characterize elements of the sets.
- Example: A = {x | x is a positive integer less than or equal to 5}

Set Terminology

1. Belongs To (∈)

- x ∈ A means that x is an element of A.
- Using this notation we can specify the set {0,1,2,3,4} call it Z by writing
Z = {x | x ∈ N | x <= 5}
Where N = set of natural numbers.

2. Subset

- Let A and B be two sets. Then A is a subset of B if every element of A is an element of B.
- It is represented by A⊆ B.
- If A is a subset of B and B is a subset of A, then A = B. Also if a is a subset of B but is not equal to B then it is represented as A⊂ B.

3. Universal Set

- The set U of all the elements we might ever consider in the discourse is called the universal set.

4. Complement

- Let A be a set, then the complement of A is the set consisting of all elements of the universal set that are not in A.
A' = {x | x∈ U \land \!\, x ∉ A}
- It is denoted by A'.
- Example:
If U is a set of natural numbers and A = {1,2,3}, then
A' = {x | x∈ U \land \!\, x > 3}

Set Operations

Different operations can be performed on sets;

1. Union:

- If A and B are two sets, then the union of A and B is the set that contains all the elements that are in A and B including the ones in both A and B.
- Union is denoted by A∪B.
- Example:
If A = {1,2} and B = {3, 4, 5} then A∪B = {1, 2, 3, 4, 5}.

2. Difference

- If A and B are two sets, then the difference of A from B is the set that contains all the elements that are in A but not in B.
- The difference is denoted by A-B.
- Example:
If A= {1, 2, 3} and B = {3, 4, 5} then A-B = {1,2} also B-A = {4,5}.
- It can be seen that A-B ≠ B-A.

3. Intersection

- If A and B are two sets, then the intersection of A and B is the set that contains all the elements that are in both A and B.
- The intersection is denoted by A∩B.
- Example:
If A= {1, 2, 3} and B = {3, 4, 5} then A∩B = {3}.

Disjoint Sets

- A and B sets are said to be disjoint if they contain no common element, i.e. A∩B = ∅, where ∅ is an empty set.
- Example:
Let A= {1, 2, 3} and B = {4,5,6,7} then A and B are disjoint sets as A∩B = ∅.

Some Standard Identities of Sets

Let A, B, C represent arbitrary sets and ∅ be the empty set and U be the Universal set, then

1. Commutative Laws:

- A∪B = B∪A
- A∩B = B∩A

2. Associative Laws:

- A∪(B∪C) = (A∪B)∪C
- A∩(B∩C) = (A∩B)∩C

3. Distributive Laws:

- A∩(B∪C) = (A∩B)∪(A∩C)
- A∪(B∩C) = (A∪B)∩(A∪C)

4. Idempotent Laws:

- A∪A = A
- A∩A = A

5. Absorption Laws:

- A∪(A∩B) = A
- A∩(A∪B) = A

6. De Morgan Laws:

- (A∪B)' = A' ∩ B'
- (A ∩ B)' = A' U B'

7. Laws involving Complements:

- (A')' = A
- A ∩ A' = ∅
- A ∪ A' = U

8. Laws involving empty set:

- A ∪ ∅ = Λ
- A ∩ ∅ = ∅

9. Laws involving Universal set:

- A ∪ U = U
- A ∩ U = A

Tuesday 27 December 2016

Smallest of two 8-bit numbers

Here is an example of Assembly Language code for 8086. This example illustrates how the smallest of two 8-bit number using Direct Addressing Mode is done.

CODE SEGMENT // start of the logical code segment
ASSUME CS:CODE // this instruction will inform
the assembler the assumed name of CS. START: MOV AL, 09H // this instruction will move the operand 09H to the accumulator.
MOV BL, 03H // this instruction will move
the operand 03H to the Register B.
CMP AL, BL // this instruction will compare the
content of the Register B with the
content of the accumulator, by the
means of subtraction.
JC NEXT // this instruction will cause a jump
to the next label if a carry is
generated.
MOV [2035H], BL // if carry is not generated the result
from Register B would be moved
to the memory location 2035H.
NEXT: MOV [2035H], AL // if carry is generated the result
from accumulator would be moved
to the memory location 2035H.
CODE ENDS // end of the logical code segment

END START // end of the program

NOTE:
While actually implementing this code the keyword next should be replaced with the address of the instruction.

Largest of two 8-bit numbers

Here is an example of Assembly Language code for 8086. This example illustrates how the largest of two 8-bit number using Direct Addressing Mode is done.

CODE SEGMENT // start of the logical code segment
ASSUME CS:CODE // this instruction will inform
the assembler the assumed name of CS. START: MOV AL, 09H // this instruction will move the operand 09H to the accumulator.
MOV BL, 03H // this instruction will move
the operand 03H to the Register B.
CMP AL, BL // this instruction will compare the
content of the Register B with the
content of the accumulator, by the
means of subtraction.
JNC NEXT // this instruction will cause a jump
to the next label if no carry is
generated.
MOV [2035H], BL // if carry is generated the result from
Register B would be moved to the
memory location 2035H.
NEXT: MOV [2035H], AL // if carry is not generated the result
from accumulator would be moved
to the memory location 2035H.
CODE ENDS // end of the logical code segment

END START // end of the program

NOTE:
While actually implementing this code the keyword next should be replaced with the address of the instruction.

1's Complement

Here is an example of Assembly Language code for 8086. This example illustrates how the 1's complement of an 8-bit number using Direct Addressing Mode is done.

CODE SEGMENT // start of the logical code segment
ASSUME CS:CODE // this instruction will inform
the assembler the assumed name of CS. START: MOV AL, 07H // this instruction will move the operand 07H to the accumulator.
NOT AL // this instruction will flip the
content of the accumulator by
finding 1's complement of its single
operand.
MOV [2035H], AL // the result would be moved to
the memory location 2035H.
CODE ENDS // end of the logical code segment