# Proving that a set with a quaternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows:

$N(w,x,y,z)=((x\land y)\land(w\lor z))$

I know that we cannot express $\lnot$ with this $N$ connective but when I tried to prove it I got stucked.

Thanks for any hint or help.

Given some proposition $q$, consider the set of propositions $M(q)$ formed as follows:

• $T \in M(q)$
• $F \in M(q)$
• $q \in M(q)$
• $\forall \{e_w,e_x,e_y,e_z : (e_w \in M(q) \land e_x \in M(q) \land e_y \in M(q) \land e_z \in M(q)) \implies N(e_w,e_x,e_y,e_z) \in M(q)$

What we need to prove is that $\lnot q \not \in M(q)$ .

To do that, consider a subset $M_k(q) \subset M(q)$ consisting of those elements that may be reached using only up to $k$ applications of that last rule (that is, up to $k$ applications of $N(e_w,e_x,e_y,e_z)$). (Define $M_0(q) = \{q, T, F\}$).

Clearly, if $M_{k+1}(q)= M_k(q)$ then $M_k(q) = M(q)$ since no new propositions can later be added.

Starting with the set $\{q, T, F\}$ form $M_1(q)$ by explicitly simplifying the 81 possible combinations of $(e_w,e_x,e_y,e_z)$. The answer will be that $$M_1(q) = \{q, T, F\} = M_0(Q)$$ therefore, $$M(q) = \{q, T, F\}$$ and $\lnot q \not \in M(q)$.

Q.E.D.

Sketch solution/hint: So the only thing you need to prove (in this simple) when you want to show that it can not express $\neg$ is that for some valuation (i.e. line in a truth table), things do not work correctly.

So what if we choose the valuation function $v$ which evaluate all propositional variables $p$ as $v(p)= true$ (i.e. the top line of a truth table)? You can now show trough induction over how formulas are created that for any formula $\varphi$ created using only $N$ we have that $v(\varphi)=true$. But the formula $\neg p$ we have that $v(\neg p)= false$. Thus N can not be truth functional complete, as it can not express the formula $\neg p$.