Assignment #2, Orders of Magnitute question

1) Comodore 64 = 64 K = 64*1024 bytes = 65536 bytes. A 1 gig computer has 1*1024*1024*1024 bytes = 1073741824 bytes. Therefore a 1 gig computer woud have 16384 times more bytes of memory than a comodore 64.

2) A floppy disk can store 800K. A DVD can store 4.7GB of data. 4.7GB=4.7*1024= 4812.8MB=4812.8*1024= 4928307.2K. Therefore a DVD can store 6160 worth of floppy disks.

3) During my 'surfing' I found that the "The original IBM PC (c. 1981) had a clock rate of 4.77 MHz (4,770,000 cycles/second)" (http://en.wikipedia.org/wiki/Clock_rate).

In terms of comparing processor clock rates of computers with respect to factors of speed, wikipedia is once again useful when it is explained that:

The clock rate of a computer is only useful for providing comparisons between computer chips in the same processor family. An IBM PC with an Intel 486 CPU running at 50 MHz will be about twice as fast as one with the same CPU, memory and display running at 25 MHz, while the same will not be true for MIPS R4000 running at the same clock rate as the two are different processors with different functionality. Furthermore, there are many other factors to consider when comparing the speeds of entire computers, like the clock rate of the computer's front side bus (FSB), the clock rate of the RAM, the width in bits of the CPU's bus and the amount of Level 1, Level 2 and Level 3 cache.
Clock rates should not be used when comparing different computers or different processor families. Rather, some software benchmark should be used. Clock rates can be very misleading since the amount of work different computer chips can do in one cycle varies. For example, RISC CPUs tend to have simpler instructions than CISC CPUs (but higher clock rates), and superscalar processors can execute more than one instruction per cycle, yet it is not uncommon for them to do "less" in a clock cycle. In addition, subscalar CPUs or use of parallelism can also affect the quality of the computer regardless of clock rate.

Nevertheless, computers today boast processor clock rates which are superior to the original IBM PC (circa 1981) clock rate of 4.77MHZ. My iBook G4 (2004), for example, has a processor speed of 1.07 GHZ.

For definitions of Hz, MHz, GHz click on http://en.wikipedia.org/wiki/GHz.

So the IBM PC with a clock rate of 4.77 MHz = 4.77 * 10^6=4770000Hz, is at least 224 times slower than my iBook G4 which has a clock rate of 1.07*10^9=1070000000Hz. But as noted from the wikipedia source above, the RAM, frontside buss speed and cache levels, I would estimate that my iBook is infact 3*224 faster than the IBM PC (c. 1981).

Assignment #2, Question 6d

I have faced some challenges getting GIMP on my iBook which runs on an OS which is 1 step below what GIMP can run on.

Having difficulty locating a 'free' copy of photoshop at my school. All YRDSB schools have licensing for adobe software...just can't locate the disk!!!!!!

Had to go low-tech in order to give AN answer.



Here is a picture showing Pic 1 AND Pic 2.









Here is a picture showing Pic 1 OR Pic 2.






Here is the picture of NOT(Pic1) XOR Pic2.

Will try to get on campus early and create the GIMP/Photoshop version.

Assignment #2, Question 5

This is a tricky one...

One answer is that I would need 3^9 binary operations to represent every possible two argument function on Trinary operations. But this could be labeled a 'crappy answer'.

So, a more interesting question to answer would be what is the minimal number of binary operations needed to represent every possible two argument function on Trinary.

I immediately attempted using familiar binary operations such as {AND, OR, NOT} but soon found that the NOT operation did not make too much sense on Trinary.

That is, how would NOT 1 look like? Well NOT 1 in Trinary would be 2 or 0. The problem we run into is how to logically differentiate between the two? I abandoned this method.

Instead I made new symbols that might satifsy this question.

I believe I would need at least 4 binary operations to represent every possible two argument function on Trinary. Mind you it would have to be 'repeated' applications of one, two, three, or all four of these NEW operations...Much like how we can use compositions of {AND, OR, NOT} to represent every possible binary operation in binary.

The new symbols are:

SHIFTRIGHT= function shifts entire line to the right, last digit moves to the start of string = (100100000) = (010010000)
INSERT 1 = function replaces number in the 1st space with a 1 = (000000000) = (100000000)
INSERT 2 = function replaces number in the 1st space with a 2 = (000000000) = (200000000)
INSERT 0 = function replaces number in the 1st space with a 0 = (100000000) = (000000000)

Using these symbols you can apply them repeatedly to represent every possible binary operation on Trinary.

Assignment #2, Question 3a.

Which of the 16 binary operations are commutative?

Recall the definition of commutative: f(x,y) = f(y,x).

We can say OR is commutative because if x=(0011) and y=(0101), then xORy=(0111) and yORx=(0111).

After working on the other 15 binary operations in a similar manner, I found the following list of binary operations which are commutative.

(0000)=y AND NOT(y)=y AND NOT(y)
(0001)=x AND y=y AND x
*(0011)=trivial
*(0101)=trivial
(0110)=x XOR y = y XOR x
(0111)=already shown
(1000)=NOT(x OR y)=NOT(y OR x)
(1001)=x IFF y=y IFF x
*(1010)=NOT(y)=NOT(y)
*(1100)=NOT(x)=NOT(x)
(1110)=NOT(x AND y)=NOT(y AND x)
(1111)=NOT(x) OR x

Not certain about the ones with *.

Assignment #2, Question 2f

Using compositions of {OR, IMPL}, and x=(0011) y=(0101), can all 16 binary functions be represented?

I worked systematically using Prof. Zabrocki's suggestion during Monday's class.

I found that I could only represent 6 of the 16 binary functions; namely: (0011), (0101), (0111), (1101), (1011), (1111).

Notice that because I am only using compositions of {OR, IMPL}, the likelihood of (***0) happening is impossible.

So I will not be able to represent:

(0000), (0010), (0100), (0110), (1000), (1010), (1100), (1110).

Also note that {OR, IMPL} = {OR, x OR NOT(y)}. I can therefore not reproduce or represent binary operations that utilize {AND, NOT} directly.

So I will also not be able to represent:

(1001), (0001).

Assignment #2, Question 4

Here we are asked to find how many possible binary operations there are if we are working in trinary.

Recall that when we were working in binary, we ended up having 16 binary operations, where each of the binary operations could be represented by a unique 4-tuple composed of either 0s or 1s.

Thus, by the multiplication principle, we get 2x2x2x2=16 operations.

Applying this to trinary.

We see that each binary operation, in trinary, can be represented by a unique 9-tuple composed of either 0s, 1s, or 2s.

Again, apply the multiplication principle and we get 3x3x3x3x3x3x3x3x3 = 3^9 possible operations.

Assignment #2, Question 7

In this question we are required to use symbols to represent the truth values of phrases, and to create new (connective) symbols in cases where using {and, or, not} might be too cumbersome.

New Symbols:

Let "<=>" = x IFF y = NOT[(x or y) and NOT(x and y)]

Let "<=" = x ONLY IF y = NOT(y) or x

Let "XOR" = x OR y AND NOT(x AND y)

Statements:

Poison cased the victim's death if and only if there was a change in his blood chemistry or a residue of poison in his stomach.

Let
A=Poison cased the victim's death
B=there was a change in his blood chemistry
C=residue of poison in his stomach

A <=> (B or C) {I believe we don't use XOR here because if both a change in blood chemistry and residue of poison is observed, then Poison still caused the victim's death. So no need for XOR here, just OR.}

There was neither a change in blood chemistry nor a residue of poison in his stomach, but there were puncture marks on the body.

Let D=there were puncture marks on the body.

NOT (B OR C) AND D

Poison was injected by a needle only if there were puncture marks on the body.

Let E=poison was injected by a needle

E <= D

Let S=Either poison was the cause of the victim's death, or there are no puncture marks on the body.

I initially thought the truth equivalent should be A OR NOT(D) but this was merely a 'straight' translation of the sentence instead of a truth equivalent statement. The 'Either' at the start of the sentence throws everything off and is a hint that S is an 'exclusive or' (XOR) case, where "you can have one or the other but not both events happening".

So S can be written as A XOR NOT(D).

Assignment #2, Question 1

In this question we were asked to show that every binary function (16 in total) can be expressed as a composition of binary operations {and, or, not}.

To make things easier to read, I will write each binary operation as a 4-tuple. That is, I will write x as (0011) and y as (0101).

Below I will write each of the 16 binary functions and an accompanying equivalent expression which uses a composition of {and, or, not} to explain how we can derive any given binary function using x and y.

Let:

X=(0011)

Y=(0101)

Find using {AND, OR, NOT}

0000= NOTx AND x

0001= x AND y

0010= x AND NOTy

0011= x

0100= NOTx AND y

0101= y

0110= x OR y and NOT (x AND y)

0111= NOTx OR x

1000= NOT (x OR y)

1001= Not (x OR y and NOT (xANDy))

1010= NOTy

1011= x OR NOTy

1100= NOTx

1101= NOTx OR y

1110= NOT (x AND y)

1111= y OR NOTy , x OR NOTx