Engineering Mathematics - Mathematical Logic and Graph Theory
Exam Duration: 30 Mins Total Questions : 15
Let G be a non-planar graph with the minimum possible number of edges. Then, G has
- (a)
9 edges and 5 vertices
- (b)
9 edges and 6 vertices
- (c)
10 edges and 5 vertices
- (d)
10 edges and 6 vertices
Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is
- (a)
0
- (b)
8
- (c)
9
- (d)
13
Which one of the following is the most appropriate logical formula to represent the statement 'Gold and silver ornaments are precious'?
The following notations are used
G(x) : x is a gold ornament
S(x) : x is a silver ornament
P(x) : x is precious
- (a)
\(\forall x(P(x))\rightarrow (G(x)\wedge S(x))\)
- (b)
\(\forall x(G(x)\wedge S(x)\rightarrow P(x))\)
- (c)
\(\exists x((G(x)\wedge S(x))\rightarrow P(x))\)
- (d)
\(\forall x((G(x)\wedge S(x))\rightarrow P(x))\)
P and Q two propositions. Which of the following logical expressions are equivalent?
\(1.\quad P\wedge \sim Q\\ 2.\quad \sim (\sim P\wedge Q)\\ 3.\quad (P\wedge Q)\vee (P\wedge \sim Q)\vee (\sim P\wedge \sim Q)\\ 4.\quad (P\wedge Q)\vee (P\wedge \sim Q)\vee (\sim P\wedge Q)\)
- (a)
1 and 2
- (b)
1, 2 and 3
- (c)
1, 2 and 4
- (d)
All of 1, 2, 3 and 4
Let graph (x) be a predicate which denotes that x is a graph. Let connected (x) be predicate which denotes that x is connected. Which of the following first order logic sentences does not represent the statement 'Not every graph is connected'?
- (a)
\(\neg \forall \) x (graph(x)\(\Rightarrow \)connected(x))
- (b)
\(\exists x(graph(x)\wedge \neg connected(x))\)
- (c)
\(\neg \forall (\neg graph(x)\vee connected(x))\)
- (d)
\(\forall x(graph(x))\Rightarrow \neg connected(x))\)
Which one of the first order predicate calculus statements given below, correctly expresses the following english statement?
Tiger and lions attack, if they are hungry or threatened.
- (a)
\(\forall x\) [(tiger (x) \(\wedge \) lion (x))\(\rightarrow \){(hungry (x) \(\vee \) threatened (x))\(\rightarrow \)attacks(x))}]
- (b)
\(\forall x\) [(tiger (x) \(\vee\) lion (x))\(\rightarrow \){(hungry (x) \(\vee \) threatened (x))\(\rightarrow \)attacks(x))}]
- (c)
\(\forall x\) [(tiger (x) \(\vee \) lion (x))\(\rightarrow \){(attacks(x)\(\rightarrow \)hungry (x) \(\vee \) threatened (x))}]
- (d)
\(\forall x\) [(tiger (x) \(\vee\) lion (x))\(\rightarrow \){(hungry (x) \(\vee \) threatened (x))\(\rightarrow \)attacks(x))}]
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n \(\ge \) 2
- (a)
2
- (b)
3
- (c)
n-1
- (d)
n
Which one of the following is true for any simple connected undirected graph with more than 2 vertices?
- (a)
No two vertices have the same degree
- (b)
Atleast two vertices have the same degree
- (c)
Atleast three vertices have the same degree
- (d)
All vertices have the same degree
Consider the following propositional statements
\({ P }_{ 1 }:((A\wedge B)\rightarrow C)\equiv ((A\rightarrow C)\wedge (B\rightarrow C))\)
\({ P }_{ 2 }:((A\vee B)\rightarrow C)\equiv ((A\rightarrow C)\vee (B\rightarrow C))\)
Which one of the following is true?
- (a)
P1 is a tautology, but not P2
- (b)
P2 is a tautology, but not P1
- (c)
P1 and P2 are both tautologies
- (d)
Both P1 and P2 are not tautologies
Let P, Q and R be three atomic propositional assertions. Let X denotes (P V Q) \(\rightarrow\) R and Y denotes \((P\rightarrow R)\nu (Q\rightarrow R)\). Which one of the following is a tautology?
- (a)
\(X\equiv Y\)
- (b)
\(X\rightarrow Y\)
- (c)
\(Y\rightarrow X\)
- (d)
\(\rightharpoondown Y\rightarrow X\)
What is the first order predicate calculate calcus statement equivalent to the following?
Every teacher is liked by some students.
- (a)
\( \forall (x)[teacher(x)\rightarrow \exists (y)\{ student\quad (y)likes(y,\quad x)\} ]\)
- (b)
\(\forall (x)[teacher(x)\rightarrow \exists (y)\{ student\quad (y)\wedge likes(y,\quad x)\} ]\)
- (c)
\(\exists (y),\forall (x)\{ teacher(x)\rightarrow \{ student(y)\wedge likes(y,x)\} ]\)
- (d)
\(\forall (x)\{ teacher(x)\wedge \exists (y)\{ student(y)\rightarrow likes(y,x)\} ]\)
The following propositional statement
\((P\rightarrow (Q\vee R))\rightarrow ((P\wedge Q)\rightarrow R)is\)
- (a)
Satisfible but not valid
- (b)
valid
- (c)
a contradiction
- (d)
None of the above
Consider the following logic program P:
\(A(x)\leftarrow B(x,y),C(y)\\ \quad \quad \quad \leftarrow B(x,x)\)
Which of the following first order sentences is equivalent to P?
- (a)
\((\forall x)[\exists y][B(x,y)\wedge C(y)]\Rightarrow A(x)]\wedge \neg (\exists x)[(B(x,x)] \)
- (b)
\((\forall x)[Ay][B(x,y)\wedge C(y)]\Rightarrow A(x)]\wedge \neg (\exists x)[(B(x,x)] \)
- (c)
\((\forall x)[Ey][B(x,y)\wedge C(y)]\Rightarrow A(x)]\wedge \neg (\exists x)[(B(x,x)] \)
- (d)
\((\forall x)[Ay][B(x,y)\wedge C(y)]\Rightarrow A(x)]\wedge \neg (\exists x)[(B(x,x)] \)
The following resolution rule is used in logic programming. Drive clause (P^Q) from clauses (PvR),\((Q\wedge \neg R)\)
Which one of the following statements related to this rule is false?
- (a)
\(\\ P\vee R\wedge (Q\vee \neg R)\Rightarrow (P\wedge R)is\quad logically\quad valid\)
- (b)
\(P\wedge Q\Rightarrow (P\vee R)\wedge (Q\vee \neg R)\quad is\quad logically\quad valid\)
- (c)
\(\\ (P\vee R)is\quad satisfiable\quad if\quad and\quad only\quad if\quad (P\vee R)\wedge (Q\wedge \neg R)\quad is\quad satisfiable\)
- (d)
\(\\ (P\vee Q)\Rightarrow False\quad if\quad and\quad only\quad if\quad both\quad P\quad and\quad Q\quad are\quad unsatisfiable\)
Consider the following recurrence relationT(1) = 1
T(n+1) = T(n) = \(\left\lfloor \sqrt { { n }^{ 2 }+1 } \right\rfloor \) , \(\forall \) n \(\ge \) 1. The value of T(m2) for m \(\ge \) 1 is
- (a)
\(\frac{m}{6}\) (21m - 39) +4
- (b)
\(\frac{m}{6}\) (4m2-3m+5)
- (c)
\(\frac{m}{2}\)(3m2.5 - 11m+20) -5
- (d)
\(\frac{m}{6}\) ( 5m3-34m2-137m-104+\(\frac{5}{6}\) )
1654060945.png)
1654060942.png)
1653987551.png)
1653987086.png)
1582095229.jpg)
