Intereting Posts

How to draw by hand mathematical figures?
How can you prove that a function has no closed form integral?
Cross product in $\mathbb R^n$
Proving an interpolation inequality
A prime formed by concatenating Fibonacci numbers?
Relation between exterior (second) derivative $d^2=0$ and second derivative in multi-variable calculus.
determinant of permutation matrix
What is the opposite category of $\operatorname{Top}$?
Measure of the Cantor set plus the Cantor set
general equation of a tangent line to a hyperbola
Betti numbers and Fundamental theorem of finitely generated abelian groups
Variance of sum of random variables 2
Finding $\lim\limits_{n \rightarrow \infty}\left(\int_0^1(f(x))^n\,\mathrm dx\right)^\frac{1}{n}$ for continuous $f:\to
A convergence problem： splitting a double sum
Let $G$ be a finite group with $|G|>2$. Prove that Aut($G$) contains at least two elements.

I have to prove that this set of logical operators is not functional complete –

$$ \{\lnot,\leftrightarrow\} $$

i’ve tried implement this set by $ \{\rightarrow,\lor\} $ which is not functional complete too, but didn’t success..

thanks !

- Power set representation of a boolean ring/algebra
- FOUR-algebra - boolean algebra?
- proving logical equivalence $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$
- Can someone explain consensus theorem for boolean algebra
- Prove XOR is commutative and associative?
- How to prove boolean ordering question

- Logic: Using Quantifiers To Express “At Least 2?”
- Prove that if an average of a thousand numbers is less than 7, then at least one of the numbers being averaged is less than 7
- Are (some) axioms “unprovable truths” of Godel's Incompleteness Theorem?
- Is $\lor$ definable in intuitionistic logic?
- In classical logic, why is $(p\Rightarrow q)$ True if both $p$ and $q$ are False?
- Image of a strictly increasing computable function is computable?
- Logical Conditional Truth Table Rationale
- Is 1+1 =2 a theorem?
- What are the prerequisites for studying mathematical logic?
- Logical implication help

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.

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$.)

**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.

**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?

- Solving the complex polynomial
- Writing Integrals using Differential Forms
- Does the series $\sum_{n = 1}^{\infty}\left(2^{1/n} – 1\right)\,$ converge?
- Integrable function whose Fourier transform is not integrable
- How can we show that $\int_{0}^{\pi/2}x\cos(8x)\ln\left(1+\tan x\over 1-\tan x\right)\mathrm dx={\pi\over 12}?$
- Outer measure is countably subadditive
- Inverse images and $\sigma$-algebras
- Union of uncountable cardinals
- Why characters are continuous
- Parametrisation of the surface a torus
- Permutations to satisfy a challenging restriction
- Singular values of $AB$ and $BA$ matrices
- Why is the axiom of choice separated from the other axioms?
- Positive Elements of $\mathbb{C}G$: as functionals versus as elements of the C*-algebra
- A good, free, graphics package for mathematics?