GATE CS

Propositional and first-order logic

Propositional logic studies statements built from true/false atoms with connectives, and first-order logic adds predicates and the quantifiers $\forall$ and $\exists$ over a domain. In GATE questions you use it to decide equivalence, validity and satisfiability, to check whether an argument follows, to translate English into formulae, and to negate or compare quantified statements.

7 previous-year questions · 7 solved · 5 practice questions

Propositions, connectives and truth tables

A proposition is a declarative statement that is either true or false. We build compound propositions from atoms $p, q, r, \dots$ using the connectives $\neg$ (not), $\land$ (and), $\lor$ (inclusive or), $\to$ (implies), $\leftrightarrow$ (if and only if) and $\oplus$ (exclusive or).

Convention on brackets. Here $\neg$ binds tightest, then $\land$ , then $\lor$ , then $\to$ , then $\leftrightarrow$ , and brackets are written wherever they matter. $\land$ , $\lor$ , $\leftrightarrow$ and $\oplus$ are associative, but $\to$ is not: $(p \to q) \to r$ and $p \to (q \to r)$ differ when $p$ , $q$ and $r$ are all false (the first is false, the second true).

Truth tables of the connectives (T = true, F = false)

$p$	$q$	$\neg p$	$p \land q$	$p \lor q$	$p \to q$	$p \leftrightarrow q$	$p \oplus q$
T	T	F	T	T	T	T	F
T	F	F	F	T	F	F	T
F	T	T	F	T	T	F	T
F	F	T	F	F	T	T	F

The implication $p \to q$ is false in exactly one case: $p$ true and $q$ false. When $p$ is false the implication is true whatever $q$ is (it is vacuously true).

IMPLICATION AS A DISJUNCTION

p \to q \equiv \neg p \lor q

Use it to remove $\to$ before any manipulation; it holds for all truth values.

BICONDITIONAL

p \leftrightarrow q \equiv (p \to q) \land (q \to p) \equiv (p \land q) \lor (\neg p \land \neg q)

True exactly when $p$ and $q$ have the same truth value; $p \oplus q \equiv \neg (p \leftrightarrow q)$ .

COUNTING TRUTH TABLES

rows in a truth table = 2^{n}, distinct Boolean functions of n variables = 2^{2^{n}}

For $n$ distinct atoms; the second count is the number of different possible output columns.

Classifying a formula

Term	Meaning
Tautology (valid)	True under every assignment
Contradiction (unsatisfiable)	False under every assignment
Contingency	True under some assignment and false under another
Satisfiable	True under at least one assignment (tautologies and contingencies)

A formula $φ$ is a tautology exactly when $\neg φ$ is unsatisfiable. To test satisfiability by hand, try to find one assignment that makes the formula true; to test validity, try to find one that makes it false.

Logical equivalences

Two formulae are equivalent ( $\equiv$ ) when they have the same truth value under every assignment, i.e. $φ \leftrightarrow ψ$ is a tautology.

IDENTITY, DOMINATION AND COMPLEMENT LAWS

p \land T \equiv p, p \lor F \equiv p, p \lor T \equiv T, p \land F \equiv F, p \lor \neg p \equiv T, p \land \neg p \equiv F

Here T and F stand for the constants true and false.

DE MORGAN'S LAWS

\neg (p \land q) \equiv \neg p \lor \neg q, \neg (p \lor q) \equiv \neg p \land \neg q

Negation swaps $\land$ and $\lor$ and negates each part.

DISTRIBUTIVE LAWS

p \land (q \lor r) \equiv (p \land q) \lor (p \land r), p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)

Each of $\land$ and $\lor$ distributes over the other.

ABSORPTION AND DOUBLE NEGATION

p \lor (p \land q) \equiv p, p \land (p \lor q) \equiv p, \neg\neg p \equiv p

Useful for quickly simplifying a formula.

NEGATION OF AN IMPLICATION

\neg (p \to q) \equiv p \land \neg q

An implication fails only when the hypothesis holds and the conclusion fails.

MOVING IMPLICATIONS AROUND

