in Mathematical Logic recategorized by
162 views
3 votes
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?

  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)$
in Mathematical Logic recategorized by
162 views

1 Answer

2 votes
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.

edited by