8
$\begingroup$

I have to prove that this set of logical operators is not functionally complete - $$ \{\lnot,\leftrightarrow\} $$

i've tried to implement this set with $ \{\rightarrow,\lor\} $ which is also not functionally complete, but didn't succeed.. thanks !

$\endgroup$

4 Answers 4

5
$\begingroup$

Claim: Any truth-function $\phi$ defined over two or more variables and using $\neg$ and $\leftrightarrow$ only will have an even number of $T$'s and (therefore) an even number of $F$'s in the truth-table.

Proof: Take any such truth-function $\phi$. Since it involves two or more variables, the number of rows in the truth-table is a multiple of 4. By Induction over structure of $\phi$ we'll show that any subformula of $\phi$ will have an even number of $T$'s and $F$'s in the truth-table of $\phi$

Base: Take atomic statement $P$. In the truth-table of $\phi$, exactly half of the times $P$ will be $T$, and the other half it is $F$. So given that the number of rows in the truth-table is a multiple of 4, there are an even number of $T$'s and an even number of $F$'s

Step: Let $\psi$ be a subformula of $\phi$. We need to consider two cases:

Case 1: $\psi = \neg \psi_1$

By inductive hypothesis, $\psi_1$ has an even number of $T$'s and $F$'s in the truth-table. Since all $T$'s become $F$'s and vice versa when negating, that means that $\psi$ has an even number of $T$'s and $F$'s in the truth-table.

Case 2: $\psi = \psi_1 \leftrightarrow \psi_2$

By inductive hypothesis, $\psi_1$ and $\psi_2$ both have an even number of $T$'s and $F$'s in the truth-table.

Now consider what happens when we evaluate $\psi = \psi_1 \leftrightarrow \psi_2$. Let us first consider the $m$ rows where $\psi_1$ is $T$. Of those rows, assume that $\psi_2$ is $T$ in $m_1$ of those and hence $F$ in $m-m_1$ of those. This gives us $m_1$ $T$'s and $m-m_1$ $F$'s for $\psi$. Now consider the $n$ rows where $\psi_1$ is $F$. Of those rows, assume that $\psi_2$ is $T$ in $n_1$ of those and hence $F$ in $n-n_1$ of those. This gives us $n_1$ $F$'s and $n-n_1$ $T$'s for $\psi$. So, in total we get $m_1 + p_2$ $T$'s and $m_2 + p_1$ $F$'s for $\psi$.

But, since by inductive hypothesis $\psi_1$ has an even number of $T$'s, we know $m = m_1 + m_2$ and $n = n_1 + n_2$ are both even and thus $m_1$ and $m_2$ have the same parity, and same for $n_1$ and $n_2$. Also, since by inductive hypothesis $\psi_2$ has an even number of $T$'s and $F$'s in the truth-table, we have that $m_1 + n_1$ and $m_2 + n_2$ are both even, meaning that $m_1$ and $n_1$ have the same parity, and same for $m_2$ and $n_2$. Combining this, that means that $m_1$ and $n_2$ have the same parity, and same for $m_2$ and $n_1$. Hence, $m_1 + p_2$ and $m_2 + p_1$ are both even, meaning that $\psi$ has an even number of $T$'s and $F$'s in the truth-table.

Now that we have proven the claim, we know that you cannot capture truth-functions that have an odd number of $T$'s and an odd number of $F$'s in the truth-table. Hence, $\{ \neg, \leftrightarrow \}$ is not expressively complete.

