Show that {∨, ¬} is adequate.

Question

So, I've been thinking lately on how to show that set {$\lor, \lnot$} is adequate. I've came across few ideas on how I'd have to build my proof, albeit I am not fairly sure how to process nor if my thoughts are good.

First, I thought I could rely on the fact that for every formula $\psi$, there is equivalent formula $\omega$ in DNF. That'd would give me adequate set of S = {$\land, \lnot, \lor$}. Then, I'd have to show, I can construct $\land$ connective out of B = {$\lor, \lnot$} set. How, however, do I prove, that if I can build connectives of adequate set S, using only set B connectives, then set B is adequate?

Another idea was to use structural induction to show set {$\lor, \lnot$} is adequate, for this, however, I am not certain how to build both base as well as induction step.

Answer 1

Say that an $n$-place Boolean function $G$ is realized by a wff $\alpha$ whose atomic sentence symbols are $A_1,...,A_n$ if $G(X_1,...,X_n)$ is equal to the truth value of $\alpha$ when $A_1,...,A_n$ are given the truth values $X_1,...,X_n$ respectively.

The key to answering your question is the following result.

Theorem. Every $n$-place Boolean function $G$ is realized by some $\alpha$.

Proof. If $G$ is constantly false then $A_1 \wedge \neg A_1$ realizes $G$. Otherwise, suppose there are $k$ points at which $G$ is true: $$X_1 = (X_{11},...,X_{1n}),...,X_k=(X_{k1},...,X_{kn}).$$

Now let $\beta_{ij}$ be $A_j$ or $\neg A_j$ according as $X_{ij}$ is true or false. Let $\gamma_i = \beta_{i1} \wedge ... \wedge \beta_{in}$ and let $\alpha = \gamma_1 \vee ... \vee \gamma_k$. Now check that $\alpha$ realizes $G$ (I leave this to you as an instructive exercise). QED

Remark. Notice that $\alpha$ in the foregoing proof is in DNF. From this observation and the theorem just proved, we see that $\{\vee, \wedge, \neg \}$ is adequate.

Finally, we have

Theorem. The set $\{\vee, \neg \}$ is adequate.

Proof. Let $\alpha$ be a wff using only connectives in $\{\vee, \wedge, \neg \}$. We can show by induction on $\alpha$ that there is a tautologically equivalent wff $\alpha '$ using only connectives in $\{\vee, \neg \}$. And from this it follows that $\{ \vee, \neg \}$ is adequate, since if $\alpha$ realizes $G$ and $\alpha \equiv \alpha '$, then $\alpha '$ realizes $G$ too.

The base case in which $\alpha$ is an atomic sentence symbol is trivial (let $\alpha '$ be $\alpha$).

For the inductive step, first suppose $\alpha$ is $\neg \beta$. Then let $\alpha '$ be $\neg \beta '$.

Second, suppose $\alpha$ is $\beta \wedge \gamma$. Then let $\alpha '$ be $\neg(\neg \beta ' \vee \neg \gamma ')$. It's easy to check that $\alpha \equiv \alpha '$. QED

Answer 2

B will work out as adequate, by reinterpreting $\land$ in S as an abbreviation for a formula with just the connectives $\lor$ and $\lnot$.

Thus, disjunctive normal forms would work out as having abbreviations in them.

For example, a disjunctive normal form like

((A$\land$B)$\lor$($\lnot$A$\land$B))

would consist of an abbreviation for

($\lnot$($\lnot$A$\lor$$\lnot$B)$\lor$$\lnot$($\lnot$$\lnot$A$\lor$$\lnot$B)).

But, is the above in disjunctive normal form? (my book implies it is not in disjunctive normal form by definition and so does Wikipedia)

If not, then disjunctive normal form is not necessary for proving expressive adequacy.

So, here's another possibility:

Note that every expressive adequacy means we can represent every truth-function. We could represent all truth-functions of an arity n by all possible bits having (2^n) members (by (2^n) I mean 2 to the nth power).

Thus, we have a sort of natural ordering for the outputs of truth-functions as follows:

[0, 1]

[00, 01, 10, 11]

[0000, 0001, 0010, ..., 1110, 1111]

[00000000, 000000001, ..., 11111111]

So, you might try to show that there exists a formula with $\lor$ and $\lnot$ which can always output any of those bits for a truth function of a given arity n, and then have some sort of induction that allows us to move up an arity.

Edit: Post basically shows the key idea in his paper A General Theory of Elementary Propositions.

Roughly, the idea goes that you show that you can obtain the following truth tables:

p  F1(p)  F2(p)  F3(p)  F4(p)
0  0      0      1      1
1  0      1      0      1

Then we show that for any truth table where the function has arity n, we can build every truth table for arity (n+1). Post uses the term 'order' for what we call arity.