Show that a set of connectives {∨, ∧} through structural induction is not a complete set of connectives

Question

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,

Answer 1

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:

1. if $\beta$ differs from $\alpha$ at a single variable $p$ and $\alpha(p) = 0$ but $\beta(p) = 1$, then $\alpha \le \beta$.
2. $\alpha(\phi \land \psi) = \min(\alpha(\phi), \alpha(\psi))$;
3. $\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$.