Prove $((a \wedge b) \to c)\to (a \to (b \to c))$.

Question

I know that this can be validated by using a truth table, But how can one go about proving this via some atomic steps, such as using bracket notation?

Answer 1

In natural deduction:

1. $(a \land b) \to c$ (ass)
2. $a$ (ass)
3. $b$ (ass)
4. $a \land b$ (intro-$\land$ from 2. and 3.)
5. $c$ (modus ponens from 1. and 4.
6. $b \to c$ (drop ass. 3); intro-$\to$.
7. $a \to (b \to c)$ (drop ass 2.; intro $\to$)
8. $(a \land b) \to c \to (a \to (b \to c))$ (drop ass. 1; intro $\to$)

and the proof is complete. Tautology.

Answer 2

In fact, a stronger statement can be made, and proven:

$((a \land b) \to c) \equiv (a \to (b \to c))$.

Starting with the left hand side, we have

$\begin{align} (a \land b) \to c &\equiv (\lnot (a \land b) \lor c)\\ \\ & \equiv (\lnot a \lor \lnot b) \lor c\\ \\ &\equiv \lnot a \lor(\lnot b\lor c)\\ \\ & \equiv a \to (\lnot b \lor c)\\ \\ & \equiv a \to (b \to c)\end{align}$

I use DeMorgan's rule, and the definition of implication, namely $p \to q \equiv \lnot p \lor q$, and the associative property of disjunction.

Answer 3

Suppose $$\lnot (((a \wedge b) \to c)\to (a \to (b \to c))).\tag{1}$$

Then we have $(a\land b)\to c$ and $\lnot(a\to(b\to c))$. By the latter, we have $\color{red}{a}$ and $\lnot (b\to c)$, which, in turn, implies $\color{green}{b}$ and $\color{blue}{\lnot c}$. From $(a\land b)\to c$, we have either $\lnot (a\land b)$ or $\color{blue}{c}$ (or both). But $\color{blue}{\lnot c}$. Hence $\lnot (a\land b)$; that is, either $\color{red}{\lnot a}$ or $\color{green}{\lnot b}$ (or both), a contradiction.

Therefore, the negation of $(1)$ holds.

Answer 4

Using DC Proof 2.0 (freeware available at my homepage)