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