Engineering Mathematics - Mathematical Logic and Graph Theory
Exam Duration: 45 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
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\)
The following resolution rulwe is used in logic programming .Drive clause ( P \(\wedge \) Q ) from clauses ( P \(\vee \) R ) \(\wedge \) (Q \(\vee \neg \) R ).
Which of the following statements related to this rule is false?
- (a)
P \(\vee \) R \(\wedge \) (Q \(\vee \neg \) R ) \(\Rightarrow\) (P \(\vee \) R ) is logically valid
- (b)
(P \(\vee \) Q ) \(\Rightarrow\) ( P \(\vee \) R ) \(\wedge \) (Q \(\vee \neg \) R ) is logically valid
- (c)
(P \(\vee \) Q ) is satisfiable if and only if ( P \(\vee \) R ) \(\wedge \) (Q \(\vee \neg \) R ) is satisfiable
- (d)
(P \(\vee \) Q ) \(\Rightarrow\) False if and only if both P anmd Q are 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)
