Discussion Class: COS1501

COS1501
THEORETICAL COMPUTER SCIENCE 1

School of Computing
 CONTENTS

• Sets: Question 1; study units 3, 4

• Relations: Question 2; study units 5, 6

• Functions: Question 3; study units 6.5, 7

• Operations: Question 4; study unit 8

• Logic: Question 5; study units 9, 10

• Mixed concepts: Question 6

 SETS (Study Guide, pp. 30 - 68)

Objects/elements belong to sets.

Example sets:
List notation: {a, b, c}; {1, 2, 3, {3}, {4}}
Set builder notation: {x ∈ ℤ x ＞2}
Cardinality of a set: Number of
elements in the set.
 SETS (Study Guide, pp. 30 - 68)
Subset: A  B every element of A also element of B
Form subsets: KEEP outside brackets, throw away some
element(s) from B. Eg {, a, b, {c}} Subsets: {}, {a}, {{c}},…

Union: A  B = {x | x  A or x  B}

Intersection: A  B = {x | x  A and x  B}

Difference: A − B = {x | x  A and x  B}

Complement: A = {x | x  U and x  A}

Symm. diff.: A + B = {x | x  A or x  B, but not both}

A + B = (A  B) − (A  B)
 SUBSETS (Study Guide, pp. 40, 41)
Example:
Subset: A  B
Proper subset: A  B Let C = {, {a}}
2 elements in C namely  and {a}
U
Cardinality: |C| = 2
B
Form subsets of C:
A
Throw away:
• both elements to form subset { };
• element  to form subset {{a}};
• element {a} to form subset {};
• no element then C  C.
Powerset:
Subsets of C: { }, {{a}}, {} and C.
P(C) = {{ }, {{a}}, {} , C}
 VENN DIAGRAMS (Study Guide, pp. 48 - 54)
AUB AnB A-B

A B A B A B

A+B

A B
A'

A B

C
Question 1
Use Venn diagrams to investigate whether, for all A,B,C  U,
A  (B  C) = (A + B) − C.
If an identity, give proof; if not, give a counterexample.
Solution: Left-hand side:
B C’ B n C’

A B A B
A B

C C
 Is A  (B  C) = (A + B) − C an identity?
Left-hand side:
A B n C’ A U (B n C ’)

A B A B A B

C C C
Right-hand side (A + B) − C:
A+B C (A + B) - C

A B A B A B

C C C

LHS ≠ RHS:
A  (B  C) = (A + B) − C is not an identity.
Provide counterexample.
Left-hand side: Right-hand side:
A U (B n C ’) (A + B) - C

A B A B

C C

Counterexample: Choose a  A, B and C.

Let U = {a, b, c}, A = {a}, B = {a, b} and C = {a}.

L-H: A  (BC) R-H: (A + B) − C

= {a}  ({a,b}{b,c}) = {b} − {a}
= {a}  {b} = {a, b} = {b}
L-H≠R-H
(Study Guide, pp. 49)
Set equality:
For any sets A, B  U,
A = B iff A  B and B  A.

To prove A = B: prove that x  A iff x  B

Cartesian product:
A × B = {(x, y) | x  A and y  B}

Example:
Suppose A = {2, 3, 4} and B = {5, 6}, then
A × B = { (2, 5), (2, 6), (3, 5), (3, 6), (4, 5), (4, 6) }
Question 1b)
Determine whether, for all X, Y, W  U,
( X − Y )  W  ( X  W ) − ( Y  W ).
Solution:
Suppose ( p, q )  ( X − Y )  W (Cartesian product)
then p  ( X − Y ) and q  W
i.e. ( p  X and p  Y ) and q  W
i.e. ( pX and qW ) and ( pY and qW )
i.e. ( p, q )  ( X  W ) and ( p, q )  ( Y  W )
i.e. ( p, q )  ( X  W ) − ( Y  W ).
Thus ( X − Y )  W  ( X  W ) − ( Y  W ).
Handy notations:

an even number can be expressed as 2n,

an odd number as 2m + 1, and
a multiple of three as 3t, for some n, m, tZ.
…

Two consecutive numbers: k and k + 1 for

some k  Z.
 Relations (Study Guide, pp.69 - 97)
