forallx-yyc-metatheory.tex

\part{Advanced Topics}
\addtocontents{toc}{\protect\mbox{}\protect\hrulefill\par}

\chapter{Normal forms and expressive completeness}}\label{ch:normalform}

\section{Disjunctive Normal Form}\label{s:DNFDefined}

Say that a sentence is in \define{disjunctive normal form} \emph{iff} it meets all of the following conditions:
	\begin{earg}
		\item[(\textsc{dnf1})] No connectives occur in the sentence other than negations, conjunctions and disjunctions;
		\item[(\textsc{dnf2})] Every occurrence of negation has minimal scope (i.e.\ any `$\enot$' is immediately followed by an atomic sentence);
		\item[(\textsc{dnf3})] No disjunction occurs within the scope of any conjunction.
	\end{earg}
So, here are are some sentences in disjunctive normal form:
	\begin{center}
		$A$\\
		$(A \eand B) \eor (A \eand \enot B)$\\
		$(A \eand B) \eor (A \eand  B \eand C \eand \enot D \eand \enot E)$\\
		$A \eor (C \eand \enot P_{234} \eand P_{233} \eand Q) \eor \enot B$
	\end{center}
Note that I have here broken one of the maxims of this book (see \S\ref{s:InductionOnLength}) and \emph{temporarily} allowed myself to employ the relaxed bracketing-conventions that allow conjunctions and disjunctions to be of arbitrary length. These conventions make it easier to see when a sentence is in disjunctive normal form. I shall continue to help myself to these relaxed conventions, without further comment.

To further illustrate the idea of disjunctive normal form, I shall introduce some more notation. I write `$\pm\meta{A}$' to indicate that $\meta{A}$ is an atomic sentence which may or may not be prefaced with an occurrence of negation. Then a sentence in disjunctive normal form has the following shape:
	$$(\pm \meta{A}_1 \land \ldots \land \pm \meta{A}_i) \lor (\pm \meta{A}_{i+1} \land \ldots \land \pm\meta{A}_j) \lor \ldots \lor (\pm\meta{A}_{m+1} \land \ldots \land \pm \meta{A}_n)$$
We now know what it is for a sentence to be in disjunctive normal form. The result that we are aiming at is:
	\factoidbox{\label{thm:dnf}\textbf{Disjunctive Normal Form Theorem.} For any sentence, there is a tautologically equivalent sentence in disjunctive normal form.
	}
Henceforth, I shall abbreviate `Disjunctive Normal Form' by `DNF'. 


\section{Proof of DNF Theorem via truth tables}\label{s:DNFTruthTable}
My first proof of the DNF Theorem employs truth tables. I shall first illustrate the technique for finding an equivalent sentence in DNF, and then turn this illustration into a rigorous proof. 

Let's suppose we have some sentence, $\meta{S}$, which contains three atomic sentences, `$A$', `$B$' and `$C$'. The very first thing to do is fill out a complete truth table for $\meta{S}$. Maybe we end up with this:
\begin{center}
\begin{tabular}{c c c | c}
$A$ & $B$ & $C$ & $\meta{S}$\\
\hline
 T & T & T & T \\
 T & T & F & F \\
 T & F & T & T \\
 T & F & F & F \\
 F & T & T & F \\
 F & T & F & F \\
 F & F & T & T \\
 F & F & F & T
\end{tabular}
\end{center}
%Now, consider a sentence, whose only connectives are negations and conjunctions, where no connective occurs within the scope of any negation, e.g.:
%	$$A \eand \enot B \eand C$$
%This sentence is true when, and only when, `$A$' is true, `$B$' is false and `$C$' is true. Similarly, the sentence:
%	$$\enot A \eand \enot B \eand C$$
%this is true when, and only when, `$A$' is false, `$B$' is false and `$C$' is true. 
%
%A disjunction is true when, and only when, at least one of the disjuncts is true. So if I write down a disjunction of sentences of the above form, perhaps
%	$$(A \eand \enot B \eand C) \eor (\enot A \eand \enot B \eand C)$$
%then it will be true on exactly \emph{two} lines of the truth table which describes all possible valuations of `$A$', `$B$' and `$C$'. 
%
As it happens, $\meta{S}$ is true on four lines of its truth table, namely lines 1, 3, 7 and 8. Corresponding to each of those lines, I shall write down four sentences, whose only connectives are negations and conjunctions, where every negation has minimal scope:
	\begin{earg}
		\item[\textbullet]  `$A \eand B \eand C$'\hfill which is true on line 1 (and only then)
		\item[\textbullet] `$A \eand \enot B \eand C$' \hfill which is true on line 3 (and only then)
		\item[\textbullet] `$\enot A \eand \enot B \eand C$' \hfill which is true on line 7 (and only then)
		\item[\textbullet] `$\enot A \eand \enot B \eand \enot C$' \hfill which is true on line 8 (and only then)
	\end{earg}
But if I now disjoin all of these conjunctions, like so:
$$(A \eand B \eand C) \eor (A \eand \enot B \eand C) \eor (\enot A \eand \enot B \eand C) \eor (\enot A \eand \enot B \eand \enot C)$$
I have a sentence in DNF which is true on exactly those lines where one of the disjuncts is true, i.e.\ it is true on (and only on) lines 1, 3, 7, and 8. So this sentence has exactly the same truth table as $\meta{S}$. So I have a sentence in DNF that is tautologically equivalent to $\meta{S}$. Which is exactly what I required!

Now, the strategy that I just adopted did not depend on the specifics of $\meta{S}$; it is perfectly general. Consequently, we can use it to obtain a simple proof of the DNF Theorem.

Pick any arbitrary sentence, $\meta{S}$, and let $\meta{A}_1, \ldots, \meta{A}_n$ be the atomic sentences that occur in $\meta{S}$. To obtain a sentence in DNF that is tautologically equivalent $\meta{S}$, we consider $\meta{S}$'s truth table. There are two cases to consider:
	\begin{enumerate}
		\item \emph{$\meta{S}$ is false on every line of its truth table.} Then, $\meta{S}$ is a contradiction. In that case, the contradiction $(\meta{A}_1 \eand \enot \meta{A}_1)$ is in DNF and tautologically equivalent to~$\meta{S}$. 
	
		\item \emph{$\meta{S}$ is true on at least one line of its truth table.}
		For each line $i$ of the truth table, let $\meta{B}_i$ be a conjunction of the form 
		$$(\pm\meta{A}_1 \land \ldots \land \pm\meta{A}_n)$$
		where the following rules determine whether or not to include a negation in front of each atomic sentence:
			\begin{align*}
				\meta{A}_m\text{ is a conjunct of }\meta{B}_i&\emph{ iff }\meta{A}_m\text{ is true on line }i\\
				\enot\meta{A}_m\text{ is a conjunct of }\meta{B}_i&\emph{ iff }\meta{A}_m\text{ is false on line }i
			\end{align*}
		Given these rules, a trivial proof by induction shows that $\meta{B_i}$ is true on (and only on) line $i$ of the truth table which considers all possible valuations of $\meta{A}_1, \ldots, \meta{A}_n$ (i.e.\ $\meta{S}$'s truth table). 
		
		Next, let $i_1, i_2, \ldots, i_m$ be the numbers of the lines of the truth table where $\meta{S}$ is \emph{true}. Now let $\meta{D}$ be the sentence:
		$$\meta{B}_{i_1} \eor \meta{B}_{i_2} \eor \ldots \eor \meta{B}_{i_m}$$
		Since $\meta{S}$ is true on at least one line of its truth table, $\meta{D}$ is indeed well-defined; and in the limiting case where $\meta{S}$ is true on exactly one line of its truth table, $\meta{D}$ is just $\meta{B}_{i_1}$, for some $i_1$.
		
		By construction, $\meta{D}$ is in DNF. Moreover, by construction, for each line $i$ of the truth table: $\meta{S}$ is true on line $i$ of the truth table \emph{iff} one of $\meta{D}$'s disjuncts (namely, $\meta{B_i}$) is true on, and only on, line $i$. (Again, this is shown by a trivial proof by induction.) Hence $\meta{S}$ and $\meta{D}$ have the same truth table, and so are tautologically equivalent.
	\end{enumerate}
	These two cases are exhaustive and, either way, we have a sentence in DNF that is tautologically equivalent to $\meta{S}$.

So we have proved the DNF Theorem. Before I say any more, though, I should immediately flag that I am hereby returning to the austere definition of a (TFL) sentence, according to which we can assume that any conjunction has exactly two conjuncts, and any disjunction has exactly two disjuncts.


\section{Conjunctive Normal Form}\label{s:CNF}
So far in this chapter, I have discussed \emph{disjunctive} normal form. Given the duality of disjunction and conjunction (see \S\ref{s:Duality}), it may not come as a surprise to hear that there is also such a thing as \emph{conjunctive normal form} (CNF).

The definition of CNF is exactly analogous to the definition of DNF. So, a sentence is in CNF \emph{iff} it meets all of the following conditions:
	\begin{earg}
		\item[(\textsc{cnf1})] No connectives occur in the sentence other than negations, conjunctions and disjunctions;
		\item[(\textsc{cnf2})] Every occurrence of negation has minimal scope;
		\item[(\textsc{cnf3})] No conjunction occurs within the scope of any disjunction. 
	\end{earg}
Generally, then, a sentence in CNF looks like this
	$$(\pm \meta{A}_1 \lor \ldots \lor \pm \meta{A}_i) \land (\pm \meta{A}_{i+1} \lor \ldots \lor \pm\meta{A}_j) \land \ldots \land (\pm\meta{A}_{m+1} \lor\ldots \lor \pm \meta{A}_n)$$
where each $\meta{A}_k$ is an atomic sentence.

Since `$\enot$' is its own dual, and `$\eor$' and `$\eand$' are the duals of each other, it is immediate clear that if a sentence is in DNF, then its dual is in CNF; and \emph{vice versa}. Armed with this insight, we can immediately prove another normal form theorem:
	\factoidbox{\label{thm:cnf}\textbf{Conjunctive Normal Form Theorem.} For any sentence, there is a tautologically equivalent sentence in conjunctive normal form.}

        
	Given a TFL sentence, $\meta{S}$, we begin by writing down the complete truth table for $\meta{S}$.
	
	If $\meta{S}$ is \emph{true} on every line of the truth table, then $\meta{S}$ and $(\meta{A}_1 \eor \enot \meta{A}_1)$ are tautologically equivalent.
	
	If $\meta{S}$ is \emph{false} on at least one line of the truth table then, for every line on the truth table where $\meta{S}$ is false, write down a disjunction $(\pm\meta{A}_1 \eor \ldots \eor \pm\meta{A}_n)$ which is \emph{false} on (and only on) that line. Let $\meta{C}$ be the conjunction of all of these disjuncts; by construction, $\meta{C}$ is in CNF and $\meta{S}$ and $\meta{C}$ are tautologically equivalent.

\practiceproblems
\problempart
\label{pr.DNF}
Consider the following sentences:
	\begin{earg}
		\item $(A \eif \enot B)$
		\item $\enot (A \eiff B)$
		\item $(\enot A \eor \enot (A \eand B))$
		\item $(\enot (A \eif B ) \eand (A \eif C))$
		\item $(\enot (A \eor B) \eiff ((\enot C \eand \enot A) \eif \enot B))$
		\item $((\enot (A \eand \enot B) \eif C) \eand \enot (A \eand D))$
	\end{earg}
        For each sentence, find a tautologically equivalnet sentence in DNF and one in CNF.
        
\section{The expressive adequacy of TFL}
In discussing duality (\S\ref{s:Duality}), I introduced the general idea of an $n$-place connective. We might, for example, define a three-place connective, `$\heartsuit$', into existence, by stipulating that it is to have the following characteristic truth table:
\begin{center}
\begin{tabular}{c c c | c}
$\meta{A}$ & $\meta{B}$ & $\meta{C}$ & $\heartsuit(\meta{A},\meta{B},\meta{C})$\\
\hline
 T & T & T & F \\
 T & T & F & T \\
 T & F & T & T \\
 T & F & F & F \\
 F & T & T & F \\
 F & T & F & T \\
 F & F & T & F \\
 F & F & F & F
\end{tabular}
\end{center}
Probably this new connective would not correspond with any natural English expression (in the way that `$\eand$' corresponds with `and'). But a question arises: if we wanted to employ a connective with this characteristic truth table, must we add a \emph{new} connective to TFL? Or can we get by with the connectives we \emph{already have}?

Let us make this question more precise. Say that some connectives are \define{jointly expressively adequate} \emph{iff}, for any possible truth function, there is a scheme containing only those connectives which expresses that truth function. Since we can represent truth functions using characteristic truth tables, we could equivalently say the following: some connectives are jointly expressively adequate \emph{iff}, for any possible truth table, there is a scheme containing only those connectives with that truth table.

I say `scheme' rather than `sentence', because we are not concerned with something as specific as a sentence. To see why, consider the characteristic truth table for conjunction; this schematically encodes the information that a conjunction $(\meta{A} \eand \meta{B})$ is true iff both $\meta{A}$ and $\meta{B}$ are true (whatever $\meta{A}$ and $\meta{B}$ might be). When we discuss expressive adequacy, we are considering something at the same level of generality. 

The general point is, when we are armed with some jointly expressively adequate connectives, no truth function lies beyond our grasp. And in fact, we are in luck.
	\factoidbox{\label{thm:ExpressiveAdequacy}\textbf{Expressive Adequacy Theorem.}
		The connectives of TFL are jointly expressively adequate. Indeed, the following pairs of connectives are jointly expressively adequate:
			\begin{earg}
				\item\label{expressive:eor} `$\enot$' and `$\eor$'
				\item\label{expressive:eand} `$\enot$' and `$\eand$'
				\item\label{expressive:eif} `$\enot$' and `$\eif$'
			\end{earg}}

	 Given any truth table, we can use the method of proving the DNF Theorem (or the CNF Theorem) via truth tables, to write down a scheme which has the same truth table. For example, employing the truth table method for proving the DNF Theorem, I can tell you that the following scheme has the same characteristic truth table as $\heartsuit(\meta{A},\meta{B},\meta{C})$, above:
		$$(\meta{A} \eand \meta{B} \eand \enot \meta{C}) \eor (\meta{A} \eand \enot\meta{B} \eand \meta{C}) \eor (\enot \meta{A} \eand \meta{B} \eand \enot \meta{C})$$			
			It follows that the connectives of TFL are jointly expressively adequate. I now prove each of the subsidiary results.
	
				\emph{Subsidiary Result \ref{expressive:eor}: expressive adequacy of `$\enot$' and `$\eor$'.} Observe that the scheme that we generate, using the truth table method of proving the DNF Theorem, will only contain the connectives `$\enot$', `$\eand$' and `$\eor$'. So it suffices to show that there is an equivalent scheme which contains only `$\enot$' and `$\eor$'. To show do this, we simply consider that
		\begin{align*}
		(\meta{A} \eand \meta{B}) & \text{\quad and \quad} \enot(\enot \meta{A} \eor\enot \meta{B})
		\end{align*}
		are tautologically equivalent.

		\emph{Subsidiary Result \ref{expressive:eand}: expressive adequacy of `$\enot$' and `$\eand$'.} Exactly as in Subsidiary Result \ref{expressive:eor}, making use of the fact that
		\begin{align*}
		(\meta{A} \eor \meta{B}) & \text{\quad and \quad}\enot(\enot \meta{A} \eand\enot \meta{B})
		\end{align*}
                are tautologically equivalent.

			\emph{Subsidiary Result \ref{expressive:eif}: expressive adequacy of `$\enot$' and `$\eif$'.} 		Exactly as in Subsidiary Result \ref{expressive:eor}, making use of these equivalences instead:
		\begin{align*}
		(\meta{A} \eor \meta{B}) &\text{\quad and \quad} (\enot \meta{A} \eif\meta{B})\\
		(\meta{A} \eand \meta{B}) &\text{\quad and \quad} \enot(\meta{A} \eif \enot\meta{B})
		\end{align*}
		Alternatively, we could simply rely upon one of the other two subsidiary results, and (repeatedly) invoke only one of these two equivalences.

In short, there is never any \emph{need} to add new connectives to TFL. Indeed, there is already some redundancy among the connectives we have: we could have made do with just two connectives, if we had been feeling really austere.

\section{Individually expressively adequate connectives}
In fact, some two-place connectives are \emph{individually} expressively adequate. These connectives are not standardly included in TFL, since they are rather cumbersome to use. But their existence shows that, if we had wanted to, we could have defined a truth-functional language that was expressively adequate, which contained only a single primitive connective.

The first such connective we shall consider is `$\uparrow$', which has the following characteristic truth table. 
\begin{center}
\begin{tabular}{c c | c}
$\meta{A}$ & $\meta{B}$ & $\meta{A} \mathrel{\uparrow} \meta{B}$\\
\hline
 T & T & F \\
 T & F & T \\
 F & T & T  \\
 F & F & T
\end{tabular}
\end{center}
 This is often called `the Sheffer stroke', after Henry Sheffer, who used it to show how to reduce the number of logical connectives in Russell and Whitehead's \emph{Principia Mathematica}.\footnote{Sheffer, `A Set of Five Independent Postulates for Boolean Algebras, with application to logical constants,' (1913, \emph{Transactions of the American Mathematical Society} 14.4)} (In fact, Charles Sanders Peirce had anticipated Sheffer by about 30 years, but never published his results.)\footnote{See Peirce, `A Boolian Algebra with One Constant', which dates to c.1880; and Peirce's \emph{Collected Papers}, 4.264--5.} It is quite common, as well, to call it `nand', since its characteristic truth table is the negation of the truth table for `$\eand$'.
\factoidbox{\label{prop:upexpressive}`$\uparrow$' is expressively adequate all by itself.}

		Theorem \ref{thm:ExpressiveAdequacy} tells us that `$\enot$' and `$\eor$' are jointly expressively adequate. So it suffices to show that, given any scheme which contains only those two connectives, we can rewrite it as a tautologically equivalent scheme which contains only `$\uparrow$'. As in the proof of the subsidiary cases of Theorem \ref{thm:ExpressiveAdequacy}, then, we simply apply the following equivalences:
		\begin{align*}
			\enot \meta{A} &\text{\quad and \quad} (\meta{A} \uparrow \meta{A})\\
			(\meta{A} \eor \meta{B}) & \text{\quad and \quad} ((\meta{A} \uparrow \meta{A}) \uparrow (\meta{B} \uparrow \meta{B}))
		\end{align*}
		 to Subsidiary Result \ref{expressive:eor} of Theorem \ref{thm:ExpressiveAdequacy}.

Similarly, we can consider the connective `$\downarrow$':
\begin{center}
\begin{tabular}{c c | c}
$\meta{A}$ & $\meta{B}$ & $\meta{A} \mathrel{\downarrow} \meta{B}$\\
\hline
 T & T & F \\
 T & F & F  \\
 F & T & F  \\
 F & F & T
\end{tabular}
\end{center}
This is sometimes called the `Peirce arrow' (Peirce himself called it `ampheck'). More often, though, it is called `nor', since its characteristic truth table is the negation of `$\eor$'.
	\factoidbox{
	`$\downarrow$' is expressively adequate all by itself. }


	As in Proposition \ref{prop:upexpressive}, although invoking the dual equivalences:
		\begin{align*}
			\enot \meta{A} &\text{\quad and \quad} (\meta{A} \downarrow \meta{A})\\
			(\meta{A} \eand \meta{B}) & \text{\quad and \quad} ((\meta{A} \downarrow \meta{A}) \downarrow (\meta{B} \downarrow \meta{B}))
		\end{align*}
		and Subsidiary Result \ref{expressive:eand} of Theorem \ref{thm:ExpressiveAdequacy}.


\section{Failures of expressive adequacy}
 In fact, the \emph{only} two-place connectives which are individually expressively adequate are `$\uparrow$' and `$\downarrow$'. But how would we show this? More generally, how can we show that some connectives are \emph{not} jointly expressively adequate? 
 
The obvious thing to do is to try to find some truth table which we \emph{cannot} express, using just the given connectives. But there is a bit of an art to this. Moreover, in the end, we shall have to rely upon induction; for we shall need to show that \emph{no} scheme -- no matter how \emph{long} -- is capable of expressing the target truth table. 
 
 To make this concrete, let's consider the question of whether `$\eor$' is expressively adequate all by itself. After a little reflection, it should be clear that it is not. In particular, it should be clear that any scheme which only contains disjunctions cannot have the same truth table as negation, i.e.:
				\begin{center}
				\begin{tabular}{c | c}
				$\meta{A}$ & $\enot \meta{A}$\\
				\hline
				 T &  F \\
				 F & T
				\end{tabular}
				\end{center}
The intuitive reason, why this should be so, is simple: the top line of the desired truth table needs to have the value False; but the top line of any truth table for a scheme which \emph{only} contains disjunctions will always be True.
 	\factoidbox{
		`$\eor$' is not expressively adequate by itself.}

        In fact, we can generalise this to:
        
	\factoidbox{The \emph{only} two-place connectives that are expressively adequate by themselves are `$\uparrow$' and `$\downarrow$'. }

\factoidbox{\label{prop:Eiff4}
  Exactly four 2-place truth functions can be expressed using schemes whose only connectives are biconditionals:
			\begin{align*}
				\meta{A} \eiff \meta{A}\\
				\meta{A}\\
				\meta{B}\\
				\meta{A} \eiff \meta{B}
			\end{align*}
			It is clear that we can express all four, and that they are distinct.}