1
$\begingroup$

I want to show that the set $\{\wedge, \top, \bot\}$ is not complete. I can't quite figure out a wff that cannot be expressed using just these three. Anyone have any ideas?

$\endgroup$
3
  • $\begingroup$ How about the wtf $\lnot x$? Show by induction that all wff are 'non increasing' in terms of the constituent variables.e $\endgroup$
    – copper.hat
    Commented Mar 9, 2017 at 15:31
  • $\begingroup$ A wff in what language? How about $x \vee y$, with $x$ and $y$ as sentential variables? $\endgroup$ Commented Mar 9, 2017 at 15:31
  • $\begingroup$ The wff is in sentential logic. $\endgroup$ Commented Mar 9, 2017 at 16:10

1 Answer 1

1
$\begingroup$

HINT: You know that $\{\wedge, \neg\}$ is complete, and clearly $\wedge$ is expressible by your set (since it contains $\wedge$ already); so what's a wff $\mathcal{W}$ that has to be inexpressible by your set, if your set is to be incomplete?

Now to show this, you're going to have to use induction on formula complexity; and the easiest way to do this is to classify exactly what connectives in the "right" number of variables (that is: as many variables as are in $\mathcal{W}$) are expressible by your set. So try a few combinations; what connectives does it look like you can build?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .