Propositional Logic – GATE CSE Engineering MathematicsPractice Questions & PYQs

Let C represent "candidate is corrupt," E represent "candidate is elected," and K represent "candidate is kind."
Statement S1 is C → ¬E.
Statement S2 is K → E.
The contrapositive of S1 is logically equivalent, which is E → ¬C.
Using the rule of hypothetical syllogism, we can chain S2 and the contrapositive of S1:
(K → E) and (E → ¬C) implies (K → ¬C).
This translates to "If a candidate is kind, then he is not known to be corrupt."

The statement is "The result of the toss is head if and only if I am telling the truth." Let's analyze the two possible cases for the person.

Case 1: The person is a Type 1 (truth-teller).
Their statement must be true. Since "I am telling the truth" is true, the other part of the biconditional, "The result of the toss is head," must also be true.

Case 2: The person is a Type 2 (liar).
Their statement must be false. For a biconditional to be false, the two parts must have different truth values. Since "I am telling the truth" is false, "The result of the toss is head" must be true.

In both scenarios, the result of the coin toss must be a head.

The sentence "not all rainy days are cold" can be broken down to understand its logical structure.

1. "All rainy days are cold" can be represented as $\forall d (Rainy(d) \rightarrow Cold(d))$.
2. The original sentence is the negation of "all rainy days are cold". Therefore, we negate the expression from step 1: $\sim \forall d (Rainy(d) \rightarrow Cold(d))$.
3. Using the logical equivalence $\sim \forall x P(x) \equiv \exists x \sim P(x)$, we transform the expression to $\exists d \sim (Rainy(d) \rightarrow Cold(d))$.
4. Next, we use the implication equivalence $P \rightarrow Q \equiv \sim P \vee Q$: $\exists d \sim (\sim Rainy(d) \vee Cold(d))$.
5. Applying De Morgan's Law $\sim (P \vee Q) \equiv \sim P \wedge \sim Q$: $\exists d ( \sim (\sim Rainy(d)) \wedge \sim Cold(d))$.
6. Finally, simplifying $\sim (\sim P) \equiv P$: $\exists d (Rainy(d) \wedge \sim Cold(d))$.

Let's represent the basic propositions as:
$G$: The mobile phone is good.
$C$: The mobile phone is cheap.

Statement P, "Good mobile phones are not cheap," can be written as: If a phone is good, then it is not cheap.
$P: G \rightarrow \neg C$

Statement Q, "Cheap mobile phones are not good," can be written as: If a phone is cheap, then it is not good.
$Q: C \rightarrow \neg G$

Now, let's examine the logical relationship between P and Q. The contrapositive of a statement $A \rightarrow B$ is $\neg B \rightarrow \neg A$.
The contrapositive of statement P ($G \rightarrow \neg C$) is $\neg(\neg C) \rightarrow \neg G$, which simplifies to $C \rightarrow \neg G$. This is exactly statement Q.

Since a statement and its contrapositive are always logically equivalent, P and Q are equivalent ($P \equiv Q$).

• L: $P \implies Q$. Since $P \equiv Q$, this is TRUE.
• M: $Q \implies P$. Since $Q \equiv P$, this is TRUE.
• N: $P$ is equivalent to $Q$. This is TRUE by definition of contrapositive.

Therefore, L, M, and N are all TRUE.

Let's analyze each component of the given options based on the condition that exactly two of $p, q, r$ are TRUE.

Case 1: Exactly two of $p, q, r$ are TRUE.
Possible scenarios: $(p=T, q=T, r=F)$, $(p=T, q=F, r=T)$, $(p=F, q=T, r=T)$.

Consider the term $p \leftrightarrow q$:

• If $(p=T, q=T, r=F)$, then $p \leftrightarrow q$ is TRUE.
• If $(p=T, q=F, r=T)$, then $p \leftrightarrow q$ is FALSE.
• If $(p=F, q=T, r=T)$, then $p \leftrightarrow q$ is FALSE.

Consider the term $p \wedge q \wedge \sim r$:

