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