R  A  A: R a binary relation from A to A (or on A).
R reflexive on A: ∀xA, (x, x)  R.
R irreflexive: ∀xA, (x, x)  R.

R symmetric: ∀x, y  A, if (x, y)  R, then (y, x)  R.

R antisymmetric: ∀x, y  A, if x  y and (x, y)  R,

then (y, x)  R.
if (x, y)  R and (y, x)  R, then x = y.
R on A satisfies trichotomy: ∀x, y  A, such that
x ≠ y we have (x, y)  R or (y, x)  R.
E.g. R on Z: (v, w)  R iff w − v = 7k, k  Z.
Note order of variables:(x, y)  R: y − x = 7k
(y, z)  R: z − y = 7m
(x, z)  R: z − x = 7t
Def: R transitive: ∀ x, y, z Z,
if (x, y)  R and (y, z)  R, then (x, z)  R.

Proof: Assume (x, y)  R and (y, z)  R,

then y − x = 7k ➀ and z − y = 7m ➁
➀ + ➁: z − x = 7(k + m),
thus (x, z)  R.
(Study Guide, pp. 83 - 97)
Kinds of Relations:
R on A
• weak partial order:
reflexive on A, antisymmetric, and
transitive.

• strict partial order:

irreflexive, antisymmetric, and transitive.

Weak or strict total (or linear) order also

satisfies trichotomy.
(Study Guide, pp. 91 – 94)
A relation R on A is an equivalence relation
iff R is reflexive on A, symmetric, & transitive.

Equivalence classes:
[x] = {y | y  A and x R y}
Say [x1] & [x2] eq. classes of R: [x1], [x2]  A,
then
P = {[x1], [x2]} is a partition of A:
1. [x1] ≠ , [x2] ≠ ,
2. [x1]  [x2] = , and 3. [x1]  [x2] = A
Question 2a)
R on Z: (x, y)  R iff y - x is even.
Prove: R an equivalence relation. Show equivalence classes.
Solution:
Eq. rel: Reflexive on Z, symmetric & transitive
y - x is even, i.e. multiple of two, so
y - x = 2k for some k  Z.

Reflexivity: (Is ( x, x )  R for all x  Z?

i.e. is x - x = 2k for all x  Z?)
Proof:

For all x  Z, x - x = 0 = 2(0) with 0  Z.

Hence ( x, x )  R.
Thus R is reflexive on Z.
Symmetry: (If (x, y)  R, is (y, x)  R?)
Suppose (x, y)R,
then y – x = 2k for some k  Z ➀
– ➀: – (y – x) = – (2k)
i.e. x–y = 2 (– k), –kZ
Thus (y, x)  R, hence R is symmetric.

Transitivity: (If (x, y)R & (y, z)R. Is (x, z)R?)

Suppose (x, y)R and (y, z)  R then
y – x = 2k ➀ and z – y = 2m ➁
➀ + ➁: (y – x) + (z – y) = 2k + 2m
i.e. z–x = 2 (k + m), (k+m)Z
Thus (x, z)  R, hence R is transitive.
Continue
Equivalence classes of R:
[x] = { y | (x, y)  R } = { y | y - x = 2k for some kZ }
= { y | y = 2k + x for some kZ }
Let x = 0:
[0] = { y | y = 2k + 0, for some k  Z }
= {...,- 8, - 6, - 4, - 2, 0, 2, 4, 6, 8,...} (even integers)
Let x = 1:
[1] = { y | y = 2k + 1 , for some k  Z }
= { ..., - 7, - 5, - 3, - 1, 1, 3, 5, 7, ... } (odd integers)

Try x = ..-4,-2, 2, 4,.. then ...= [-4] = [-2] = [0] = [2] = [4] =...
Try x = ..-3,-1,3,5,.. then … = [-3] = [-1] = [1] = [3] = [5] =…

Two eq. classes: [0]  [1] = Z; [0]  [1] = ;

[0]   and [1]  .
thus S = { [0] , [1] } is a partition of Z.
Question 2

R on Z: (x, y)  R iff mx = y for some m  Z+.

(y is a multiple of x)
bi) Give element in R & element not in R.
Solution: ( 3, 12 )  R (3  4 = 12);

