Assignment # 2

The first 4 digits of my student number are 2087. For question 2 I have assigned part h, for question # 3 – part c, for question # 6 – part b.

Question # 1

Show that every binary function can be expressed as a composition of the binary operations AND/OR and NOT.
1111 x OR NOT y
1110 x OR y
1101 (x AND y) OR NOT (x AND y)
1100 (x AND y) OR (x AND NOT y)
1011 y OR (NOT x)
1010 y AND y
1001 (x AND y) OR [(NOT x )AND (NOT y)]
1000 x AND y
0111 NOT(x AND y)
0110 x AND (NOT y) OR [(y AND (NOT x)]
0101 NOT y
0100 x AND (NOT y)
0011 NOT x
0010 y AND (NOT x)
0001 NOT (x OR y)
0000 y AND (NOT Y), (x AND NOT x ) AND (y AND NOT y)

Question # 2

Which of the 16 possible binary functions cannot be represented using only compositions of {NOT, IMPL}

Since NOT y IMPL [(NOT x IMPL y) IMPL NOT(x IMPL y) can be represented as x OR y or NOT (x OR y) = x AND y, all of the possible 16 binary functions can be represented using only compositions of {NOT,IMPL}.

Question # 3

Which of the 16 binary operators are idempotent?
A binary operation is called idempotent if, whenever it is applied to two equal values, it gives that value as the result. Based on this definition ( if I understood it correctly?) AND , OR are idempotent functions (1 AND 1 = 1, 0 AND 0 = 0), (1 OR 1 = 1, 0 OR 0 = 0)

Question # 4

Since we are creating 9-tuples (3 choices for the first position and 3 choices for the second position 3x3 = 9) using 3 possible inputs, the number of possible functions will be 3 ^ 9 = 19683.

Question # 5

How many binary operations are necessary to express every possible 2 argument function for ternary inputs?
Based on the following source: www.fw.uri.br/~arpasi/artigos/ternary.pdf
there are four binary operations which can be use to express every possible 2 argument function for ternary inputs: NOT,OR, AND, and IMPLY.


Question # 6











The images are displayed in the following order:
pic1 AND pic 2
pic1 IMPL pic2
pic1 OR pic2

Question # 7


P - Poison caused the victim's death.
B - There was a change in his blood chemistry.
S - There was a residue of poison in the stomach.

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

P IFF B OR S

G - There were puncture marks on the body.

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

(NOT B AND NOT S) AND G

N - Poison was injected by a needle only.

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

N IMPL G

Sentence 4: Either poison was the cause of the victim's death, or there are no puncture marks on the body.

P OR NOT G

If we assume that all statements are true we may conclude that P is true; poison caused the victim's death.

Orders of Magnitude

(1) 1024^3 /64 x1024 = 16384


(2) 4.7x1024^3/800x1024= 6160.384= approximately 6160

(3) First commercial PC Altair 8800 had a clock rate of 2 MHz (2 million cycles/sec.)
The original IBM PC (c. 1981) - 4.77 MHz.
In 2002 - 3GHz ( 3 billion cycles/sec.)
Source: http://en.wikipedia.org/wiki/Clock_rate


(3)