(a) Note that $+^{3}A\top\bot$ is tautologically equivalent to $\neg A$ . Together with $\wedge$ we have a complete system of connectives.

(b) Now, similar to the previous exercise, 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 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.

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

For $\wedge$ we could proceed in two possible ways. First, similar to the first solution of Exercise 3, we could consider all wffs in two sentence symbols $A$ and $B$ using $\{\top,\bot,+^{3}\}$ only, and show that we cannot construct any wffs tautologically equivalent to $\downarrow$ or $\vert$ . It seems that, eventually, we would have to show that the set of wffs generated by $A$ , $B$ under $\{\top,\bot,+^{3}\}$ is the same as the one generated by $A$ , $B$ under $\{\neg,+\}$ , which is not complete according to Exercise 5. Second, the first solution suggests that we can apply ideas of Exercise 5. Namely, we can consider $+^{3}$ on the set of sentence symbols $\{A,B\}$ . Similar to Exercise 5, we call a wff in $A$ and $B$ even, if the number of truth assignments that evaluates the wff to $T$ is even. Then, all sentence symbols are even, $\top$ is even ($4$ $T$ ’s), $\bot$ is even ($0$ $T$ ’s), and if for $\alpha$ , $\beta$ and $\gamma$ the number of truth assignments that evaluate $i$ , $i\wedge j$ , $i\wedge j\wedge k$ to $T$ , where $i,j,k\in\{\alpha,\beta,\gamma\}$ , is, respectively, $n_{i}$ , $n_{ij}$ and $n_{ijk}$ ($n_{\alpha}$ , $n_{\beta}$ and $n_{\gamma}$ are even), then $+^{3}\alpha\beta\gamma$ is even as well ($n_{\alpha}+n_{\beta}+n_{\gamma}-2n_{\alpha\beta}-2n_{\alpha\gamma}-2n_{\beta\gamma}+4n_{\alpha\beta\gamma}$ $T$ ’s). Hence, the set of all even wffs in $A$ and $B$ contains the set of wffs generated by $\{A,B\}$ under $\{\top,\bot,+^{3}\}$ , yet it does not cover all wffs in $A$ and $B$ , such as $A\downarrow B$ and $A\vert B$ . We conclude that $\{\top,\bot,+^{3}\}$ is not complete.

$+^{3}$ is a bit harder as we did not use any property in the previous exercises that would distinguish $+^{3}$ from the set of others. Indeed, two properties used in Exercise 2 are already used for $\top$ and $\bot$ . Another property used in Exercise 2, which is dependance on no more than 1 sentence symbol, satisfies the first two connectives only. The property used in Exercises 3 and 4 (self-duality) satisfies $+^{3}$ only. And the property used in Exercise 5 is already used. However, in this case the method of Exercise 3 (the first solution) is most applicable. We just note that the set of wffs $E=\{\top,\bot,A,B,A\wedge B\}$ is closed under $\{\top,\bot,\wedge\}$ in the sense that the application of any connectives from $\{\top,\bot,\wedge\}$ to any wffs that are tautologically equivalent to some wffs in $E$ , results in a wff that is again tautologically equivalent to one from $E$ . If the connective is $\top$ or $\bot$ then the result is immediate, and if $\alpha$ and $\beta$ are tautologically equivalent to some wffs from $E$ , then $\alpha\wedge\beta$ is also tautologically equivalent to some wff from $E$ (we need to consider cases such as $\top\wedge C$ being tautologically equivalent to $C$ , $\bot\wedge C$ to $\bot$ , $A\wedge B$ to itself, and $A\wedge(A\wedge B)$ to $A\wedge B$ ). Hence, by induction, noting that all sentence symbols are in $E$ , we conclude that the set of wffs generated from $\{A,B\}$ using $\{\top,\bot,\wedge\}$ consists of wffs that are tautologically equivalent to one of those in $E$ , but since not all wffs are equivalent to one of those, the set $\{\top,\bot,\wedge\}$ is not complete.

Another way to see that $+^{3}$ is necessary for completeness, is to note that all connectives in $\{\top,\bot,\wedge\}$ are “increasing” in the sense that changing the truth assignment for any sentence symbol from $F$ to $T$ never results in changing of the evaluation of a wff built with these connectives from $T$ to $F$ (it may not change at all, or increase, but never decrease). This property is also inherited by wffs from sentence symbols, if the connectives used in the wff satisfy this property. And $\{\top,\bot,\wedge\}$ do satisfy this condition, while, for example, $\downarrow$ or $\vert$ do not.