Exams › GATE › Engineering Mathematics

Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a 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”?

1. ¬∀x (Graph(x) ⇒ Connected(x))
2. ∃x (Graph(x) ∧ ¬Connected(x))
3. ¬∀x (¬Graph(x) ∨ Connected(x))
4. ∀x (Graph(x) ⇒ ¬Connected(x))

Correct answer: ∀x (Graph(x) ⇒ ¬Connected(x))

Solution

The option states that for every graph, it is not connected, which implies that all graphs are disconnected. This contradicts the original statement that not every graph is connected, as it suggests that every graph fails to be connected.

Related GATE Engineering Mathematics questions

• Organic fraction of municipal solid waste (OFMSW) with bulk density of 315 kg/m³ and water content of 30% is mixed with municipal sludge of bulk density 700 kg/m³ and water content of 70%, such that the water content of the mixture is 40%. The amount (in kg) of sludge to be mixed per kg of OFMSW (rounded off to 2 decimal places) and the density of the mixture (in kg/m³) (rounded off to the nearest integer) are calculated. Which of the following options is/are true:
• A probability distribution with right skew is shown in the figure. The correct statement for the probability distribution is
• The probability density function of a continuous random variable distributed uniformly between x and y (for y > x) is
• The dimension of dynamic viscosity is:
• A single-lane highway has a traffic density of 40 vehicles/km. If the time-mean speed and space-mean speed are 40 kmph and 30 kmph, respectively, the average headway (in seconds) between the vehicles is
• A fair (unbiased) coin was tossed four times in succession and resulted in the following outcomes: (i) H head, (ii) H head, (iii) H head, (iv) H head. The probability of obtaining a 'Tail' when the coin is tossed again is

⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →