# Mfcs important questions

1.

(a) Construed a truth table for each of there (easy) compound statements

i. (p -> q)( p ->q)

ii. p ->(qV r)

(b) Write the negation of the following statements.

i. Jan will take a job in industry or go to graduate school.

ii. James will bicycle or run tomorrow.

iii. If the processor is fast then the printer is slow.

2. Prove using rules of inference or disprove.

(a) Duke is a Labrador retriever

All Labrador retriever like to swin

Therefore Duke likes to swin.

(b) All ever numbers that are also greater than

2 are not prime

2 is an even number

2 is prime

Therefore some even numbers are prime.

UNIVERSE = numbers.

(c) If it is hot today or raining today then it is no fun to snow ski today

It is no fun to snow ski today

Therefore it is hot today

UNIVERSE = DAYS

3.

(a) Consider f; Z+ à Z+ define by f (a)=. a2. Check if f is one-to-one and / or

into using suitable explanation.

(b) What is a partial order relation? Let S = { x,y,z} and consider the power set

P(S) with relation R given by set inclusion. ISR a partial order.

(c) Define a lattice. Explain its properties

4

(a) State and explain the properties of the pigeon hole principle.

(b) Apply is pigeon hole principle show that of any 14 integers are selected from

the set S={1, 2, 3...........25} there are at least two where sum is 26. Also write

a statement that generalizes this result.

(c) Show that if eight people are in a room, at least two of them have birthdays

that occur on the same day of the week. [4+8+4]

5,6,7,8,9,10
5

(a) Determine whether the following relations are injective or surjective or bijective, Find the inverse of the functions if they exist.

i. A={v,w,x,y,z} B={1,2,3,4,5} f1={(v,2),(w,1),(x,1),(y,5)}

ii. A={1,2,3,4,5} B={1,2,3,4,5} f2={(1,2),(2,3),(3,4),(4,5),(5,1)}

(b)Let P(S) be the power set of a non -empty set S. Let ‘n' be an operation in

P(S). Prove that associate law and commutative law are true for the operation

‘n' in P(S).

6

(a) Let p,q and r be the propositions.

P: you have the flee

q: you miss the final examination.

r: you pass the course.

Write the following proposition into statement form.

i. P-> q

ii. p-> r

iii. q ->r

iv. pVqVr

v. (p ->r) V (q -> r)

vi. (pq) V (7qr)

(b) Define converse, contrapositive and inverse of an implication.

7

(a) Let p,q and r be the propositions.

P: you have the flee

q: you miss the final examination.

r: you pass the course.

Write the following proposition into statement form.

i.pq

ii.p<->q

iii.p->q

iv. pqr

v.(p->q)(q->7r)

vi.(pVq)(7qVr)

(b) Construct truth tables for AND, OR, NEGATION, IMPLICATION and BIIMPLICATION.

8

a)Define group.

b) The set of integers Z, is an abelian group under the composition defined by o

such that aob = a + b+ 1 for a, b 2 Z. Find

i. the identity of (Z, o ) and

ii. inverse of each element of Z.

9. Define Semi group. Verify which of the following are semi groups.

i. (N, +),

ii. (Q, -),

iii. (R, +)

iv. (Q, o), aob = a - b +ab.

10.

(a) Let P(x) denote the statement. “x is a professional athlete” and let Q(x)denote

the statement” “x plays soccer”. The domain is the let of all people. Write

each of the following proposition in English.

i. x (P (x)-> Q(x))

ii. x (P (x)Q(x))

iii. x (P (x) V Q(x))

(b) Write the negation of each of the above propositions, both in symbols and in

words.

11,12,13,14,15,
11.

(a) Let P(x) denote the statement. “x is studying engineering” and let Q(x)denote

the statement” “x studying computer engineering”. The domain is the let of all people. Write

each of the following proposition in English.

i. x (P (x) Q(x))

ii. x (P (x)7Q(x))

iii. x (P (x) -> Q(x))

(b) Write the negation of each of the above propositions, both in symbols and in

words.

12.Check whether the following statements are logically equivalent or not.

i. ((pvq)->r)ó((p->r)(q->r))

ii.((p->q)(p->r))ó(p->(qr))

iii. ((p->q)->r)ó ((p7r)->7q)

(prove by using truth table)

13.

(a) Define partial order and total order of relations.

(b) If R is a relation defined on the set Z by a R b if a-b is a non negative even

integer. Determine if R define a partial order and total order.

14.

(a) If a, b are any two elements of a group (G, .) which commute show that

i. a - 1 and b commute,

ii. b - 1 and a commute and

iii. a - 1 and b - 1 commute.

(b) Let S be a non-empty set and o be an operation on S defined by aob=a for a,

b 2 S. Determine whether o is commutative and associative in S.

15. (a) Define a bijective function. Explain with reasons whether the following func-

tions are bijiective or not. Find also the inverse of each of the functions.

i. f(x) = 4x+2, A=set of real numbers

ii. f(x) = 3+ 1/x, A=set of non zero real numbers

(b) Let f and g be functions from the positive real numbers to positive real numbers

defined by

f(x) = ?2x?

g(x) = x2

Calculate f o g and g o f. [10+6]

16.
(a) Define a bijective function. Explain with reasons whether the following func-
tions are bijiective or not. Find also the inverse of each of the functions.
i. f(x) = x2, A=set of integers
ii. f(x) = x3, A=set of real numbers
iii. F(x)=sin(x) A=set of integers

(b) Let f and g be functions from the positive real numbers to positive real numbers
defined by
f(x) = 2x+3
g(x) = x2+2
Calculate f o g and g o f.

17.
(a) If G is the set of even integers i.e., G = { ... - 4, - 2, 0,2,4.....}, then prove that
G is an abelian group with usual addition as the operation.

(b) Let G = { - 1, 0, 1} . Verify whether G forms a group under usual addition.

18.
(a) Explain about types of lattices.
(b) Explain the properties of lattices.
(c)What is partial order relation R is
[23:04] gtarun_1990: edi enti ra
[23:04] gtarun_1990: 18 qus aaa
[23:05] deepak Sharma: (c)What is partial order relation R is a relation defined on the set of integers, check whether R is partial order or not.(R=divisability)

19.
(a) State and explain the properties of the pigeon hole principle.
(b) Show that if any five numbers are selected from 1 to 8 then sum of any two numbers is 12.
(c) Show that if any 30 people are selected, one may choose to subset of 5, so that 5 are born on same day of the week.

20.
(a) Use De Morgon’s laws to write the negations.
i. I want a car and a worth cycle.
ii. My cat stays outside or it makes a mess.
iii. I have fallen and I can’t get up.
iv. You study or you don’t get a good grade.

(b)Are (p->q)->r and (p->(q->r)) logically equivalent.

Justify using truth table.

21.
(a)Construct truth tables for
i.(p->q)v(p->7q)