( 3, 4 )  R (4 is not a multiple of 3)
R is a weak partial order on Z because R is reflexive
on Z, antisymmetric, and transitive.
R not trichotomous:Counterex: (3,4)R and (4,3) R

Example: Relation T on B = {1, 2, 3, 4} satisfies trichotomy:

T = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
Each element of B is grouped with each other element
of B in ordered pairs of T.
 Functions (Study Guide, pp. 98 – 114)
R  X  Y:
domain of R: dom(R)  X,
range of R: ran(R)  Y (codomain = Y)

• dom(R) = {x | for some y  Y, (x, y)  R}

• ran(R) = {y | for some x  X, (x, y)  R}

R is function iff R is functional and dom(R)=X.

(functional: each element that appears as first co-
ordinate do so exactly once.)
Function denoted by R: X → Y.
Ex. f: Z→Z is def. by
f(x) = x + 2

Graph for f:

Consider function h: A → B:
h injective: if h(a1) = h(a2) then a1 = a2
h surjective: ran(h) = B
h bijective iff h injective & surjective
 Images

Ex: function f: Z→Z is def by f(x) = x2 - 3x and

function g: Z→Z is def by g(x) = 5x + 4

The image of x under f: f(x) = x2 - 3x

[ Examples: f(u) = u2 – 3u or even

f(m + 1) = (m + 1)2 - 3(m + 1) etc. ]

Composition:
f￮g(x) = f(g(x)) = (g(x))2 - 3g(x) (image of x under f￮g)
i.e. f(5x + 4) = (5x +4)2 - 3(5x +4)
Question 3 f on Z: (x, y)  f iff y = 3x – 1
g on Z: (x, y)  g iff y = 3 – x
(a)Prove f a function: f: Z→Z (i.e. f functional & dom (f)=Z)
Solution:
Is f functional? Yes.
Suppose (x, y)  f and (x, z)  f,
then y = 3x – 1 and z = 3x – 1
i.e. y = 3x – 1 = z
i.e. y = z.

Is dom (f) = Z? Yes.

dom(f) = { x | for some y  Z, (x, y)  f}

= { x | for some y  Z, y = 3x – 1}
= { x | 3x – 1 is an integer}
=Z
Question 3b)
f (y = 3x – 1) and g (y = 3 – x) functions on Z.
Which function not bijective? Do two tests on it.

Solution:
f not bijective: injective (one-to-one); but
not surjective (not onto).
f injective:
Suppose f(u) = f(v) for some u, v  Z,
then 3u – 1 = 3v – 1 i.e. u = v.
f not surjective: Counterexample:
Choose y = 3.
There is no x  Z such that f(x) = y,
i.e. such that 3x – 1 = 3. (x = 4/3  Z.)
Hence 3  ran(f) and thus ran(f)  Z.
Question 3 c) Determine inverse of bijective function g.
Solution: (y, x)  g-1 iff (x, y)  g
iff y = 3 – x
iff x = 3 – y

Hence g-1: Z → Z def. by g-1(y) = 3 - y

Question 3 d) Composition function f￮g. (f(x)=3x-1; g(x)=3-x)
Solution: f ￮ g(x) = f (g(x))
= f (3 – x) (replace g(x) by 3 – x))
= 3 (3 – x) – 1 (f(x) = 3x – 1))
= 8 – 3x

Thus f ￮ g: Z → Z def. by f ￮ g(x) = 8 – 3x.

 Operations (Study Guide, pp. 115 – 134)

Ex. Binary operation : X  X → X

• commutative:
x  y = y  x for all x, y  X.

• associative:
(x  y)  z = x  (y  z) for all x, y, z  X.

• an identity element:
e  x = x  e = x for all x  X.
Question 4
Let X = { b, c, d }
ai) Give example of binary operation * on X in a table:
* is commutative & has identity element.

* b c d * b c d
b b c d b b c d
c c c c c c c c
d d c d d d c d
Commutative: Symmetry around diagonal from top
left to bottom right corner. b is the identity element.
Question 4 Let X = { b, c, d }
aii) Show that your operation has both these properties,
and name the identity element. Solution:
Commutative
b * b = b = b * b; b*c = c = c*b
b * d = d = d * b; c*c = c = c*c
c * d = c = d * c; d*d = d = d*d
Check commutativity:
Diagonal top left to bottom right.
* b c d
Identity element: b, because b b c d
b*b = b = b * b, c c c c
c*b = c = b * c, and
d*b = d = b * d. d d c d
Question 4 Let X = { b, c, d }

