Solutions to Chapter 33 Using Interpretations

A. Show that each of the following is neither a validity nor a contradiction:

1. 1.
   ​

   $D(a)\wedge D(b)$

   The sentence is true in this model:

   domain:

   Stan

   $D(x)$:

   Stan

   $a$:

   Stan

   $b$:

   Stan

   And it is false in this model:

   domain:

   Stan

   $D(x)$:

   $a$:

   Stan

   $b$:

   Stan

2. 2.
   ​

    $\exists xT(x,h)$

   The sentence is true in this model:

   domain:

   Stan

   $T(x,y)$:

   $⟨$Stan, Stan$⟩$

   $h$:

   Stan

   And it is false in this model:

   domain:

   Stan

   $T(x,y)$:

   $h$:

   Stan

3. 3.
   ​

   $P(m)\wedge \neg \forall xP(x)$

   The sentence is true in this model:

   domain:

   Stan, Ollie

   $P(x)$:

   Stan

   $m$:

   Stan

   And it is false in this model:

   domain:

   Stan

   $P(x)$:

   $m$:

   Stan

4. 4.
   ​

   $\forall zJ(z)\leftrightarrow \exists yJ(y)$

5. 5.
   ​

   $\forall x(W(x,m,n)\vee \exists yL(x,y))$

6. 6.
   ​

   $\exists x(G(x)\to \forall yM(y))$

7. 7.
   ​

   $\exists x(x=h\wedge x=i)$

B. Show that the following pairs of sentences are not logically equivalent.

1. 1.
   ​

   $J(a)$, $K(a)$

   Making the first sentence true and the second false:

   domain:

   $0$

   $J(x)$:

   $0$

   $K(x)$:

   $a$:

   $0$

2. 2.
   ​

   $\exists xJ(x)$, $J(m)$

   Making the first sentence true and the second false:

   domain:

   $0$, $1$

   $J(x)$:

   $0$

   $m$:

   $1$

3. 3.
   ​

   $\forall xR(x,x)$, $\exists xR(x,x)$

   Making the first sentence false and the second true:

   domain:

   $0$, $1$

   $R(x,y)$:

   $⟨$$0$,$0$$⟩$

4. 4.
   ​

   $\exists xP(x)\to Q(c)$, $\exists x(P(x)\to Q(c))$

   Making the first sentence false and the second true:

   domain:

   $0$, $1$

   $P(x)$:

   $0$

   $Q(x)$:

   $c$:

   $0$

5. 5.
   ​

   $\forall x(P(x)\to \neg Q(x))$, $\exists x(P(x)\wedge \neg Q(x))$

   Making the first sentence true and the second false:

   domain:

   $0$

   $P(x)$:

   $Q(x)$:

6. 6.
   ​

   $\exists x(P(x)\wedge Q(x))$, $\exists x(P(x)\to Q(x))$

   Making the first sentence false and the second true:

   domain:

   $0$

   $P(x)$:

   $Q(x)$:

   $0$

7. 7.
   ​

   $\forall x(P(x)\to Q(x))$, $\forall x(P(x)\wedge Q(x))$

   Making the first sentence true and the second false:

   domain:

   $0$

   $P(x)$:

   $Q(x)$:

   $0$

8. 8.
   ​

   $\forall x\exists yR(x,y)$, $\exists x\forall yR(x,y)$

   Making the first sentence true and the second false:

   domain:

   $0$, $1$

   $R(x,y)$:

   $⟨$$0$, $1$$⟩$, $⟨$$1$, $0$$⟩$

9. 9.
   ​

   $\forall x\exists yR(x,y)$, $\forall x\exists yR(y,x)$

   Making the first sentence false and the second true:

   domain:

   $0$, $1$

   $R(x,y)$:

   $⟨$$0$, $0$$⟩$, $⟨$$0$, $1$$⟩$

C. Show that the following sentences are jointly satisfiable:

1. 1.
   ​

   $M(a),\neg N(a),Pa,\neg Q(a)$

2. 2.
   ​

   $L(e,e),L(e,g),\neg L(g,e),\neg L(g,g)$

3. 3.
   ​

   $\neg (M(a)\wedge \exists xA(x)),Ma\vee F(a),\forall x(F(x)\to A(x))$

4. 4.
   ​

   $M(a)\vee M(b),M(a)\to \forall x\neg M(x)$

5. 5.
   ​

   $\forall yG(y),\forall x(G(x)\to H(x)),\exists y\neg I(y)$

6. 6.
   ​

   $\exists x(B(x)\vee A(x)),\forall x\neg C(x),\forall x\left[(A(x)\wedge B(x))\to C(x)\right]$

7. 7.
   ​

   $\exists xX(x),\exists xY(x),\forall x(X(x)\leftrightarrow \neg Y(x))$

8. 8.
   ​

   $\forall x(P(x)\vee Q(x)),\exists x\neg (Q(x)\wedge P(x))$

9. 9.
   ​

   $\exists z(N(z)\wedge O(z,z)),\forall x\forall y(O(x,y)\to O(y,x))$

10. 10.
    ​

    $\neg \exists x\forall yR(x,y),\forall x\exists yR(x,y)$

11. 11.
    ​

    $\neg R(a,a)$, $\forall x(x=a\vee R(x,a))$

    The sentences are both true in this interpretation:

    domain:

    Harry, Sally

    $R(x,y)$:

    $⟨$Sally, Harry$⟩$

    $a$:

    Harry

12. 12.
    ​

    $\forall x\forall y\forall z[(x=y\vee y=z)\vee x=z]$, $\exists x\exists y\neg x=y$

    There are no predicates or constants, so we only need to give a domain. Any domain with 2 elements will do.

13. 13.
    ​

    $\exists x\exists y((Z(x)\wedge Z(y))\wedge x=y)$, $\neg Z(d)$, $d=e$

D. Show that the following arguments are invalid:

1. 1.
   ​

   $\forall x(A(x)\to B(x))\therefore \exists xB(x)$

2. 2.
   ​

   $\forall x(R(x)\to D(x)),\forall x(R(x)\to F(x))\therefore \exists x(D(x)\wedge F(x))$

3. 3.
   ​

   $\exists x(P(x)\to Q(x))\therefore \exists xP(x)$

4. 4.
   ​

   $N(a)\wedge N(b)\wedge N(c)\therefore \forall xN(x)$

5. 5.
   ​

   $R(d,e),\exists xR(xd)\therefore R(e,d)$

6. 6.
   ​

   $\exists x(E(x)\wedge F(x)),\exists xF(x)\to \exists xG(x)\therefore \exists x(E(x)\wedge G(x))$

7. 7.
   ​

   $\forall xO(x,c),\forall xO(c,x)\therefore \forall xO(x,x)$

8. 8.
   ​

   $\exists x(J(x)\wedge K(x)),\exists x\neg K(x),\exists x\neg J(x)\therefore \exists x(\neg J(x)\wedge \neg K(x))$

9. 9.
   ​

   $L(a,b)\to \forall xL(x,b),\exists xL(x,b)\therefore L(b,b)$

10. 10.
    ​

    $\forall x(D(x)\to \exists yT(y,x))\therefore \exists y\exists z\neg y=z$