Problem

Let \(\alpha\) be a wff whose only connective symbols are \(\land,\lor,\) and \(\lnot\). Let \(\alpha^*\) be the result of interchanging \(\land\) and \(\lor\) and replacing each sentence symbol by its negation. Show that \(\alpha^*\) is tautologically equivalent to \((\lnot\alpha)\). Use the induction principle.

Solution

Let \(S\) be the set of wffs for which the desired property is true. Consider \(A\) an arbitrary sentence symbol. Then \(A^* = (\lnot A)\) Clearly \(A^*\) is tautologically equivalent to \((\lnot A)\). Thus, \(A\in S\), so \(S\) contains all sentence symbols.

Now, suppose \(\alpha\) and \(\beta\) are members of \(S\). I want to show that \((\lnot\alpha)\in S\). Notice that \((\lnot\alpha)^* = (\lnot(\lnot\alpha))\). Clearly \((\lnot\alpha)^*\) is tautologically equivalent to \((\lnot(\lnot\alpha))\). Thus, \((\lnot\alpha)\in S\).

Now I will show that \((\alpha\land\beta)\in S\). Suppose that \(v\) is a truth assignment which satisfies \((\alpha\land\beta)^* = ((\lnot\alpha)\lor(\lnot\beta))\). By the De Morgan’s law tautology, \(v\) must also satisfy \((\lnot(\alpha\land\beta))\), so that \((\alpha\land\beta)^*\) tautologically implies \((\lnot(\alpha\land\beta))\). On the other hand, let \(v\) be a truth assignment which satisfies \((\lnot(\alpha\land\beta))\), then by the De Morgan’s law tautology \(v\) also satisfies \(((\lnot\alpha)\lor(\lnot\beta)) = (\alpha\land\beta)^*\). Thus, \((\lnot(\alpha\land\beta))\) tautologically implies \((\alpha\land\beta)^*\). Therefore, \((\alpha\land\beta)^*\) and \((\lnot(\alpha\land\beta))\) are tautologically equivalent, meaning \((\alpha\land\beta)\in S\).

Now I will show that \((\alpha\lor\beta)\in S\). Suppose that \(v\) is a truth assignment which satisfies \((\alpha\lor\beta)^* = ((\lnot\alpha)\land(\lnot\beta))\). By the De Morgan’s law tautology, \(v\) must also satisfy \((\lnot(\alpha\lor\beta))\), so that \((\alpha\lor\beta)^*\) tautologically implies \((\lnot(\alpha\lor\beta))\). On the other hand, let \(v\) be a truth assignment which satisfies \((\lnot(\alpha\lor\beta))\), then by the De Morgan’s law tautology \(v\) also satisfies \(((\lnot\alpha)\land(\lnot\beta)) = (\alpha\lor\beta)^*\). Thus, \((\lnot(\alpha\lor\beta))\) tautologically implies \((\alpha\lor\beta)^*\). Therefore, \((\alpha\lor\beta)^*\) and \((\lnot(\alpha\lor\beta))\) are tautologically equivalent, meaning \((\alpha\lor\beta)\in S\).

Since we are not interested in wffs which contain \(\to\) or \(\leftrightarrow\), we do not show that \(S\) is closed under their respective sentence building operations.

By the induction principle, it follows that \(S\) is the set of all wffs whose only connective symbols are \(\lnot,\to,\) and \(\leftrightarrow\). Thus, if \(\alpha\) is a wff whose only connective symbols are \(\lnot,\to,\) and \(\leftrightarrow\), it will be that \(\alpha^*\) and \((\lnot\alpha)\) are tautologically equivalent.