• If $(p=T, q=T, r=F)$, then $p \wedge q \wedge \sim r$ is TRUE.
• If $(p=T, q=F, r=T)$, then $p \wedge q \wedge \sim r$ is FALSE.
• If $(p=F, q=T, r=T)$, then $p \wedge q \wedge \sim r$ is FALSE.

Now let's evaluate Option B: $(\sim (p \leftrightarrow q) \wedge r) \vee (p \wedge q \wedge \sim r)$

• If $(p=T, q=T, r=F)$: $(\sim T \wedge F) \vee (T \wedge T \wedge T) = (F \wedge F) \vee T = F \vee T = T$.
• If $(p=T, q=F, r=T)$: $(\sim F \wedge T) \vee (T \wedge F \wedge F) = (T \wedge T) \vee F = T \vee F = T$.
• If $(p=F, q=T, r=T)$: $(\sim F \wedge T) \vee (F \wedge T \wedge F) = (T \wedge T) \vee F = T \vee F = T$.

Since Option B evaluates to TRUE for all scenarios where exactly two of $p, q, r$ are TRUE, it is the correct answer.

The other options can be discarded as they do not hold TRUE for all these scenarios. For instance, Option A fails for $(p=T, q=F, r=T)$, and Option D is an AND of two terms which cannot be simultaneously true.

The statement "Not all that glitters is gold" means that there exists at least one object that glitters but is not gold.
Let $G(x)$ represent "x glitters" and $D(x)$ represent "x is gold".
The phrase "Not all that glitters is gold" can be translated to "It is not true that for all x, if x glitters then x is gold".
This can be expressed as $\neg (\forall x : G(x) \Rightarrow D(x))$.
Using the logical equivalence $\neg (\forall x : P(x)) \equiv \exists x : \neg P(x)$, we get $\exists x : \neg (G(x) \Rightarrow D(x))$.
Further applying $\neg (P \Rightarrow Q) \equiv P \wedge \neg Q$, we obtain $\exists x : (G(x) \wedge \neg D(x))$.
This formula states "There exists an x such that x glitters AND x is not gold."

We are asked to find the option that is NOT logically equivalent to the given statement $\neg \exists x(\forall y(\alpha )\wedge \forall z(\beta ))$.
First, simplify the given statement:
$\neg \exists x(\forall y(\alpha )\wedge \forall z(\beta )) \equiv \forall x \neg (\forall y(\alpha )\wedge \forall z(\beta ))$
$\equiv \forall x (\neg \forall y(\alpha ) \vee \neg \forall z(\beta ))$
$\equiv \forall x (\exists y(\neg \alpha ) \vee \exists z(\neg \beta ))$
Using the implication rule $P \rightarrow Q \equiv \neg P \vee Q$, we can rewrite this as:
$\forall x (\neg \exists y(\neg \alpha ) \rightarrow \exists z(\neg \beta )) \equiv \forall x (\forall y(\alpha ) \rightarrow \exists z(\neg \beta ))$
This matches option C.

Let's check option D: $\forall x ( \exists y(\neg \alpha ) \rightarrow \exists z(\neg \beta ))$.
This is NOT logically equivalent to $\forall x (\exists y(\neg \alpha ) \vee \exists z(\neg \beta ))$.
is NOT logically equivalent to the given expression.

Let's check option A: $\forall x(\exists z(\neg \beta ) \rightarrow \forall y(\alpha ))$.
This is equivalent to $\forall x(\neg \exists z(\neg \beta ) \vee \forall y(\alpha )) \equiv \forall x(\forall z(\beta ) \vee \forall y(\alpha ))$.
This is also not equivalent to our simplified expression.

Let's check option B: $\forall x(\forall z(\beta ) \rightarrow \exists y(\neg \alpha ))$.
This is equivalent to $\forall x(\neg \forall z(\beta ) \vee \exists y(\neg \alpha )) \equiv \forall x(\exists z(\neg \beta ) \vee \exists y(\neg \alpha ))$.
This is logically equivalent to the given statement.

Thus, options A and D are NOT logically equivalent to the original statement. However, the provided Given the choices, there might be a nuance in the question's intended interpretation or an error in the provided options/solution. Assuming the question expects only one answer to be "NOT logically equivalent" and there might be a typo in the provided answer key or the question itself. But based on direct logical equivalences, both A and D are not equivalent.

