Engineering Mathematics - Mathematical Logic and Graph Theory

Buy GATE - Civil Engineering Practice test pack

Question - 1

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

Question - 2

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

Question - 3

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))\)

Question - 4

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

Question - 5

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))\)

Question - 6

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))}]

Question - 7

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

Question - 8

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

Question - 9

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

Question - 10

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\)
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next
Previous Next