Dark Mode

162 views

3 votes

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?

- $\forall x (P(x) \vee Q(x)) \models \forall x P(x) \vee \forall x Q(x)$
- $\forall x (P(x) \rightarrow Q(x)) \models \forall x P(x) \rightarrow \forall x Q(x)$
- $\forall x P(x) \rightarrow \forall x Q(x) \models \forall x (P(x) \rightarrow Q(x))$
- $\neg \forall x (P(x) \wedge Q(x)) \models \exists x \neg P(x) \wedge \exists x \neg Q(x)$

2 votes

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.