6
$\begingroup$

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)=T\to 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_3\land p_1)\land (p_2\land(p_1\land p_4))$, normal form=$p_1\land p_2 \land p_3 \land p_4$)

Really appreciate any help offered!

$\endgroup$
  • $\begingroup$ Using $\lnot$ you can only create two functions. $\endgroup$ – copper.hat Jan 31 '18 at 5:56
  • 1
    $\begingroup$ If you assign $F$ to all variables, any formula composed with the connective $\land$ has the value $F$. $\endgroup$ – copper.hat Jan 31 '18 at 6:02
  • $\begingroup$ Use the Boole expansion and induction to show that a formula can be created for any given truth table. $\endgroup$ – copper.hat Jan 31 '18 at 6:05
  • $\begingroup$ which textbook are you using may I ask? $\endgroup$ – John11 Oct 17 '18 at 17:57
  • 1
    $\begingroup$ Thank you! @DanielMak $\endgroup$ – John11 Oct 18 '18 at 6:49
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your help time and again! The whole approach is crystal clear to me; just wanna follow up: so trying to show that for any formula constructed from $\{\lnot\}$, $v(p)=T\to v(\phi)=F$ would never work because the double negation can always flip it back to $T$, correct? And to prove that $\{¬\}$ cannot show any truth function with 2 or more arguments, would we need to use induction or just an argument? Because this seems to be a counter-argument example type of work, so an induction doesn't seem to work, but I am just not sure. $\endgroup$ – Daniel Mak Feb 2 '18 at 0:35
  • 1
    $\begingroup$ @DanielMak well, the only kind of statement you can get with only a $\neg$ is of the form $\neg \neg \neg .... P$ with $P$ some atomic propsition; I don't think that would need any further elaboration. $\endgroup$ – Bram28 Feb 2 '18 at 1:33
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much for your help! I don't quite understand the diagram you drew to illustrate the Boolean function, but I am guessing you constructed a conjunctive normal form that can represent any truth function? The whole approach is understandable to me, but is there a way to count the number of truth functions any given normal form can represent? $\endgroup$ – Daniel Mak Feb 2 '18 at 0:22
  • $\begingroup$ We know that this number for a CNF/DNF is $2^{2^n}$ because we know there are in total that many truth functions given $n$ arguments, but what if we are given a normal form (eg. like the one I talked about above where a string of conjunction is being rearranged into an orderly one by equivalence) that cannot represent every possible truth function? $\endgroup$ – Daniel Mak Feb 2 '18 at 0:24
  • $\begingroup$ And to prove that {¬} cannot show any truth function with 2 or more arguments, would we need to use induction or just an argument along the lines of what you wrote above would do? I think whether to use induction or not is where I am getting stuck with that one. Спасибо! $\endgroup$ – Daniel Mak Feb 2 '18 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.