Let $F(x)$ represent "x is my friend" and $P(x)$ represent "x is perfect".
The statement "None of my friends are perfect" means that there is no individual who is both my friend and perfect.
This can be translated as "It is NOT true that there exists an x such that x is my friend AND x is perfect."
Symbolically, this is written as $\neg \exists x (F(x) \wedge P(x))$.
Alternatively, using logical equivalences, $\neg \exists x (F(x) \wedge P(x))$ is equivalent to $\forall x \neg (F(x) \wedge P(x))$, which further simplifies to $\forall x (\neg F(x) \vee \neg P(x))$ using De Morgan's laws. This can also be expressed as $\forall x (F(x) \implies \neg P(x))$, meaning "For all x, if x is my friend, then x is not perfect."
All these forms convey the same meaning as option D.

To translate "Some real numbers are rational" into mathematical logic, we need to identify the quantifiers and logical connectives.

1. "Some" indicates the existential quantifier, $\exists x$.
2. The statement asserts that there exists an $x$ such that $x$ is a real number AND $x$ is a rational number.
3. "and" is represented by the conjunction operator, $\wedge$.
4. So, we are looking for an $x$ such that $real(x)$ is true and $rational(x)$ is true.

Combining these, the correct translation is $\exists x (real(x) \wedge rational(x))$.

Let $R$ denote "It rains" and $C$ denote "The cricket match will be played."
The premise "If it rains then the cricket match will not be played" can be written as $R \implies \neg C$. This is logically equivalent to $\neg R \lor \neg C$.

For Inference $I_1$:
Premises: $R \implies \neg C$ and $C$ (The cricket match was played).
We can use the contrapositive: $\neg(\neg C) \implies \neg R$, which simplifies to $C \implies \neg R$.
Since $C$ is true, we can logically conclude $\neg R$ (There was no rain). Thus, $I_1$ is a correct inference (Modus Tollens).

For Inference $I_2$:
Premises: $R \implies \neg C$ and $\neg R$ (It did not rain).
Knowing that it did not rain ($\neg R$) does not allow us to conclude anything about $C$ from $R \implies \neg C$. The match could have been played, or it could have been canceled for another reason. This is a fallacy of denying the antecedent. Thus, $I_2$ is not a correct inference.

Therefore, $I_1$ is correct, but $I_2$ is not.

Let's break down the predicate $P(x)$:
$P(x) = \neg (x=1) \wedge \forall y((\exists z(x=y \cdot z)) \Rightarrow (y=x) \vee (y=1))$

The first part, $\neg (x=1)$, means $x$ is not equal to 1.
The second part, $\forall y((\exists z(x=y \cdot z)) \Rightarrow (y=x) \vee (y=1))$, states that for all positive integers $y$, if $y$ is a factor of $x$ (i.e., $x=y \cdot z$ for some integer $z$), then $y$ must be either $x$ itself or 1.

Combining both parts, $P(x)$ is true if $x$ is not 1, and its only positive integer factors are 1 and $x$. This is the definition of a prime number.

Let's break down the given logical formula and translate it into plain English. The predicate $F(x,y,t)$ means 'person x can fool person y at time t'.

The formula is: $\forall x \exists y \exists t (\neg F(x,y,t))$

We can translate this piece by piece from left to right:

• $\forall x$: This means "For every person x" or "Everyone".
• $\exists y$: This means "there exists a person y" or "for some person y".
• $\exists t$: This means "there exists a time t" or "at some time t".
• $\neg F(x,y,t)$: This is the negation, meaning "person x cannot fool person y at time t".

Combining these parts, the formula reads: "For every person x, there exists some person y and some time t, such that x cannot fool y at t."

Now, let's analyze the given options to find the one that is logically equivalent to this statement:

• A. Everyone can fool some person at some time: This translates to $\forall x \exists y \exists t (F(x,y,t))$. This is the opposite of our formula.

