1
$\begingroup$

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,

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.