Propositional Logic Practice Questions

This question asks about the validity of logical implications in the context of mathematical induction or related principles over natural numbers.
Option (a): $(P(0) \land (\forall x [P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x P(x))$
This statement is the principle of mathematical induction. If a property $P$ holds for $0$ (base case) and if it holds for any natural number $x$, it also holds for $x+1$ (inductive step), then $P$ holds for all natural numbers $x$. This is a TRUE statement.

Option (b): $(P(0) \land (\forall x [P(x) \Rightarrow P(x-1)])) \Rightarrow (\forall x P(x))$
This statement suggests an induction going downwards from $x$ to $x-1$. While valid for a finite set, for natural numbers (which extend infinitely upwards), knowing $P(0)$ and $P(x) \Rightarrow P(x-1)$ is not enough to prove $P(x)$ for all $x$. For example, $P(1)$ can only be inferred from $P(0)$ if we read $P(x-1)$ as $P(x)$ for negative indices or specific interpretation. If $P(x) \Rightarrow P(x-1)$ for $x \ge 1$, then $P(0)$ implies $P(-1)$ (if defined), $P(1)$ implies $P(0)$, etc. It doesn't prove $P(x)$ for $x>0$. This is FALSE.

Option (c): $(P(1000) \land (\forall x [P(x) \Rightarrow P(x-1)])) \Rightarrow (\forall x P(x))$
This is similar to (b), but with $P(1000)$ as the base case. Even if $P(x) \Rightarrow P(x-1)$ were valid, it would only prove $P(x)$ for $x \le 1000$. It cannot prove $P(x)$ for all $x$, specifically for $x > 1000$. This is FALSE.

Option (d): $(P(1000) \land (\forall x [P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x P(x))$
This statement is an induction starting from $P(1000)$. It can prove $P(x)$ for all $x \ge 1000$. However, it does not prove $P(x)$ for $x < 1000$. For example, $P(0)$ is not covered. This is FALSE.

Therefore, only option (a) is TRUE.

The statement "Everyone has exactly one mother" implies two conditions for every person $x$:

1. Every person $x$ has at least one mother $y$. This is represented as $\forall x \exists y (mother(y, x))$.
2. Every person $x$ has at most one mother. This means if $y$ is a mother of $x$, then any other person $z$ cannot be a mother of $x$ if $z$ is different from $y$.

Let's evaluate the given options:
Option B: $\forall x \exists y [mother(y, x) \land \forall z (noteq(z, y) \to \neg mother(z, x))]$
This formula states that for every person $x$, there exists a person $y$ such that $y$ is the mother of $x$, AND for all persons $z$, if $z$ is not equal to $y$, then $z$ is not the mother of $x$. This correctly captures both "at least one" and "at most one" mother.

Option D: $\forall x \exists y [mother(y, x) \land \neg \exists z (noteq(z, y) \land mother(z, x))]$
This formula states that for every person $x$, there exists a person $y$ such that $y$ is the mother of $x$, AND there does NOT exist any person $z$ such that $z$ is not equal to $y$ AND $z$ is also the mother of $x$. This is logically equivalent to option B and correctly represents the statement.

[CORRECT_OPTION: B, D]

The statement is: "Fail grade cannot be given when student scores more than 50% marks."
Let $p$: Fail grade can be given.
Let $q$: Student scores more than 50% marks.
The statement can be rephrased as: "If a student scores more than 50% marks, then a fail grade cannot be given."
In logical terms, "If $q$ then $\neg p$".
This is represented as $q \rightarrow \neg p$.

Geetha's conjecture is $\forall x\left[P(x)\Rightarrow \exists yQ(x,y) \right]$.
Option (B) is $\forall x \forall y Q(x,y)$. If this is true, it means for every x and every y, Q(x,y) is true. This implies that for every x, there exists a y such that Q(x,y) is true. Thus, $\forall x\left[P(x)\Rightarrow \exists yQ(x,y) \right]$ would be true regardless of P(x).
Option (C) is $\exists y \forall x \left[P(x) \Rightarrow Q(x,y) \right]$. If this is true, it means there is some specific y (let's call it y0) such that for all x, if P(x) is true, then Q(x,y0) is true. This directly implies that for every x, if P(x) is true, then there exists a y (namely y0) such that Q(x,y) is true.
Options (A) and (D) do not guarantee the conjecture for all x.
Therefore, options (B) and (C) imply Geetha's conjecture.

The assertion is $S: (( P \wedge Q) \rightarrow R) \rightarrow (( P \wedge Q) \rightarrow (Q \rightarrow R))$.
Let $A = P \wedge Q$. The assertion becomes $S: (A \rightarrow R) \rightarrow (A \rightarrow (Q \rightarrow R))$.
Using the equivalence $X \rightarrow Y \equiv \neg X \vee Y$:
$S \equiv \neg(A \rightarrow R) \vee (A \rightarrow (Q \rightarrow R))$
$S \equiv \neg(\neg A \vee R) \vee (\neg A \vee (\neg Q \vee R))$
$S \equiv (A \wedge \neg R) \vee (\neg A \vee \neg Q \vee R)$
This is a tautology.
To check if the antecedent is equivalent to the consequent:
Antecedent: $A \rightarrow R \equiv \neg A \vee R$.
Consequent: $A \rightarrow (Q \rightarrow R) \equiv \neg A \vee (\neg Q \vee R)$.
These are not logically equivalent. For example, if $A$ is false, $Q$ is true, $R$ is false, then $\neg A \vee R$ is true, but $\neg A \vee (\neg Q \vee R)$ is true.
If $A$ is true, $Q$ is false, $R$ is false, then $\neg A \vee R$ is false, but $\neg A \vee (\neg Q \vee R)$ is true.
So, the antecedent is not equivalent to the consequent.
However, the assertion $S$ is a tautology.
is correct.

For $S_1: (\neg p \wedge (p \vee q)) \rightarrow q$:
First, simplify the antecedent: $(\neg p \wedge (p \vee q)) \equiv (\neg p \wedge p) \vee (\neg p \wedge q) \equiv \text{False} \vee (\neg p \wedge q) \equiv (\neg p \wedge q)$.
So, $S_1 \equiv (\neg p \wedge q) \rightarrow q$.
This is equivalent to $\neg (\neg p \wedge q) \vee q \equiv (p \vee \neg q) \vee q \equiv p \vee (\neg q \vee q) \equiv p \vee \text{True} \equiv \text{True}$.
Thus, $S_1$ is a tautology.

For $S_2: q \rightarrow (\neg p \wedge (p \vee q))$:
Simplify the consequent: $(\neg p \wedge (p \vee q)) \equiv (\neg p \wedge p) \vee (\neg p \wedge q) \equiv \text{False} \vee (\neg p \wedge q) \equiv (\neg p \wedge q)$.
So, $S_2 \equiv q \rightarrow (\neg p \wedge q)$.
This is equivalent to $\neg q \vee (\neg p \wedge q) \equiv (\neg q \vee \neg p) \wedge (\neg q \vee q) \equiv (\neg q \vee \neg p) \wedge \text{True} \equiv \neg q \vee \neg p$.
This expression is a contingency, not always true.
Therefore, $S_1$ is a tautology and $S_2$ is not a tautology.

To determine which predicate formula is NOT logically valid, we analyze each option using logical equivalences and the properties of quantifiers with a predicate $W$ that has no free occurrence of $x$.

A. $\forall x(p(x)\vee W)\equiv \forall xp(x)\vee W$
This statement is logically valid. The universal quantifier can be distributed over disjunction when $W$ does not depend on $x$.
This is equivalent to: $(\forall x p(x)) \vee W$.

B. $\exists x(p(x)\wedge W)\equiv \exists xp(x)\wedge W$
This statement is logically valid. The existential quantifier can be distributed over conjunction when $W$ does not depend on $x$.
This is equivalent to: $(\exists x p(x)) \wedge W$.

C. $\forall x(p(x)\rightarrow W)\equiv \forall xp(x)\rightarrow W$
Let's analyze the left-hand side (LHS) and right-hand side (RHS).
LHS: $\forall x(p(x)\rightarrow W) \equiv \forall x(\neg p(x)\vee W) \equiv (\forall x \neg p(x)) \vee W \equiv (\neg \exists x p(x)) \vee W \equiv \exists x p(x) \rightarrow W$.
RHS: $\forall x p(x) \rightarrow W$.
The LHS simplifies to $\exists x p(x) \rightarrow W$, while the RHS is $\forall x p(x) \rightarrow W$. These are not equivalent. For instance, if $W$ is false, $\forall x p(x)$ is false, and there exists some $x$ for which $p(x)$ is true, then LHS would be true but RHS would be true, which is not an example. Let's reconsider.
If $W$ is false, LHS becomes $\forall x(\neg p(x)) \equiv \neg \exists x p(x)$. RHS becomes $\forall x p(x) \rightarrow False \equiv \neg \forall x p(x) \equiv \exists x \neg p(x)$. These are not equivalent.
This statement is NOT logically valid.

D. $\exists x(p(x)\rightarrow W)\equiv \forall xp(x)\rightarrow W$
LHS: $\exists x(p(x)\rightarrow W) \equiv \exists x(\neg p(x)\vee W) \equiv (\exists x \neg p(x)) \vee W$.
RHS: $\forall x p(x) \rightarrow W \equiv \neg \forall x p(x) \vee W \equiv (\exists x \neg p(x)) \vee W$.
The LHS is equivalent to the RHS. This statement is logically valid.

The first-order logic sentence $\varphi$ asserts the existence of three elements $s, t, u$ for which a property holds for all elements in the universe. If a model with a universe of 7 elements satisfies this, it means such $s, t, u$ can be found within those 7 elements. We can then construct a new, smaller model whose universe consists only of these three specific elements $\{s, t, u\}$. In this universe of size 3, the sentence $\varphi$ remains true. Therefore, if a model of size 7 exists, a model of size less than or equal to 3 must also exist.

To determine which Boolean expression is NOT a tautology, we analyze each option. A tautology is an expression that is always true, regardless of the truth values of its variables.

Option A: $((a\rightarrow b)\wedge (b\rightarrow c))\rightarrow (a\rightarrow c)$ is the Law of Hypothetical Syllogism, which is a known tautology.
Option D: $a\rightarrow (b\rightarrow a)$ simplifies to $a \rightarrow (\neg b \vee a)$, which further simplifies to $\neg a \vee (\neg b \vee a)$. This is always true as $\neg a \vee a$ is a tautology.
Option C: $(a\wedge b\wedge c)\rightarrow (c\wedge a)$ simplifies to $\neg (a\wedge b\wedge c) \vee (c\wedge a)$. If $(a\wedge b\wedge c)$ is true, then $a, b, c$ are all true, making $(c\wedge a)$ true. If $(a\wedge b\wedge c)$ is false, the implication is true. Thus, it's a tautology.
Option B: $(a\rightarrow c)\rightarrow (\neg b\rightarrow (a\wedge c))$. Let's test if this can be false. An implication $P \rightarrow Q$ is false only if $P$ is true and $Q$ is false.
For the expression to be false, $(a \rightarrow c)$ must be true, and $(\neg b \rightarrow (a \wedge c))$ must be false.
For $(\neg b \rightarrow (a \wedge c))$ to be false, $\neg b$ must be true (meaning $b$ is false) and $(a \wedge c)$ must be false.
So, we have: $b$ is false, $(a \wedge c)$ is false, and $(a \rightarrow c)$ is true.
Consider $a=T, b=F, c=F$.
Then $(a \rightarrow c)$ becomes $(T \rightarrow F)$, which is false. This contradicts our assumption that $(a \rightarrow c)$ is true.
Consider $a=F, b=F, c=T$.
$(a \rightarrow c)$ is $(F \rightarrow T)$, which is true.
$\neg b$ is $T$.
$(a \wedge c)$ is $(F \wedge T)$, which is false.
So, $(\neg b \rightarrow (a \wedge c))$ is $(T \rightarrow F)$, which is false.
Therefore, for $a=F, b=F, c=T$, the main expression $(a\rightarrow c)\rightarrow (\neg b\rightarrow (a\wedge c))$ is $(T \rightarrow F)$, which is false. This expression is not always true.

The statement $F: \forall x(\exists yR(x,y))$ means "for every x, there exists some y such that R(x,y) is true".

Statement IV, $\neg \exists x(\forall y\neg R(x,y))$, is equivalent to F. By applying De Morgan's laws for quantifiers, we get $\forall x \neg (\forall y\neg R(x,y))$, which simplifies to $\forall x (\exists y R(x,y))$.

Statement I, $\exists y(\exists xR(x,y))$, is implied by F. Since for every x there is a corresponding y, the domain is non-empty, guaranteeing that there is at least one such (x,y) pair. Thus, there must exist a y and an x for which R(x,y) holds.

The expression $(p \rightarrow q) \rightarrow r$ is a contradiction, meaning it is always False. An implication $A \rightarrow B$ is False only when $A$ is True and $B$ is False.
Therefore, we must have:

1. $(p \rightarrow q)$ is True.
2. $r$ is False.

Now, we evaluate the expression $(r \rightarrow p) \rightarrow q$ under these conditions.
Since $r$ is False, the antecedent $(r \rightarrow p)$ is always True (as False implies anything).
The expression simplifies to $(T \rightarrow q)$, which is logically equivalent to $q$.
Thus, the value of the expression is the same as the value of $q$. This means the expression is always TRUE when q is TRUE.

The statement $(\neg p)\Rightarrow (\neg q)$ is a conditional statement. According to the rule of contrapositive, a conditional statement is logically equivalent to its contrapositive. The contrapositive of $(\neg p)\Rightarrow (\neg q)$ is formed by swapping the hypothesis and conclusion and negating both, which results in $q \Rightarrow p$. This matches statement II.

Furthermore, any implication $A \Rightarrow B$ is logically equivalent to $(\neg A) \vee B$. Applying this to $q \Rightarrow p$, we get $(\neg q) \vee p$, which matches statement III.

The given English statement has two parts connected by "and".
The first part is "It is not raining and it is pleasant". Translating this using the given symbols gives $\neg p \wedge r$.
The second part is "it is not pleasant only if it is raining and it is cold". The logical structure "A only if B" is equivalent to the implication $A \rightarrow B$. Therefore, this part translates to $\neg r \rightarrow (p \wedge q)$.
Combining both parts with a logical AND ($\wedge$) results in the final expression: $(\neg p \wedge r) \wedge (\neg r \rightarrow (p \wedge q))$.

The expression $P \wedge (P \Rightarrow Q)$ is logically equivalent to $P \wedge (\neg P \vee Q)$. Using the distributive law, this becomes $(P \wedge \neg P) \vee (P \wedge Q)$, which simplifies to $F \vee (P \wedge Q)$, or just $P \wedge Q$.

We now check which of the given expressions are logically implied by $P \wedge Q$:

1. $P \wedge Q \Rightarrow Q$ (True)
2. $P \wedge Q \Rightarrow \text{true}$ (True)
3. $P \wedge Q \Rightarrow P \vee Q$ (True)
4. $P \wedge Q \Rightarrow (\neg Q \vee P)$ (True, as this is equivalent to $P \wedge Q \Rightarrow (Q \Rightarrow P)$)

Thus, four expressions-(ii), (iii), (iv), and (v)-are logically implied.

The given logical expression is $\neg((p\Rightarrow q)\wedge (\neg r \vee \neg s))$. For this to be true, the inner expression $((p\Rightarrow q)\wedge (\neg r \vee \neg s))$ must be false. An AND expression is false if at least one of its operands is false.

Case 1: $(p\Rightarrow q)$ is false.
This occurs only when $p$ is true and $q$ is false.

• $p$ is true: $x \in \{8, 9, 10, 11, 12\}$.
• $q$ is false: $x$ is not a composite number.
  From the set for $p$, the only non-composite number is 11 (which is prime). So, $x=11$ satisfies this case.

Case 2: $(\neg r \vee \neg s)$ is false.
This is equivalent to $r \wedge s$ being true.

• $r$ is true: $x$ is a perfect square.
• $s$ is true: $x$ is a prime number.
  No integer is both a prime number and a perfect square. This case is impossible.

Thus, the only integer that satisfies the condition is $x=11$.

A tautology is a formula that is always true, regardless of the truth values of its components. The formula in option C is of the form $X \leftrightarrow Y$, where $X$ is $[\forall x\exists y(P(x,y)\rightarrow R(x,y))]$ and $Y$ is $[\forall x\exists y(\neg P(x,y))\vee R(x,y)]$. This is a tautology because the logical implication $A \rightarrow B$ is equivalent to $\neg A \vee B$. The right side of the biconditional is simply the left side with the implication rewritten in its equivalent disjunctive form, making the entire statement always true.

The biconditional expression $p \leftrightarrow q$ is logically equivalent to $(p \rightarrow q) \wedge (q \rightarrow p)$. This can be rewritten using the definition of implication $(A \rightarrow B \equiv \neg A \vee B)$ as $(\neg p \vee q) \wedge (\neg q \vee p)$. This form matches options A and B.

Expanding this expression gives $(\neg p \wedge \neg q) \vee (p \wedge q)$, which matches option D.

Option C, $(\neg p \wedge q) \vee (p \wedge \neg q)$, represents the exclusive OR (XOR) operation, which is the negation of the biconditional and therefore not equivalent.

The truth table provided for the operator $\neq$ corresponds exactly to the logical XOR (exclusive OR) operation. The output is true (1) if and only if the inputs are different. The XOR operation is a fundamental binary operation in logic and computer science, and it is well-established that it is both commutative ($p \oplus q = q \oplus p$) and associative ($p \oplus (q \oplus r) = (p \oplus q) \oplus r$).