Show that a set of connectives {∨, ∧} through structural induction is not a complete set of connectives I understand how a set of connectives such as {∨,∧,¬}, can be considered adequate, but I'm not fully understanding how one would go proving something that is not adequate
The full problem is as follows:
Use structural induction to prove that any formula φ defined using only the connectives
∨ and ∧ has the following property: Let α be an assignment of truth values to the variables
in φ, and let ˆα be an assignment that results by switching the value of α at one variable from
false to true. (That is, there is a variable p such that α(p) = false and ˆα(p) = true, but
α(q) = ˆα(q) for all other variables q.) If φ = true then φ = true. The desired result
follows because not every formula has this property
I drew up a truth table for this but I'm stuck from there.
Thank you,
 A: Assume $false = 0 < true = 1$, and order all assignments pointwise, so that $\alpha \le \beta \iff (\forall \text{ variables } p)\, \alpha(p)\le \alpha(q)$.
Where $\alpha$ is an assignment and $\phi, \psi$ are formulas, note the following:


*

*if $\beta$ differs from $\alpha$ at a single variable $p$ and $\alpha(p) = 0$ but $\beta(p) = 1$, then $\alpha \le \beta$.

*$\alpha(\phi \land \psi) = \min(\alpha(\phi), \alpha(\psi))$;

*$\alpha(\phi \lor \psi) = \max(\alpha(\phi), \alpha(\psi))$;


By induction on formulas, it's easy to see from 2. and 3. that

If $\alpha \le \beta$ then 
  
  
*
  
*$\alpha(p)\le\beta(p)$ for every variable $p$,
  
*$\alpha(\phi \land \psi)\le\beta(\phi \land \psi),$
  
*$\alpha(\phi \lor \psi)\le\beta(\phi \lor \psi).$
  

Thus, every formula $\phi$ built up from variables and $\{\land, \lor\}$ has the property that if $\alpha \le \beta$ then $\alpha(\phi)\le\beta(\phi)$.
However, there are formulas of propositional calculus that don't have this property. For example, let $\alpha(p)=\alpha(q)=0$, $\beta(p)=1, \beta(q)=0$. Then $\alpha\le\beta$; however, $\alpha(p\to q) =1$ whereas $\beta(p\to q) = 0$.