(p \land q) \to r \equiv p \to (q \to r), (p \to q) \land (p \to r) \equiv p \to (q \land r), (p \to r) \land (q \to r) \equiv (p \lor q) \to r

Exportation and the two combining rules; note the hypotheses combine with $\lor$ when the conclusion is shared.

COMBINING IMPLICATIONS WITH OR

(p \to q) \lor (p \to r) \equiv p \to (q \lor r), (p \to r) \lor (q \to r) \equiv (p \land q) \to r

Rewrite each side with $\neg a \lor b$ to check them. With a shared conclusion and $\lor$ between the implications, the hypotheses combine with $\land$ .

Contrapositive, converse and inverse of $p \to q$

Statement	Form	Equivalent to $p \to q$ ?
Original	$p \to q$	Itself
Contrapositive	$\neg q \to \neg p$	Yes
Converse	$q \to p$	No
Inverse	$\neg p \to \neg q$	No (it is the contrapositive of the converse, so equivalent to the converse)

EXAM TIP

The converse and the inverse of an implication are equivalent to each other, but not to the original. A statement is always equivalent to its contrapositive.

Normal forms and functional completeness

A literal is an atom or its negation. A clause is a disjunction of literals, and a term is a conjunction of literals. A formula is in CNF (conjunctive normal form) if it is a conjunction of clauses, and in DNF (disjunctive normal form) if it is a disjunction of terms.

Converting a formula to CNF or DNF

Eliminate $\leftrightarrow$ and $\to$ using $p \to q \equiv \neg p \lor q$ and the biconditional rule.
Push every $\neg$ inwards with De Morgan's laws until negations sit only on atoms, and cancel double negations.
Distribute $\lor$ over $\land$ for CNF, or $\land$ over $\lor$ for DNF.
Simplify: drop repeated literals, and drop clauses (CNF) or terms (DNF) made redundant by absorption.

Reading a normal form off a truth table

DNF: for each row where the formula is true, write a term that is true only on that row (a minterm: every variable appears, negated if it is F in the row); take the disjunction.
CNF: for each row where the formula is false, write a clause that is false only on that row (a maxterm: every variable appears, negated if it is T in the row); take the conjunction.
So a formula in $n$ variables with $k$ true rows has a full DNF of $k$ minterms and a full CNF of $2^{n} - k$ maxterms.

Quick tests on normal forms

Form	Test	Result
CNF	Is it valid?	Valid iff every clause contains some $x$ and $\neg x$
DNF	Is it satisfiable?	Satisfiable iff some term contains no $x$ together with $\neg x$
DNF	Is it valid?	Not a quick test
CNF	Is it satisfiable?	Not a quick test in general (this is the SAT problem)

FUNCTIONALLY COMPLETE SETS

{\neg, \land}, {\neg, \lor}, {\neg, \to}, {\to, F}, {NAND}, {NOR} are functionally complete

Every Boolean function can be written using only the connectives in any one of these sets (F is the constant false). ${\land, \lor}$ is not complete: a formula built from $\land$ and $\lor$ alone is true whenever all its atoms are true, so it cannot express $\neg p$ . For the same reason ${\to}$ alone is not complete, while ${\to, F}$ is, since $\neg p \equiv p \to F$ .

EXAM TIP

Converting a formula to CNF or DNF can make it exponentially longer. For example, $p_{1} \oplus p_{2} \oplus \dots \oplus p_{n}$ has no DNF with fewer than $2^{n - 1}$ terms: a term missing a variable would also be true on a row where only that variable is flipped, and the formula is false there.

Translating English and checking arguments

Common English phrasings

English	Logic
if $p$ then $q$ ; $p$ only if $q$ ; $q$ whenever $p$	$p \to q$
$p$ if $q$ ; $p$ provided $q$	$q \to p$
$p$ is sufficient for $q$	$p \to q$
$p$ is necessary for $q$	$q \to p$
$p$ if and only if $q$ ; $p$ iff $q$	$p \leftrightarrow q$
$p$ unless $q$	$\neg q \to p$ (equivalently $p \lor q$ )
neither $p$ nor $q$	$\neg p \land \neg q$
$p$ but $q$	$p \land q$

An argument with premises $P_{1}, \dots, P_{n}$ and conclusion $C$ is valid when $C$ is true in every assignment that makes all premises true. Validity is about form, not about whether the premises are actually true.

TEST FOR A VALID ARGUMENT

valid ⟺ (P_{1} \land \dots \land P_{n}) \to C is a tautology ⟺ P_{1} \land \dots \land P_{n} \land \neg C is unsatisfiable

To refute an argument, find one assignment making every premise true and the conclusion false.

EXAM TIP

If the premises cannot all be true together (for example $p$ and $\neg p$ ), the argument is valid whatever the conclusion is, because no assignment makes every premise true. Check that the premises are consistent before reading much into a verdict of valid.

Rules of inference

Rule	Premises	Conclusion
Modus ponens	$p, p \to q$	$q$
Modus tollens	$\neg q, p \to q$	$\neg p$
Hypothetical syllogism	$p \to q, q \to r$	$p \to r$
Disjunctive syllogism	$p \lor q, \neg p$	$q$
Resolution	$p \lor q, \neg p \lor r$	$q \lor r$
Constructive dilemma	$p \lor q, p \to r, q \to s$	$r \lor s$
Simplification / addition	$p \land q$ / $p$	$p$ / $p \lor q$

EXAM TIP

Two invalid patterns that look like valid ones: affirming the consequent ( $p \to q$ and $q$ , so $p$ ) and denying the antecedent ( $p \to q$ and $\neg p$ , so $\neg q$ ). Take $p$ false and $q$ true to see both fail.

WORKED EXAMPLE

Show that $((p \to q) \land (q \to r)) \to (p \to r)$ is a tautology.

Solution

Suppose the formula is false for some assignment. Then the hypothesis $(p \to q) \land (q \to r)$ is true and the conclusion $p \to r$ is false.
$p \to r$ false forces $p = T$ and $r = F$ .
$p \to q$ true with $p = T$ forces $q = T$ .
But then $q \to r$ is $T \to F$ , which is false, contradicting the hypothesis being true.
So no assignment makes the formula false.

Answer: The formula is a tautology (this is hypothetical syllogism).

First-order logic: predicates and quantifiers

First-order logic adds a domain of objects (assumed non-empty throughout these notes), predicates such as $P (x)$ or $R (x, y)$ that are true or false for given objects, the universal quantifier $\forall x$ (for all $x$ ) and the existential quantifier $\exists x$ (there is some $x$ ). A formula is evaluated in an interpretation: a domain together with a meaning for every predicate (and every constant).

In $\forall x φ$ and $\exists x φ$ the variable $x$ is bound in $φ$ ; a variable occurrence not captured by any quantifier is free. A formula with no free variables is a sentence and is simply true or false in an interpretation. In $\forall x (P (x) \to Q (x, y))$ , $x$ is bound and $y$ is free. Convention: a quantifier applies only to the formula immediately after it, so $\forall x P (x) \lor Q (x)$ means $(\forall x P (x)) \lor Q (x)$ , in which the last $x$ is free; brackets extend the scope, as in $\forall x (P (x) \lor Q (x))$ .

NEGATING QUANTIFIERS

\neg\forall x P (x) \equiv \exists x \neg P (x), \neg\exists x P (x) \equiv \forall x \neg P (x)

Push $\neg$ inside by flipping each quantifier and negating the body; repeat for nested quantifiers.

QUANTIFIERS THAT DISTRIBUTE

\forall x (P (x) \land Q (x)) \equiv \forall x P (x) \land \forall x Q (x), \exists x (P (x) \lor Q (x)) \equiv \exists x P (x) \lor \exists x Q (x)

$\forall$ distributes over $\land$ and $\exists$ distributes over $\lor$ , as equivalences.

Where distribution only goes one way