aiii) Using your table, test for associativity (one ex.).

Decide from example: Does your binary operation

has the property of associativity?
Justify your answer.
Solution:
* b c d
b b c d
( b * c ) * d = c * d = c and
b*(c*d) =b*c=c c c c c
Example shows associativity, d d c d
but one example does not show that it
is true for all possible combinations.
Question 4

bi) Let Y = {, {}}. Complete the following table for the
binary operation  (intersection) on Y:

(Note:
 = { } ( has no elements) and
{} has one element namely , so  and {} has no
common elements, thus   {} =  .)

Solution:
  {}

  

{}  {}
Question 4 Let Y = {, {}}
  {}
bii) Write  in list notation.
  
{}  {}
Solution:
   = , so ( (,),  ) is an element in the set;
 {} = , so ( (,{}),  ) is an element in set;
etc.

 in list notation:
{ ( (,),  ), ( (,{}),  ), ( ({},),  ),
( ({},{}), {} ) }
Logic (Study Guide, pp. 135 – 165)
Connectives for declarative disjunction
statements p & q: , , →,  p q
p q
conjunction
p q T T T
pq
T F T
T T T
F T T
T F F
F F F
F T F
F F F biconditional
p q
pq
conditional
p q T T T
p→q
T F F
T T T
F T F
T F F
F T T F F T
F F T
Declarative statement True or False
Compound statement always true: tautology
Compound statement always false: negation

Statements p and q logically equivalent:

p  q iff p  q a tautology

De Morgan’s laws:
• ¬ (p  q)  ¬ p  ¬ q
• ¬ (p  q)  ¬ p  ¬ q

NOTE: p → q  ¬ p  q
Universal quantifiers e.g.:
• “For all x  Z …” i.e. “∀ x  Z …”
Existential quantifiers e.g.:
• “There exists an x  Z …” i.e.“∃ x  Z …”

Predicate P(x):
P(x) is true for any variable x  A that satisfies the
property, and P(x) is false otherwise.
Eg if P(x) is the pred. “x is an even integer”: P(x) is
True ∀ even integers and false ∀ odd integers.

Negation:
• ¬ (∀ x  A, P(x)) i.e. ∃ x  A, ¬ P(x)
• ¬ (∃ x  A, P(x)) i.e. ∀ x  A, ¬ P(x)
Question 5a)
Write the English sentence
‘If the wind is blowing then it will bring wind or rain’
in symbolic logic notation.
Use
the letter t for ‘the wind is blowing’,
the letter d for ‘it will bring wind’ and
the letter h for ‘it will bring rain’.

Solution:
Symbolic logic notation:
t → (d  h)
Question 5b)
Use the double negation property and De
Morgan’s laws to rewrite the following expression
as an equivalent statement that does not have the
not symbol (¬) outside parentheses.

¬ (q  (¬ q  p))

Solution:

¬ (q  (¬ q  p))
 ¬ q  ¬ (¬ q  p) De Morgan’s law
 ¬ q  (¬ ¬ q  ¬ p) De Morgan’s law
 ¬ q  (q  ¬ p) Double negation
Question 5c)
Use a truth table to determine whether the compound statement
( ¬p  q )  [ ¬( p → q ) ]
is a tautology, a contradiction or neither.
Solution:

p q ¬p ¬p  q p → q ¬(p → q) (¬p  q) 
[ ¬ (p → q) ]
T T F T T F F
T F F F F T F
F T T T T F F
F F T T T F F

All values false, the statement is a contradiction.

Question 5d)
Let D = {1, 2, 4}. Provide negation of following statement:
∀ xD, 4x + 1  16
Which is true, the original statement or the negation?
Solution:
Negation: ∃ xD, 4x + 1 > 16
x 4x + 1
1 5
2 9
4 17
4x + 1 > 16 true for x = 4.

So there exists an x D such that 4x + 1 > 16.