• B. No one can fool everyone all the time: Let's translate this carefully.

  • "No one can..." is equivalent to "For all people, it is not the case that...". This is $\forall x (\neg ...)$.
  • "...fool everyone all the time." For a person x, this means they fool every person y at every time t. This translates to $\forall y \forall t (F(x,y,t))$.
  • So, option B translates to: $\forall x (\neg (\forall y \forall t (F(x,y,t))))$.
  • Using De Morgan's laws for quantifiers, which state that $\neg(\forall z P(z)) \equiv \exists z (\neg P(z))$, we can simplify the inner part:
    $\neg (\forall y \forall t (F(x,y,t))) \equiv \exists y (\neg (\forall t (F(x,y,t)))) \equiv \exists y \exists t (\neg F(x,y,t))$.
  • Substituting this back into the full expression for option B gives: $\forall x \exists y \exists t (\neg F(x,y,t))$.
  • This matches the original formula exactly.

• C. Everyone cannot fool some person all the time: This statement is ambiguous in English but doesn't naturally map to the given formula.

• D. No one can fool some person at some time: This translates to $\forall x \neg(\exists y \exists t (F(x,y,t)))$, which simplifies to $\forall x \forall y \forall t (\neg F(x,y,t))$. This means "nobody can ever fool anybody," which is different.

Therefore, option B is the best English expression for the given logical formula.

The statement "Gold and silver ornaments are precious" means that any item that is either a gold ornament OR a silver ornament is considered precious. It implies two conditions:

1. If something is a gold ornament, then it is precious.
2. If something is a silver ornament, then it is precious.

Combining these, if an item $x$ satisfies $G(x)$ (is a gold ornament) or $S(x)$ (is a silver ornament), then it satisfies $P(x)$ (is precious). This translates to the logical implication:
$\forall x((G(x) \vee S(x)) \rightarrow P(x))$
Option D correctly represents this by stating that for all $x$, if $x$ is a gold ornament or a silver ornament, then $x$ is precious. Options A, B, and C misinterpret the implication direction or the logical connector between G(x) and S(x).

The fundamental rule of quantifier negation states that the negation of a universally quantified statement is equivalent to an existentially quantified statement with the negation of the predicate, i.e., $\neg \forall x(Q(x)) \equiv \exists x(\neg Q(x))$.

Applying this rule to formula I:
$\text{I. } \neg \forall x(P(x))$
According to the rule, this is equivalent to:
$\exists x(\neg P(x))$
This expression is exactly formula IV.
$\text{IV. } \exists x(\neg P(x))$
Therefore, I and IV are equivalent.

Using De Morgan's laws, expression II is $\sim (\sim P \wedge Q) \equiv \sim (\sim P) \vee \sim Q \equiv P \vee \sim Q$, which matches expression I.
For expression III, we simplify the first two terms: $(P \wedge Q) \vee (P \wedge \sim Q) \equiv P \wedge (Q \vee \sim Q) \equiv P \wedge T \equiv P$.
Thus, expression III simplifies to $P \vee (\sim P \wedge \sim Q)$, which by the distributive law becomes $(P \vee \sim P) \wedge (P \vee \sim Q) \equiv T \wedge (P \vee \sim Q) \equiv P \vee \sim Q$.
For expression IV, the first two terms simplify to $P$, leaving $P \vee (\sim P \wedge Q) \equiv (P \vee \sim P) \wedge (P \vee Q) \equiv P \vee Q$.
Since expressions I, II, and III are equivalent to $P \vee \sim Q$ while IV is equivalent to $P \vee Q$, only I, II, and III are equivalent.

