Counterexample to see that $\{\implies, \vee\}$ and $\{\iff,\lnot\}$ are not alone adequate to express all the truth functions.

what could be the counterexample?

what expression could not be expressed with these pairs of operators?

I don't know how to do it.

  • $\begingroup$ The last one is a bit tricky, but the first pair should be clear... both functions preserve truth, i.e. if $Q, R$ are true, so is their disjunction and any conditional formed with them. Which connective does not have this property? $\endgroup$ – Nagase Oct 13 '17 at 1:09
  • $\begingroup$ @Nagase you're right $\lnot$? $\endgroup$ – user178403 Oct 13 '17 at 1:11
  • $\begingroup$ By "v" do you mean "or"? That is \vee and \wedge for "and" in LaTeX. $\endgroup$ – Dair Oct 13 '17 at 1:12
  • 4
    $\begingroup$ @Dair Perhaps easier to remember: \lor and \land (along with \implies, \lnot, \iff) $\endgroup$ – spaceisdarkgreen Oct 13 '17 at 1:51
  • 1
    $\begingroup$ There is a set of functions that can be defined by composing $\{\to, \lor \}$, call that set $S$. For example, $F(a, b, c) = a \lor (b \to c)$ is one of them. Every function in $S$ has the property that if all the inputs are true, then the output is true. $\endgroup$ – DanielV Oct 14 '17 at 23:20

As was pointed out in a comment to the original post, both $\implies$ and $\lor$ are truth-preserving, which means (check this!) that all compositions of $\implies$ and $\lor$ will be truth-preserving. Since for example $\lnot$ isn't truth-preserving, $\{\implies,\lor\}$ cannot be functionally complete.

You can do something very similar for the other set. The connectives $\iff$ and $\lnot$ both happen to be affine (or linear), and it can be shown (but this is tricky) that all compositions of affine connectives are affine themselves. Since not all truth functions are affine (find a counterexample yourself!), $\{\iff,\lnot\}$ cannot be functionally complete.

A good place to start reading more about this is the section about characterization of functional completion on Wikipedia. Another excellent reference, that focuses specifically on $\{\iff,\lnot\}$, is the article On Proving Functional Incompleteness in Symbolic Logic Classes from 1988 by Pelletier and Sharp.


As shown in this answer, there is an elementary method to show that the entire set $\{¬,⊕,⇔,⊤,⊥\}$ is not adequate.


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.