cs702_final_term_2_www.vu786.com.rar_algorithm

www.vu786.com

Solved paper of cs702

Problem # 1 (((5+5+5) + (5+5) = 25 Points)))

a)

Let N be a set of natural numbers. The symbols, < (less than), ≤ (less than or equal) and = (equal)

are relations over N. Prove or disprove the following.

Reflexive:

A binary relation R on a set A is said to be reflexive if

(x, x) Є R, for all x Є A.

‘<’ Relationship is not reflexive.

Example:

x < x is not possible.

Symmetric:

A relation R between the elements in a universal set is called symmetric when x R y always implies y

R x; in other words, when R is symmetric it does not matter whether x is written first or y is written

imply x R z.

‘<’ is transitive.

Example:

If x < y and y < z; then x < z is true.

2. ≤ is reflexive, symmetric and transitive?

Reflexive:

A binary relation R on a set A is said to be reflexive if

(x, x) Є R, for all x Є A.

first in the expression x R y.

‘≤’ Relationship is not symmetric.

Example:

If x ≤ y then y ≤ x is not possible for x < y.

Transitive:

A relation R between the elements in a universal set is called transitive when x R y and y R z always

imply x R z.

‘≤’ Relationship is transitive.

www.vu786.com

Example:

If x ≤ y and y ≤ z; then x ≤ z is true.

Example:

x = x is true.

Symmetric:

A relation R between the elements in a universal set is called symmetric when x R y always implies y

R x; in other words, when R is symmetric it does not matter whether x is written first or y is written

first in the expression x R y.

‘=’ Relationship is symmetric.

Example:

If x = y then y = x is true.

b)

Prove that ¬ C ⇒ ¬ (B ∧ (B ⇒ C)) by

1. Logical equivalences

2. Truth table

Solution:

1- By Logical Equivalence

()()()()(()()()()()()()~~~~(~)~~~~~~~~~~~~~TrueHenceprovedthat~~CBBCCBBCCBBBCCfB

CCBCCBCCBCCCBtBCBBC→∧→⇒→∧∨⇒→∧∨∧⇒→∨∧⇒→∧⇒∨∧⇒∨∨⇒∨∨⇒∨⇒→∧→

2- By Truth Table

C

C

Problem # 2 (((5+5+5) + (5+5) = 25 Points)))

www.vu786.com

a)

2

Solution:

1.

Let P(n) denote the proposition

Note that

1+3+5+…..+(2k-1) +(2k+1) = k

+2k+1

= (k+1)

2

Basic Step:

P(1) is true, since 2=2

= (k+1) ((k+1)+1)

So P(k+1) true, by induction, P(n) is true for all n belongs to positive integers.

3.

Deduce the result of part 2 from part 1:

Similarly, vice versa

Subtracting 1 from each of the first m even numbers gives us the first m odd numbers, i.e.