Valid implication	Converse	Counter-model for the converse
$(\forall x P (x) \lor \forall x Q (x)) \to \forall x (P (x) \lor Q (x))$	Not valid	Domain ${1, 2}$ ; $P$ true only at 1, $Q$ true only at 2
$\exists x (P (x) \land Q (x)) \to (\exists x P (x) \land \exists x Q (x))$	Not valid	Domain ${1, 2}$ ; $P$ true only at 1, $Q$ true only at 2
$\forall x (P (x) \to Q (x)) \to (\forall x P (x) \to \forall x Q (x))$	Not valid	Domain ${1, 2}$ ; $P$ true only at 1, $Q$ false everywhere
$\exists x \forall y R (x, y) \to \forall y \exists x R (x, y)$	Not valid	Domain ${1, 2}$ ; $R (x, y)$ true exactly when $x = y$
$\forall x P (x) \to \exists x P (x)$ (non-empty domain)	Not valid	Domain ${1, 2}$ ; $P$ true only at 1

PULLING A QUANTIFIER PAST A FORMULA THAT DOES NOT MENTION $X$

if x is not free in ψ : \forall x (P (x) \lor ψ) \equiv \forall x P (x) \lor ψ, \exists x (P (x) \land ψ) \equiv \exists x P (x) \land ψ

The same holds for $\forall$ with $\land$ and $\exists$ with $\lor$ . The step $\exists x ψ \equiv ψ$ (or $\forall x ψ \equiv ψ$ ) used here relies on the domain being non-empty.

MOVING A QUANTIFIER OUT OF AN ANTECEDENT

if x is not free in ψ : \forall x (P (x) \to ψ) \equiv \exists x P (x) \to ψ, \exists x (P (x) \to ψ) \equiv \forall x P (x) \to ψ

The quantifier flips when it leaves the antecedent. It keeps its kind when it leaves the consequent: $\forall x (ψ \to P (x)) \equiv ψ \to \forall x P (x)$ and $\exists x (ψ \to P (x)) \equiv ψ \to \exists x P (x)$ . The $\exists$ forms need a non-empty domain.

EXISTENTIAL OVER AN IMPLICATION

\exists x (P (x) \to Q (x)) \equiv \forall x P (x) \to \exists x Q (x)

Write the body as $\neg P (x) \lor Q (x)$ , distribute $\exists$ over $\lor$ , and use $\exists x \neg P (x) \equiv \neg\forall x P (x)$ . By contrast, $\forall x (P (x) \to Q (x))$ only implies $\forall x P (x) \to \forall x Q (x)$ .

Order of quantifiers. Like quantifiers commute: $\forall x \forall y$ equals $\forall y \forall x$ , and $\exists x \exists y$ equals $\exists y \exists x$ . Mixed quantifiers do not: $\forall x \exists y R (x, y)$ lets $y$ depend on $x$ , while $\exists y \forall x R (x, y)$ demands a single $y$ that works for every $x$ .

Translating English into first-order logic

English	Formula
All $S$ are $P$	$\forall x (S (x) \to P (x))$
Some $S$ is $P$	$\exists x (S (x) \land P (x))$
No $S$ is $P$	$\forall x (S (x) \to \neg P (x))$
Not every $S$ is $P$	$\exists x (S (x) \land \neg P (x))$
Everyone has a parent, where $Parent (y, x)$ means $y$ is a parent of $x$	$\forall x \exists y Parent (y, x)$
There is exactly one $x$ with $P (x)$	$\exists x (P (x) \land \forall y (P (y) \to y = x))$

EXAM TIP

The usual translation traps are $\forall x (S (x) \land P (x))$ for "all $S$ are $P$ " (it claims everything is an $S$ ) and $\exists x (S (x) \to P (x))$ for "some $S$ is $P$ " (it is true as soon as one object is not an $S$ , even if no $S$ is $P$ ). Use $\to$ after $\forall$ and $\land$ after $\exists$ .

Rules of inference for quantifiers

Rule	From	Infer
Universal instantiation	$\forall x P (x)$	$P (c)$ for any object $c$ of the domain
Universal generalization	$P (c)$ for an arbitrary $c$ (nothing assumed about $c$ )	$\forall x P (x)$
Existential instantiation	$\exists x P (x)$	$P (c)$ for some $c$ , using a new name that appears nowhere else
Existential generalization	$P (c)$ for some object $c$	$\exists x P (x)$

WORKED EXAMPLE

Write the negation of $\forall x \exists y (P (x) \to Q (x, y))$ with no negation in front of a quantifier or a bracket.

