# Prove $(A\rightarrow C)\land(C\rightarrow\neg B) \land B\rightarrow\neg A$ is valid without using truth tables

just finished proving an argument without the use of truth tables and was wondering if my reasoning is sound.

The problem given was

Prove using a proof sequence that the argument is valid (hint: the last A’ has to be inferred). Justify each step with a comment.

$(A\rightarrow C)\land(C\rightarrow\neg B) \land B\rightarrow\neg A$

I have

1. A -> C given
2. C -> B' given
3. B given
4. A -> B' hypothetical syllogism of 1 and 2
5. (B')' -> A' contrapositie of 4
6. B -> A' double negation of 5
7. A' modus ponens from 6,3

This answer seems correct to me but I am new to solving these types of problems and any input would be appreciated.

Thanks!

• \land, \to for $\land$ and $\to$. Formatting tips here. – Em. Jul 3 '16 at 8:02
• It looks correct :-) – Musa Al-hassy Jul 3 '16 at 8:13
• thanks for the formatting tips! thanks Musa! – fluffy dog Jul 3 '16 at 8:33

Indeed it is perfectly correct logical reasoning to prove your desired tautology. To be completely self-contained, you might want to add a final line stating that the desired implication is true since you have derived the consequent from the antecedent.

However, do take note that if you're required to work in some specific framework, such as natural deduction, then your proof is probably not in the required format, since at one point you replace $B''$ with $B$, which is certainly true but not allowed by the typical natural deduction rules, although it is valid in boolean algebra.

$(A→C)\land (C→\overline{B})\land B→\overline{A}$

$=(A→C)\land (C→\overline{B})$

Using Hypothetical syllogism :

$=(A→\overline{B})\land B$

Using Modus tollens :

$=\overline{A}$

## Alternative way:

$(A→C)\land (C→\overline{B})\land B→\overline{A}$

$=\overline{((\overline{A}\lor C)\land (\overline{C}\lor\overline{B})\land B)}\lor\overline{A}$

$=(\overline{(\overline{A}\lor C)}\lor\overline{(\overline{C}\lor \overline{B})}\lor \overline{B})\lor \overline{A}$

$=((\overline{\overline{A}}\land \overline{C})\lor(\overline{\overline{C}}\land\overline{\overline{B}})\lor\overline{B})\lor\overline{A}$

$=((A \land\overline{C})\lor(C \land B)\lor\overline{B})\lor\overline{A}$

$=(A \land\overline{C})\lor(C \land B)\lor\overline{B}\lor\overline{A}$

$=((A \land\overline{C})\lor\overline{A})\lor((C \land B)\lor\overline{B})$

$=((A \lor\overline{A})\land (\overline{C}\lor \overline{A}))\lor((C \lor\overline{B})\land(B\lor\overline{B}))$

$=(T\land (\overline{C}\lor \overline{A}))\lor((C \lor\overline{B})\land T)$

$=(\overline{C}\lor \overline{A})\lor(C \lor\overline{B})$

$=\overline{C}\lor \overline{A}\lor C \lor\overline{B}$

$=(\overline{C}\lor C) \lor (\overline{A} \lor\overline{B})$

$=T \lor (\overline{A} \lor\overline{B})$

$=T$

• Why voted down? – 1 0 Jul 3 '16 at 10:48