Thus negation is true.

Question 5e)
Prove “for any n  Z, if 5n2 is odd then n is odd”
(p →q) by using contrapositive of given statement.

Solution:
(To prove: (¬q) → (¬p),
i.e. if n is not odd, then 5n2 is not odd,
i.e. if n is even then 5n2 is even.)

Suppose n is even, then n=2k, for some k  Z.

Then 5n2 = 5(2k)2 = 5(4k2) = 2(10k2)

i.e. 5n2 is even.
Question 5f)
Prove by contradiction (reduction ad absurdum) that for any
integer n, if n2 + 2n is even then n is even.
Solution:
Suppose n2 + 2n is even.
Two possibilities: either n is odd or n is even.
Suppose n is odd, i.e. n = 2k + 1 for some kZ. ***
Then n2 + 2n = (2k + 1)2 + 2(2k + 1)
= 4k2 + 8k + 3
= (4k2 + 8k + 2) + 1
= 2(2k2 + 4k + 1) + 1, i.e. n2 + 2n is odd
This contradicts initial supposition,
so questionable supposition*** wrong,
thus n is even if n2+2n is even.
 mixed
Power set of A: set that has as members all the subsets of A
Example:
A = {1, {1}}: 2 elements: 1 and {1} (n = 2)
Ƥ (A) = { , {1}, {{1}}, {1, {1}} } (nr of elements: 2 to power n)

Ex. of factorisation:
x2 – 4x + 3 < 0
i.e. (x – 3)(x – 1) < 0
then (x – 3) > 0 and (x – 1) < 0 (pos. nr  neg. nr = neg. nr)
i.e. x > 3 and x < 1 ___1______3____ impossible
OR
(x – 3) < 0 and (x – 1) > 0
i.e. x < 3 and x > 1, ___1______3____
i.e. 1 < x < 3.
Question 6 Let A = { 1, 2, 3 }, B = { 0, 1 } and C = {  }.
a) Give A + B and an equivalence relation on A + B (not identity relation).

Solution: A+B={ 0, 2, 3 } Equivalence relation on A+B:

{ ( 0, 0 ) , ( 2, 2 ) , ( 3, 3 ) , ( 0, 2 ) , (2, 0 ) }
b) Determine values of sets:

Ƥ(B)Ƥ (C); Ƥ(BC); Ƥ(B)–Ƥ(C); Ƥ(B)+Ƥ(C)

Solution: Ƥ (B)={, { 0 }, { 1 }, { 0, 1 }}; Ƥ (C)={ , {}};

hence Ƥ (B)  Ƥ (C) = {}.

B  C = ; hence Ƥ (B  C) = {  }.

Ƥ (B) – Ƥ (C) = { { 0 }, { 1 }, { 0, 1 } }
Ƥ (B) + Ƥ (C) = { {}, { 0 }, { 1 }, { 0, 1 } }
Question 6 Let A = { 1, 2, 3 }, B = { 0, 1 } and C = {  }.
c) Give injective function on B  B.
Solution:
BB = { (0, 0) , (0, 1) , (1, 0) , (1, 1) };
Injective function on BB :
{((0,0), (0,0)), ((0, 1), (0, 1)), ((1, 0), (1, 0)), ((1, 1), (1, 1))}
d) Give example of surjective function from B  B to B  C.
Solution: Surjective: Ran(f) = B  C. Function: Each member
of BB must appear only once as first co-ordinate.

B  B = { (0,0), (0,1), (1,0), (1,1) } and

B  C = { 0, 1,  }
Surjective function: { ( (0,0), 0 ), ( (0,1), 1 ),
( (1,0), 1 ), ( (1,1),  ) }
Question 6 Let A = { 1, 2, 3 }, B = { 0, 1 } and C = {  }.

e) Give simplest equivalence relation on Ƥ (C).

Solution:

Relation: Reflexive on Ƥ (C), symmetric and

transitive.
Ƥ (C) = { , {  } }
Simplest equivalent relation on Ƥ (C):
Identity relation: { (, ) , ({  }, {  }) }
f) Give an example of a partition of B.
Solution:
One example: {{0}, {1}}
({0}   & {1}  ; {0}  {1} = B; {0}  {1} = )