Solution

Flip the outer quantifier: $\exists x \neg\exists y (P (x) \to Q (x, y))$ .
Flip the inner quantifier: $\exists x \forall y \neg (P (x) \to Q (x, y))$ .
Use $\neg (a \to b) \equiv a \land \neg b$ on the body.

Answer: $\exists x \forall y (P (x) \land \neg Q (x, y))$

Validity in first-order logic and counter-models

A first-order sentence is valid if it is true in every interpretation, satisfiable if it is true in at least one (a model), and unsatisfiable if it is true in none. A sentence is valid exactly when its negation is unsatisfiable. Unlike propositional logic, there is no truth table: validity of first-order sentences is undecidable in general (no algorithm decides it for every sentence), but a single counter-model settles that a sentence is not valid.

Deciding whether a first-order formula is valid

Read the formula as an implication and ask whether the conclusion must hold whenever the premise does.
If it looks valid, argue for an arbitrary interpretation: assume the premise is true and show the conclusion is true, reasoning about an arbitrary object wherever a $\forall$ has to be shown.
If it looks invalid, build a small counter-model: choose a domain (often ${1, 2}$ ), define each predicate by listing where it is true, and check the premise is true and the conclusion false.
Start with a domain of one or two elements; that is enough for every counter-model in these notes. It is a place to start, not a guarantee: some satisfiable sentences have only infinite models, so a failed search over small domains does not prove validity.

WORKED EXAMPLE

Show that $\forall x \exists y R (x, y) \to \exists y \forall x R (x, y)$ is not valid.

Solution

Take the domain ${1, 2}$ and let $R (x, y)$ be true exactly when $x = y$ , i.e. $R (1, 1)$ and $R (2, 2)$ true, $R (1, 2)$ and $R (2, 1)$ false.
Premise $\forall x \exists y R (x, y)$ : for $x = 1$ take $y = 1$ , for $x = 2$ take $y = 2$ . It is true.
Conclusion $\exists y \forall x R (x, y)$ : for $y = 1$ the object $x = 2$ fails, and for $y = 2$ the object $x = 1$ fails. It is false.
The premise is true and the conclusion false in this interpretation.

Answer: This interpretation is a counter-model, so the sentence is not valid. (The reverse implication is valid.)

COUNTING RELATIONS THAT SATISFY A SENTENCE

number of relations R \subseteq A \times A with \forall x \exists y R (x, y) = (2^{n} - 1)^{n}, ∣ A ∣ = n

For a fixed set $A$ with $∣ A ∣ = n$ , a relation on $A$ is a subset of $A \times A$ . In its 0/1 matrix (row $x$ , column $y$ ) each of the $n$ rows must contain at least one 1, and a row has $2^{n} - 1$ such patterns.

EXAM TIP

Do not confuse "true in this interpretation" with "valid". To prove invalidity you need one interpretation; to prove validity you need an argument that works in every interpretation, so testing a few examples never proves validity.

PREVIOUS-YEAR QUESTIONS

7 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS2 Q.11

GATE 2026 · CS2Q.11 · 1 mark · MCQ

For two different persons $x$ and $y$ , the predicate $M (x, y)$ denotes that $x$ knows $y$ . Consider the following statement.

There is a person who does not know anyone else, but that person is known by everyone else.

Which one of the following expressions represents the above statement?

