Simplifying $((A\Rightarrow B)\land(B\Rightarrow C))\Rightarrow(C\Rightarrow A)$ to $C\Rightarrow A$.

Question

How can I get from $((A\Rightarrow B)\wedge (B\Rightarrow C))\Rightarrow (C\Rightarrow A)$ to $C\Rightarrow A$?

I started with $$((A\Rightarrow B)\land (B\Rightarrow C))\Rightarrow (C\Rightarrow A)\equiv \lnot((\lnot A\lor B)\land(\lnot B\lor C))\lor(\lnot C\lor A)\equiv((A\land\lnot B)\lor(B\land\lnot C))\lor(\lnot C\lor A)$$, but don't know how to continue. Is it even useful to write $A\Rightarrow B$ as $\lnot A\lor B$?

Answer 1

Yes, rewriting the conditionals as disjunctions is usually the thing to do in these cases, since we have a lot of useful equivalence principles involving the Boolean connectives $\land, \lor$, and $\neg$

To continue from what you have, use:

Absorption

$P \land (P \lor Q) \Leftrightarrow P$

$P \lor (P \land Q) \Leftrightarrow P$

From where you got to, you can first drop some parentheses (we can call this Association), and then do Absorption (The $A$ absorbs the $A \land \neg B$, and the $\neg C$ absorbs the $B \land \neg C$):

$$((A\land\lnot B)\lor(B\land\lnot C))\lor(\lnot C\lor A) \Leftrightarrow \text{ (Association)}$$

$$(A\land\lnot B)\lor(B\land\lnot C)\lor \lnot C\lor A \Leftrightarrow \text{ (Absorption!)}$$

$$\lnot C\lor A \Leftrightarrow \text{ (Implication)}$$

$$C\rightarrow A $$

Answer 2

This might be easier to just negate:

$$\lnot\bigg(\big( (A \to B) \land (B \to C) \to (C \to A) \big) \to (C \to A)\bigg)$$

$$\bigg( (A \to B) \land (B \to C) \to (C \to A) \bigg) \land \lnot (C \to A)$$

$$\bigg( (A \to B) \land (B \to C) \to (C \to A) \bigg) \land C \land \lnot A$$

$$\bigg( (\bot \to B) \land (B \to \top) \to (\top \to \bot) \bigg) \land C \land \lnot A$$

$$\top \land \top \to \bot$$

$$\bot$$