To determine the validity of the formula $[(\exists x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, (\alpha(x) \rightarrow \beta)]$, we use the condition that $\beta$ contains no free variable $x$. We begin by rewriting the antecedent using the definition of implication:
$(\exists x, \alpha(x)) \rightarrow \beta \equiv \neg(\exists x, \alpha(x)) \lor \beta$
Applying the quantifier negation rule $\neg(\exists x, \alpha(x)) \equiv \forall x, \neg \alpha(x)$, we have:
$\forall x, \neg \alpha(x) \lor \beta$
Since $\beta$ has no free variable $x$, it is equivalent to $\forall x, \beta$. Thus, we can move the disjunction inside the quantifier:
$\forall x, (\neg \alpha(x) \lor \beta)$
Applying the implication rule $\neg P \lor Q \equiv P \rightarrow Q$ within the universal quantifier yields $\forall x, (\alpha(x) \rightarrow \beta)$. Because the antecedent and consequent are logically equivalent, the implication holds as a tautology.

To find the negation of $[\forall x, \alpha \rightarrow (\exists y, \beta \rightarrow (\forall u, \exists v, y))]$, we apply the negation operator $\neg$ to the entire statement.
Using the rules $\neg (\forall x, P) \equiv \exists x, \neg P$ and $\neg (A \rightarrow B) \equiv A \wedge \neg B$, the first step yields $\exists x, \alpha \wedge \neg (\exists y, \beta \rightarrow (\forall u, \exists v, y))$.
Applying the rules $\neg (\exists y, Q) \equiv \forall y, \neg Q$ and $\neg (A \rightarrow B) \equiv A \wedge \neg B$ to the sub-formula results in $\exists x, \alpha \wedge (\forall y, \beta \wedge \neg (\forall u, \exists v, y))$.
Next, using the quantifier negation rules $\neg (\forall u, R) \equiv \exists u, \neg R$ and $\neg (\exists v, S) \equiv \forall v, \neg S$, we negate the final term to obtain $\exists x, \alpha \wedge (\forall y, \beta \wedge (\exists u, \forall v, \neg y))$.
This sequence of logical transformations leads directly to the expression provided in the target answer.

To represent the statement "Each finite state automaton has an equivalent pushdown automaton," we must translate the conditional nature of the sentence into first-order logic. The statement asserts that for any object $x$, if $x$ is a finite state automaton ($fsa(x)$), then there exists some object $y$ such that $y$ is a pushdown automaton ($pda(y)$) and $y$ is equivalent to $x$ ($equivalent(x,y)$).

1. The core logical structure of "Each $A$ has $B$" is expressed using the material implication operator ($\implies$), which sets $A$ as the precondition for $B$.
2. We identify $fsa(x)$ as the antecedent, requiring $x$ to be a finite state automaton.
3. We identify $\exists y \; (pda(y) \wedge equivalent(x,y))$ as the consequent, specifying the existence of a corresponding pushdown automaton $y$.
4. Combining these, we obtain the relationship $fsa(x) \implies \exists y (pda(y) \wedge equivalent(x,y))$.
5. By quantifying over all $x$, we assert this holds for every automaton in the domain. Option A is the only choice that correctly employs the implication operator to conditionally restrict the existence requirement to finite state automata.

To prove the validity of $\forall x(P(x) \implies Q(x)) \implies (\forall x P(x) \implies \forall x Q(x))$, assume the premise $\forall x (P(x) \implies Q(x))$ is true alongside the antecedent $\forall x P(x)$.
Consider an arbitrary element $c$ from the domain of discourse.
Since $\forall x P(x)$ holds, the statement $P(c)$ is necessarily true.
From the first premise $\forall x (P(x) \implies Q(x))$, the specific instance $P(c) \implies Q(c)$ must also be true.
Applying Modus Ponens to $P(c)$ and $P(c) \implies Q(c)$ yields $Q(c)$.
Because $c$ was an arbitrary element, we can generalize to $\forall x Q(x)$, which demonstrates that the implication holds true in all models.

To translate the statement "Some boys in the class are taller than all the girls," we proceed as follows:

1. "Some boys" indicates an existential quantifier, represented as $(\exists x) (boy(x) \land \dots)$, where we use conjunction ($\land$) because the existence claim must assert the existence of an object that is actually a boy.
2. "Taller than all the girls" is a universal property for a specific $x$, represented as $(\forall y) (girl(y) \rightarrow taller(x, y))$. The implication operator (\rightarrow$) is used because we only compare$x$to objects$y$that satisfy the condition$girl(y)$.
3. Combining these, we arrive at the logical expression: $(\exists x) (boy(x) \land (\forall y) (girl(y) \rightarrow taller(x, y)))$.
4. This ensures there exists at least one $x$ such that $x$ is a boy, and for every $y$, if $y$ is a girl, then $x$ is taller than $y$.