(A)
$(\exists y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
(B)
$(\forall y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
(C)
$(\exists y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
(D)
$(\forall y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$

Answer and solution

GATE 2026 CS2 Q.11: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.11: answer and solution

GATE 2025 CS1 Q.48

GATE 2025 · CS1Q.48 · 2 marks · MSQ

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"?

The meanings of the predicates used are:
- $m o t h er (y, x)$ : $y$ is the mother of $x$
- $n o t e q (x, y)$ : $x$ and $y$ are not equal

(A)
$\forall x \exists y \exists z (m o t h er (y, x) \land \neg m o t h er (z, x))$
(B)
$\forall x \exists y [m o t h er (y, x) \land \forall z (n o t e q (z, y) \to \neg m o t h er (z, x))]$
(C)
$\forall x \forall y [m o t h er (y, x) \to \exists z (m o t h er (z, x) \land \neg n o t e q (z, y))]$
(D)
$\forall x \exists y [m o t h er (y, x) \land \neg\exists z (n o t e q (z, y) \land m o t h er (z, x))]$

Answer and solution

GATE 2025 CS1 Q.48: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.48: answer and solution

GATE 2025 CS2 Q.15

GATE 2025 · CS2Q.15 · 1 mark · MCQ

Let $P (x)$ be an arbitrary predicate over the domain of natural numbers.

Which ONE of the following statements is TRUE?

(A)
$(P (0) \land (\forall x [P (x) \Rightarrow P (x + 1)])) \Rightarrow (\forall x P (x))$
(B)
$(P (0) \land (\forall x [P (x) \Rightarrow P (x - 1)])) \Rightarrow (\forall x P (x))$
(C)
$(P (1000) \land (\forall x [P (x) \Rightarrow P (x - 1)])) \Rightarrow (\forall x P (x))$
(D)
$(P (1000) \land (\forall x [P (x) \Rightarrow P (x + 1)])) \Rightarrow (\forall x P (x))$

Answer and solution

GATE 2025 CS2 Q.15: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.15: answer and solution

GATE 2024 CS2 Q.12

GATE 2024 · CS2Q.12 · 1 mark · MCQ

Let $p$ and $q$ be the following propositions:

$p$ : Fail grade can be given.

$q$ : Student scores more than 50% marks.

Consider the statement: "Fail grade cannot be given when student scores more than 50% marks."

Which one of the following is the CORRECT representation of the above statement in propositional logic?

(A)
$q \to \neg p$
(B)
$q \to p$
(C)
$p \to q$
(D)
$\neg p \to q$

Answer and solution

GATE 2024 CS2 Q.12: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.12: answer and solution

GATE 2023 CS Q.26

GATE 2023 · CSQ.26 · 1 mark · MSQ

Geetha has a conjecture about integers, which is of the form

\forall x (P (x) \Rightarrow \exists y Q (x, y)),

where $P$ is a statement about integers, and $Q$ is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

(A)
$\exists x (P (x) \land \forall y Q (x, y))$
(B)
$\forall x \forall y Q (x, y)$
(C)
$\exists y \forall x (P (x) \Rightarrow Q (x, y))$
(D)
$\exists x (P (x) \land \exists y Q (x, y))$

Answer and solution

GATE 2023 CS Q.26: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.26: answer and solution

GATE 2020 CS Q.39

GATE 2020 · CSQ.39 · 2 marks · MCQ

Which one of the following predicate formulae is NOT logically valid?

Note that $W$ is a predicate formula without any free occurrence of $x$ .

(A)
$\forall x (p (x) \lor W) \equiv \forall x p (x) \lor W$
(B)
$\exists x (p (x) \land W) \equiv \exists x p (x) \land W$
(C)
$\forall x (p (x) \to W) \equiv \forall x p (x) \to W$
(D)
$\exists x (p (x) \to W) \equiv \forall x p (x) \to W$

Answer and solution

GATE 2020 CS Q.39: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.39: answer and solution

GATE 2018 CS Q.28

GATE 2018 · CSQ.28 · 2 marks · MCQ

Consider the first-order logic sentence $φ \equiv \exists s \exists t \exists u \forall v \forall w \forall x \forall y ψ (s, t, u, v, w, x, y)$ , where $ψ (s, t, u, v, w, x, y)$ is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose $φ$ has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?

(A)
There exists at least one model of $φ$ with universe of size less than or equal to 3.
(B)
There exists no model of $φ$ with universe of size less than or equal to 3.
(C)
There exists no model of $φ$ with universe of size greater than 7.
(D)
Every model of $φ$ has a universe of size equal to 7.

Answer and solution

GATE 2018 CS Q.28: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.28: answer and solution

OTHER EXAMS

ISRO: 1 question

From ISRO's Scientist/Engineer written test: ISRO CS 2023. They are not counted in the GATE numbers on this page.

ISRO CS 2023 Q.47

ISRO 2023 · CSQ.47 · 1 mark · MCQ

A truth table will need how many rows if there are n variables.

(A)
2 * n
(B)
n
(C)
2^n
(D)
None of the above

Answer and solution

ISRO CS 2023 Q.47: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.47: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · MCQ

Which formula is equivalent to $\neg (p \to (q \land r))$ ?

(A)
$p \land (\neg q \lor \neg r)$
(B)
$\neg p \land (\neg q \lor \neg r)$
(C)
$p \land \neg q \land \neg r$
(D)
$(p \land q) \to \neg r$

Answer and solution

Answer: (A)

Use $\neg (a \to b) \equiv a \land \neg b$ : the formula becomes $p \land \neg (q \land r)$ .
De Morgan: $\neg (q \land r) \equiv \neg q \lor \neg r$ , giving $p \land (\neg q \lor \neg r)$ .
Option C is stricter (it needs both $q$ and $r$ false); B has the wrong sign on $p$ ; D equals $\neg p \lor \neg q \lor \neg r$ , which is true when $p$ is false, whereas the original is false then.

PRACTICE 21 mark · NAT

For how many of the 16 assignments to $p, q, r, s$ is the formula $(p \lor q) \to (r \land s)$ true?

Answer and solution

Answer: $7$

The formula is false only when $p \lor q$ is true and $r \land s$ is false.
$p \lor q$ is true for 3 of the 4 choices of $(p, q)$ ; $r \land s$ is false for 3 of the 4 choices of $(r, s)$ .
So $3 \times 3 = 9$ assignments make it false.
The number making it true is $16 - 9 = 7$ .

PRACTICE 32 marks · MSQ

Assume every domain is non-empty. Which of the following sentences are valid?

(A)
$\forall x (P (x) \to Q (x)) \to (\forall x P (x) \to \forall x Q (x))$
(B)
$(\exists x P (x) \land \exists x Q (x)) \to \exists x (P (x) \land Q (x))$
(C)
$\exists x \forall y R (x, y) \to \forall y \exists x R (x, y)$
(D)
$\forall x \exists y R (x, y) \to \exists y \forall x R (x, y)$

Answer and solution

Answer: (A), (C)

A is valid: if every $P$ -object is a $Q$ -object and every object is a $P$ -object, then every object is a $Q$ -object.
B is not valid: domain ${1, 2}$ , $P$ true only at 1, $Q$ true only at 2; both existentials hold but no single object satisfies both.
C is valid: if $x_{0}$ satisfies $R (x_{0}, y)$ for all $y$ , then for each $y$ that same $x_{0}$ works.
D is not valid: domain ${1, 2}$ with $R (x, y)$ true iff $x = y$ makes the premise true and the conclusion false.

PRACTICE 42 marks · MCQ

The premises are $p \lor q$ , $p \to r$ and $q \to s$ . Which one of the following is true in every assignment that makes all three premises true?

(A)
$r \land s$
(B)
$r \lor s$
(C)
$r$
(D)
$s$

Answer and solution

Answer: (B)

If $p$ is true, modus ponens with $p \to r$ gives $r$ ; if $q$ is true, $q \to s$ gives $s$ . One of $p, q$ is true, so $r \lor s$ holds (constructive dilemma).
A fails: $p = T, q = F, r = T, s = F$ satisfies all premises but $r \land s$ is false.
C fails: $p = F, q = T, r = F, s = T$ satisfies all premises but $r$ is false.
D fails: $p = T, q = F, r = T, s = F$ satisfies all premises but $s$ is false.

PRACTICE 52 marks · NAT

Let $A = {1, 2, 3}$ . A binary relation on $A$ is a subset of $A \times A$ . How many relations $R$ on $A$ make the sentence $\forall x \exists y R (x, y)$ true?

Answer and solution

Answer: $343$

Think of $R$ as a $3 \times 3$ 0/1 matrix with row $x$ and column $y$ .
$\forall x \exists y R (x, y)$ says every row contains at least one 1.
A row of 3 entries has $2^{3} - 1 = 7$ nonzero patterns.
The three rows are independent, so the count is $7^{3} = 343$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Propositional and first order logic

Preparing in Kolkata? IAE Academy's course for GATE CSE.