Chapter 38 Conversion of quantifiers

In this section, we will add some additional rules to the basic rules of the previous section. These govern the interaction of quantifiers and negation.

In chapter 23, we noted that $\neg\exists x\mathscr{A}$ is logically equivalent to $\forall x\,\neg\mathscr{A}$ . We will add some rules to our proof system that govern this. In particular, we add:

Line number	Subproof level	Formula	Justification
$m$	0	$\forall\mathscr{x}\,\neg\mathscr{A}$
	0	$\neg\exists\mathscr{x}\,\mathscr{A}$	CQ $m$

and

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\exists\mathscr{x}\,\mathscr{A}$
	0	$\forall\mathscr{x}\,\neg\mathscr{A}$	CQ $m$

Equally, we add:

Line number	Subproof level	Formula	Justification
$m$	0	$\exists\mathscr{x}\,\neg\mathscr{A}$
	0	$\neg\forall\mathscr{x}\,\mathscr{A}$	CQ $m$

and

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\forall\mathscr{x}\,\mathscr{A}$
	0	$\exists\mathscr{x}\,\neg\mathscr{A}$	CQ $m$

Practice exercises

A. Show in each case that the sentences are inconsistent:

1.

$S(a)\rightarrow T(m),T(m)\rightarrow S(a),T(m)\wedge\neg S(a)$
2.

$\neg\exists x\,R(x,a),\forall x\,\forall y\,R(y,x)$
3.

$\neg\exists x\,\exists y\,L(x,y),L(a,a)$
4.

$\forall x(P(x)\rightarrow Q(x)),\forall z(P(z)\rightarrow R(z)),\forall y\,P(y% ),\neg Q(a)\wedge\neg R(b)$

B. Show that each pair of sentences is provably equivalent:

1.

$\forall x(A(x)\rightarrow\neg B(x)),\neg\exists x(A(x)\wedge B(x))$
2.

$\forall x(\neg A(x)\rightarrow B(d)),\forall x\,A(x)\vee B(d)$

C. In chapter 24, we considered what happens when we move quantifiers ‘across’ various logical operators. Show that each pair of sentences is provably equivalent:

1.

$\forall x(F(x)\wedge G(a)),\forall x\,F(x)\wedge G(a)$
2.

$\exists x(F(x)\vee G(a)),\exists x\,F(x)\vee G(a)$
3.

$\forall x(G(a)\rightarrow F(x)),G(a)\rightarrow\forall x\,F(x)$
4.

$\forall x(F(x)\rightarrow G(a)),\exists x\,F(x)\rightarrow G(a)$
5.

$\exists x(G(a)\rightarrow F(x)),G(a)\rightarrow\exists x\,F(x)$
6.

$\exists x(F(x)\rightarrow G(a)),\forall x\,F(x)\rightarrow G(a)$

NB: the variable ‘ $x$ ’ does not occur in ‘ $G(a)$ ’. When all the quantifiers occur at the beginning of a sentence, that sentence is said to be in prenex normal form. These equivalences are sometimes called prenexing rules, since they give us a means for putting any sentence into prenex normal form.