1
$\begingroup$

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.

$\endgroup$
11
  • $\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
    Commented Oct 13, 2017 at 1:09
  • $\begingroup$ @Nagase you're right $\lnot$? $\endgroup$ Commented Oct 13, 2017 at 1:11
  • $\begingroup$ By "v" do you mean "or"? That is \vee and \wedge for "and" in LaTeX. $\endgroup$
    – Dair
    Commented Oct 13, 2017 at 1:12
  • 4
    $\begingroup$ @Dair Perhaps easier to remember: \lor and \land (along with \implies, \lnot, \iff) $\endgroup$ Commented Oct 13, 2017 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
    Commented Oct 14, 2017 at 23:20

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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