GATE 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
k5 and k3,3 are the smallest non-planar graphs, Out of this k5 has 5 vertices and 5C2 = 10 edges and k3,3 has 6 vertices and 3 x 3 = 9 edges. So, the non-planar graph with minimum number of edges. So, the non-planar graph with minimum number of edges is k3,3 with 9 edges and 6 vertices.
Note k5 is the non-planar graph with minimum number of 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
Given, V=13, E=19
Let, R be the number of regions
Applying Euler's formula (Here faces and regions mean one and the same)
R = E - V + 2 = 19 - 13 + 2 = 8
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))\)
The correct translation of gold and silver ornaments are precious is choice (d).
\(\forall x((G(x)\wedge S(x))\rightarrow P(x))\)
which reads as "if an ornament is gold or silver, then it is precious". Since, a given ornament cannot be both gold and silver at the same time.
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
\((i)\quad P\wedge \sim Q\equiv p+{ q }^{ ' }\)
\((ii)\quad \sim (\sim P\wedge Q)\equiv { \left( { P }^{ ' }+q \right) }^{ ' }\equiv p+{ q }^{ ' }\)
\((iii)\quad (P\wedge Q)\vee (P\wedge \sim Q)\vee (\sim P\wedge \sim Q)\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv pq+{ pq }^{ ' }+{ p }^{ ' }{ q }^{ ' }\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv p(q+{ q }^{ ' })+{ p }^{ ' }{ q }^{ ' }\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv p+{ p }^{ ' }{ q }^{ ' }\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv (p+{ p }^{ ' })(p+{ q }^{ ' })\quad \\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv p+{ q }^{ ' }\)
\((iv)\quad (P\wedge Q)\vee (P\wedge \sim Q)\vee (\sim P\wedge Q)\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv pq+{ pq }^{ ' }+{ p }^{ ' }{ q }\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv p(q+{ q }^{ ' })+{ p }^{ ' }{ q }\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv p+{ p }^{ ' }{ q }\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv (p+{ p }^{ ' })(p+{ q })\\ \quad \quad \quad \quad \quad \quad \quad \quad \equiv p+q\)
Clearly, (i), (ii), (iii) are equivalent. Correct choice is (b).
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))\)
The statement 'Not every graph is connected' is same as 'There exists some graph which is not connected' which is same as \(\exists x\{ graph(x)\wedge \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))}]
The given statement should be read as 'If an animal is a tiger or a lion, then (if the animal is hungry or threatened) it will attack.'
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
If an n-vertex simple connected graph contains no cycles of odd length, then its chromatic number is two, since the vertices can be alternately coloured with first colour, then the second colour, then the first colour and then the second colour and so on.
Alternatively, since a simple connected graph with no cycles of odd length must be bipartite and since, the chromatic number of a bipartite graph is always 2 (in a bipartite graph each partition requires one colour (there are no edge within a partition of a bipartite graph) and there are only two partitions).
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
\({ P }_{ 1 }:((A\wedge B)\rightarrow C)\equiv ((A\rightarrow C)\wedge (B\rightarrow C))\)
LHS \((A\wedge B)\rightarrow C)\) \(\equiv AB\rightarrow C\)
\(\equiv { \left( AB \right) }^{ ' }+C\\ = { A }^{ ' }+{ B }^{ ' }+C\)
RHS \((A\rightarrow C)\wedge (B\rightarrow C)\equiv \left( { A }^{ ' }+C \right) \left( { B }^{ ' }+C \right) \)
\(={ A }^{ ' }{ B }^{ ' }+C\)
\(\Rightarrow \quad \quad \quad RHS\neq LHS\)
\(\therefore \) P1 is not tautology
\({ P }_{ 2 }:((A\vee B)\rightarrow C)\equiv ((A\rightarrow C)\vee (B\rightarrow C))\)
LHS \((A\vee B)\rightarrow C)\) \(\equiv A+B\rightarrow C\)
\(\equiv { \left( A+B \right) }^{ ' }+C\\ ={ A }^{ ' }{ B }^{ ' }+C\)
RHS \((A\rightarrow C)\vee (B\rightarrow C)\)
\(\equiv \left( { A }^{ ' }+C \right) +\left( { B }^{ ' }+C \right) \quad \quad \\ ={ A }^{ ' }{ +B }^{ ' }+C\)
\(\Rightarrow \quad \quad \quad LHS\neq RHS\)
\(\Rightarrow \) P2 is also not tautology.
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\)
\(X:(P\vee Q)\rightarrow R\\ Y:(P\rightarrow R)\vee (Q\rightarrow R)\\ X:P+Q\rightarrow R\equiv (P+Q)'+R\equiv P'Q'+R\\ Y:(P'+R)+(Q'+R)\equiv P'+q'+R\\ Clearly,\quad X\ncong Y\\ Consider\quad X\rightarrow Y\\ \equiv (P'Q'+R)\rightarrow (P'+Q'+R)\\ \equiv (P'Q'+R)'+P'+Q'+R\\ \equiv (P'Q')'R'+P'+Q'+R\\ \equiv (P+Q)R'+P'+Q'+R\\ (\because \quad by\quad distribution\quad law)\\ \equiv PR'+QR'+P'+Q'+R\\ \equiv (PR'+R)+(QR'+Q')+P'\\ \equiv (P+R)(R'+R)+(Q+Q')\times (R'+Q')+P'\\ \equiv P+P'+R+R'+Q'\quad (by\quad complement\quad law)\\ \equiv 1+1+Q'\equiv 1\\ \therefore \quad X\rightarrow Y\quad is\quad tautology.\)
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)\} ]\)
Every teacher is liked by some students, then the logical expression is \(\forall (x)[teacher(x)\rightarrow \exists (y)\)
[student (y)^likes y(x)]].
Where, likes (y,x) mean y likes x, such that y represents the student and x represents the teacher.
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
\(P\rightarrow (Q\vee R)\equiv P\rightarrow Q+R\\ \equiv P'+Q+R\\ P\wedge Q\rightarrow R\equiv PQ\rightarrow R\\ \equiv (PQ)'+R\\ \equiv P'+Q'+R\\ \therefore \quad [P\rightarrow (Q\vee R)\rightarrow [(P\wedge Q)\rightarrow R]\\ \equiv (P'+Q+R)\rightarrow P'+Q'+R\\ \equiv (P'+Q+R)'+P'+Q'+R\\ \equiv PQ'R'+P'+Q'+R\\ \equiv P'+Q'+R\quad (by\quad complement\quad law)\\ Which\quad is\quad a\quad contigency.\)
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)] \)
\(p\Rightarrow q\equiv \sim p\vee q\\ (B(x,x)\rightarrow [B(x,y),C(y)\rightarrow A(x)]\\ \equiv \neg B(x,x)\vee [B(x,y)\wedge C(y)\rightarrow A(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
Drive clause P \(\vee \) Q from clauses P \(\vee \) R ,Q \(\vee \neg \) R means that ( P \(\vee \) R ) \(\wedge \) Q \(\vee \neg \) R \(\Rightarrow\) P \(\vee \) Q
Since, x \(\Rightarrow\) y doesnot imply that y \(\Rightarrow\) x
( P \(\vee \) Q ) \(\wedge \) (P \(\vee \neg \) R )\(\Rightarrow\) (Q \(\vee \) R)
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}\) )
T(1) = 1
T(2) = T(1) + \(\left\lfloor \sqrt { 2 } \right\rfloor \)
= 1+ 1
= 2
T(3) = T(2) + \(\left\lfloor \sqrt { 3 } \right\rfloor \)
= 2+ 1
= 3
T(4) = T(3) + \(\left\lfloor \sqrt { 4 } \right\rfloor \)
= 3+ 2
= 5
T(5) = T(4) + \(\left\lfloor \sqrt { 5 } \right\rfloor \)
= 5+ 2
= 7
T(6) = T(5) + \(\left\lfloor \sqrt { 6 } \right\rfloor \)
= 7+ 2
= 9
T(7) = T(6) + \(\left\lfloor \sqrt { 7 } \right\rfloor \)
= 9+ 2
= 11
T(8) = T(7) + \(\left\lfloor \sqrt { 8 } \right\rfloor \)
= 11 +2
= 13
T(9) = 13 + \(\left\lfloor \sqrt { 9 } \right\rfloor \)
= 16 and so on till
T(16) = 16 \(\times\) 6 + 3 + 4 = 38
\(\therefore\) T(1) = 1 , T (4) = 5 , T(9) = 16 and T(16) = 38
(a) does not satisfy T(16)
(c) does not satisfy T(4)
(d) doesnot satisfy T(1)
\(\therefore\) (b) which satisfy T(1) upto T(16).