$\endgroup$
8
  • 1
    $\begingroup$ @Y.X. The assumption is that P occurs in a larger statement $\phi$, and that $\phi$ has at least two variables. Also, the truth-table for a statement with $n$ variables has $2^n$ rows. So, with two or more variables (i.e. $n \ge 2$, the number of rows becomes a multiple of 4. Finally, in the truth-table for $\phi$, P is one of the reference columns on the left, and they always have exactly as many $T$'s as $F$'s. And just to be clear: an atomic statement is the same as a variable. $\endgroup$
    – Bram28
    Commented Mar 6, 2017 at 13:02
  • 2
    $\begingroup$ Nice proof, and self-contained, unlike other answers. A few devilish details, sorry it's years after you answered: (*) There's no need for the claim to require 2 or more variables: clearly an atomic formula has an even number of T rows in its truth table. With that change the Base case of the proof will be correct/appropriate; it isn't now. (**) The undefined variables $p_i$ should be $n_i$. (***) $m_2$ and $n_2$ are used but never actually defined [$m_2$ maybe implicitly, $n_2$ never]. Of course $m_2 = m - m_1$, and $n_2 = n - n_1$. $\endgroup$
    – BrianO
    Commented Mar 8, 2022 at 20:26
  • 1
    $\begingroup$ @BrianO Makes sense, thanks!! $\endgroup$
    – Bram28
    Commented Mar 8, 2022 at 21:01
  • 1
    $\begingroup$ @DuduBob The truth-table for any function that refers to $2$ or more variables (and that is what we are dealing with here) will have a number of rows that is a multiple of $4$. Working out the truth-conditions for an atomic statement in such a truth-table will have an even number of T's and an even number of F's. $\endgroup$
    – Bram28
    Commented Jan 15, 2023 at 15:10
  • 1
    $\begingroup$ @DuduBob An atomic formula $P$ occurring in $\phi$ receives a T or an F in each row of the truth table for $\phi$; we're not considering a separate, smaller truth table for $P$ alone, which yes would have only two rows. Here, the number of rows is a multiple of 4, and the claim is that $P$ the number of rows in which it's T equals the number of rows in which it's F. $\endgroup$
    – BrianO
    Commented Jan 16, 2023 at 5:09
3
$\begingroup$

Both of these functions are linear. If you make compositions of linear functions, the result is also linear. So any non-linear function is not constructible using these two.

Also, any problem of this sort can be solved in a similar way. For instance, the other set that you mention $\{\to, \lor\}$ is not complete because both connectives are truth-preserving, and composing truth-preserving functions again leads to truth-preserving functions. See here.

$\endgroup$
4
  • $\begingroup$ Reading the description of the link, neither of the two given operations is linear, since that property requires taking the value 'false' when all arguments are false. For $\leftrightarrow$ one could repair this by intrchanging the roles of 'true' and 'false', but for $\lnot$ this does not work. So one needs a different notion than 'linear'. $\endgroup$ Commented Nov 8, 2013 at 9:16
  • $\begingroup$ @MarcvanLeeuwen Note that $a_0\ldots a_n$ are fixed boolean values. $\endgroup$
    – Lord_Farin
    Commented Nov 8, 2013 at 9:19
  • $\begingroup$ @Marc $b_1 \leftrightarrow b_2 = 1 \oplus b_1 \oplus b_2$. It fits the definition on wikipedia. Although I do agree that it would be better to stick to calling such functions affine. $\endgroup$
    – Dan Shved
    Commented Nov 8, 2013 at 9:25
  • $\begingroup$ I missed the $a_0$ in the initial description of the WP article. But then the WP article contradicts itself, as it later clearly states that all arguments false should result in a false value. I think calling "linear" functions that need $a_0=1$ is very confusing since inconsistent with the use in linear algebra (which field may have usurpated the term "linear" that originally meant "straight", true, but that is now history). $\endgroup$ Commented Nov 8, 2013 at 9:39
2
$\begingroup$

Represent Boolean functions as functions $\def\F{\Bbb F_2}\F^n\to\F$ (with $\F=\Bbb Z/2\Bbb Z$) by identifying false with$~0$ and true with$~1$. Such a function is called affine if it is of the form $(x_1,\ldots,x_n)\mapsto c_0+c_1x_1+\cdots+c_nx_n$ for some constants $c_0,c_1,\ldots,c_n\in\F$. Composing affine functions (for varying $n$) results in affine functions: in the expression for $f(g_1(x_1,\ldots,x_n),\ldots,g_k(x_1,\ldots,x_n))$ just work everything out by the distributive law.

Now $\lnot: x\mapsto 1+x$ and ${\leftrightarrow}:(x,y)\mapsto 1+x+y$ are affine functions, but among all $2^4=16$ functions $\F^2\to\F$, only $8$ are affine (there are three constants $c_0,c_1,c_2$ to choose), so there are certainly functions that are not affine, and therefore cannot be obtained by composition of $\lnot$ and $\leftrightarrow$. For instance $\land$ is such a function. (In fact the affine ones are $0$, $(x,y)\mapsto x$, $(x,y)\mapsto y$, $\leftrightarrow$, and their negations; all of these can be obtained as compositions of $\lnot$ and $\leftrightarrow$.)

$\endgroup$
1
$\begingroup$

Hint: If you have a formula made up of these and consider it as a function, in which ways can this function change when you negate one of the input variables?

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .