Vtyjkyuk

In my textbook I am introduced to two ways to prove that a set of connectives is functionally incomplete. The first one is to prove that it has a property that not all truth functions do.

I am stuck at finding one such property for $lnot$ (and I can't believe I am so dumb to be stuck...). I have two ideas: first one is to prove that $lnot$ always returns a $F$ for any true argument (thus rendering a truth function that returns $T$ from a true arugment impossible).

Prove that if $phi$ is built up using the variable $P$ with $lnot$, and $v$ is the truth assignment s.t. $v(p)=T$, then $v(phi)=F$.

Induction on the number $n$ of connectives in $phi$.

Base case $n=0$: $phi=P$ - there isn't any $lnot$ to talk about, so it is vacuously true.

Assume that it holds true for $le n$, prove that it holds true for $n+1$.

$phi=lnot psi$: Number of connectives within $psi=n$, thus it holds true for $psi$. Therefore $v(p)=Tto v(psi)=F$.

As you can see, if $v(psi)=F$, then $v(phi)=v(lnot psi)=T$, which is not what we want. This seems to be an instance of double negation; it can flip whatever truth value to the opposite, so it seems futile to try and show that there is a truth function $lnot$ cannot show, because with double negation you can always show a $T/F$.

The second idea to show that a negation can only show a truth function with one argument, but not one with more than one. But this seems only to be a syntactical problem: yes, you can't show a formula of $>1$ variables with only negation, but you can still draw a truth table for it nonetheless.

So my first question is,

1) what went wrong with my proof, and how to prove $lnot$ is functionally incomplete by showing a property that only this set has?

The second way is to show how many truth functions of $n$ arguments can be represented; if this number is $<2^2^n$, then it is not complete; vice versa.

The book showed how to use this approach to prove that $land$ is incomplete. The number for this set is $2^n -1$. My question is,

2) how do we know the number for $lnot,land,lor=2^2^n$?

It must be so since it is complete, but I just don't know how to prove it.

(The book equivalated formulas $phi$ built up using variables in the set $p_1, p_2, . . . , p_n$ to a normal form where no parenthesis remains and only variables are left, and explained that the number of non-empty subsets of this
set of variables used to build the normal form $=2^n -1$. e.g. $phi=(p_3land p_1)land (p_2land(p_1land p_4))$, normal form=$p_1land p_2 land p_3 land p_4$)

Really appreciate any help offered!

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.

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.

$$beginmatrix 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\ endmatrix$$

Here $alpha_i_j,beta_iinmathbfT,mathbfF$ and $k=2^n$ with $iin1,ldots,k$ and $jin1,ldots,n$. We construct the conjunction $bigwedgelimits^n_m=1p^*_m$ for every truth value assignment with number $i$ of propositional variables $p_1,ldots,p_n$.

$$p^*_m=left{beginmatrixp_m&Leftrightarrow&alpha_i_j=mathbfT\neg p_m&Leftrightarrow&alpha_i_j=mathbfFendmatrixright.$$
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)=mathbfT$.

One

Assume $eta$ returns $mathbfT$ 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 $mathbfC_i$ for every such assignment and then join them together into $bigveelimits^r_i=1mathbfC_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 $bigveelimits^n_i=1(p_iwedgeneg 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.