Problem

Of the following three formulas, which tautologically imply which? (a) \((A\leftrightarrow B)\) (b) \((\lnot((A\to B)\to (\lnot(B\to A)))) = \alpha\) (c) \((((\lnot A)\lor B)\land (A\lor (\lnot B))) = \beta\)

Solution

I claim that all three statements are tautologically equivalent, consider the following truth table \begin{array}{|c|c|} A & B & (\lnot A) & (\lnot B) & (A\to B) & (\lnot(B\to A)) & (A\leftrightarrow B) & \alpha & \beta
\hline T & T & F & F & T & F & T & T & T
T & F & F & T & F & F & F & F & F
F & T & T & F & T & T & F & F & F
F & F & T & T & T & F & T & T & T\end{array} Notice that an arbitrary truth assignment \(v\) satisfies \((A\leftrightarrow B)\) if and only if it also satisfies \(\alpha=(\lnot((A\to B)\to (\lnot(B\to A))))\) and \(\beta = (((\lnot A)\lor B)\land (A\lor (\lnot B)))\). Similarly, \(v\) satisfies \(\beta\) if and only if it also satisfies \((A\leftrightarrow B)\) and \(\alpha\), and \(v\) satisfies \(\alpha\) if and only if it also satisfies \((A\leftrightarrow B)\) and \(\beta\). Thus, all three statements are tautologically equivalent.