162 views

Let $A, B$ be two predicate logic formulas. We say that “$A \models B$” (which means that “$A$ infers $B$”) iff for all interpretations in which $A$ is true, $B$ is also true.
So, “$A \models B$” iff “$A \rightarrow B$” is valid.

Which of the following inferences are valid in predicate logic?

1. $\forall x (P(x) \vee Q(x)) \models \forall x P(x) \vee \forall x Q(x)$
2. $\forall x (P(x) \rightarrow Q(x)) \models \forall x P(x) \rightarrow \forall x Q(x)$
3. $\forall x P(x) \rightarrow \forall x Q(x) \models \forall x (P(x) \rightarrow Q(x))$
4. $\neg \forall x (P(x) \wedge Q(x)) \models \exists x \neg P(x) \wedge \exists x \neg Q(x)$

Option A Explanation:
Inference in Option A is Not Valid, but the converse is valid inference.
It is not hard to come up with a counterexample. Let the interpretation $M$ be given by

• $A = \{a,b\};$
• $P(a) =$ True, $P(b) =$ False
• $Q(b) =$ True, $Q(a) =$ False

Please verify that $M$ satisfies $\forall x (P(x) \vee Q(x)),$ but that $M$ does not satisfy $\forall x P(x) \vee \forall x Q(x).$ Thus, the semantic entailment/inference above is not valid in predicate logic.

Note that the following is Valid.

$\forall x P(x) \vee \forall x Q(x)|= \forall x (P(x) \vee Q(x))$

Option B, C Explanation:
Inference in Option B is  Valid, but the converse (Option C) is not valid inference.
We have seen this in our “GO Classes Discrete Mathematics $2023$ Course” lectures.

Option D Explanation:
Inference in Option D is Not Valid, but the converse is valid inference.
It is not hard to come up with a counterexample. Consider the interpretation M be given by

• Universe $A = \{a,b\};$
• $P^M = \{a,b\}$
• $Q^M = \{b\}.$

Please verify that $\neg \forall x (P(x) \wedge Q(x))$ is satisfied, but that $\exists x\neg P(x) \wedge \exists x \neg Q(x)$ is not satisfied. Thus, the semantic entailment/inference above is not valid in predicate logic.

1
176 views