Questions on how to prove that a set of connectives is NOT functionally complete

Solution 1:

Daniil wrote an excellent post, but just to add to that a little bit:

As Daniil pointed out, you can't capture any truth-functions that non-trivially depend on more than $1$ variable, such as $P \land Q$, with only a $\neg$. So, let's restrict ourselves to functions defined over one variable, $P$, and see if maybe we can capture all those using a $\neg$?

Unfortunately, the answer is still no. Again, as Daniil already pointed out, we can't capture any tautology or contradiction. That is, we can't capture the truth-function that always returns true (i.e. the function $f$ such that $f(T)=f(F)=T$), nor can we capture the truth-function that always returns false (i.e. the function $f'$ such that $f'(T)=f'(F)=F$)

So in this post I just wanted to show you how you can prove that result using induction. In particular, let's prove the following:

Claim

For any expression $\phi$ built up from $P$ and $\neg$ alone, it will be true that if $v$ is the valuation that sets $P$ to true (i.e. $v(P)=T$), and $v'$ is the valuation that sets $P$ to false (i.e. $v'(P)=F$), then either $v(\phi)=T$ and $v'(\phi)=F$, or $v'(\phi)=T$ and $v(\phi)=F$ (in other words, $v(\phi)$ and $v'(\phi)$ will always opposite values, meaning that $\phi$ can not be a tautology or contradiction, for that would require that $\phi$ has the same value for any valuation)

Proof

We'll prove the claim by structural induction on the formation of $\phi$:

*Base: *

$\phi=P$. Then $v(\phi)=v(P)=T$, while $v'(\phi)=v'(P)=F$. Check!

Step:

If $\phi$ is not an atomic proposition, then there is only one possibility: $\phi$ is the negation of some other statement $\psi$, i.e. $\phi = \neg \psi$.

Now, by inductive hypothesis we can assume that $v(\psi)=T$ and $v'(\psi)=F$, or $v'(\psi)=T$ and $v(\psi)=F$

Well, if $v(\psi)=T$ and $v'(\psi)=F$, then $v(\phi)=v(\neg \psi)=F$ and $v'(\phi)=v'(\neg \psi) =T$. On the other hand, if $v(\psi)=F$ and $v'(\psi)=T$, then $v(\phi)=v(\neg \psi)=T$ and $v'(\phi)=v'(\neg \psi) =F$. So, we can conclude that $v(\phi)=T$ and $v'(\phi)=F$, or $v'(\phi)=T$ and $v(\phi)=F$, as desired.

Solution 2:

Let's begin with a definition.

A set of classical logical connectives is called “functionally complete” w.r.t. class of Boolean functions iff any Boolean function with a finite number of arguments can be expressed using only the connectives from that set.

In your first question you want to find such a property for negation that there are some other functions lacking it. Well, it is simple: if you have only negation, you cannot do any of the following.

1. Construct tautologies and contradictory formulas. You can make tautologies, e.g. if you have only implication and XOR is enough for contradictiory formulas.
2. You cannot construct formulas with more than one variable. This can be done using any function with at least two arguments.

I am sure, there are some other properties.

Now, to your second question.

We can prove an equivalent result: that $\{\wedge,\vee,\neg\}$ is functionally complete as defined above. But first let us recall, that there are exactly $2^{2^n}$ Boolean functions with $n$ arguments. Hence, if $\{\wedge,\vee,\neg\}$ is functionally complete, then there will be $2^{2^n}$ Boolean functions with $n$ arguments for any $n$.

$\{\neg,\vee,\wedge\}$ is functionally complete with respect to the class of all $n$-ary Boolean functions.

Assume now, we have arbitrary $n$-ary Boolean function $\eta$ defined as follows.

$$\begin{matrix} p_1&\ldots&p_n&\eta(p_1,\ldots,p_n)\\ \alpha_{1_1}&\ldots&\alpha_{1_n}&\beta_1\\ \vdots&\ddots&\vdots&\vdots\\ \alpha_{k_1}&\ldots&\alpha_{k_n}&\beta_k\\ \end{matrix}$$

Here $\alpha_{i_j},\beta_{i}\in\{\mathbf{T},\mathbf{F}\}$ and $k=2^n$ with $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$. We construct the conjunction $\bigwedge\limits^{n}_{m=1}p^*_m$ for every truth value assignment with number $i$ of propositional variables $p_1,\ldots,p_n$.

$$p^*_m=\left\{\begin{matrix}p_m&\Leftrightarrow&\alpha_{i_j}=\mathbf{T}\\\neg p_m&\Leftrightarrow&\alpha_{i_j}=\mathbf{F}\end{matrix}\right.$$ We will call these conjunctions truth constituents.

The proof splits into three parts depending on under how many (none, one, some) assignments $\eta(p_1,\ldots,p_n)=\mathbf{T}$.

One

Assume $\eta$ returns $\mathbf{T}$ on exactly one assignment, say, $\alpha_{i_1},\ldots,\alpha_{i_n}$. We construct a truth constituent for this assignment which contains only negation and conjuction and is true under this assignment. It is quite easy to see that this truth constituent is true only under $\alpha_{i_1},\ldots,\alpha_{i_n}$. The case is proven.

Some

Assume there are $r$ such different assignments that $\eta$ is true. We construct a truth constituent $\mathbf{C}_i$ for every such assignment and then join them together into $\bigvee\limits^{r}_{i=1}\mathbf{C}_i$. It is easy to see that our formula is true under the same assignments as $\eta$.

None

In this case $\eta$ is represented as $\bigvee\limits^{n}_{i=1}(p_i\wedge\neg p_i)$. Obviously, this is a contradictory formula.

Now, since we have shown that $\{\wedge,\vee,\neg\}$ is indeed functionally complete, we know that for any $n$ it can express any Boolean function with $n$ arguments. Since we know that there are $2^{2^n}$ of them, we proved what we needed.