Section 1.5: Problem 13-A Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

(Additional) The ternary connective "conditioned disjunction" (written with brackets $[[]]$ ) is defined as follows: $[\alpha[\beta]\gamma]$ , which can be read " $\alpha$ or $\gamma$ , according as $\beta$ or not $\beta$ ," or equivalently as "if $\beta$ then $\alpha$ , else $\gamma$ ," is tautologically equivalent to $((\beta\rightarrow\alpha)\wedge(\neg\beta\rightarrow\gamma))$ . Show that $\{[[]],\top,\bot\}$ is a complete set of connectives.

$[B[A]\top]$ is tautologically equivalent to $A\rightarrow B$ , which together with $\bot$ forms a complete set of connectives (page 52).

Note. A more interesting question is whether it is independent. Similar to previous exercises, we look for some properties of connectives such that the set of wffs satisfying each such property is closed under connectives, but not all connectives satisfy the property, in particular, $\downarrow$ and $\vert$ do not. To show that no proper subset of $\{[[]],\top,\bot\}$ is complete, for each connective in the set we need to find such property that all the other connectives satisfy it, but not the given one. In other words, there should be something unique in each connective that makes the set complete. In the previous exercises we have already listed some such properties.

$[[]]$ is the only connective that depends on more than 1 operand (see Exercise 2).

$\top$ is the only connective that is not evaluated to $F$ when all operands are evaluated to $F$ .

Similarly, $\bot$ is the only connective that is not evaluated to $T$ when all operands are evaluated to $T$ .

So, this set of connectives is complete and independent.

Subpages

Section 1.5: Problem 13-A Solution

Section 1.5: Problem 13-A Solution